一种基于异构系统的实时调度算法研究

郑小长,杨红和

(1.闽南师范大学 信息与网络中心，福建 漳州，363000；2.闽南师范大学 教务处，福建 漳州，363000)



一种基于异构系统的实时调度算法研究

郑小长1,杨红和2

(1.闽南师范大学 信息与网络中心，福建 漳州，363000；2.闽南师范大学 教务处，福建 漳州，363000)

高效调度是异构系统中实现高性能计算的关键.调度问题已经被证明是NP完全问题，由于其关键性，调度问题已经被国内外研究机构广泛研究，并提出了多种算法.尽管在一些文献中提出了异构多处理器的调度算法，但是这些算法的调度成本较高，并且在较低的调度成本下无法提供高质量的调度.本文提出一种最小评分优先算法(HMSF)，该算法是一种适用于异构系统的高性能、快速调度算法，通过和传统的HEFT算法和DLS算法进行试验对比发现，HMSF算法可以使调度长度更短.

异构系统；实时调度；DAG调度；任务图；调度长度

异构计算系统是一种通过高速网络将异构计算资源连接到一起的计算平台，可以对计算密集型的并行和分布式应用提供支持[1].异构计算系统在执行应用程序时需要编译时和运行时两种方式的支持.对于应用，对可用资源的有效调度是实现高性能的关键因素.

传统的任务调度问题包括如何将程序分配到处理器上和如何对任务执行顺序进行排序.一个程序可以通过静态模型来表示，模型中的元素包括任务的运行时间、任务间通信的数据量和任务之间的依赖关系等等[2-4].在传统形式的静态调度问题中，可以使用有向无环图(DAG)来表示一个应用，其中节点代表应用程序中的任务，边代表任务间的数据依赖关系.每个节点上标识了该任务的计算时间消耗情况，边上标识了任务之间的数据通信消耗[4].该问题的研究目标是将任务映射到处理器上，并且对他们的运行进行排序，从而实现在满足任务优先级的前提下，获得总的最小的完成时间.任务调度问题通常被认为是NP完全问题[5].

近年来，国内外学者对任务调度问题进行了充分的研究，并提出了如静态任务调度算法、启发式算法、列表调度算法、聚类启发式算法、任务复制启发式算法、遗传算法和随机引导搜索算法等方法[6-8].本文提出了一种静态调度方法：最小评分优先算法，尽管异构系统的静态调度都是离线调度，但是为了使调度方案更贴近实际，人们通常把算法的调度长度(调度总时间)作为考量算法性能优劣的关键约束条件.因此本文提出的算法的动机是为了在保证高质量调度的同时，尽量降低调度算法的资源消耗.

本文其余部分按如下组织：第2节主要描述了本文对异构系统任务调度的理解，将任务调度抽象成数学模型，使用有向无环图来表示任务集合，并给出一个异构系统多任务调度的实例；在第3节中，详细描述了最小评分优先算法的计算过程，并给出第2节中给出的任务集合的调度方案；第4节通过仿真试验将多种不同调度算法进行对比，通过比较试验数据来分析最小评分优先算法的有效性、合理性和优越性；在文章的最后，给出了全文的总结.

1 任务调度模型

任务调度模型由一个三元组表示.M=，其中G为应用任务图、Q为目标系统、W为性能要求.应用任务图是一个有向无环图G=(V,E)，其中V代表任务v的集合、E代表任务之间的边e的集合.在任务图中没有父节点的任务叫做入口任务，没有子节点的任务叫做出口任务.假设目标系统由一组异构处理器集合Q组成，集合Q中的q个异构处理器相互连接成拓扑结构.在该模型中，计算时间包含通信消耗时间，并假定所有任务都是非抢占的.w是一个vXq的计算消耗矩阵，wi,j为任务ni在处理器Pj上的运行时间预估值.在调度之前，所有任务使用平均运行时间来标识.

任务ni的平均运行时间定义该任务在所有处理器上运行时间的总和除以q.

任务ni和任务nk的通信消耗定义为

其中，Tbuild代表处理器启动并建立通信所消耗的时间，S用于存储不同处理器之间的数据传输速率，datai,k是任务ni向任务nk发送的数据量.如果任务ni和任务nk在用一个处理器上执行，在这两个任务之间没有通信消耗，则ci,k的值为0.

平均通信消耗时间定义为

EST(ni,pj)为任务ni在处理器pj运行的最早开始时间，EFT(ni,pj)为任务ni在处理器pj运行的最早结束时间.对于入口任务nentry，

EST(nentry,Pj)=0.

在计算任务ni的EFT之前，该任务的所有前序任务必须全部调度完毕，即

EST(ni,pj)=max{avail[j],maxnm∈pred(nj)

(AFT(nm)+cm,i)},

EFT(ni,pj)=wi,j+EST(ni,pj),

其中，pred(ni)是任务的前序任务集合，avail[j]是处理器Pj的最早可用时间.如果任务ni是处理器pj执行的最后一个任务，那么avail[j]就是处理器pj执行完任务ni的时间.

当任务nm被调度到处理器pj上运行之后，EST(nm,pj)和该任务的实际开始时间AST(nm)相同，EFT(nm,pj)和该任务的实际结束时间AFT(nm)相同.当任务图中的所有任务都调度完成之后，调度完成时间为出口任务nexit的实际结束时间.

图1是一个经典的异构系统执行多任务的案例，该案例中共有10个任务，n1是入口任务，n10是出口任务，该异构系统由两个异构处理器组成，表1展示了不同任务在不同处理器下的计算消耗.

图1 任务图Fig.1 Task graph

表1 任务计算消耗图Table 1 task calculation consumption graph

2 任务调度算法

本文提出了一种基于优先级评分的最小评分优先算法(HMSF).HMSF(Heterogeneous-Minimal-Score-First)算法包含两个阶段：任务选择阶段和处理器选择阶段.

HMSF算法的第一个阶段是任务选择阶段.在任务选择阶段中，算法根据任务ni的平均计算量和平均通信消耗计算出任务的优先级评分sni，并对优先级sni进行降序排序.sni的计算方法为

HMSF算法的第二个阶段是处理器选择阶段.对于大多数的任务调度算法，一个处理器的最早可用时间是该处理器所处理的上一个任务的截止时间.HMSF算法采用与常规方法相同的处理方法，当处理器处于空闲时，就可以从就绪任务列表中按照任务选择阶段的方法挑选一个待调度的任务，分配给空闲的处理器.当同时存在多个空闲处理器时，对于已选择出的任务，找到执行该任务运行时间最短的处理器，将该任务分配到该处理器上，从而实现整体性能的最优化.

HMSF算法的详细描述如下:

1)为每个任务预估计算时间消耗和任务间通信时间消耗；

2)从出口任务向上递归遍历任务图，为所有任务计算优先级评分；

3)对调度列表中的任务集合按照优先级评分降序的顺序排序；

4)对于每个为调度的任务进行如下操作：

a)从任务列表中选取任务ni；

b)对于处理器集合中的每个处理器pj进行如下操作：计算任务ni在处理器pj上的最早结束时间EST(ni,pj)；

c)将任务ni分配到处理器pj上，使得任务ni的最早结束时间EST(ni,pj)最小.

对于图1中的案例，使用HMSF算法的计算过程图表2所示，算法将得到如图2所示的调度方案.

表2 优先级得分表Table 2 Priority score table

图2 调度方案Fig.2 Scheduling scheme

图2的调度方案展示的调度方案为：

(1)选择任务1分配给处理器P2，运行时间区间为[0,9]；

(2)选择任务3分配给处理器P1，运行时间区间为[9,16]；

(3)选择任务2分配给处理器P2，运行时间区间为[9,27]；

(4)选择任务4分配给处理器P1，运行时间区间为[16,32]；

(5)选择任务6分配给处理器P2，运行时间区间为[27,41]；

(6)选择任务7分配给处理器P1，运行时间区间为[32,45]；

(7)选择任务5分配给处理器P2，运行时间区间为[41,63]；

(8)选择任务8分配给处理器P1，运行时间区间为[63,76]；

(9)选择任务9分配给处理器P2，运行时间区间为[63,77]；

(10)选择任务10分配给处理器P1，运行时间区间为[77,94].

任务集合在该异构系统的调度长度为94，处理器占用率为76%.

3 仿真试验

在本节中，我们通过使用几种不同的调度算法来调度同一组任务图来对比调度算法的性能.调度长度是考核异构系统调度算法最重要的指标之一，调度长度的长短可以有效的衡量出调度算法调度结果的好坏程度.本文通过使用随机图形生成系统，随机生成出3550个不同参数属性的加强有向无环图作为任务集合，并针对每个任务集合随机生成了异构系统计算消耗表，其中任务数量为{10,20,30,40,50,60,70,80,90,100}，处理器数量都是4.针对每个任务集合和其对应的计算消耗表，本文选取了HEFT算法[6]、DLS算法[8]和HMSF算法进行比较，比较结果如图3所示.

图3 调度算法对比结果Fig.3 Comparison of scheduling algorithms

图3中展示了任务数量从10个增加到100个的过程中，不同算法调度长度增长的态势.从图3中我们可以看出，随着任务数量的增长，各算法的调度长度不断增加，但HMSF算法的调度长度相对更短，从实验结果可以看出，HMSF算法的调度效率更高.

4 结语

本文提出了一种基于优先级评分的最小评分有限算法(HMSF)，该算法用于对异构系统中的任务集合进行合理调度.通过对大量随机生成的任务图进行试验、对比和分析发现，HMSF算法的调度长度明显比其他算法短，调度效率更高.在未来的工作中，我们将对不同算法的调度质量进行更深入的调查和分析，同时我们计划对HMSF算法进行扩展，实现对任务进行重新调度以应对处理负载和网络负载的变化情况.

[1]RITCHIE G,LEVINE J.A fast effective local search for scheduling independent jobs in heterogeneous computing environments[C]//G Hay ward.Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group.Glasgow,UK:Journal of Computer Applications,2003:178-183.

[2]支青,蒋昌俊.一种适于异构环境的任务调度算法[J].自动化学报,2005,31(6):835-872.

[3]IBARRA O H.Heuristic algorithms for scheduling independent tasks on non-identical processors[J].Journal of the ACM,1997,24(2):280-289.

[4]YEN TY,WOLF W.Hardware/Software Co-Synthesis of Distrubuted Embedded System[M].Netherlands:Kluwer Academic Publishers,1996.

[5]KWOK YK,AHMAD I.Dynamic critical-path scheduling:An effective technique for allocation task graphs to multiprocessors[J].IEEE Trans.On Parallel and Distributed Systems,1996,7(5):506-521.

[6]TOPCUOGLU H,HARIRI S,WU MY.Performance-Effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Trans.On Parallel andDis ributed Systems,2002,13(3):260-274.

[7]冯国富,董小社.面向Cell宽带引擎架构的异构多核访存技术[J].西安交通大学学报,2009,43(2):1-5.

[8]SIH GC,LEE EA.A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures[J].IEEE Trans.On Parallel and Distributed Systems,1993,4(2):175-186.

Real-time scheduling algorithm based on heterogeneous systems

ZHENG Xiaochang1,YANG Honghe2

(1.Information and Network Center,Minnan Normal University,Zhangzhou 363000，China;2.Office of Educational Administration,Minnan Normal University,Zhangzhou 363000,China)

Efficient scheduling is the key to high performance computing in heterogeneous system.The scheduling problem has been proved to be NP-complete problem.Because of its significance,it has been studied extensively in research institutes at home and abroad,and a variety of algorithms have been put forward.Despite the fact that some scheduling algorithms of heterogeneous multi-core processor are proposed in some literatures,the scheduling cost of these algorithms is high and high-quality scheduling is not to be achieved at low cost of scheduling.In this paper,a minimum score priority algorithm (HMSF) is proposed.The algorithm is applicable in heterogeneous system with the advantage of high performance and speed.The HMSF can shorten the scheduling length,which is found in comparison tests between traditional heft algorithm and DLS algorithms.

heterogeneous systems; real-time scheduling ; DAG scheduling; task graph; scheduling length

1672-7010(2016)02-0036-05

2016-03-17

闽南师范大学教学改革项目(JG201542)

郑小长(1977-)，男，福建漳州人，硕士，讲师，从事云计算、软件工程研究；E-mail:53388110@qq.com

TP302

A