分布式调度Chapter 10

第十章分布式调度主讲陈志刚教授第十章分布式调度22020/3/11中南大学信息科学与工程学院10.1调度算法概述调度算法的分类Casavant和Kuhl对调度算法做了如下分类：调度算法局部调度全局调度静态调度动态调度分散式调度集中式调度协作式调度非协作式调度优化调度次优化调度近似调度启发式调度优化调度次优化调度近似调度启发式调度第十章分布式调度32020/3/11中南大学信息科学与工程学院调度算法的分类对于大量的实时调度方法而言，还存在着其他一些划分方法：抢占式(preemptive)和非抢占(non-preemptive)调度：对抢占式调度算法，正在运行的任务可能被其他任务所打断。而后者一旦任务开始运行，该任务只有在运行完成而主动放弃CPU资源，或是因为等待其他资源被阻塞的情况下才会停止运行。实时内核大都采用了抢占式调度算法，使关键任务能够打断非关键任务的执行，确保关键任务的截止时间能够得到满足。10.1调度算法概述第十章分布式调度42020/3/11中南大学信息科学与工程学院调度算法的分类适应性(Adaptive)和非适应性(Non-Adaptive)调度：非适应性调度算法只是用一种负载分配策略，不会根据系统的反馈而改变自己的行为。适应性调度算法能够根据系统的反馈调整自己的行为，采用不同的负载分配策略。一个适应性调度算法是许多种调度算法的集合，根据系统的各种参数来选择一种合适的算法。10.1调度算法概述第十章分布式调度52020/3/11中南大学信息科学与工程学院调度算法的目标和有效性评价分布式调度的基本目标是尽快得到计算结果和有效地利用资源。其具体目标有2个：负载平衡(LoadBalancing)：它的努力目标是维持整个分布式系统中各个资源上的负载大致相同。负载共享(LoadSharing)：它的目标仅仅是防止某个处理机上的负载过重。10.1调度算法概述第十章分布式调度62020/3/11中南大学信息科学与工程学院调度算法的目标和有效性评价从调度算法的有效性来看，调度算法分为最优调度算法和次优调度算法。从理论上来说，最优调度只有在能够完全获知所有任务在处理、同步和通信方面的需求，以及硬件的处理和时间特性的基础上才能实现。实际的应用很难实现，特别是需要获知的信息处于动态变化的情况下。即使在这些需要的信息都是可以预见的情况下，常用的调度问题仍然是一个NP难题。调度的复杂性将随调度需要考虑的任务和约束特性的数量呈现出指数增长。10.1调度算法概述第十章分布式调度72020/3/11中南大学信息科学与工程学院调度算法的目标和有效性评价选择调度算法时，通常需要综合考虑如下因素通信代价：这个参数考虑了向一个给定的节点传送或者从一个给定节点接收一个报文所花费的时间，更为重要的是必须考虑为一个进程分配一个执行地点而引起的通信代价。执行代价：这个参数反映的是将一个进程分配到一个指定的执行节点，在这个节点的执行环境下，执行这个程序所需的额外开销。资源利用率参数：表明基于分布式系统当前各个节点的负载情况，给一个进程分配的执行节点是否合适。10.1调度算法概述第十章分布式调度82020/3/11中南大学信息科学与工程学院调度算法的目标和有效性评价次优的调度算法分为两类：近似的次优调度算法：在近似次优调度方法中，负载分配算法仅搜索一个解空间的子集，当寻找到一个好的解时，终止执行。使用近似的次优调度算法必须能够判定所得到的解是否是可以被接受的，也就是说，必须能够确定最优解和次优解之间的近似程度。启发式的次优调度算法：使用比较简明的规则和一些直觉的规则来进行调度。这些启发式的规则往往是不能证明其正确性，在特定情况下可能还是错误的，但是在绝大多数的情况下是能够被接受的。10.1调度算法概述第十章分布式调度92020/3/11中南大学信息科学与工程学院静态调度算法是根据系统的先验知识做出决策。运行时负载不能重新分配。设计调度策略时要考虑的三个主要因素是处理机的互连、任务的划分和任务的分配。通常用图模型表示任务和处理机的结构。我们用任务优先图或者任务交互作用图对任务集合建模。任务优先图又称为有向无环图(DAG)，每个链接定义了任务间的优先关系。节点和链接上的标记表示任务执行时间和任务完成后启动后续任务所需的时间间隔。任务交互作用图中，链接定义了两个任务间的相互关系。每个链接赋予一对数，表示这两个任务在同一个处理机上时的通信开销和在不同处理机上时的通信开销。10.2静态调度第十章分布式调度102020/3/11中南大学信息科学与工程学院10.2静态调度2114211422T1T2T3T4T5(a)任务优先图23423T1T2T3T4T51,41,51,41,31,51,4(b)任务相互作用图第十章分布式调度112020/3/11中南大学信息科学与工程学院任务划分与分配任务划分的一个主要目标就是尽可能消除处理器间通信引起的开销。一个给定任务划分的粒度被定义为任务的计算量与通信量的比值。粒度太大，就会降低并行度，因为潜在并行任务可能被划分进同一个任务而分配给一个处理器。粒度太小，进程切换和通信的开销就会增加。任务聚类：在图模型中，任务的划分被称作任务聚类，即在给定的图模型中对小任务进行分类。任务划分把任务图当作一个整体，将图中的小任务(节点)划分成不同的聚类，聚类中的小任务串行执行，不同的聚类之间并行执行。任务聚类中可以使用两种策略：将不相关的任务映射到一个聚类中；将DAG中一条优先路径上的任务映射到一个聚类中。10.2静态调度第十章分布式调度122020/3/11中南大学信息科学与工程学院任务划分与分配任务划分的方法关键路径划分：主要思想是在给定的任务优先图中垂直或者水平划分。关键路径(最长路径)的概念常常在垂直划分中使用。水平划分把给定的任务分成若干层，任务的优先级由它们所在的层次决定。通信延迟最小划分：主要思想是把通信频繁的节点归成一类。然而，这些需要通信的任务分配在一个处理器上会丧失任务间的并发性。如果减小通信延迟的好处抵销了并行任务串行化的损失，就采用通信延迟最小划分。任务复制：为了消除任务间的通信开销，将任务在处理机上进行复制有时是最有效的方法。这个方法保留了任务原有的并行性；但是存储空间要求和同步开销增加了。可以利用任务复制来达到容错性。任务复制也被用来实现无错调度，以保证处理器出现错误时最后计算结果正确。10.2静态调度第十章分布式调度132020/3/11中南大学信息科学与工程学院任务划分与分配10.2静态调度关键路径划分的例子132457964252472T1T2T5T3T6T4T7消除通信延迟的划分133112T2T3T4T5T63133312T1第十章分布式调度142020/3/11中南大学信息科学与工程学院任务划分与分配任务复制：10.2静态调度132457964252472T1T2T5T3T6T4T7时间处理机1处理机2处理机31T1T1T12T2T3T44T2T2T45T3T2T46T3T2T27T5T6T29T5T6T7第十章分布式调度152020/3/11中南大学信息科学与工程学院任务划分与分配基于任务优先图的任务调度甘特图(ganttchart)能够最有效描述进程对处理器的分配情况。甘特图以处理器为纵坐标，以时间为横坐标。图中的每个方块表示进程在某个系统中的开始时间、持续时间和结束时间。处理器内的时间延迟和处理器间的时间延迟都能够在图中体现。10.2静态调度第十章分布式调度162020/3/11中南大学信息科学与工程学院任务划分与分配基于任务优先图的任务调度10.2静态调度2114211422T1T2T3T4T5(a)任务优先图(b)甘特图时间处理器P1P2T102T23T3T47T512第十章分布式调度172020/3/11中南大学信息科学与工程学院任务划分与分配基于任务优先图的任务调度通信延迟和任务复制对调度的影响：10.2静态调度T1T2T3dd时间处理器P1P2T1T1T2T3时间处理器P1P2T1T2T3时间P1P2处理器T1T2T3d(a)任务优先图(b)使用任务复制的调度(c)任务分配在一个处理器上(d)通信延迟对调度的影响第十章分布式调度182020/3/11中南大学信息科学与工程学院任务划分与分配基于任务优先图的任务调度线性聚类与非线性聚类：如果至少有一个聚类中包含两个独立的任务，则聚类是非线性的；否则，聚类就是线性的。10.2静态调度432T1T2T311432T1T2T311(a)线性聚类(b)非线性聚类第十章分布式调度192020/3/11中南大学信息科学与工程学院两种最优调度算法多数调度算法是NP完全的。下面介绍2种有约束的调度问题，他们有多项式时间的执行复杂度。两种方法都假设通信代价可以忽略，优先图中每个节点的执行时间是一样的，即一个时间单元。具体限制如下：在第一个有约束的调度问题中，优先图是一棵树。在第二个有约束的调度问题中，只有两个处理器可用。两种调度算法都是最高层优先(highest-level-first)方法，也就是说，通过节点的优先级来选择节点。10.2静态调度第十章分布式调度202020/3/11中南大学信息科学与工程学院两种最优调度算法10.2静态调度T1T2T3T4T5T6T7T8T9T10T11T12T13时间处理器P1P2P30T1T2T3T4T5T7T6T9T10T8T12T11T13(a)树结构的任务优先图(b)对三个处理器的调度树结构任务优先图的最优调度第十章分布式调度212020/3/11中南大学信息科学与工程学院两种最优调度算法10.2静态调度任务优先图对双处理器的最优调度T9T10T11T7T8T6T4T5T1T2T31234567891011(a)优先级的标记时间处理器P1P2T9T10T7T8T11T6T5T4T3T2T1(b)对双处理器的调度第十章分布式调度222020/3/11中南大学信息科学与工程学院基于任务相互关系图的任务调度任务相互关系图由无向图Gt(Vt,Et)表示，Vt是进程集合，Et是边集合，每条边用相关两个进程的通信代价标记；处理器图Gp(Vp,Ep)用顶点集Vp和边集Ep表示，Vp中的每个元素是一个处理器，Ep中的每个元素是一个通信信道；然后进行分配M：进行Vt→Vp的变换和执行时间的估计。假设w(u)和w(u,v)分别表示节点u和链接(u,v)的代价。10.2静态调度第十章分布式调度232020/3/11中南大学信息科学与工程学院10.2静态调度基于任务相互关系图的任务调度对分配M的评估：处理器p的计算负载为：处理器p的通信负载为：整个应用程序中总的计算量是：整个应用程序中总的通信量是：tVupuMuwpComp)(|)()(pptVpVpVupuMuwpCompComp)(|)()(ptpVpEvuVpvMpuMvuwpCommpComm),(2121)()(|),()(tEvuvMpuMvuwpCommp),()()(|),()(第十章分布式调度242020/3/11中南大学信息科学与工程学院10.2静态调度基于任务相互关系图的任务调度对分配M的评估：程序总的执行时间大概是：α是依据处理器的执行速度确定的值，β是依据每个通信信道的通信速度和通信进程间的距离确定的值。注意如果两个进程u和v在Gt中邻接，它们在Gp的映像(M的映像结果)可能邻接也可能不邻接。理想的情况下，所有通信进程被分配在邻接的处理机上，以此减少处理器间通信。(两个进程通常不应该映射在一个处理器上,任务聚类时,这两个进程应当聚类到同一进程.)pVppCommpCompT)},()(max{第十章分布式调度252020/3/11中南大学信息科学与工程学院10.2静态调度基于任务相互关系图的任务调度映射的势：评估映射质量的一个指标是任务图Gt中的边映射到处理器图Gp中