基于异构多核处理器的静态任务调度研究（一）

　　摘 要：针对现存任务调度算法优先级选取过于单一、冗余任务处理较晚的问题，提出一种基于加权优先级的任务调度算法-WPTS算法。该算法综合考虑任务3个属性的加权值以决定任务被处理的先后次序，从而克服了任务选取时的单一性问题。在将任务分配到处理器的过程中，保证任务优先调度到完成时间早的处理器上。同时，引入冗余任务处理过程，及时消除冗余任务，达到对处理器空闲时间段进行有效回收、减少处理器调度长度的效果。性能对比实验表明，WPTS算法较CPFD算法、HCPFD算法和HDEFT算法能取得更好的性能。

　　0 引 言

　　异构多核处理器以其芯片面积利用率高、处理器功耗低、应用程序的并行化程度高等诸多优势成为处理器体系结构发展的一个重要方向，同时它的出现给计算机学科发展带来了新的挑战。研究发现多核处理器任务调度的优劣对处理器的执行时间、任务调度长度、处理器的功耗等诸多性能产生直接影响。因此，多核处理器的任务调度作为影响操作系统性能的重要因素成为近年来系统结构方向的热点研究问题之一。当前对异构多核处理器上任务调度的研究很少考虑任务优先级的选取对调度结果的影响以及使用复制技术的任务调度算法会产生冗余任务的问题。

　　本文深入分析了CPFD、HCPFD和HDEFT这3种有代表性的任务调度算法，并在总结目前任务调度算法存在的缺点基础上，根据异构多核处理器系统结构的特点，设计了基于加权优先级的任务调度算法（weighted prioritytask scheduling,WPTS），算法以3个参数构成的加权值作为任务的优先级，将任务排序构成任务调度列表，然后依次将任务映射到处理器上，并在映射过程中对任务进行优化处理，通过预先设定的性能评价参数对算法进行实验验证。本研究能有效改善原有任务调度算法的不足，提升了多核处理器在实际应用中的性能，对异构多核处理器上静态任务调度技术的发展具有重大理论和现实意义。

　　1 WPTS算法设计

　　1.1 3种现有高效算法的分析

　　目前基于异构多核处理器取得较好调度性能的算法有CPFD算法、HCPFD算法和HDEFT算法。CPFD算法使用任务节点到入口节点的长路径b-level作为任务调度的优先级，将任务调度到具有早完成时间的处理器上，其时间复杂度是O （v4），v是DAG图中任务节点的数目。

　　HCPFD算法以关键任务和任务的晚开始时间划分任务的优先级，将任务分配到使其完成时间早的处理器节点上，在任务到处理器的映射阶段优先考虑使用处理器上的空闲时间段来处理任务，其时间复杂度为O （pv2），p是任务调度中处理器的总个数。HDEFT算法在任务分配阶段采用sumu （vi）作为任务优先级，在任务到处理器的映射阶段使用任务插入和复制技术，其时间复杂度为O （pv2）。

　　CPFD算法和HCPFD算法的调度性能不够理想，原因在于算法只选择任务属性作为任务的优先级，没有考虑任务间的约束关系和通信开销等影响调度性能的重要因素。HDEFT算法时间复杂度不高，但没有对使用任务复制技术后存在的冗余任务进行处理，冗余任务延长了总的任务调度完成时间，浪费了处理器资源。

　　本文在总结并分析上述算法不足的基础上，设计出WPTS算法，并给出任务调度实验以验证新算法的正确性和有效性。

　　1.2 WPTS算法执行过程

　　WPTS算法的执行分为两个阶段：任务优先级计算和任务到处理器的映射。其中阶段包括任务合并、任务分层和任务权值计算3个过程，第二阶段包括任务分配到处理器和任务调度结果优化两个过程，如图1所示。

图1 WPTS算法执行过程

1.3 WPTS算法实现原理

1.3.1 任务优先级计算阶段

(1)任务优先级计算阶段的设计思想任务合并是将任务中较独立、任务间通信开销较大的任务进行合并优化。对DAG图进行深度优先搜索,当任务vi只有一个直接后继节点vj、任务vj只有一个直接前驱节点vi,且c (vi,vj)≥wj,k,即任务vi、vj间的通信开销大于任务vj在所有处理器上的平均执行开销,则合并任务vi、vj,并记为vi*,vi*的计算开销为vi、vj计算开销的总和,在随后的调度中任务vi*被作为整体处理。

任务分层是为方便后续任务权值的计算。用level标记任务在DAG图中的层数,设置入口节点任务level=0,从上到下遍历任务DAG图,计算任务节点到入口节点的通信边数目,以此作为任务的level值。非入口节点任务vi的level值为其所有前驱节点的level值加1,计算公式如下所示level(vi)=Max (level(vj))+1,vj∈pred (vi)(1)在任务权值计算过程中,WPTS算法综合考虑任务各属性对任务优先级排序的影响,选择使用平均计算开销和通信开销作为任务的优先级参数。平均计算开销ACC是任务在所有处理器上计算开销的平均值,计算公式如式(2)所示。通信开销包括平均数据传输开销ADTC和平均数据接收开销ADRC,计算公式如式(3)和式(4)所示,式中x为vi直接后继节点数量,y为vi直接前驱节点数量

定义weight (vi)为任务vi的权值,它是任务的ADTC、ADRC、ACC之和,对每个处在level=i层的任务来说weight(vi)的计算公式如公式下所示weight(vi)=ADTC (vi)+ADRC (vi)+ACC (vi)(5)(2)任务优先级计算阶段流程

任务优先级计算流程如图2所示。

图２　任务优先级计算阶段流程

 

　　任务优先级计算阶段完成后，所有的任务已经按照优先级从高到低的次序加入到调度列表中，可以继续执行任务到处理器映射阶段的步骤。

　　1.3.2 任务到处理器映射阶段

　　（1）任务到处理器映射阶段的设计思想

　　任务到处理器映射阶段包括任务映射到处理器和处理图2 任务优先级计算阶段流程器上的冗余任务处理。

　　在任务映射到处理器的过程中，遍历所有处理器，直接将任务vi分配到具有早完成时间的处理器上，其完成时间记为EFT1;将vi分配具有空闲时间段的处理器上且不使用任务复制技术的早完成时间为EFT2;记使用复制任务技术复制任务vi的直接前驱节点到vi所处的处理器空闲时间段上早完成时间为EFT3.比较三者的值，将任务vi分配到具有完成时间的处理器上。EFT1、EFT2、EFT3的计算公式如下

　　式中：AST （vi,pn）-任务vi在处理器pn上的实际开始时间；AFT （vi,pk）-任务vi在处理器pk上的实际完成时间；vpar-一个与任务vi通信的任务；Avail（pn）-处理器pn执行完分配到其上的所有任务的时间。

　　通过对DAG图的深入研究发现，某层冗余任务的处理在其下一层任务到处理器的映射之后执行效果，如对level=1层任务调度完成后对level=0层任务进行冗余判断，将任务分配到处理器和冗余任务处理两个过程交替执行，直到冗余任务列表为空。

　　（2）任务到处理器映射流程任务到处理器映射流程如图3所示。

　　（3）任务到处理器映射阶段具体步骤

　　步骤1 初始化level=0,判断任务调度列表TL在level层的任务是否调度完毕，如果是则跳转到步骤5;否则向下执行步骤2.

　　步骤2 取任务调度列表TL的首任务记为vi,遍历所有处理器，如果处理器存在空闲时间段且满足vi插入条件，则将vi分配到空闲时间段，并计算其早完成时间，记为EFT1;否则向下执行步骤3.

　　步骤3 计算将vi分配到所有处理器上的早完成时间，记为EFT2.如果处理器上存在空闲时间段且能使用任务复制技术，则计算在处理器上复制vi的前驱获得早完成时间，记为EFT3,继续执行步骤4.

　　步骤4 选择EFT1、EFT2、EFT3的值，并将任务分配到具有早完成时间的处理器上，从调度列表中删除vi,建立冗余任务列表RTL,将被复制的任务加入到RTL中，格式为vi,0~vi,k,vi为被复制的任务节点，k为任务所在处理器的编号。

　　步骤5 判断RTL中是否有（level-1）层任务，如果是则跳转到步骤6;否则跳转到步骤8.

　　步骤6 取RTL首任务节点，记为vi,k,判断删除任务vi,k后vi,k直接后继节点的早开始时间是否延迟，如果延迟，判定任务vi,k非冗余任务，从RTL中删除vi,k,跳转到步骤5;否则判定任务vi,k为冗余节点，从RTL中删除vi,k,从任务映射图中删除vi,k,跳转到步骤7继续执行。

　　步骤7 判断任务vi,k的后继任务能否提前执行，如果能则将其前移执行，修改任务映射图，跳转到步骤5;否则，直接跳转到步骤5.

　　步骤8 如果level<Max （level），令level=level+1,跳转到步骤1;否则任务到处理器映射阶段执行完毕。

　　2 WPTS算法时间复杂度分析

　　任务合并过程是对DAG图进行深度优先遍历，因此其时间复杂度为O （v+e），v为DAG图中任务的数量，e为有向边的数目。任务分层是从上到下计算每个节点的level值，时间复杂度为O （n+e），n为任务合并后DAG图中任务的数量。任务权值计算对DAG图进行广度优先遍图3 任务到处理器映射阶段流程历，计算任务节点的weight值和寻找关键路径节点，时间复杂度为O （n2），因此任务优先级计算阶段的时间复杂度为O （v+e）+O （n+e）+O （n2）；任务到处理器的映射阶段考虑了处理器空闲时间段插入和任务复制技术，因此每层任务被映射到处理器上的时间复杂度为O （kp），k为每层的任务数量，p为处理器的数量，冗余任务处理的时间复杂度为O （k2），将所有任务映射到处理器上并完成调度结果优化所需的时间复杂度为O （kpm+k2 m），m 为任务DAG图的层数，其在坏情况下等于任务数量v.

图３　任务到处理器映射阶段流程

 

　　综上所述，WPTS算法的时间复杂度为O （v+e）+O（n+e）+O （n2）+O （kpm+k2 m），即O （v3），算法没有提高时间复杂度，且能有效处理使用任务复制技术带来的冗余任务，减少任务的调度长度，避免处理器资源的浪费。