分布式系统中的负载分配

1、分布式系统中的负载分配,分布式系统提供了巨大的处理能力。然而，为了实现和充分利用这种能力，需要优良的资源分配方案。 负载分配是分布式系统的资源管理模块，它主要是合理和透明地在处理器之间重新分配系统负载，以达到系统的综合性能最优。 负载分配大致可分为静态和动态两类。,负载分配的分类（1）,通常，负载分配方法可做如下分类： 局部和全局 局部负载分配处理单个处理器上的进程对时间片(单元)的分配。全局负载分配首先进行进程对处理器的分配，然后完成每个处理器内这些进程的局部调度。 静态和动态(在全局类中) 静态负载分配中，进程对处理器的分配是在进程执行以前的编译阶段完成的，而动态负载分配要到进程在系统中执

2、行时才做出分配。静态方法又叫做确定性调度，而动态方法叫做负载平衡。,负载分配的分类（2）,最优和次优(在静态和动态两种类型中) 如果根据标准，比如最小执行时间和最大系统输出，可以取得最优分配，那么就可以认为这种负载分配方法是最优的。一般地，负载分配问题是NP完全问题。某些情况下，次优方案也是可以接受的。有四类算法(对于最优的和次优的)被使用：解空间枚举搜索、图模型、数学编程(例如01编程)和队列模型。 近似和启发式(在次优类型中) 在近似方法中，负载分配算法仅搜索一个解空间的子集，当寻找到一个好的解时，终止执行。在启发式方法中，调度算法使用某些特殊参数，能够近似地对真实系统建模。,负载分配的分

3、类（3）,集中控制的和分散控制的(在动态类型中) 在分散控制中，决策工作被分配给不同的处理器。在集中控制中，这些工作是由一个处理器完成的。 协作的和非协作的(对分散控制) 动态负载分配机制可以分成：协作的分布式对象间有协同操作，非协作的处理器独立做出决策。,负载分配的分类（4）,下面是另一种负载分配算法的分类方法，包括一些不能直接归人上面分类的负载分配类型： 单个和多个应用程序 多数负载分配算法是针对单个应用程序。多应用程序情况可以转换成单个应用程序情况。然而，多应用程序情况下的进程分配远复杂于单个应用程序的情况。 非抢占式的和抢占式的 对非抢占式的负载分配算法，一个任务(进程)开始执行后就不

4、能中断。在抢占式负载分配算法中，进程可以中断，并从处理器上移走，过后继续执行。,负载分配的分类（5）,非自适应的和自适应的 非自适应负载分配只使用一种负载分配算法，不会依据系统反馈而改变自己的行为。自适应负载分配能够根据系统反馈调整分配算法。典型地，一个自适应负载分配算法是许多负载分配算法的集合，依据系统的各种参数来选择一个合适的算法。,静态负载分配,静态负载分配算法根据系统的先验知识做出决策。运行时负载不能够重新分配。 静态负载分配算法的目标是调度一个任务集合，使它们在各个目标PE上有最小的执行时间。静态负载分配因此又称做调度问题。 总体上，处理器互连、任务划分(粒度决策)和任务分配是设计调

5、度策略时的三个主要因素。 如前所述，通常的调度问题即使在简单地对计算开销和通信开销做某种假设以后，依然是一个NP完全问题。因此，许多方法利用数学工具如图、启发式规则来得到次优的解。,任务图模型,通常，用图模型表示任务和PE结构。我们可以用任务优先图或者任务交互作用图对任务集合建模。任务优先图又称为有向无环图(DAG)，每个链接定义了任务间的优先关系。节点和链接上的标记表示任务执行时间和任务完成后启动后续任务所需的时间间隔。任务交互作用图中，链接定义了两个任务间的相互关系。每个链接赋予一对数，表示这两个任务在同一个PE上时的通信开销和在不同PE上时的通信开销。,处理机互连（1）,互连网络的拓扑可

6、以分为静态的和动态的。静态网络由固定的点到点直接连接组成，并且进程执行过程中不能改变。动态网络利用交换机实现动态配置来满足用户程序的通信要求。,静态互连网络：16节点系统的不同连接方案（每个节点四个双向链接） a) 依里埃克网格( Illiac Mesh) b) 圆环网,处理机互连（2）,c) 超 立 方 体（4维立方体由两个3维立方体节点互连而成，每维两个节点）,d) WK层次网络（n层网络由四个（n-1）层网络组成，每个子网络是一个虚拟节点，1层WK网络是基元）,动态互连网络（1）,有三种类型的动态拓扑：单级、多级和纵横制(见图1-8)。通常，处理机位于网络的两侧。一个单级网络由一级交换单

7、元组成。每个交换单元是一个带两个输入和两个输出的2x2的开关，输入和输出的连接可以是直连或交叉，这由一个布尔变量控制。 图1-8a表示了一个完全混洗连接的例子。一个多级网络包含多级的交换单元并支持从任意数量的输入处理机到任意数量的输出处理机的连接。在一些网络中，输入和输出处理机的同时连接可能导致使用网络通信链路的冲突。这种网络叫做阻塞式网络(见图1-8c所示的基线制网络)；否则，就叫做可重新安排的非阻塞式网络(见图1-8d所示的Benes网络)。在纵横制交换机中，每个输入可以无阻塞地和一个空闲的输出相连(见图1-8b)。,动态互连网络（2）,图1-8 a) 8 8混洗交换,b) 4 4纵横制,

8、动态互连网络（3）,c) 8 8基线制,d) 8 8 Benes,任务划分,一个给定任务划分的粒度定义是任务分解中影响通信开销的所有单元的平均尺度。算法可以分成细粒度、中粒度和粗粒度。 如果数据单元(即粒度)小，这种算法就是细粒度。如果数据单元大，算法就是粗粒度。介于细粒度和粗粒度之间的就是中粒度。粒度太大，就会降低并行度，因为潜在并行任务可能被划分进同一个任务而分配给一个处理器。粒度太小，进程切换和通信的开销就会增加。 任务划分的一个主要目标就是尽可能消除处理器间通信引起的开销。,任务划分的方法,水平或者垂直划分。主要思想是在给定的任务优先图中垂直或者水平划分。关键路径(最长路径)的概念常常

9、在垂直划分中使用。水平划分把给定的任务分成若干层，任务的优先级由它们所在的层次决定。 通信延迟最小划分。 主要思想是把通信频繁的节点归成一类。然而，这些需要通信的任务分配在一个处理器上会丧失任务间的并发性。如果减小通信延迟的好处抵销了并行任务串行化的损失，就采用通信延迟最小划分。 任务复制。这是任务划分的一个可选方法。主要思想是通过在PE上复制任务来降低通信开销。这个方法保留了任务原有的并行性；但是存储空间要求和同步开销增加了。可以利用任务复制来达到容错性。任务复制也被用来实现无错调度，以保证处理器出现错误时最后计算结果正确。,任务分配（1）,任务分配是指在多处理机系统中，针对某一目标，按照一

10、定的策略，将规模为N的任务划分并映射到P台处理机上。 在多处理机系统中，一个任务的执行时间为 T f ( tcomp，tcomm，te ) 其中，tcomp为子任务的最大执行时间，tcomm为完成子任务所需的通信时间，而te为其它开销。 一个问题划分的子任务越多，tcomp就越小，而tcomm和te可能很大。tcomm和te的增大不仅可能抵消tcomp的减小，甚至可能使并行处理所得到的效益完全丧失。 任务分配的主要目标是寻找一种合适的算法，使T降到最低程度。 任务的静态分配又称确定性调度，指任务在运行前就指定运行的处理机，并在其生命周期内一直驻留在该处理机上。,任务分配（2）,任务分配就是在给

11、定了互连网络的并行系统或者分布式系统中分配颗粒(颗粒是任务划分的结果)。 如果任务图和处理器图的节点数目都是n，那么就有n!种不同的分配方法把任务图Gt里的节点分配到处理器图Gp的节点上。我们把每种方法称做Gt到Gp的一个映射。在总执行时间概念下，有些映射比较好。 下面是关于Gp的典型假设： 存储器容量无限。 每个PE有相同的处理能力。 忽略网络拥塞，虽然通信进程间的距离是影响通 信延迟的因素。 注意，任务调度不必要一定分两个步骤做，即任务划分和任务分配。分两步的方法只是为了简化原本是NP完全的调度过程。,调度模型,前面提到，绝大多数最优调度问题是NP完全的。主要的研究努力集中在下面的方法：

12、对特殊情况的最优调度，比如，带特殊约 束的模型。 非最优调度，可以分成局部最优方案和次 优方案。 局部最优方法使用有效的搜索技术确定问题解空间中的(局部)最优调度方案。这些方案可以进一步分成下面四种：,局部最优方案（1）, 解空间枚举和搜索。首先构建状态空间，其中每个状态对应一个可能的调度方案。它依靠各种搜索技巧如分支搜索和边界搜索在解空间中寻找解。 数学编程。一个给定的调度问题转换成一个整数、线性或者非线性编程问题。有三个步骤：(a)一个目标函数，以求目标函数最小化，常常定义成程序执行时间。(b)一个约束集合，例如优先关系和通信延迟。(c)使用动态编程技巧解决基于a和b的约束最优问题。 模拟

13、退火。模拟退火利用物理退火过程的特性构建一种局部最优方案的搜索方法。通常这样一个过程由三部分组成：(a)对初始非最优调度方案做小幅度的随机的变动。(b)评估新的调度方案。(c)继续这一过程直到没有更好的方案产生，也就是说得到了一个局部最优方案。,局部最优方案（2）, 遗传算法。遗传算法是基于自然界遗传和进化规律的搜索算法。它结合已有结果和搜索空间的新领域来产生新的结果。Kwok和Ahmad提出了一个并行遗传调度算法。 和特殊情况的最优解一样，局部最优解也有极大的计算量并且极端耗费时间。次优解法依靠启发式方法取得次优解。,任务静态分配算法,使用两台处理机的最佳调度,图8.3 任务图和Gantt图

14、,性能分析,最早调度算法（1）,最早调度算法ESA(Earliest Scheduling Algorithm)的基本思想是，只要系统中有可用的处理机，便从任务系统中选出一个能满足偏序限制条件的任务，并立即使其投入运行，当有多个能满足偏序限制条件的任务时，选择其中最早的一个任务。 我们以图8.3(a)中的任务图为例，说明最早调度算法的调度过程。假定系统中有两台处理机，按ESA算法来分配处理机的步骤如下： (1)作业开始时，只有启动任务T1能满足偏序限制条件，故调度程序将处理机P1分配给T1 ，因无任务分配给P2，故P2空闲，用表示。 (2)执行一个单位时间后， T1已完成，T2和T3能满足偏序

15、限制条件，于是调度程序将P2和P1分别分配给T2和T3 ，使它们并行执行。 (3)T3运行一个单位时间后完成，调度程序立即把P1分配给唯一能满足偏序限制条件的任务T6，调度程序按ESA算法不断地为任务分配处理机，直至该作业完成。图84示出了按ESA算法进行调度产生的Gantt表格的时间图。,最早调度算法（2）,最早调度算法（3）,考虑通信延迟的调度算法（1）,考虑通信延迟的调度算法（2）,图9-4a显示了一个实例的任务优先图，给出了处理器间的通信延迟和任务执行时间。图9-4b是根据图9-4a的数据给出的对处理器P1、P2的调度结果。圆圈中的数对应任务的执行时间。与每个链接相关的数对应于处理器间

16、的通信时间。两个连接任务分配在不同的处理器上时就会发生通信延迟。例如，w(T1)=2和w(T1,T2)=1表示T1的执行时间是2， T1 T2间处理器间的通信代价是1（没有给出处理器内的通信代价）。本例中，两个处理器间的通信发生在有1个单位通信延迟的T2到T4和有2个单位通信延迟的T4到T5。总的执行时间是12。,考虑通信延迟的调度算法（3）,考虑通信延迟的调度算法（4）,通信延迟使调度算法大大地变复杂。图9-5a给出了三种不同调度的例子。如果通信延迟d大于任务T2的执行时间，图9-5c的调度就比图9-5d的要好。可以说，若通信延迟太大的话，所有任务分配在一个处理器上是比较合适的。,通常我们总

17、是尝试尽量增加并行度，同时尽可能降低通信延迟。然而在多数时间这两个目标是互相矛盾的。因此需要某种程度折衷。有时可以使用任务复制的方法减少通信需求。显然，由于通过任务复制而避免了处理器间的通信，图9-5b的结果是最好的。,动态负载分配,分布式系统中，许多算法包含不统一的计算和通信代价，它们不容易事先确定。某些应用中，工作负载随着计算进度而变化，这意味着初始好的映射可能会变坏。动态负载分配(又称负载平衡、负载转移或者负载共享)能够用来恢复平衡。动态负载分配算法使用系统状态信息(节点的负载信息)，至少部分使用，来做负载分配的决策，而静态负载分配没有使用这些信息。 静态负载分配的限制是以一种一劳永逸的

18、方式把任务分配给处理器，而且要求预先知道程序状态。包含通信进程的系统会产生冲突，同时计算进程也可能发生加速，但是多数方法忽略这两种影响。相反地，动态负载平衡很少假设关于例如任务执行时间或者通信延迟的运行时参数的先验信息。动态负载平衡延迟在运行时重分配进程，以达到高性能目标。动态负载分配更好地动态使用了全系统的所有资源，提高了系统的性能。,基本概念,所谓负载是指处理机上的用户进程尚未完成的工作量。主要包括进程的计算开销和通信开销。在多处理机系统中，对节点机上系统资源的负载度量，称为负载指标。以向量形式表示的某一节点机的各项负载指标，称为负载向量，它描述的是某一节点机的负载情况。以矩阵形式表示的各

19、节点机负载向量的集合，称为负载矩阵，用以描述整个系统的负载情况。 负载向量所描述的内容，是任务分配的依据，其定义必须准确、完备和有效。负载向量可以包括多种负载指标，例如：节点机就绪队列的长度，局部存储器空闲空间的容量，单位时间内进行系统功能调用的次数，单位时间内存储器页面的调入调出次数，单位时间内CPU被占用的百分比，单位时间内磁盘的读写次数等。大多数任务分配算法采用单个负载指标作为负载向量，其中选择节点机就绪队列长度的颇多。,负载平衡,为了描述节点机上负载的轻重程度，我们使用负载阀值进行衡量。负载阀值是节点机负载的界限值，其下界为T1，上界为T2，且T1T2。我们有如下的定义。 轻载：当节点

20、机的负载小于T1时，该节点机为轻载； 重载：当节点机的负载大于T2时，该节点机为重载； 适载：当节点机负载大于T1而小于T2时，该节点机为适载； 空载：当节点机负载为0时，该节点机为空载。 负载平衡：是指系统中的所有处理机均处于适载状态。这是一种严格意义下的负载平衡。更广泛意义下的负载平衡应是系统中每个节点机都不是空载，或者当某个节点机为空载时，其它节点机均为空载或轻载。,动态负载平衡,负载分配算法可以分为静态负载分配算法和动态负载分配算法。静态负载分配算法是指在系统中进行任务分配时，根据各节点的负载情况决定给任务分配处理机。动态负载分配算法通过交换系统的状态信息来决定系统负载的分配。动态负载

21、分配算法能适应系统负载的变化，比静态负载分配算法更灵活、更有效，但它以一定的系统开销为代价。 所谓动态负载平衡，是指系统根据其负载变化和进程的执行情况，自动实现进程从重载节点机到轻载节点机的迁移。重载节点机提供迁出进程，轻载节点机要求迁入进程。 在分布存储器结构多处理机系统中，各节点处理机缺乏对全局信息的了解，处理机间需要经常交换进程状态信息。这种交换可以按同步方式进行，也可以按异步方式进行。同步方式简单，控制方便，但同步时间间隔难以确定。若间隔偏小，则节点之间信息交换频繁，通信开销大，因此可能会抵销负载平衡所带来的并行处理效益，若间隔偏大，则达不到动态平衡负载的目的，在异步方式下，系统只有在

22、某一事件触发下才能引起节点处理机间的信息交换。这里的触发事件较典型的有两种：某节点机负载过重和某节点机负载过轻。,动态负载平衡的几个策略（1）,动态负载平衡算法由以下四个策略组成： (1)迁移策略。当一个新任务在一个节点上产生时，如果它所在的节点机的负载超过了负载阀值的上界，则该节点机就是一个发送者，另一方面，一个节点机上的负载降到了阀值Tl(T2)以下，那么该节点就被认为是一个接收者。 (2)选择策略。一旦迁移策略确定了发送者和接收者之后，选择策略将用于从发送者那里选择哪些任务作为迁移对象。最简单的选择策略就是选择一个最新产生的任务，在它未执行之前就迁移到接收者那里。选择一个迁移任务时，应考

23、虑到由迁移所产生的开销要小，被迁移的任务应具有较长的生命期，否则迁移的开销将抵消性能的提高。被迁移的任务可以是未被启动执行的任务，也可以是正在运行的任务。,动态负载平衡的几个策略（2）,(3)定位策略。一旦确定了一个节点机是发送者(或接收者)之后，定位策略负责为其寻找合适的搭档节点机。定位策略可有分布式和集中式两种。分布式定位策略采用轮询(Polling)方式寻找一个搭档机，也可以采用广播查询方式搜索任何可以进行分载的节点机。在集中式定位策略中，任何节点机都可向一个称为管理者的特殊节点机发出请求，由管理者确定一个进行分载的合适的节点机。,动态负载平衡的几个策略（3）,(4)信息策略。它用于决定什么时候(When)，从什么地方(Where)搜集