并行算法的设计与分析第19章

第19章并行算法（程序）性能优化——任务调度任务调度的概念调度问题的一般模型构成调度问题的基本元素：资源集、消费者集及这些资源为这些消费者服务所依据的一定规则。调度问题就是在满足资源集和消费者集约束条件的基础上，设计一个有效的调度系统来管理消费者如何高效地使用这些资源，并使得一些系统性能指标达到最优或近似最优。消费者集（并行应用程序）资源集（并行分布系统）调度程序策略规则调度问题的一般模型任务调度的概念调度问题的一般模型调度性能和调度效率是评价一个调度系统优劣程度的两个方面。调度性能（SchedulingPerformance）通过性能测试指标的取值来反映，它直接体现了调度结果的好坏。调度效率（SchedulingEfficiency）主要指调度系统本身的复杂度。任务调度的概念并行计算中的任务调度并行分布计算中的任务调度问题：根据一定的调度规则和调度策略，把组成并行程序的一组任务或构成工作负载的一组作业，按照一定执行时序分配到并行分布系统的多个计算节点上，以期取得较好的系统执行性能。任务调度与作业调度任务层调度针对某个用户的单一并行应用程序的一组任务（子任务），面向的一般是单应用程序系统，它的调度实体是任务，调度目标一般就是求得任务最短的执行时间。作业层调度针对若干个用户的多个并行应用程序构成的一组作业，面向的一般是多应用程序系统，它的调度实体是传统批处理意义下的作业，调度目标有多个，如最短的平均作业响应时间、最大的资源利用率或最大的系统吞吐率等。任务调度的概念并行计算中的任务调度任务调度与任务划分在分布系统中一组任务相互间发生关系的方式有多种多样，其中有一种是通信关系，如果两个任务被分配到不同的处理器上，那么就产生以通信成本形式表示的通信开销（CommunicationOverhead），如果两个任务被分配到相同的处理器上，那么就不产生任何通信开销，这种特殊的任务调度我们称作任务划分（TaskPartitioning）。对于任务划分，我们通常用任务交互作用图（TaskInteractionGraph）来表示并行算法（程序）模型对于任务调度，通常用带权有向图（WeightedDirectGraph）来表示并行算法（程序）模型。任务调度的概念并行计算中任务调度的分类静态调度、动态调度和混合调度静态调度（StaticScheduling）在编译并行程序时，就决定每个任务的执行处理器及执行时序，它经常用于任务图比较确定的情况。动态调度（DynamicScheduling）在并行程序运行过程中，根据当前任务调度及系统执行情况，实时决定每个任务的执行处理器及起始执行时刻。混合调度（HybridScheduling）介于静态调度和动态调度之间的调度方法，它在编译时先静态调度部分任务，而剩余部分则采用动态调度方法在系统运行过程中来给它们分配处理器。任务调度的概念并行计算中任务调度的分类最优调度和启发式调度最优调度一般是指静态调度，如果一个调度算法能在多项式复杂度的时间内获得最佳调度结果，那么称之为有效的最优调度算法。启发式调度方法将任务调度分配到各处理器上，它虽然不能确保获得最优解，但可以获得最优调度的近似解。共享存储结构的任务调度和分布存储结构的任务调度共享存储结构的任务调度：不考虑通信延迟，任务调度的着重点在于如何最大限度地获得并行程序任务间的并行性。分布存储结构的任务调度：通信延迟的存在使得任务调度更为复杂，需尽可能利用各任务之间的并行性和尽量减少计算节点通信开销之间进行折衷。任务调度的概念并行计算中任务调度的分类集中式调度和分布式调度集中式调度：由一个叫作中心调度器的处理器来收集全局调度信息，其他处理器把它们的状态信息传送给中心调度器，并由中心调度器作出调度决定。优点在于实现比较简单，但在计算节点数较多的大规模并行分布系统中，各节点与调度服务器的通信成为瓶颈，调度开销比较大。分布式调度：由各处理器的调度程序根据局部范围内的一些调度信息来调度任务。优点在于具有良好的可扩放性（Scalability），但调度算法复杂。任务调度的概念并行计算中任务调度的分类抢占式调度和非抢占式调度抢占式调度：动态地将优先权更高的任务调度分配给处理器。自适应调度和非自适应调度自适应调度（AdaptiveScheduling）：根据调度程序在以前一段时间内的执行效果，以及当前系统状态信息（系统资源和任务负载情况）自动修正调度程序的执行机制，它们通过收集当前系统状态信息来动态修正调度策略。非自适应调度（Non-adaptiveScheduling）：一旦确定任务调度算法的调度策略，那么在并行程序执行过程中就固定地按照这些调度策略来进行任务调度，即使某些不确定因素（如动态产生的任务）使得调度效率比较低，那么也必须等到非执行状态时，再修正调度策略。任务调度的概念并行计算中任务调度的模型并行应用程序任务一个并行应用程序的性质可用(A,﹤,D,W)来刻画，其中A={ak|k=1,2,…,n}为任务集；D={dij|i,j=1,2,…,n}是一个n×n的通信矩阵，dij(≥0)表示任务ai传送给任务aj的数据量；工作负载W={w(ai)}，w(ai)表示任务ai的工作负载大小。在同构的并行分布系统中，由于每个节点的计算能力（包括运算速度、内存大小等）相同，所以也可以直接用w(ai)来表示任务ai的执行成本。而在异构的并行分布计算环境下，相同负载在不同的（计算能力不同）节点上的执行成本是不相同的。“﹤”定义了任务间的偏序（PartialOrdering）关系,“ai﹤aj”表示任务aj的执行依赖于任务ai的执行。任务调度的概念并行计算中任务调度的模型目标机器（TargetMachine）假定有m个处理器组成，该m个处理器可以是同构的，也可以是异构的，它们通过任意的互连网络进行连接。每个处理器某一时刻只能处理一个任务，每个任务可在任何一个处理器上运行。可用六元组TM=（P,[Pij],[Si],[Ii],[Bi],[Rij]）来刻画目标机器的特性：①P=｛P1,P2,…,Pm｝为构成并行分布系统的一组处理器；②[Pij]为m×m的互连网络拓扑矩阵；③Si(1≤i≤m)为处理器Pi的执行速度；④Ii(1≤i≤m)表示在处理器Pi上启动一个消息传递所需的时间；⑤Bi(1≤i≤m)表示在处理器Pi上启动一个进程执行所需的时间；⑥Rij(1≤i≤m,1≤j≤m)为两个相邻处理器之间的消息传输率，即每单位时间传送的数据量。任务调度的概念并行计算中任务调度的模型执行时间与通信开销tij表示任务ai在处理器Pj上的执行时间表示处理器P上的任务a与处理器P上的任务a之间的通信开销，如果这两个处理器相邻，则其中R表示这两个处理器间的传输率，O表示P与P之间通信线路的竞争开销。如果P与P之间不相邻，假定每两个相邻处理器之间的消息传输率均为R，每个处理器的消息传递启动时间均为I，用H表示处理器P到处理器P的线路条数，则()iijjjwatBS2211jijiCO+I+Rd=21121212211jjjjjiijijiC2121212211jjjjiiO+H*I)+Rd(=jijiC任务调度的概念并行计算中任务调度的模型调度及调度目标并行应用程序的一个调度其实就是其对应的任务图G到目标机器的一个映射f：V{P1,P2,…,Pm}×[0,∞]，f(ai)=(p,t)表示任务ai被调度到编号为p的处理器上，起始执行时刻为t。一般地，我们可用Gantt图GC={(p(ai),t(ai))|ai∈V}来直观地表示调度结果，其中函数p(ai)表示分配给任务ai的处理器号，t(ai)表示任务ai的起始执行时刻。一般入口节点任务的起始执行时刻以零计算，那么所有任务执行完的那个时刻称为调度长度SL（SchedulingLength），它反映了整个并行程序任务的执行时间，显然SL={t(ai)+w(ai)/Sj}，其中j=p(ai)。任务调度的目标就是要获得最短的整个应用程序执行时间，即最短的调度长度。静态任务调度的最优算法在忽略通信延迟的情况下，对任务图再加以一些限制条件可以得到最优调度算法。限制一：任务图是树结构。代表算法：T.C.Hu线性的最优调度算法、M.Kaufman最优调度算法。限制二：区间有序条件。代表算法：C.Papadimitriou算法。限制三：对目标机器加以限制。代表算法：E.G.Coffman调度算法，时间复杂度为O(n2)。静态任务调度的启发式算法贪心算法基本思想是优先权高的任务先执行，又称为优先权队列调度（PriorityListScheduling）。任务一旦分配出去通常就不会再更改，称为无回溯（Non-backtracking）。贪心算法的关键在于优先权，可以分为静态优先权和动态优先权两大类。常用的几种贪心算法：①最高层次优先HLF（HighestLevelFirst）②最长路径优先LPF（LongestPathFirst）③最早任务优先ETF（EarliestTaskFirst）④最大处理时间优先LPTF（LargestProcessingTimeFirst）⑤最大总代价优先LGCF（LargestGlobalCostFirst）静态任务调度的启发式算法随机算法算法的主要思想：采取某种随机扰动的机制来跳出局部最优解以便获得更优的解。模拟退火：一个调度方案s及其代价函数f(s)分别对应于固体的一个微观状态及其能量，再设置一个随算法过程递降的控制参数t来表示固体的温度。算法将施行“产生新方案s’判断接受／舍弃”的迭代过程。其中，新方案s’的接受概率p可计算如下：刚开始的时候t值较大，当f(s’)≥f(s)时，s’将以较大的概率被接受；随着t值的减小，这个概率也将减小并趋向于零。这种机制使得算法既能跳出局部最优（LocalOptimal）的陷阱，又能稳定收敛到系统的最终稳态，是整个算法的关键所在。否则当))'()(exp()()'(1tsfsfsfsfp静态任务调度的启发式算法随机算法禁忌搜索：在每次迭代中都向近邻集合中的最优方案移动。为了避免循环移动和陷入局部最优，该算法通过建立禁忌列表（TabuList）用以记录先前移动步的信息，并从近邻集合中删除相应的元素。禁忌列表是一个有长度限制的先进先出队列。遗传算法：算法以字符串代表基因（Gene），字符串集合代表种群（Population），以适应性函数和代价函数表示物种的适应度（Fitness）。算法首先产生一组的字符串，即种群；然后在每一次迭代中，选择部分基因执行遗传操作，适应度越高的基因被选中的概率越大，这样做是为了让优秀的遗传特征能以较大的可能性被保留下来，而低劣者则被淘汰，从而提高种群的整体适应度，并最终产生次优解。静态任务调度的启发式算法聚簇策略聚簇策略实际上是上述贪心算法和随机算法的一个折衷，通过将一些任务合并成一个簇（Cluster），增加问题粒度，减小问题规模，从而达到这样一个效果：既具备贪心算法的高计算效率，又能保证解的质量不会跟随机算法的相差太多。分类：①合并法（AgglomerativeAlgorithms）：开始时把每个任务看成是一个簇，然后执行合并操作，每次选择最合适的两个簇进行合并，直至簇的数目达到预定的要求。②分割法（DivisiveAlgorithms）：开始的时候把所有任务作为一个簇，然后执行分割操作，每次选择合适的簇进行分割，直至簇的数目达到预定的要求。动态负载平衡基本概念负载平衡（LoadBalancing）策略是为了提高并行机的利用率，将提交的作业任务与并行机中计算节点进行有效的匹配，使各节点被指派的任务量与其处理能力相当。负载平衡又分为静态负载平衡SLB（StaticLoadBalancing）和动态负载平衡DLB（DynamicLoadBalancing）两类。静态负载平衡是在程序执行之前根据每个节点的计算能力指派（Assignment）作业。动态负载平衡是在程序执行过程中在并行计算机各个处