一种用于异构环境中并行任务调度的弹性节能算法

摘 要：节能调度算法设计是高性能计算领域中的一个研究热点。本文通过软件方法设计异构多核计算机的调度算法，实现系统的弹性节能，达到降低能耗并提升系统性能的目的。本文的调度策略建立在基于处理器异构的并行任务调度的环境中，构建了节能模型，提出了EAPS（Energy-aware parallel scheduling）算法模型，该算法在每一任务完成之后重新计算优先级以使优先级符合任务的实时情况，并对复制的前驱任务是否冗余任务进行判断从而避免资源的浪费，并通过调节节点电压选择能耗最少的节点进行调度，在节能与期望完成时间之间取得平衡。

关键词：异构；并行任务；节能；DAG

中图分类号：TP301.6

随着计算机体系结构的发展以及人们对于性能需求的提高，大型计算系统在计算能力大幅提高的同時，成本和体积逐渐下降，并在数据密集型领域得到了广泛应用[1]。其中，异构多核计算系统以应用程序并行化程度高及处理器功耗低等优点比同构计算系统更适合于工作中的常见应用。在计算机系统集群化越来越普遍，并且朝着高性能发展的同时，能量的消耗也逐渐增多，如何实现绿色节能已成为当前计算机系统能耗所关注的方向[2]。

现存的异构多核处理器调度算法大多采用任务复制的方法，以减少任务总体完成时间为研究目标，并没有考虑到能量消耗的问题[3]。而将同一任务复制到不同的处理器进行调度时，所耗费的时间及所消耗的能量都会因为处理器的不同而有所区别。而现在的处理器具有电压级别，可采用动态电调整技术根据任务的处理需求在执行时使用不同的电压级别，产生不同的能耗，在一定程度上可减少设备的能量消耗，缩短任务的总体执行时间，在实际工作中具有广阔的前景[4]。

1 EAPS（Energy-aware parallel scheduling）算法

本算法的假设条件有以下几点：（1）所有的资源状态确定已知，如处理器的数目、每个任务在每个处理器上运行所耗费的时间。（2）处理器之间的链路是双通高速链路，处理器可以在运行处理器上任务的同时向别的处理器传递数据。（3）任务属于非抢占式任务，在执行过程当中不可中断。任务需按事先设定好的顺序执行，即任务之间具有先后依赖性。任务在执行过程中分成若干个子任务，这些子任务需按照设定的顺序在前驱任务完成后，并且所需资源达到相应处理器后，才可开始执行，执行完毕后，也将相应的资源传递给后续子任务。（4）节点的电压具有相应的运行级别，并且可以动态调整，同一任务运行在同一节点的不同电压所耗费的能量有所不同。

下表展示的是本文中计算相关的一些变量：

本算法采用任务的最早开始时间est（ni）以及任务与出口任务之间的最长距离nlevel（ni）作为优先级的设置值。在任务的调度过程当中，选择具有最早开始时间的任务进行调度，如果有多于一个任务的最早开始时间相同，则选nlevel（ni）值较大的任务，因为这是影响调度长度的关键任务，nlevel（ni）值最大的任务的是当前所有任务中对于提前完成总任务调度具有最大影响的节点，所以需要优先进行调度。

在按照算法1生成调度列表后，开始进行处理器节点的分配。由于任务的优先值在任务的调度过程当中会有所更新，如果一直采用任务调度前设定好的优先值，会对任务的调度时间有所影响，不能进行最有效的调度，所以这里会在每一个任务调度完后重新计算任务的优先级，以使调度状态更加符合真实情况，有利于算法性能的提高。

任务确定以后进行处理器的选择。在进行处理器的选择时，考虑到节能的需要，通过对处理器电压所处级别的调整达到节能的目的。首先所有可调度的节点必然是已经处理完任务、所有资源就绪的结点，对于这些空闲结点，电压已调整至最低级别，在此基础之上，不断试探各处理器是否可以在截止期内完成任务，如不能则逐级调高电压，直至任务可在截止需求时间内完成，最后选择能耗最少的节点进行调度。如各就绪节点调至最高电压，也没有满足在截止期内完成任务的节点，则选择最高电压能耗最少的结点进行调度即可。

当然此时的处理器还没有进行实质的任务调度，只是选择了合适的处理器以及合适的电压级别进行了标记。本算法为了减少数据传递开销，缩短任务的总调度时间，借鉴了一些算法的复制思路，对于任务并行性的提高也起到了一定作用。之前许多算法虽然有复制前驱任务这一思路，但都有不足之处，或是没有对复制任务进行判断，导致复制的任务对于缩短任务的总体调度时间没有任何帮助，反而浪费了资源，或是在所有的任务调度完成以后再对复制的前驱任务进行判断是否冗余，如果冗余则删除此前驱任务，必然造成处理器结点在删除任务后又存在大量空闲时间段，浪费资源的后果，不能进行理想的任务调度、提高调度成功的概率。而本算法则是在任务调度前就先进行判断前驱任务是否有必要复制，有的话再进行调度，否则放弃复制，达到了提高任务调度率、节省资源的目的。

2 结束语

本节内容通过实验数据测试EAPS算法的有效性。这里将用异构环境类似的HNDP与HCPFD算法与EAPS算法进行比较分析。在实验过程中，针对每组实验只改变一个参数，保持其他参数值不变，这样可以更加清楚地观察到什么参数对于任务的调度影响最大，也可以比较各算法在评测指标上的变化。本节将从CCR值、处理器异构两个参数值来测评算法的性能。由图1和2可知EAPS的能耗最小，具有最好的效果。

参考文献：

[1]李新，贾智平，鞠雷等.一种面向同构集群系统的并行任务节能调度优化方法[J].计算机学报，2012（03）.

[2]朱晓敏，贺川，王建江等.异构计算系统中弹性节能调度策略研究[J].计算机学报，2012（06）.

[3]过敏意.绿色计算：内涵及趋势[J].计算机工程，2010（10）：1-7.

[4]乔颖，邹冰，方亭，王宏安，戴国忠.一种实时异构系统的集成动态调度算法[J].软件学报，2002（12）.

[5]林闯，田源，姚敏.绿色网络和绿色评价：节能机制、模型和评价[J].计算机学报，2011（04）.

[6]蒋韵联，孙广中，孙胤龙.并行异构系统中的一种高效任务调度算法[J].计算机工程，2007（06）.

作者简介：肖瑶星（1985-），女，贵州六盘水人，讲师，计算机技术硕士，研究方向：计算机网络技术。

作者单位：湖南信息学院 电子信息学院，湖南长沙 410000；湖南信息职业技术学院 计算机工程系，湖南长沙 410000

基金项目：湖南省教育厅科学研究项目（项目编号：13C649）。