基于异构多核机群系统的任务调度算法研究

2016-07-10 08:07李霞
电子技术与软件工程 2016年8期
关键词:机群任务调度

李霞

摘 要:针对多核机器构成的异构机群系统,充分利用多核机器并行性及处理核心共享二级缓存的特点,提出基于DAG图的相关任务调度算法,该算法通过三个阶段完成任务的分配及调度过程,通过对相应任务的复制减少各处理节点之间的通信开销,提升任务调度的效率和减少任务调度的长度。

【关键词】任务调度 DAG 多核 机群

近年来,单芯片多核心处理器(Chip Multi-core Processors,CMP)体系结构在计算机硬件领域已经处于主导地位,在理论上通过增加多个处理核心以减少单个处理芯片由于主频过高带来的散热问题,然而针对多核机器构成的机群系统上的任务调度算法尚未成熟,如果直接把传统的任务调度的算法直接移植到此类系统中,则不能很好的发挥多核机器的多个处理核心可以并行执行的优势,因此,多核机器的任务调度作为影响系统性能的重要因素成为近些年来系统结构方向的热点研究问题之一。

通过实践的检验,人们发现目前最有发展前景的任务调度技术是先用启发式调度算法对任务进行分组,分组之后再采用遗传算法对任务单独进行调度。基于这种思想,本文提出了基于异构多核机群系统的相关任务调度算法。

任务调度是一类非常重要的组合优化问题,除了一些假设的简单的调度模型外,大多数相关任务的调度是一个NP完全问题。目前很多研究学者提出了多种算法,包括各种启发式算法、遗传算法及其混合算法等,而启发式算法则目前认为是寻求NP完全问题的接近最优解的一种可行的方法。文献[3]中提出了一个基于迭代的启发式算法,用于对多核处理机系统中的各个处理器进行任务的分配,该算法利用多核处理器的处理核心之间通过共享二级缓存或通过高速信道的内连接进行通信,因此子任务之间的通信开销可以忽略不计,因而将通信比较频繁或通信代价比较大的子任务分配到同一个多核处理机节点上执行,这样就大大的利用了多核机器的优点,同时也减少了任务在执行的过程中由于相关任务被分配到了不同的处理机节点而带来的通信开销。但是该算法只分析了多核系统上的任务分配问题,而未考虑任务分配之后如何在多核处理机节点内的调度。

本文基于文献[2]提出的思想,并结合多核处理机本身具备的并行性能,首先将任务分配到合适的多核处理机节点,然后根据多核机器多个核心可以并行执行的特点,在单个节点内再次进行任务调度,从而将任务分配到具体的处理核心进行处理。

1 任务调度模型

假设机群系统由N个多核处理机节点(P1,P2……PN)构成,且Pi处理节点有Ci个处理核。将实际应用的任务分解成M个子任务,且假设预先已经知道每个子任务运行所需要的时间,而子任务之间的约束关系我们可以通过一个有向无环图(directed acyclic graph DAG)来表示。并且将DAG图定义为一个四元组:G={T,E,C,S},其中各个参数的含义如下所述:

T={Ti|i=1,2…,M}是顶点的集合,每个顶点用来表示一个子任务。

E={Eij|Ti,Tj∈T}是有向边的集合,边Eij表示有向边Ti->Tj,即Ti和Tj之间存在约束关系,任务Ti一定要在任务Tj前执行。

C={C1,C2,…,CM}是一个M维的向量,其中Ci>0表示任务Ti运行时所花费的时间。

S是表示通信矩阵,对于任务图中任意边(Ti,Tj)∈E,S(Ti,Tj)表示子任务Ti和Tj之间的通信开销。如果两个任务被分配到同一个处理机节点上,则他们之间的通信时间可以忽略,用0表示。

如图1是包含有十一个子任务的DAG图,其中用T1、T2……、T11表示分解后的子任务,节点之间的有向边则表示子任务和子任务之间的约束关系,有向边上的数字则表示该有向边的通信开销,节点中下部的数字表示该子任务执行所需的时间。

基于DAG任务图调度时追求的目标有很多,本文考虑的目标是将M个子任务调度到N个处理机节点上,以期获得最短的调度长度即总的处理时间最少。

2 算法的思想

2.1 任务分配

为了达到最短的任务调度长度,结合多核机器的性能:同一个处理器上的多个处理核心共享二级缓存,因此尽量将任务之间通信时间较长的子任务分配到同一个节点上执行,并且根据每个多核处理机节点处理能力及所分配到的子任务总的执行时长来决定子各个多核处理机节点所分配的子任务的数量。经过任务分配之后的DAG图如图2所示,原始的DAG图被分成了四个子任务群。

2.2 任务复制

在多核处理机系统中,单个多核机器节点内的多个处理核是共享二级缓存的,因此使相关联的任务尽可能的在同一个处理机节点上完成,这样就有效的降低了相关任务被分配到不同处理机节点而需要花费的通信时间,为此要进行任务的复制。任务复制主要是对分配到不同的处理机节点上的任务进行复制,通过对具有前驱后继关系的任务进行复制,将关联的任务之一从一个处理机节点复制到另一个处理机节点上去,即在不同的处理机节点上都执行该任务,以通过增加任务的计算时间来减少任务之间的通信花费。在选择复制的任务时,把所有子任务的前驱任务复制到当前处理机节点上,而对于新复制过来的子任务亦是如此,将其所有的前驱任务复制过来,直到入口节点为止。

按照如此复制的原则,四个子任务群对应的DAG图经过复制后的结果如图3所示。

2.3 任务调度

经过任务的分配及任务的复制操作之后,每个多核处理机节点上的子任务群都是互不关联的,因此一个相关任务的调度问题就转换成了多个可以并行执行的子任务群,而这些子任务群分布在不同的处理机节点上,且它们的执行不相互依赖,在执行的过程中,处理机节点之间不需要进行信息的通信。这样,对每个处理机上的子DAG图就可以采用独立的调度算法进行任务调度,本文采用文献[4]所述的遗传算法进行调度。

3 算法的实现

本文的算法由三部分组成:第一部分根据各个任务之间的关联特性将各个子任务分配给多核处理机节点;第二轮操作将处在不同处理机节点上的相关任务进行复制,使最原始的DAG图变成相互独立的多个子任务群。第三轮,将各个多核处理机节点上的子任务群再次进行调度,调度到各个处理核心上处理。

第一部分操作由迭代组成,每次选择DAG图中C(Ti,Tj)值最大的两个子任务节点,即子任务之间通信开销最大的那对节点,将选中的两个子任务节点归到同一个子DAG图中,并且它们之间的通信开销变为0,为了后面进行分配时使各个处理机节点负载均衡,同时要统计这两个被选中任务的执行时间,重复这种归集操作,直到所有的子任务节点都有归属为止。

第二部分操作进行相关任务的复制,对于具有前驱后继关系而又分布在不同处理机节点上的任务进行前驱节点的复制工作,而对于新复制过来的节点如果其前驱节点不在当前处理机上时,则仍要进行前驱的复制,直到入口节点为止,并且在进行任务复制的同时叠加复制过来的任务的执行时间。经过该轮的操作,所有的子DAG图都是互相独立的,子DAG图中的任务执行都不依赖于其他的处理机节点,即各个处理机节点可以并行执行。而对各个独立的子DAG图进行分配的时候,根据各个子任务图中任务执行时间的多少来进行多核处理机节点的选择:即子DAG图中任务执行时间总和长的分配到处理能力强的处理机节点上。

第三部分操作对各个处理机节点上的子DAG图分别使用遗传算法将各个子任务分配给多核处理机节点的内核进行处理。本文采用文献[4]所述的遗传算法进行节点内任务的调度,步骤在此省略。

4 结束语

对于多核异构机群系统,本文充分利用多核机器多个处理核心共享二级缓存的特性,针对基于DAG图的相关任务的调度问题,采用三个阶段分别进行任务的分配、复制以及调度,在任务的分配阶段利用多核机器共享二级缓存的特性减少相关任务之间的通信开销;任务的复制阶段使相关的任务变成可以并行执行的多个子任务群,然后根据各个处理机节点的处理能力的不同进行子任务群的分配;而在多核处理机节点内采用现有的遗传算法对各个子任务群进行调度,从而分配到具体的处理核心进行处理。

参考文献

[1]Laurea De Giusti,EmilioLuque,FrancoChichizola.AMTHA:An algorithm for automatically mapping tasks to processors in heterogeneous multiprocessor architectures[C]//World Congress.

[2]吴佳骏.多核多线程处理器上任务调度技术研究[D].北京:中国科学院,2006.

[3]LIU YI,ZHANGXIN,LIHE,etal.Allocatingtasksinmulti-core processorbasedparallelsystem[C].Proceedingsofthe2007IFIPInternationalConferenceonNetworkandParallelComputingWorkshops.WashingtonDC:IEEEComputerSociety,2007:748 -753.

[4]HOUESH,ANSARIN,RENH.Ageneticalgorithmformultiprocessorscheduling[J].IEEETransactionsonParallelandDistributed Systems,1994,5(2):113-120.

作者单位

广西财经学院防城港学院 广西壮族自治区防城港市 538000

猜你喜欢
机群任务调度
基于PEPA的云计算任务调度性能分析
基于改进NSGA-Ⅱ算法的协同制造任务调度研究
基于时间负载均衡蚁群算法的云任务调度优化
施工机群配置优化研究综述
施工机群配置优化研究综述
广东省机群吊桶洒水灭火技术发展与应用①
基于小生境遗传算法的相控阵雷达任务调度
基于多核机群的Petri网系统并行化模型的研究
云计算环境中任务调度策略
云计算中基于进化算法的任务调度策略