众核任务映射算法研究现状与发展趋势*

吴 倩，王小航

（华南理工大学软件学院，广州 510006）

1 引言

随着计算需求的不断增长，众核系统得到广泛应用，单个芯片上集成的处理器核多达数十到数百个。在应用执行任务之前，资源管理器需按照特定算法为各个任务选择执行指令的处理器核，即分配处理器核给该应用，该过程称为任务映射，所使用的算法称为任务映射算法。任务映射直接影响芯片性能。

任务映射需考虑通信延时。任务映射直接决定运行任务的处理器核之间的距离，若将两个相互间数据通信量较大的任务映射至相距较远的处理器核，会导致通信延迟增大。所以任务映射需考虑任务间的通信距离。

任务映射需考虑系统功耗。处理器核功耗过高，容易降低处理器核的可靠性和寿命。此外，功耗过高，容易使得处理器核温度过高，增加冷却成本。

任务映射需考虑处理器核可靠性。如果在任务映射时不考虑可靠性，会导致某些处理器核的老化速度比其他处理器核快，使之成为系统可靠性瓶颈。

任务映射需考虑处理器核温度。任务映射直接影响芯片热分布，例如将高计算需求的任务映射至连续区域，在功率密度大的系统中，容易使得系统产生热点（芯片局部温度过高）。因此，在设计任务映射算法时需考虑芯片温度。

任务映射算法可从以下角度进行分类和分析：根据是否可以在线实时为应用选择处理器核对任务映射算法进行分类[1]；从应用软硬实时要求角度对任务映射算法进行比较[2]；从应用映射的处理器区域连续与否讨论映射区域对任务映射的影响[3]；从任务是否可重映射的角度讨论现有任务映射算法的优劣[4]。本文从系统架构和任务映射算法目标两个角度对现有任务映射算法进行分析。

2 任务映射算法

2.1 任务映射过程

任务映射过程如图1所示。在任务映射算法研究中，通常采用任务图（加权有向无环图）来表示一个应用，如图1(b)所示。图1(b)所示的应用有4个任务，每个任务的权重表示该任务需执行的指令数/执行时间。任务之间用有向边相连，其方向表示数据传输的方向，边的权重表示传送的数据包数量。应用开始运行前，需资源管理器按照特定算法为它的各个任务选择执行指令的处理器核，即分配处理器核给该应用，该过程称为任务映射。

图1 任务映射

2.2 任务映射算法分类

2.2.1 二维片上网络

1）优化通信的任务映射算法

应用任务间具有通信，任务映射时需考虑任务映射位置，减少处理器核间的通信距离，进而减少应用执行时间。

FATTAH等人[1]提出一种CoNA算法，该方法首先选择距离资源管理器最近、具有4个空闲邻居处理器核的处理器核(文中称为第一节点)，然后将具有最大通信量的任务映射到第一节点上，接着围绕第一节点建立连续区域以映射应用的其余任务。在CoNA算法的基础上，FATTAH等人[2]还提出了SHiC算法，该方法使用随机爬山算法来估计一个处理器核的空闲相邻处理器核数，从而快速确定最佳的第一节点。ANAGNOSTOPOULOS等人[3]针对可扩展的应用提出了一种工作负载感知的分布式框架，提高了处理器核利用率，同时减少了核间通信开销。这些方法以最小化通信距离或降低网络拥塞为目标，为应用选择连续处理器区域。

通过将任务迁移至另一个处理器核（任务重映射）可降低处理器核的通信距离。NG等人[4]提出了一个评估碎片化程度的度量指标，并基于该指标提出了一个处理器核碎片整理方案。WANG等人[5]提出了一种重新定位应用处理器区域的碎片整理算法。PATHANIZ等人[6]将碎片整理问题转换成一个可以在多项式时间内求解的问题。这些方法通过将任务重新映射来获得连续空闲区域，减少了后续应用通信开销。

优化通信的任务映射方法可降低应用通信延时和网络拥塞，但是该类方法偏向于为应用选择一个连续处理器区域。随着处理器核不断分配和释放，优化通信的任务映射算法会导致碎片化程度加重，迫使后续应用延迟执行或系统需执行碎片化整理。同时，优化通信的任务映射方法，考虑芯片功率预算，容易使系统产生热点，尤其是在功率密度大的系统中。

2）提高可靠性的任务映射算法

提高可靠性的任务映射算法可分为老化缓解算法和故障避让算法。

关于老化缓解算法，随着单芯片上集成的处理器核越来越多，芯片功率密度也不断增大、温度也迅速提升，导致器件老化和磨损速度加快，缩短了芯片使用时间。HUANG等人[7]提出了一个估计系统使用时间的可靠性模型，并基于该模型，采用模拟退火技术提出了一种感知处理器核可靠性的任务映射算法。WANG等人[8]通过对系统生命周期定量化建模，提出了一种考虑处理器核和物理链路老化程度的任务映射算法。WANG等人[9]在系统可靠性和温度阈值约束下，结合轻量级温度预测模型，提出了一种混合整数线性规划模型，确定应用调度和映射方案。上述方法可为应用选择连续区域。

关于故障避让算法，为提高处理器可靠性，降低处理器故障，部分学者关闭部分处理器以降低处理器功率密度，选择性能良好的处理器进行任务映射。关闭的处理器核被称为暗核。KAPADIA等人[10]在系统可靠性和功率限制的约束下，提出了一种任务映射算法，该方法通过考虑芯片热分布变化来确定应用的映射位置和处理器核的电压频率，从而提高应用的性能要求。KRIEBEL等人[11]在系统中集成了一组具有不同可靠性级别的处理器核，在满足功耗约束条件下，考虑应用的可靠性级别，为应用选择具有合适的可靠性级别的处理器核，进而为系统提供不同级别的保护。KAPADIA等人[12]提出了一个结合动态电压频率调整技术的资源管理框架，该框架为应用任务选择映射位置时优化系统性能和降低功耗，同时满足处理器核的可靠性约束。上述方法只是简单、机械地在功率约束下关闭系统一部分核心，而并没有明确指出关闭哪些处理器核。

3）降低功耗的任务映射算法

SHAFIQUE等人[13]提出了一种快速确定系统最佳暗核集合（关闭哪些处理器核为暗核）以及确定任务与处理器核映射的任务映射算法。HOVEIDA等人[14]提出的HCPS方法尝试在开启的集群中争取最高的处理器核利用率，从而可以关闭更多的集群以节省功耗。RAGHUNATHAN等人[14]基于排队论估计应用在异构集群的执行时间，为到达系统的应用选择最佳集群，而其他的集群保持关闭状态。BHARATHWAJ等人[15]提出在片上网络中引入加速器来加速由于处理器核关闭而不能在规定时间内完成的应用。上述算法[12-15]结合动态电压频率调整技术，使得系统在功率预算下运行。但是功率预算是在系统所有处理器核开启以及最差任务空间分布下确定的值，将系统限制在功率预算下运行的方法过于保守。

图2是8个处理器核开启并且系统达到温度阈值80℃时的芯片热分布图，实验配置是4×4的片上网络以及温度模拟器Hotspot，图2（a）所示分布的功率是53.6 W，图2（b）所示分布的功率为61.2 W。因此，任务映射时，在应用处理器区域中包含部分关闭的处理器核可以降低处理器核功率密度。MUHAMMAD等人[16]提出了一种称为PAT的任务映射算法，为应用选择一个包含暗核的处理器区域，工作处理器核和暗核间隔放置，使得系统在高于功率预算下运行。KANDURI等人[17]在PAT的基础上又提出了Adboost方法，通过利用合理分布暗核而获得的额外功率加速了计算密集型应用的执行。ANIL等人[18]提出的HCRS算法在实时计算功率的约束下，提高了集群处理器核的利用率。

图2 芯片热分布（图中色度单位为℃）

4）优化温度的任务映射算法

芯片局部或全局过热容易影响使用寿命。因此，学者们提出了以温度为优化目标的任务映射算法。

ANUP等人[19]综合考虑瞬态温度、稳态温度和处理器核温度三个因素提出了一个温度模型，并基于该模型确定了任务与处理器核的映射关系。THIDAPAT等人[20]提出了一种用于任务分配和调度的技术框架，该技术框架基于稳态温度来优化芯片的峰值温度。JUNLONG等人[21-22]考虑应用执行时间和功耗两个因素的时变特征，有效地将应用映射到处理器核上，最大程度减少了应用执行时间。

为进一步降低系统温度，学者们将任务从过热的处理器核迁移到较冷的处理器核，以减少系统热点或均衡处理器核温度。MAJED等人[23]提出了基于分析历史温度数据的热感知任务迁移机制。BAGHER等人[24]提出了一种基于处理器核热行为的任务调度和任务迁移算法。YOUNG等人[25]提出了一种异构多核处理器的迁移算法，将应用迁移到小核，以便大核可以快速冷却。

研究学者利用工作处理器核和暗核之间的温度梯度均衡处理器核温度。HANWOONG等人[26]利用指令级并行和线程级并行特性，提出了一种热约束下的资源分配策略，可有效地确定工作处理器核和暗核数目。HANWOONG等人[27]提出了将暗核放置在工作处理器核周围的模式资源映射方法，通过暗核和工作处理器核交错分布的方式确定暗核位置。文献[25-26]提出的方法是针对已知应用的，具有局限性。文献[25，27-31]是在系统暗核数量固定的假设下设计的，事实上，暗核数会因为工作负载而不断发生变化。

2.2.2 三维集成片上网络

1）优化通信的任务映射算法

相比于二维片上网络，在三维片上网络中，位于不同层的处理器核距离底层散热器的距离不同，这直接导致了位于不同层的处理器核散热能力不同。在三维片上网络中，应用处理器区域垂直方向层数影响应用通信延时，例如在处理器核数目相等的条件下，处理器核均在同一层的处理器区域的平均通信延时会比垂直方向多层的处理器区域的高。因此，任务映射算法应考虑架构特性。

DING等人[32]提出了考虑层间和层内通信的任务映射算法。MANNA等人[33]提出了基于线性规划和粒子群优化算法的任务映射机制。JHA等人[34]提出的任务迁移算法可减少两个任务之间的通信跳数。该类算法以最小化处理器核间的通信距离为目标；只考虑通信一个因素，将任务映射至连续处理器区域，容易使系统产生热点。

2）降低功耗的任务映射算法

AGYEMAN等人[35]针对异构三维集成片上网络，提出了降低功耗和提升系统性能的任务映射算法。ELMILIGI[36]实现了使用遗传算法搜索任务的映射位置。王源等人[37]针对非规则的三维集成片上网络，提出了考虑系统通信功耗的任务映射方法，并设计了基于在线学习的启发式任务映射算法。RAPARTI等人[38]以降低系统功耗为目标，利用量子粒子群算法确定了任务映射位置。然而，该类算法无法避免热点。

3）优化温度的任务映射算法

三维集成片上网络功率密度大，为此FENG等人[39]提出基于遗传算法的任务映射算法，优化芯片温度。WANG等人[40]提出了一个异构三维集成片上网络架构，并针对该架构提出了考虑系统运行温度的任务映射算法和路由算法。DEMIRIZ等人[41]针对异构三维集成片上网络提出了一种热管理方案。MOSAYYEBZADEH等人[42]提出了优化系统温度和功耗的任务映射算法，在为应用选择处理器区域时，考虑了任务间的通信量以及热点等因素。LI等人[43]提出了一种降低应用通信延时、减少应用执行时间的任务映射算法。

4）提高可靠性的任务映射算法

三维集成网格片上网络采用硅通孔（Through Silicon Via，TSV）技术将二维网格片上网络连接起来，提供了更高的集成度和更短的层间连接距离，所以在三维片上网络中比较关注针对TSV的可靠性优化。

DING等人[44]提出的方法试图在任务映射过程中通过算法优化TSV技术的使用和降低处理器核之间的通信延时。HAGHBAYAN等人[45]提出了一个分层框架，并通过该分层框架，为应用选择使用压力较小的处理器核，从而为使用压力较大的处理器核提供较长的恢复时间。HAGHBAYAN等人[46-47]在为应用选择处理器区域时引入了处理器核寿命指标以提高系统可靠性。GNAD等人[48]提出了一个轻量级的处理器核老化评估技术，并基于该评估技术，将计算密集型任务映射到健康处理器核，以避免部分处理器核老化过快。RATHORE等人[49]提出了一种称为HipMap的动态分层映射方法，该方法利用暗核来降低系统峰值温度，从而延长了系统的使用寿命。

3 发展趋势

3.1 暗核

考虑暗核的任务映射算法可以使得处理器核运行在高频，但是引入暗核会增加工作处理器核间的通信距离。因此考虑暗核的任务映射算法需同时考虑功耗、温度、通信三个因素。此外，考虑暗核的任务映射算法需考虑暗核数量。计算密集型应用需更多的暗核，通信密集型应用则应减少暗核。PARSEC测试集中的应用Facesim和Swaptions在众核模拟器中运行时的计算需求变化如图3所示，其中计算需求是以吞吐率（每周期指令数，Instructions Per Cycle，IPC）来衡量的。分配给应用的暗核数也应该随时间变化。

图3 应用计算需求变化

3.2 三维集成片上网络

目前针对三维集成片上网络的任务映射算法较少。三维集成片上网络如图4所示，有区别于二维片上网络的特点。首先，每层处理器核距离底部散热器的距离不同，这导致了处理器核散热能力不同。

图4 三维集成片上网络

其次，应用处理器区域层数影响处理器核间通信距离。不同的处理器区域如图5所示，在处理器核数相同的情况下，垂直方向只有一层的处理器区域的处理器核间最大跳数为8，垂直方向三层的处理器区域的处理器核间最大跳数为5。

图5 不同的处理器区域

由于处理器区域层数影响处理器核间通信距离，以及处理器核散热能力不同的特点，二维片上网络任务映射算法不能直接运用至三维集成片上网络。现有三维集成片上网络的典型拓扑结构是三维集成网格片上网络，采用TSV技术可将二维网格片上网络连接起来，因此可将三维集成网格片上网络所提出的任务映射算法拓展至其他拓扑结构，如Torus等。之前提出的任务映射算法多采用集中控制的方式。在未来，芯片中的处理器核数目更大，可将现有任务映射算法扩展为分布式任务映射算法。

4 结论

本文从二维片上网络和三维集成片上网络针对不同的优化目标对现有任务映射算法进行了研究，分析了优化通信的任务映射算法导致碎片化程度加重等问题的产生，考虑了三维集成片上网络区别于二维片上网络的特点，指出了如何将任务映射算法拓展到其他拓扑结构如Torus等，如何设计分布式任务映射算法将成为未来众核任务映射算法亟待解决的关键问题。