吉林大学研究所课程-并行计算课件-第5章-分布式调度

1、第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的分类调度算法的分类 调度算法 局部调度 全局调度 静态调度 动态调度 分散式调度 集中式调度 协作式调度 非协作式调度 优化调度 次优化调度 近似调度 启发式调度 优化调度 次优化调度 近似调度 启发式调度 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的分类调度算法的分类 其他一些分类方法其他一些分类方法 ：(1) 非抢先式的(non-preemptive)和抢先式的(preemptive)。对非抢先式的调度算法，一个进程开始执行后就不能中断。在抢先式调度算

2、法中，进程可以中断，从一个处理机上移走，到另一个处理机上继续执行。 (2) 适应性(adaptive)和非适应性的(non-adaptive)。非适应性调度算法只使用一种负载分配策略，不会根据系统的反馈而改变自己的行为。适应性调度算法能够根据系统的反馈调整自己的行为，采用不同的负载分配策略。典型地，一个适应性调度算法是许多种调度算法的集合，根据系统的各种参数来选择一种合适的算法。 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的目标和有效性评价调度算法的目标和有效性评价 分布式调度的基本目标分布式调度的基本目标是尽快得到计算结果和有效地利用资源。具体

3、来说，调度算法的目标有两个：一个目标是负载平衡(load balancing)，它的努力目标是维持整个分布式系统中各个资源上的负载大致相同。另一种目标是负载共享(load sharing)，它的目标仅仅是防止某个处理机上的负载过重。相对来说负载共享的目标要比负载平衡的目标容易达到。负载平衡的主要目的是提高整个系统的流量，而负载共享的主要目标是缩短特定程序的执行时间。 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的目标和有效性评价调度算法的目标和有效性评价 从调度算法的有效性来看，调度算法分为最优调度算法和次优调度算法。为了实现最优调度算法，调度者必

4、须获得所有进程的状态信息和系统中所有相关的可用信息。最优性常用执行时间、资源利用率、系统流量以及这些参数的某种综合来进行评价。一般来说最优调度是一个NP完全性问题。所以在实际的系统中，常采用次优的调度算法。 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的目标和有效性评价调度算法的目标和有效性评价 有许多参数用于确定或测量一个调度算法的有效性：有许多参数用于确定或测量一个调度算法的有效性：通信代价：通信代价：使用这个参数的调度算法可能要考虑到向一个给定的节点传送或者从一个给定节点接收一个报文花费的时间，更为重要的是必须考虑到为一个进程分配一个执行地点

5、而引起的通信代价。 执行代价：执行代价：这个参数反映的是将一个进程分配到一个指定的执行节点，在这个节点的执行环境下，执行这个程序所需的额外开销。资源利用率：资源利用率：常用来表明基于分布式系统当前各个节点的负载情况，给一个进程分配的执行节点是否是合适的。资源利用率参数常用负载状态来表示，常用的负载参数有资源的队列长度、内存的使用等等。 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的目标和有效性评价调度算法的目标和有效性评价 次优的调度算法分为两类：近似的次优调度算法和启发式的次次优的调度算法分为两类：近似的次优调度算法和启发式的次优调度算法：优调度

6、算法：近似的次优调度常和最优调度使用相同的算法，但是近似的次优调度不搜索这个算法的所有解空间，而是在这个算法的解空间中的一个子集中搜索，目的是尽快地找到一个较好的解。而最优调度则是搜索这个算法的整个解空间，目的是获得最好的解。使用近似的次优调度算法必须能够判定所得到的解是否是可以被接受的，也就是说，必须能够确定最优解和次优解之间的近似程度。 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的目标和有效性评价调度算法的目标和有效性评价 次优的调度算法分为两类：近似的次优调度算法和启发式的次次优的调度算法分为两类：近似的次优调度算法和启发式的次优调度算法：

7、优调度算法：启发式的次优调度算法常使用比较简明的规则和一些直觉的规则来进行调度。这些启发式的规则往往是不能证明其正确性，在特定情况下可能还是错误的，但是在绝大多数的情况下是能够被接受的。 第第5 5章章 分布式调度分布式调度 5.1 5.1 调度算法概述调度算法概述 v调度算法的目标和有效性评价调度算法的目标和有效性评价 启发式调度算法中常采用的一些启发式规则：启发式调度算法中常采用的一些启发式规则： 相互依赖性较大的进程，由于它们之间常有比较多的进程通信应该分配到比较接近的执行节点上，可能的话，应该在同一个节点上。 访问共享文件的进程应该分配到比较接近的执行节点上，可能的话，应该分配在文件服

8、务员节点上。 很少有内在关系的进程可以分布在不同的机器上。 如果一个节点已经是重负载的，不应该向该节点分配另外一个进程。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 设计调度策略时要考虑的三个主要因素：设计调度策略时要考虑的三个主要因素：静态调度算法的目标是调度一个任务集合，使它们在各个目标节点上有最短的执行时间。总体上来说，设计调度策略时要考虑的三个主要因素是处理机的互连、任务的划分和任务的分配。通常用图模型表示任务和处理机的结构。我们可以用任务优先图和任务交互作用图对任务集合建模。 任务优先图任务优先图是一个有向无环图(DAG)，图中每个链接定义了任务间的优先关

9、系，节点和链接上的标记表示任务的执行时间和任务完成后启动后续任务所需的时间间隔。任务交互作用图任务交互作用图中，链接定义了两个任务间的相互关系，每个链接赋予一对数，分别表示这两个任务在同一个处理机上时的通信开销和在不同处理机上时的通信开销。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 2 1 1 4 2 1 1 4 2 2 T1 T2 T3 T4 T5 (a) 任务优先图 2 3 4 2 3 T1 T2 T3 T4 T5 1,4 1,5 1,4 1,3 1,5 1,4 (b) 任务相互作用图 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v

10、任务划分与分配任务划分与分配 任务划分的粒度：任务划分的粒度：一个给定任务划分的粒度被定义为任务的计算量与通信量的比值。如果粒度太大，就会限制并行性，因为潜在的并行任务可能被划分进同一个任务而分配给一个处理器。粒度太小，进程切换和通信的开销就会增加，从而降低性能。 任务聚类：任务聚类：在图模型中，任务的划分被称作任务聚类，即在给定的图模型中对小任务进行分类。任务划分把任务图当作一个整体，将图中的小任务(节点)划分成不同的聚类，聚类中的小任务串行执行，不同的聚类之间并行执行。任务聚类中可以使用两种策略： (1) 将不相关的任务映射到一个聚类中； (2) 将DAG中一条优先路径上的任务映射到一个聚

11、类中。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v任务划分与分配任务划分与分配 一些划分算法 ：(1) (1) 关键路径划分。关键路径划分。关键路径(最长路径)的概念常常在垂直划分中使用，即用在线性聚类中。应该清楚的是，依赖于任务优先图中关键路径的细粒度任务必须串行执行。(2) (2) 消除通信延迟的划分。消除通信延迟的划分。这个方法的关键之处在于消除通信的额外开销，所以要把通信频繁的节点聚集成一类。通常的方法是将一个节点的后继节点与节点自身聚集成一类，只要总的执行时间不会被延长。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v任务划

12、分与分配任务划分与分配 关键路径划分的例子关键路径划分的例子132457964252472T1T2T5T3T6T4T7消除通信延迟的划分消除通信延迟的划分133112T2T3T4T5T63133312T1第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v任务划分与分配任务划分与分配 一些划分算法 ：(3) (3) 任务复制。任务复制。为了消除任务间的通信开销，将任务在处理机上进行复制有时是最有效的方法。它是任务划分的一个可选方法。任务复制不仅能保留程序最初的并行性，同时也能减少通信开销。 (4) (4) 其他技术。其他技术。Kim和Browne的线性聚类技术，在每一步，

13、计算量和通信量最大的有向路径上的节点聚集成一个单独的线性聚类，并且这些节点被从图中除去。对图中剩余的节点迭代执行这个过程，直到整个任务图已经全部被划分成一些聚类。Sarkar的内在化聚类方案，将每个节点最初放在一个单独的聚类中，并且以弧上通信开销的下降顺序考虑将图中的节点划分成一些聚类。这个算法不断地将两个聚类合并成一个更大的聚类，如果在合并过程中生成的更大聚类不会增加这个图的估计并行执行时间，那么这个合并过程就被接受。这个过程一直进行下去，直到不再需要合并为止。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v任务划分与分配任务划分与分配 1 3 2 4 5 7 9

14、 6 4 2 5 2 4 7 2 T1 T2 T5 T3 T6 T4 T7 时间 处理机 1 处理机 2 处理机 3 1 T1 T1 T1 2 T2 T3 T4 4 T2 T2 T4 5 T3 T2 T4 6 T3 T2 T2 7 T5 T6 T2 9 T5 T6 T7 任务复制：第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务优先图的任务调度基于任务优先图的任务调度 甘特图甘特图(gantt chart)能够最有效描述进程对处理器的分配情况。甘特图以处理器为纵坐标，以时间为横坐标。图中的每个方块表示进程在某个系统中的开始时间、持续时间和结束时间。处理器内的时

15、间延迟和处理器间的时间延迟都能够在图中体现。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务优先图的任务调度基于任务优先图的任务调度 2 1 1 4 2 1 1 4 2 2 T1 T2 T3 T4 T5 (a) 任务优先图 (b) 甘特图 时间 处理器 P1 P2 T1 0 2 T2 3 T3 T4 7 T5 12 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务优先图的任务调度基于任务优先图的任务调度 通信延迟和任务复制对调度的影响： T1 T2 T3 d d 时间 处理器 P1 P2 T1 T1 T2 T3 时间 处理器

16、 P1 P2 T1 T2 T3 时间 P1 P2 处理器 T1 T2 T3 d (a) 任务优先图 (b) 使用任务复制的调度 (c) 任务分配在一个处理器上 (d) 通信延迟对调度的影响 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务优先图的任务调度基于任务优先图的任务调度 线性聚类与非线性聚类：线性聚类与非线性聚类：如果至少有一个聚类中包含两个独立的任务，则聚类是非线性的；否则，聚类就是线性的。 4 3 2 T1 T2 T3 1 1 4 3 2 T1 T2 T3 1 1 (a) 线性聚类 (b) 非线性聚类 第第5 5章章 分布式调度分布式调度 5.2

17、5.2 静态调度静态调度 v基于任务优先图的任务调度基于任务优先图的任务调度 一个任务优先图可以认为是许多分叉和合并操作的集合，分叉x(合并x)的粒度是：max/min)(11knkknklCxg x C1 C2 Cn V1 V2 Vn l1 l2 ln x C1 C2 Cn V1 V2 Vn l1 l2 ln (a) 分叉操作 (b) 合并操作 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务优先图的任务调度基于任务优先图的任务调度 给定任务优先图给定任务优先图G G的粒度是的粒度是： )(min)(xgGgGx如果g(x)1，合并x或分叉x就是粗粒度；否则

18、就是细粒度。同样如果g(G)1，图G就是粗粒度，否则就是细粒度。当表示一个应用程序的给定的有向无环图DAG(任务优先图)是粗粒度时，也就是它的一个链接上的通信代价小于分叉或者合并操作连接的相邻节点的计算代价，任何非线性聚类可以被转换成具有更少或相等执行时间的线性聚类。注意，上面的结论暗示了一个粗粒度程序的线性聚类性能优于任何非线性聚类。然而，对细粒度程序而言，可能存在也可能不存在一个非线性聚类优于线性聚类。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v两两种最优调度算法种最优调度算法 两种方法都假设通信代价可以忽略，优先图中每个节点的执行时间是一样的，即一个时间单

19、元。具体限制如下：(1) 在第一个有约束的调度问题中，优先图是一棵树。(2) 在第二个有约束的调度问题中，只有两个处理器可用。 两种调度算法都是最高层优先(highest-level-first)方法，也就是说，通过节点的优先级来选择节点。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v两两种最优调度算法种最优调度算法 树结构的优先图和这个图在三个处理器上的最优调度 ： T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 时间 处理器 P1 P2 P3 0 T1 T2 T3 T4 T5 T7 T6 T9 T10 T8 T12 T11

20、 T13 (a) 树结构的任务优先图 (b) 对三个处理器的调度 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v两两种最优调度算法种最优调度算法 只有两个处理器可供使用的调度： T9 T10 T11 T7 T8 T6 T4 T5 T1 T2 T3 1 2 3 4 5 6 7 8 9 10 11 (a) 优先级的标记 时间 处理器 P1 P2 T9 T10 T7 T8 T11 T6 T5 T4 T3 T2 T1 (b) 对双处理器的调度 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务相互关系图的任务调度基于任务相互关系图的任务调度

21、任务相互关系图由无向图Gt(Vt,Et)表示，Vt是进程集合，Et是边集合，每条边用相关两个进程的通信代价标记；处理器图Gp(Vp,Ep)用顶点集Vp和边集Ep表示，Vp中的每个元素是一个处理器，Ep中的每个元素是一个通信信道；然后进行分配M：进行VtVp的变换和执行时间的估计。假设w(u)和w(u,v)分别表示节点u和链接(u,v)的代价。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务相互关系图的任务调度基于任务相互关系图的任务调度 对分配对分配MM的评估：的评估：处理器p的计算负载为： tVupuMuwpComp)(| )()(处理器p的通信负载为：

22、tEvuvMpuMvuwpCommp),()()(| ),()(整个应用程序中总的计算量是： pptVpVpVupuMuwpCompComp)(| )()(整个应用程序中总的通信量是： ptpVpEvuVpvMpuMvuwpCommpComm),(2121)()(| ),()(第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务相互关系图的任务调度基于任务相互关系图的任务调度 对分配对分配MM的评估：的评估：程序总的执行时间大概是： pVppCommpCompT),()(max是依据处理器的执行速度确定的值，是依据每个通信信道的通信速度和通信进程间的距离确定的值。

23、注意如果两个进程u和v在Gt中邻接，它们在Gp的映像(M的映像结果)可能邻接也可能不邻接。理想的情况下，所有通信进程被分配在邻接的处理机上，以此减少处理器间通信。 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务相互关系图的任务调度基于任务相互关系图的任务调度 映射的势：映射的势：评估映射质量的一个指标是任务图Gt中的边映射到处理器图Gp中的边的数目。这个数目被称作映射的势(cardinality)，就是Gt中映射到Gp中邻接处理器的通信进程对的数目。映射的势不会超过Gt中的链接数目。如果一个映射的势最大，它就是一个理想的映射。 第第5 5章章 分布式调度分布

24、式调度 5.2 5.2 静态调度静态调度 v基于任务相互关系图的任务调度基于任务相互关系图的任务调度 图中，映射的势是8，任务关系图中边的为13条。 1 2 3 4 5 6 7 8 9 3 1 2 4 6 7 5 9 8 (a) 任务相互关系图 (b) 任务到处理器的映射 第第5 5章章 分布式调度分布式调度 5.2 5.2 静态调度静态调度 v基于任务相互关系图的任务调度基于任务相互关系图的任务调度 嵌入：设想任务相互关系图和处理器图被各自看作Gt和Gp。为了通过Gt得到对Gp的有效模拟(emulation)，也就是在Gp中嵌入Gt。 嵌入的不同代价指标：(1) Gt的边的膨胀。Gt的边的膨

25、胀定义为被映射成Gt里的一条边的Gp中对应的路径的长度。嵌入的膨胀为Gt中的最大边膨胀。 (2) 嵌入的扩大。嵌入的扩大定义为Gt里的节点数对Gp里的节点数的比率。 (3) 嵌入的拥塞。嵌入的拥塞定义为包含Gp中的一条边的最大路径数，Gp中的每条路径表示Gt中的一条边。 (4) 嵌入的负载。嵌入的负载是Gt分配给Gp中任意处理器的进程的最大数目。 第第5 5章章 分布式调度分布式调度 5.3 5.3 动态调度动态调度 v动态调度的组成要素动态调度的组成要素 动态调度算法有六个策略：启动策略、转移策略、选择策略、收益性策略、定位策略和信息策略。 启动策略启动策略的责任是决定谁应该激活负载平衡活动

26、。 转移策略转移策略决定一个节点是否在合适的状态参与负载转移。 选择策略选择策略选择最适合转移最能起平衡作用的任务，并发送给合适的目标处理器。收益性策略收益性策略量化系统中负载不平衡程度，并且作为系统负载平衡潜在受益的估计，评估系统负载平衡是否是有收益的。定位策略定位策略是寻找合适的节点共享负载。 信息策略信息策略决定收集系统中其他节点状态信息的时机、收集的方法和收集的信息。 第第5 5章章 分布式调度分布式调度 5.3 5.3 动态调度动态调度 v动态动态负载平衡算法的分类、设计决策和使用的参数负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法可以分成以下几类： (1) 全局的和局部

27、的。局部负载平衡算法在相邻的节点间转移工作负载。全局负载平衡算法不仅在相邻节点间转移负载，还在全系统内计算负载，根据全局情况调整处理器负载。 (2) 集中控制的和分散控制的。在集中控制算法中，中心控制器收集状态信息，做出负载平衡决策。分散控制算法把控制机制分散到全系统的各个节点。混合式负载平衡算法是集中控制和分散控制算法的折衷。第第5 5章章 分布式调度分布式调度 5.3 5.3 动态调度动态调度 v动态动态负载平衡算法的分类、设计决策和使用的参数负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法可以分成以下几类： (3) 不协作的和协作的。在不协作方法中，各个节点不知道系统中其他节点的状态，独立决定自己的定位和负载转移规则。在协作算法中，节点间相互配合来决定负载平衡决策。(4) 适应性的和非适应性的。在适应性算法中，负载平衡策略根据系统状态变化而改变；而非适应性方法中，这些策略是不变的。 第第5 5章章 分布式调度分布式调度 5.3 5.3 动态调度动态调度 v动态动态负载平衡算法的分类、设计决策和使用的参数负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法的设计决策包括如下一些内容：(1)非抢先式的和抢先式的非抢先式的和抢先式的: :抢先式的主要目的是负载共享，节点只分配新到达的任务，又称为任务放置(place