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

李静梅，金胜男

（哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨150001）

0 引 言

异构多核处理器以其芯片面积利用率高、处理器功耗低、应用程序的并行化程度高等诸多优势成为处理器体系结构发展的一个重要方向，同时它的出现给计算机学科发展带来了新的挑战［1－2］。研究发现多核处理器任务调度的优劣对处理器的执行时间、任务调度长度、处理器的功耗等诸多性能产生直接影响。因此，多核处理器的任务调度作为影响操作系统性能的重要因素成为近年来系统结构方向的热点研究问题之一［3－4］。当前对异构多核处理器上任务调度的研究很少考虑任务优先级的选取对调度结果的影响以及使用复制技术的任务调度算法会产生冗余任务的问题。本文深入分析了CPFD、HCPFD和HDEFT这3种最具有代表性的任务调度算法，并在总结目前任务调度算法存在的缺点基础上，根据异构多核处理器系统结构的特点，设计了基于加权优先级的任务调度算法（weighted priority task scheduling，WPTS），算法以3个参数构成的加权值作为任务的优先级，将任务排序构成任务调度列表，然后依次将任务映射到处理器上，并在映射过程中对任务进行优化处理，最后通过预先设定的性能评价参数对算法进行实验验证。本研究能有效改善原有任务调度算法的不足，提升了多核处理器在实际应用中的性能，对异构多核处理器上静态任务调度技术的发展具有重大理论和现实意义［5－6］。

1 WPTS算法设计

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

目前基于异构多核处理器取得较好调度性能的算法有CPFD算法、HCPFD算法和 HDEFT算法［7－8］。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，计算公式如下所示

在任务权值计算过程中，WPTS算法综合考虑任务各属性对任务优先级排序的影响，选择使用平均计算开销和通信开销作为任务的优先级参数。平均计算开销ACC是任务在所有处理器上计算开销的平均值，计算公式如式（2）所示。通信开销包括平均数据传输开销ADTC和平均数据接收开销ADRC，计算公式如式（3）和式（4）所示，式中x为vi直接后继节点数量，y为vi直接前驱节点数量

定义weight（vi）为任务vi的权值，它是任务的ADTC、ADRC、ACC之和，对每个处在level＝i层的任务来说weight（vi）的计算公式如公式下所示

（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算法时间复杂度分析

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

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

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

3 实验验证

3.1 性能评价参数

在静态任务调度中，任务调度的开销比较小，任务调度的总长度成为评价一个任务调度算法的性能标准，除此之外还有任务调度长度比率、算法的效率等，具体的评定标准和公式如下：

（1）调度长度makespan，为所有处理器上的最大任务调度长度。

（2）调度长度比率SLR，计算公式如式（9）所示，分母为所有关键路径任务执行时间的最小值之和。SLR的值总是大于等于1的，且值越小，任务调度算法性能越好。

（3）算法效率Efficiency，计算公式如式（10）所示，分子为任务调度的加速比，计算公式如式（11）所示，分母为任务调度中处理器的数量，Efficiency值越大表明任务调度算法的性能越好

3.2 实验与结果

实验将任务调度性能测试分成两组，通过仿真实验检验WPTS算法在不同任务图中的性能［9］。

实验1：利用随机任务图产生器［10－11］，根据参数值v（DAG的任务数量，取值为 ｛30，40，50，60，70，80，90，100｝）、α（DAG 的形状参数，取值为｛0.5，1.0，2.0｝、β（节点的出度，取值为 ｛1，2，3，4，5｝）、γ（节点的入度，取值为 ｛1，2，3，4，5｝）、CCR（通信计算时间比，取值为 ｛0.1，0.5，1.0，5.0，10.0｝）产生3000组DAG类型，每组类型中随机产生20个具有不同节点权值的DAG图，共产生60000个随机任务图。

将随机任务图以参数形式输入算法中，通过Socket将算法运行结果传递到仿真实验环境中。仿真实验使用Simics模拟多核异构处理器结构，通过C语言实现算法和Socket通信模块，实现虚拟多核环境和算法之间的有效信息交互，通过对任务图的完成时间长短判断算法优劣（依次比较两种算法，完成时间差在线性级之内的标记为Equal，其它情况下，算法1较算法2完成时间短时标记为Better，完成时间长时标记为Worse），实验方案结构如图4所示。

将WPTS算法与CPFD算法、HCPFD算法、HDEFT算法进行比较，统计WPTS算法较其它3种算法取得Better、Equal和Worse调度性能的次数和所占的比例，比较结果见表1。

图4 验证方案结构

表1 算法调度性能对比

从表1可以看出在随机实验环境下，在将3种算法综合的情况下，WPTS算法能取得最优调度的比例为71.53%，优于其它3种算法。

实验2：（1）令α＝｛0.5，1.0，2.0｝，改变随机任务图的其它参数，计算各算法的平均SLR和Efficiency，计算公式如式（9）、式（10），实验结果如图5、图6所示。

图5 形状参数α变化时算法的平均SLR

从对比图可以看出，任务形状参数α变化会影响任务调度的结果：α值为0.5时，DAG图高度较小，任务之间并行性较高；α值为1.5时，DAG图高度较大，任务之间并行性较低。4种算法在任务并行性较高时都能取得很好的性能，其中WPTS算法的性能最优，原因是任务并行性较高时，处理器上的空闲时间较少，处理器的利用率较高，而WPTS算法能及时处理任务调度中存在的冗余任务，提高处理器的执行效率。

图6 形状参数α变化时算法的Efficiency

（2）改变处理器数量，使其分别为4、8、12、16、20，其它参数不变，各算法的性能如图7、图8所示。

从对比图可以看出，与其它任务调度算法相比，WPTS算法更具有性能优势，其原因在于新算法充分利用处理器上的空闲时间调度任务，并及时对产生的冗余任务进行处理，提前后继任务的最早开始时间，因此取得了更好的调度性能。

（3）CCR取值分别为0.1，0.5，1.0，5.0，10.0，其它参数值不变，各算法的性能测试结果如图9、图10所示。

从对比图可以看出，CCR不同时，因为WPTS算法对冗余任务有较好的处理，因此较其它3种算法取得了更好的性能。

根据这两组测试结果，可以看出WPTS算法要优于CPFD、HCPFD和HDEFT算法，随着任务规模的增大，WPTS算法的优势越明显。

4 结束语

通过深入分析目前异构多核处理器任务调度算法存在的不足，提出了WPTS算法。WPTS算法使用加权值weight标记任务的优先级，新优先级计算方法克服了优先级选取单一带来的问题，能更准确地反映任务在DAG图中的位置和属性；在任务到处理器的映射阶段及时消除任务调度中产生的冗余任务，提前后续任务的最早开始执行时间。实验结果表明，新算法能取得最优调度的比例为71.53%，且在DAG形状、处理器数量和CCR不同时较已有算法均能取得更好的性能。

［1］JIANG Wen.Research of task scheduling algorithms for heterogeneous computing environment［D］.Hunan：Master’s Graduation Thesis of Hunan University，2010：9－25（in Chinese）.［江文.异构计算环境下任务调度算法的研究［D］.湖南：湖南大学硕士学位论文，2010：9－25.］

［2］Ahmad Ishfaq，Ranka Sanjay，Khan Samee Ullah.Using game theory for scheduling tasks on multi－core processors for simultaneous optimization of performance and energy［J］.IEEE International Symposium on Parallel and Distributed Processing，2008：2645－2650.

［3］WU Jiajun.Research on task scheduling technology based on heterogeneous multi－core and multi－threaded processors［D］.Anhui：Doctor’s Graduation Thesis of Institute of Computing Technology Chinese Academy of Sciences，2006：4－17（in Chinese）.［吴佳骏.多核多线程处理器上任务调度技术研究［D］.安徽：中国科学院计算技术研究所博士学位论文，2006：4－17.］

［4］Laura De Giusti，Emilio Luque，Franco Chichizola.AMTHA：An algorithm for automatically mapping tasks to processors in heterogeneous multiprocessor architectures［C］／／World Congress on Computer Science and Information Engineering，2009：481－485.

［5］Mohammad I Daoud，Nawwaf Kharma.A high performance algorithm for static task scheduling in heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2008，68（4）：399－409.

［6］Sah S K，Singh R S.Critical path based scheduling of multiple applications in heterogeneous distributed computing［C］／／IEEE International Advance Computing Conference，2009：99－104.

［7］Hagras T，Janecek.A high performance，low complexity algorithm for compile－time task scheduling in heterogeneous system［J］.Parallel Computing，2005，31（7）：653－670.

［8］JIANG Yunlian.Task Scheduling in parallel heterogeneous systems［D］.Anhui：Master’s Graduation thesis of University of Science and Technology of China，2006：22－43（in Chinese）.［蒋韵联.并行异构系统任务调度问题研究［D］.安徽：中国科学技术大学硕士学位论文，2006：22－43.］

［9］ZHANG Jianjun，SONG Yexin，HUANG Dengbin.Task scheduling algorithm for Fork－Join task graphs in heterogeneous environment［J］.Computer Engineering and Design，2010，31（3）：486－489（in Chinese）.［张建军，宋业新，黄登斌.异构环境中Fork－Join任务图的调度算法［J］.计算机工程与设计，2010，31（3）：486－489.］

［10］Young Choon Lee，Albert Y Zomaya.A novel state transition method for metaheuristic－based scheduling in heterogeneous computing systems［J］.IEEE Trans on Parallel and Distributed Systems，2008，19（9）：1215－1223.

［11］Matthieu Gallet，Loris Marchal.Efficient scheduling of task graph collections on heterogeneous resources［C］／／International Parallel and Distributed Processing Symposium，2009：1－11.