晋高成，李丕丁

（上海理工大学医疗器械与食品学院，上海 200093）

0 引言

随着网络和通信技术的飞速发展，各式各样的电子设备已广泛应用于人们的日常生活、工作及生产等方面。近年来，机器学习、人工智能、无人驾驶等研究不断深入，使得人们对CPU 计算速度的要求不断提升［1］。然而，单核处理器一般通过提高处理器的主频以提升处理器运算速度，该方法导致处理器功耗不断提升，进而导致处理器工作温度相应升高［2］。在需求和传统处理器性能矛盾日益尖锐的情况下，多核处理器应运而生［3］。在主频不变的前提下，双核处理器的运行速度在理论上是单核处理器的1 倍，这意味着在相同时间内，双核处理器可以做单核处理器两倍的计算量，极大增加了处理器运行速率。并且，在单核处理器和双核处理器达到相同性能时，双核处理器的主频甚至比单核处理的功耗低一半以上。多核处理器在性能和功耗上都比单核处理器表现更好，因此，越来越多的研究集中在多核处理器上［4］。

多核处理器又分为异构多核处理器和同构多核处理器。在同构处理器中，所有处理器核结构一致、功能相同、地位均等，相同程序在各处理器核上单独运行所用的时间都相等［5］。正是由于以上特点，同构多核处理器在运行应用程序时并不能发挥最佳性能。每个处理器核的处理性能都相同，并不能为不同计算要求的应用程序提供更快的计算速度。异构多核处理器由多个不同类型的处理器核心构成，每个核心结构不同、功能也不同，针对某类运算具有较快处理速度，且每个核心都具有其擅长的功能［6］。如某个核心擅长浮点计算，另一个核心擅长任务切换。当处理某个含有多种计算要求的应用程序时，异构多核处理器往往比同构处理器表现得更好。尽管异构多核处理器比同构多核处理器在很多方面都表现得更好，但是异构多核处理器核心在结构和功能上都不相同，给硬件和软件设计带来了更多挑战。目前，针对异构多核处理器的硬件和软件相关研究较多，高效的调度算法是研究重点，它能及时将任务分配到特定的处理器核心上，体现出异构多核处理器的性能优势。本文主要介绍基于异构多核的任务调度算法，与已有调度算法进行对比，并分析优缺点。

1 异构多核任务调度研究现状

1.1 国外现状

静态启发式表调度算法HEFT（Heterogeneous Earliest Finish Time）与CPOP（Critical Path on a Processor）算法是由Topcuoglu 等［7］提出的两种异构环境下的多核任务调度算法。其中，HEFT 算法是针对异构多核数量有限情况下的任务调度算法，该算法分为两个阶段，分别为任务优先级排序和任务分配阶段。在第1 阶段，对于所有任务优先级，主要根据任务的向上排序进行计算；在第2 阶段，调度器会根据在第1 阶段计算的优先级，按照非递增顺序为各任务选择合适的处理器核，在该阶段还会采取区间插入技术，以减少任务间的通信时间。相比于HEFT 算法，CPOP算法在优先级计算上采取了不同的算法，它将任务的向上排序值和向下排序值作为任务优先级，计算出优先级后再将优先级最高的任务到出口节点的路径作为整个任务的关键路径。在任务分配阶段，CPOP 会将关键路径上的任务映射到同一处理器核上，剩下的节点按照最早完成时间进行映射。

在考虑减少任务调度长度的同时，也需关注异构处理器的能耗问题。Maurya 等［8］提出一种基于能耗感知的异构多核，该算法主要是以较少的高优先级任务通信时间降低总任务调度能耗。此外，有一种结合动态电压调节技术和关键路径的调度算法，不仅可减少调度长度，还能降低能耗，由Baskiyar 等［9］提出。也有较多在HEFT 算法基础上的改进算法，如Lookahead 算法［10］。

随着对智能调度算法研究的不断深入，研究者开始将目光聚焦于遗传算法［11-13］、蚁群算法［14-15］、模拟退火算法［16-17］等。

1.2 国内现状

国内对于异构多核任务调度算法的研究要晚于国外，但也取得一系列成果。谭文安等［18］提出一种带极值扰动的相关性粒子群优化算法EDCPSO（Extremum Disturbed Correlative Particle Swarm Optimization）；石 威 等［19］结 合MCP 算法和EFT 算法，提出一种动态的表调度算法。该算法不仅考虑到关键路径节点，也考虑了非关键节点，对Makesapn 影响最大的可运行任务赋予最高优先级，极大减少异构多核上的任务调度长度，提升异构多核处理器性能；徐远超等［20］实现了一种可在Linux 中运行的能进行感知的异构多核调度算法。该算法在保证各处理器利用效率达到动态平衡的基础上，减少其它处理器核心空闲时间，且算法时间复杂度低，在负载均衡时能够进行感知。

2 3 种异构多核任务调度算法

2.1 ICPOP 算法

传统的CPOP 算法虽然在一定程度上减少了任务调度时间，但依然存在许多不足。CPOP 算法首先根据任务优先级形成任务列表（基于异构多核的混合式任务调度算法研究），然后将任务分配到处理器核上。但是优先权仅仅分配了关键任务，任务之间的依赖和约束关系并没有被充分考虑进去。在这种情况下，如果关键任务的父任务并没有及时被分配运行，则关键任务的运行时间将被延后，这样会对任务的总完成时间产生不利影响。并且，CPOP 算法会将所有关键任务分配到同一个处理器核，虽然该方法可以减少这些关键任务之间的通信开销，并且可以让这些任务具有最早完成时间，但是该方法会造成不同处理器之间负载的不均衡，导致许多处理器核在某个核心过于忙碌时处于空闲状态，使得处理器核心利用不充分。针对以上不足，本文提出一种基于CPOP 的改进算法ICPOP（Im⁃provedCritical Path on a Processor）。

ICPOP 算法在整体上与CPOP 算法一样，总共分为两个阶段：任务优先级计算阶段和处理器核分配阶段。

Fig.1 Priority calculation process图1 优先级计算流程

任务优先级计算阶段：ICPOP 算法的优先级计算流程如图1 所示。在该阶段之前，要先将DAG（Directed Acy⁃clic Graph）标准化。一个标准的DAG 仅仅包含一个入口任务和一个出口任务，入口任务是父任务集合为空的节点，出口任务是子任务集合为空的节点。为了构建一个标准的DAG，就需要保证该DAG 中只含有一个入口任务和一个出口任务。因此，要使原DAG 中所有父任务集合为空的点添加一个父任务集合为空的节点，并让它成为之前父任务集合为空的节点的父节点。同理，对于所有子任务集合为空的节点，添加一个子任务集合为空的节点，并让其成为上述节点的子节点，这样便可以构建一个标准的DAG。

对于异构多核处理器，出口任务完成时间就是整个任务调度完成时间。计算任务优先级时，需将最高优先级赋予拥有最长路径的关键任务，这样可尽量保证完成时间最短。对于非关键任务，出口任务的父任务及其父任务的完成时间影响出口任务开始执行时间，故若某任务到出口任务的开销（计算开销及通信开销）越大，则该任务越需要提前执行，因此赋予该任务较高的优先级，以此缩短整个SAG 完成时间。然而，同一任务在不同处理器核心上计算开销不同，计算差异较大的任务分配较高优先权，以提升其获得开销最小处理器核的概率。综上所述，在计算任务优先级时，需计算出每个任务到出口任务的总开销ε(Ni)以及当前任务在不同处理器核上的计算开销差异σ(Ni)，计算方法如式（1）所示。

从当前任务Ni到出口任务的总开销ε(Ni)计算公式如式（2）所示。其中,child(Ni)表示任务Ni的后继任务集合。

由于异构多核处理器各处理器核之间的计算速率各不相同，在计算优先级时要计算任务在不同处理器核上的开销差异，计算开销差异用σ(Ni)表示，σ(Ni)的计算公式如式（3）所示。

在式（3）中，P 表示处理器核的数目，k 表示处理器序号。计算完任务优先级后再根据计算出的优先级按照非递增顺序对任务进行排序，以构建任务调度列表。

处理器核分配阶段：经历上述阶段后，得到已经排序好的调度列表，再利用区间插入技术对任务进行分配。不断选取任务调度列表中优先级最高的任务，然后将其放置在开始时间最接近的处理器核上执行，重复上述操作，直到调度列表为空。处理器核分配流程如图2 所示。在上述方法中，使用区间插入技术，该技术指将任务插入到同一处理器核心上两个任务之间的空闲时间space，但是不能破坏任务之间的前驱后继关系，必须满足式（4）的任务才可采用区间插入技术。

在式（4）中，st（space）表示空闲区间开始时间，space_length 表示空闲区间大小，用st（Ni，pk）表示任务Ni在处理器核pk上的开始执行时间，WO(Ni,pk)表示任务Ni在处理器核pk上的所有开销。

为了比较ICPOP 算法和CPOP 算法性能，设置不同的任务节点数以及不同的异构多核处理器，分别采用ICPOP算法和CPOP 算法进行对比实验，比较在不同DAG 下的完成时间长短，结果如图3 所示。

从图3 可以看出，ICPOP 算法在大多数情况下比CPOP 算法减少了任务调度完成时间，ICPOP 算法获得的任务调度长度更短。同时，在任务节点为50，核心数为2时，CPOP 算法比ICPOP 算法更加高效。

Fig.2 Processor core allocation process图2 处理器核分配流程

Fig.3 Completion time of ICPOP algorithm and CPOP algorithm图3 ICPOP 算法与CPOP 算法完成时间

2.2 智能蚁群调度算法

随着并行执行模型的发展和完善，文献［6］提出Code⁃let 模型，该模型是一种事件驱动的、细粒度的、混合控制流的并行执行模型。

该算法针对异构多核的Codelet 计算环境，结合HEFT算法和蚁群算法，提出一种智能蚁群调度策略（Samrt Ant Colony Task Scheduling）。该算法执行流程如图4 所示。

如图4 所示，该算法首先输入CDG、数据传输时间开销C 以及人物执行开销ETC，然后根据HEFT 算法计算每个节点的静态优先级Rank，蚂蚁从Codelet 节点开始出发，依照动态状态转移规则选择下一个调度的Codelet 节点，再将该节点分配给最早时间空闲的处理器核，开始执行该节点，跟新动态因子，重复上述步骤，直到调度达到最大迭代次数。该算法的参数和初始化值如表1 所示。

Fig.4 Scheduling strategy of ant colony optimization图4 智能蚁群调度策略算法流程

Table 1 Parameters and initialization values表1 参数与初始化值

该算法中每个节点的静态优先级可以采用ICPOP 算法中的优先级计算方法，计算每个节点的静态优先级。该算法中蚂蚁通过状态转移规则决定下一个COdelet 任务，该动态规则由式（5）计算得出。

其中，τ（i，w）为（i，w）边上的信息素强度，该值越大，该节点被选择的概率越大。该算法通过调整动态因子q0控制收敛速度，q0越小，蚁群选择的多样性越好。q0由式（6）计算得出。

在构造解的过程中，每个蚂蚁都会对自己选择的边更新局部信息素。该做法的目的在于防止完成一次迭代后，其它蚂蚁会得到同样的解。因此，需不断更新对应的信息素τ（t，n），更新公式如式（7）所示。

该算法运行结果如图5 所示。其中，Robot 拥有88 个节点，Sparse 有96 个节点，Fpppp 有334 个节点。Static 为静态调度策略，Dynamic 为原生动态导读策略，SACTS 为智能蚁群调度策略。可以看出，在解决大规模任务调度问题时，智能蚁群调度策略比原生动态调度和静态调度策略拥有更高效率，并缩短了任务执行时间。

Fig.5 The result of ant colony optimization图5 智能蚁群算法运行结果

2.3 一种启发式综合任务调度算法

IHTSGMP（Integrated Heuristic Task Scheduling Algo⁃rithm for Heterogeneous Multicore Processer）算法以表调度算法为基础，首先构建任务调度优先级，根据优先级构造调度列表。在调度过程中采取任务复制技术，再将各任务节点分配到处理器核上执行，提升处理器利用效率，可分为优先级计算阶段和任务分配阶段。

优先级计算阶段：在该阶段开始时，需根据现有任务节点，构建一个DAG，表示任务执行和依赖关系。计算优先级的方法大致类似，都是根据关键路径法，首先需找到关键路径节点最高优先级。对于其它节点，IHTSHMP 算法的优先级由式（8）计算得出。

其中，weighti表示节点i的优先级权值，ncp表示当前任务节点的直接后继关键路径节点。cp_value(ni)的定义如式（9）所示。

任务分配阶段：IHTSHMP 算法采用任务复制以及区间插入方法。首先选择最早完成任务的处理器内核，然后根据第一阶段计算出的优先级，选择优先级最好的节点，再分别计算该节点在被选择的核心上采用和不采用任务复制技术的最早完成时间，选择最早完成时间最短的方案。任务复制流程如图6 所示。

Fig.6 The process of task copy图6 任务复制流程

其中，est(ni,pu)和est2(ni,pu)分别为不采用任务复制和采用任务复制的最早完成时间。在任务复制策略基础上，采用在ICPOP 算法中叙述的区间插入技术，进一步提升处理器利用效率。

该算法运行效果如图7 和图8 所示。该实验对比了前驱复制算法CPFD（Critical Path Fast Duplication）［21］和选择性任务复制的表调度算法STDH（Selected Task Duplica⁃tion for Heterogenous System）［22］。可以看出，相比于CPFD算法和STDH 算法，IHTSHMP 算法在不同任务数下都保持着较高调度效率。

Fig.7 Comparison of average speedups of different tasks图7 不同任务数下的平均加速比对比

Fig.8 Comparison of average accelerations with different CCRs图8 不同CCR 下的平均加速比对比

3 调度算法总结

ICPOP 算法在优先级计算和处理器核分配上对CPOP算法作出改进。在任务优先级计算时，不仅考虑了当前任务到出口任务的开销，还计算了此任务在不同处理器核上的计算开销差值，相对于CPOP 算法，保证差值大的任务节点可以被优先调度，缩短任务调度时间；在处理器核分配阶段，采用区间插入技术，减少处理器在任务和任务之间的缝隙，提升处理器利用效率，从而缩短任务调度长度。

智能蚁群算法结合静态启发式调度算法HEFT 和改进蚁群算法，在优先级计算阶段采用与HEFT 算法相同的优先级计算方法，随后采用蚁群算法，改进动态状态转移规则，更加有效地选取下个待运行节点。

IHTSHMP 算法是一种启发式综合任务调度算法。该算法综合任务复制算法和表调度算法。计算优先级时考虑任务拓扑图结构，进一步优化优先级计算，提升调度效率；任务分配阶段采用任务复制技术，比较复制和不复制对整体的影响，然后选择是否采取复制，该方法减少了依赖任务通信延迟，充分发挥了异构处理器的优势。

4 结语

异构多核任务调度算法的关键在于如何合理调度，使得所有任务完成所用时间最短。该问题是一个NP（Nondeterministic Polynomial Complete）问题，目前还没有一种能确保每次都可获得最优解的算法，只能是不断地逼近最优解。异构多核任务调度算法主要分为确定性算法和非确定性算法，本文提到的任务复制算法和表调度算法为确定性调度算法，蚁群调度算法为非确定性调度算法。确定性算法在任务数量少时更具优势，非确定性算法在处理大规模任务时有更早的完成时间。目前，对于确定性任务调度算法中的列表调度算法使用最为广泛，但是在处理大规模任务量时还是会采取蚁群算法、退火算法等非确定性算法。从上述算法中可以看出，未来发展趋势是将非确定性算法和确定性算法相结合，实现优势互补。