面向温度优化的片上网络任务调度方法*

吉 慧，周 磊

(扬州大学信息工程学院,江苏 扬州 225000)

1 引言

随着半导体技术和集成电路技术的发展，单个芯片上可集成的IP(Intellectual Property)核越来越多，设计复杂度的提高和片上系统SoC(System on Chip)规模的扩大使得传统的基于总线的互连方式成为提升系统性能的瓶颈。因此，片上网络NoC(Network-on-Chip)得到了发展，以实现众核之间数据的高效传输[1 - 4]。由于片上网络规模的扩大，片上网络的设计需要考虑的问题越来越多，主要有拓扑结构设计[5,6]、路由算法[7,8]、交换机制[9]、任务调度、流量控制、QoS(Quality of Service)[10]、路由器结构、资源网络接口、性能评估[11]、定时和映射优化[12]等多个问题。并且，众多学者在这些问题上展开了深入研究。

任务的初始分配情况直接决定了系统的功耗密度和热量分布。当系统处于运行状态时，由于通信功耗的不同可能会导致局部热点的出现，动态监控并及时调整各区域的任务负载是实现系统温度动态管理的重要手段，因此任务调度对实现NoC温度优化非常重要。

目前，NoC的动态温度管理机制包括：时间性动态温度管理和空间性动态温度管理[13 - 16]。时间性动态温度管理机制通过采用临时性措施降低热点区域功耗来控制温度。空间性动态温度管理机制采用任务迁移技术将过热区域处理器中的任务迁移或者交换，让其处于相对空闲状态使得温度降低。两种动态温度管理机制相比，空间性动态温度管理的温度控制对系统性能带来的影响较小。空间性温度管理机制包括集中式管理和分布式管理。前者通过将各节点温度信息汇总传送给中央控制器，中央控制器根据接收到的温度消息判断是否执行任务调度操作。后者由NoC中各个处理器根据本地与其他区域节点的温度对比，自行决定是否执行任务调度。

在NoC系统中，各处理器均为同质的CPU核，系统需要在运行初期将等待运行的任务分配到相应CPU核之中。虽然在NoC初始运行时期，任务分配算法通过合理分布任务位置优化系统温度，但是在系统运行过程中，各区域的热量分布和峰值温度仍然会出现波动。因此，在系统运行期间实时监控各区域温度变化，并通过任务调度保障系统长时间可靠地运行是非常关键的。Ge等人[15]提出了基于神经网络温度预测模型的任务调度方法。该方法将预测温度与阈值温度对比，交换处理器核中的任务，实现系统温度动态调节。但是，该方案中温度预测模型需要的训练时间较长，对随机性任务负载突变情况不适用。Liu等人[16]提出了将平均温度作为温度阈值的任务调度算法DTM(Distributed Task Migration)。每经过一次调度系统的平均温度都会变化，随之触发条件也跟着改变，系统的任务迁移触发次数得到了优化。为了降低峰值温度和均衡系统温度，一种温度感知任务调度启发式被提出[17]。与现有的方法相比，该方法充分考虑了瞬时温度、热耦合和核的物理位置，使得峰值温度降低4.48℃和温度变化减少到45%。Sharifi等人[18]将频率/电压调节算法与任务调度算法相结合，并且使用耗尽算法搜索运行新载入任务的处理器核。该方案使得功耗和系统峰值温度得到优化，但是较大的计算量带来额外的计算功耗，反过来对整个系统的温度又产生了一定的影响。杨鹏飞等人[19]设计了新任务模型，使其能够更加真实地反映子任务间的制约关系，使其适于解决大规模任务调度问题，克服了算法前期搜索过快的不足，其缺点是后期搜索能力下降，易陷入局部最优。

以上现有的调度策略大部分考虑了系统的温度，但是都没有考虑到任务之间通信距离对系统温度优化带来的影响。基于上述问题，本文提出一种基于处理器间最短曼哈顿路径的任务调度SMDS(Shortest Manhattan Distance Scheduling)方案。该方法首先给出核通信图，将任务映射到NoC体系结构图上。当系统的平均温度高于触发机制规定的阈值温度时，则进行任务调度。该调度方案启动任务调度的时候，选择系统峰值温度节点进行任务调度。调度的目的节点选择规则为寻找核通信图中峰值节点对应的目的节点，计算通信节点之间的最短曼哈顿路径集，并且选择其中平均温度最低的一条路径，选择此条路径上的节点与峰值温度点进行任务调度，采用模拟退火算法进行任务调度的优化，降低了迁移次数和平均跳数，达到系统温度优化的目的。

2 SMDS方案设计

2.1 任务调度问题定义与描述

任务调度指的是NoC在运行过程中，由于任务或通信量的变化，可能会出现局部热点，当处理器温度情况满足任务调度触发机制的条件时，系统将启动任务调度机制。首先，热点区域中的处理器将向其他区域发出任务调度请求，并收集反馈的温度信息。然后，任务调度机制将根据接收到的信息确定任务调度对，并将温度最低的处理器作为任务调度的目的节点。最后，温度过热的处理器将发送调度信息到目的处理器，从而完成任务调度操作。任务调度对整个NoC系统性能有着重要的影响。为了更好地分析调度问题，下面提出一些定义和假设。

定义1给定核通信图CCG(Core Communication Graph)，表示为CCG(C,A)，其中顶点Ci∈C表示一个IP核，ai,j∈A表示Ci到Cj之间的通信踪迹。

定义2给定NoC架构图NAG(NoC Architecture Graph),表示为NAG(R,P)，其中ri∈R表示资源节点，Pi,j∈P表示ri到rj通信路径。hi,j表示ri到rj之间的曼哈顿距离。

将CCG上每个IP核自动分配到NoC构架图上。假设已经确定C3与C2为任务调度对，当系统满足触发机制条件时，执行任务调度，具体任务调度过程如图1所示。

Figure 1 Process diagram of task scheduling图1 任务调度过程图

针对2D Mesh片上网络结构，源节点i(xi,yi)和目的节点j(xj,yj)之间的曼哈顿距离可以表示为：

hi,j=|xi-xj|+|yi-yj|

在i(xi,yi) 和j(xj,yj)之间存在最适合调度的节点qt(t=1,2,…,r)。Thi,j是Ci到Cj这条路径上所有处理器核的温度总和。Tavg是Ci到Cj这条路径上所有处理器核的平均温度。

本文优化的温度采用系统的平均温度。假设2D Mesh的规模为N*M,对于每个核Ci′j′(i′=1,2,3,…,N；j′=1,2,3，…,M),Ci′j′对应处理核温度为TCi′j′,E为系统的平均温度，表示如下：

假设任务调度前系统的平均温度为Einitial，Enew为任务调度后系统的平均温度，Ebest为平均温度历史最优解。令Enew=Ebest=Einitial。令ΔE=Enew-Ebest。目标函数定义为：

f=min{ΔE}(min{hi,j}中{Tavg})

(1)

选择源节点对应的所有目的节点的最短曼哈顿距离min{hi,j}中平均温度最低min{Tavg}的路径进行调度。基于上述定义，结合下文提出的任务调度方案，最终使得目标函数式(1)的结果尽可能优化。

2.2 任务调度策略

2.2.1 搜索算法

任务调度是在片上网络任务分配后系统运行期间出现温度分布不均的情况下进行的任务位置的交换操作。当给定已经进行任务分配后的NoC架构图，根据CCG，通过搜索算法选择任务调度的目的节点。任务迁移对搜索算法设计步骤具体如下：

步骤1当系统进入运行状态，达到触发条件，选择需要调度的节点i(xi,yj)。

步骤2根据CCG，选择节点i(xi,yi)需要调度的目的节点j(xj,yj)。目的节点选取规则：根据CCG，选择节点i(xi,yi)在CCG中的所有目的节点，形成集合D=[j1,j2,j3,…,jn],n=1,2,3,…,k。

步骤3将i与D的每个子集之间的最短曼哈顿路径中平均温度最低的路径形成集合Pi，Pi=[Pi,j1,Pi,j2,Pi,j3,…,Pi,jn],假设Pi,jn路径中的每个节点形成集合Q,由离选中的节点i(xi,yi)距离由近到远形成集合Q，Q=[q1,q2,q3,…,qt],t=1,2,3,…,r。

步骤4选择i与Pi中平均温度最低的路径Pi,jn中的节点进行任务调度。Pi,jn中的被调度目的节点选择按照集合Q中t由小到大与i(xi,yi)依次进行调度。

2.2.2 优化算法

模拟退火算法是一种通用的概率演算法，能够实现全局优化[20]。本文提出了一种根据最短曼哈顿距离并基于模拟退火算法的任务调度算法。上述调度方法经过模拟退火算法的优化，可以在保证算法高效的前提下，减少任务在调度过程中的迁移次数和调度完成后执行整个任务图通信所需的平均跳数，提升系统性能。具体方案如下：

(1)初始化。假设系统的峰值温度为TI。初始选中的峰值温度为T0，此时系统平均温度为Einitial。令Enew=Ebest=Einitial。令△E=Enew-Ebest。

(2)对于选中的峰值节点，按照调度规则，找到与之最适应调度的目的节点，调度后系统平均温度作为Enew。

(3)若ΔE<0，则Ebest=Enew，并且进行任务调度，然后选择下一个峰值温度点，继续按此方案进行任务调度对的确定。否则直接寻找下一个峰值温度点更新TI。

(4)重复(2)～(3)，直到达到目标函数，即直到系统平均温度基本不变，则停止任务调度。

(5)输出最优解，计算迁移次数和平均跳数。

2.2.3 调度实例

通过搜索算法寻找到最优任务调度对后，完成任务调度，再利用模拟退火算法完成目标函数的优化，使得整个系统温度得到优化。假设3*3 mesh,有9个任务已经分配到NoC架构图中。具体调度过程实现如图2所示。

Figure 2 An instance of the SMDS scheme图2 SMDS方案实例

3 实验与分析

3.1 实验环境

(1)温度仿真软件：本文使用HotSpot[21]进行温度仿真。通过输入各个处理器核功耗，HotSpot将会产生每个核的温度(温度包括瞬态温度和稳态温度)。在本实验中温度指的是系统的稳态温度，具体的配置信息如表1所示。

(2)测试样例：采用E3S[22]基准进行实验。E3S基准中包括来自EEMBC基准的automation/industrial，office automation，networking，telecom-munication 和consumerelectronic 5个基准组。每个基准程序由一个任务图和预定的通信模式组成，表2展示了E3S测试样例组件的详细信息。

Table 1 HotSpot configuration information表1 HotSpot配置信息

3.2 结果分析

实验分别从任务迁移次数与平均跳数两个方面对SMDS策略与DT策略进行比较。为了验证SMDS策略的有效性，采用6*6、8*8和10*10 mesh NoC拓扑结构进行实验。本文进行了6次实验，测试过程中的测试样例全部取自E3S测试样例组件，针对本文选择的36个、64个和100个处理器将任意执行测试样例中的一个任务。任务调度方法触发机制的设定对任务调度的触发起到关键作用。假设节点温度超过温度阈值85℃时会触发SMDS任务调度算法。

Table 2 E3S benchmark specification表2 E3S测试样例

任务迁移次数定义为在实验过程中任务迁移过程的次数，如表3所示。平均跳数定义为通过模拟退火算法后，f达到最小时，完成整个CCG需求时的平均跳数，如表4所示。通过表3和表4可以得到迁移次数平均降低率和平均跳数平均降低率。迁移次数平均降低率定义为6次实验迁移次数降低率的平均值，如图3所示。平均跳数平均降低率定义为6次实验平均跳数降低率的平均值，如图4所示。

Figure 3 Average reduction of migrations图3 迁移次数平均降低率

由实验看出，SMDS策略对于解决任务调度问题是非常有效的。DTM策略通过系统的全局搜索，寻找任务调度目的节点，其空间复杂度为O(n2)。而SMDS策略沿着任务调度对之间的最短曼哈顿距离进行任务调度目的节点的搜索，其空间复杂度为O(n)。随着系统规模的扩大，SMDS策略明显优于DTM策略。SMDS策略在实现目标函数的过程中，系统的温度得到了优化。SMDS策略在确定任务迁移对的过程中，以迁移后是否降低系统平均温度为依据，决定是否同意本次任务迁移，挑选最终的任务迁移目的节点，实验通过迁移次数的降低，实现额外功耗的减小，降低系统的温度。如表3和图3所示，与DTM策略相比，针对6*6、8*8和10*10的拓扑结构，SMDS实验方案在迁移次数方面分别优化了(10%～31.58%)、(16.92%～28.21%)和(18.12%～28.95%)，平均优化率分别为22.08%、21.74%和23.02%。 此外，如表4和图4所示，与DTM策略相比，针对6*6、8*8和10*10的拓扑结构，SMDS实验方案在平均跳数方面分别优化了(9.89%～34.28%)、(18.19%～37.22%)和(19.18%～27.16%)，平均优化率分别为24.04%、29.18%和23.04%，实现了通信功耗的降低和系统温度的优化。

Table 3 Number of migrations表3 迁移次数

Table 4 Number of average hops表4 平均跳数

Figure 4 Average reduction of average hops图4 平均跳数平均降低率

4 结束语

针对片上网络中的任务调度问题，本文提出了SMDS方法。该方法充分考虑了核通信图中任务调度对之间的最短曼哈顿距离，通过模拟退火算法进行任务调度的优化。本文选择优化的目标为迁移次数和平均跳数。迁移次数的降低可以减少系统在任务调度过程中的额外功耗。平均跳数的减少可以缩小系统中通信节点之间的距离，因此可以降低节点之间的通信功耗。本文选取6*6、8*8和10*10的拓扑结构，并与传统的DTM策略相比，SMDS策略在实现目标函数的过程中，不仅使得系统的温度得到了优化，同时在迁移次数和平均跳数方面均得到了明显的改善，迁移次数和平均跳数优化率分别为(22.08%、21.74%和23.02%)和(24.04%、29.18%和23.04%)。今后将针对片上网络半实物仿真平台方面展开更为深入的研究。