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

基于异构多核机群系统任务调度算法研究 　　摘 要：针对多核机器构成的异构机群系统，充分利用多核机器并行性及处理核心共享二级缓存的特点，提出基于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维的向量，其中Ci0表示任务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 任务复制 　　在多核处理机系统中，单个多核机器节点内的多个处理核是共享二级缓存的，因此使相关联的任务尽可能的在同一个处理机节点上完成，这样就有效的降低了相关任务被分配到不同处理机节点而需要花费的通信时间，为此要进行任务的复制。任务复制主要是对分配到不同的处理机节点上的任务进行