基于改进模拟退火的三维片上网络映射算法研究

马 悦， 宋国治， 张大坤

(天津工业大学 计算机科学与软件学院 天津 300387)

基于改进模拟退火的三维片上网络映射算法研究

马 悦， 宋国治， 张大坤

(天津工业大学 计算机科学与软件学院 天津 300387)

在基于模拟退火算法的基础上提出了一种改进温度下降函数和自适应的生成邻域解的新型算法.该算法通过新提出的温度下降函数，使得在初始温度较高的时候下降较为平滑，同时在邻域解的生成过程中采用新的生成邻域解的方式，充分实现算法的全局性，克服传统模拟退火算法易陷入局部最优解的困境; 同时在温度较低时候，平滑的温度下降方式也有利于进行充分的局部搜索，取得最优解.实验结果表明，与传统的模拟退火算法相比，提出的新型的模拟退火算法在三维片上网络的映射过程中，在功耗和收敛速度两个方面有显著的提升.

三维片上网络； 模拟退火算法； 温度下降函数； 邻域解

0 引言

片上网络(network-on-chip, NoC)是片上系统(system-on-chip, SoC)的概念的延展[1-2].先是为了取代片上系统的总线连接方式从而合理高效地在单一芯片上连接数量庞大的处理单元(processing elements, PE)而提出的目前主流的二维片上网络架构.单一芯片上的集成度越来越高，受限于节点之间距离增大带来的高功耗、高延迟，三维片上网络(3D NoC)又被提出以其更短的全局互连、更低的互损功耗、更好的性能、更高的封装密度以及更小的体积等诸多优势成为当前的片上网络的一个重要的研究方向[3].本文提出了一种基于模拟退火算法的改进温度下降函数的自适应映射算法.通过改进的温度下降函数和自适应的邻域解生成策略，来保证在温度较高时算法的全局性搜索和温度较低时局部性充分搜索的实现.改进后模拟退火算法在收敛速度和功耗上面与传统的模拟退火算法相比，有了较大的性能提升.

1 3D NoC映射问题

1.1 研究现状

目前使用的映射算法大致分为两类：启发式映射算法；非启发式算法.启发式算法主要代表有：基于遗传算法的映射算法；基于粒子群算法的映射算法；基于模拟退火算法的映射算法以及基于禁忌搜索算法的映射算法等.非启发式算法主要包括：异构3D NoC映射算法；常规3D NoC热感知方法以及快速低能耗映射方法SYMMAP等[4].本文选用模拟退火算法来进行映射，通过改变模拟退火算法的温度下降函数和邻域解生成策略，在较短的时间内可以获得较优的映射结果.

1.2 映射问题定义

片上网络映射就是在已知NoC体系结构和IP核间通信量的基础上，按某种方法将给定应用特征图 (application characteristic graph, ACG)上的IP核 (包括微处理器、DSP以及各种专用功能模块等)分配到NoC拓扑结构图 (topology architecture graph, TAG)中的各资源节点上，使得3D NoC的一个或多个性能指标达到最优.有关片上网络的映射问题是一个非多项式时间复杂性问题(NP-hard problem)[5-6].

为了清楚地描述映射问题，这里我们给出两个定义：

定义1 特定任务的应用特征图ACG,G(V，E)为有向非循环加权图，顶点vi∈V，代表着一个执行特定任务的IP核，用整数来表示，不同数字代表不同的顶点.有向弧ei,j∈E，表示节点vi与vj之间的通信关系，权重wi,j代表vi与vj的通信量.

定义2 给定的片上网络拓扑结构图TAG,T(R，P)为有向图，顶点ri∈R，表示NoC中的一个资源节点；有向弧pi,j∈P表示从ri到rj的路径.hi,j表示从ri到rj之间的曼哈顿距离.

由定义我们给出3D NoC的映射过程为：给定的G和T,在函数map( )的作用下找到G→T下的最优解,使得目标函数尽可能的优化.映射的同时必须满足以下的约束条件：

∀vi∈V⟹map(vi);∀vi≠vj⟹map(vi)≠map(vj);size(j)≤size(T).

图1 经典DVOPD应用特征图Fig.1 Classical ACG DVOPD

约束条件保证每个资源节点与通信任务节点一一对应.图1所示就是经典的DVOPD图，节点共有32个，从1～32代表32个不同的IP核.两个节点间的有向箭头代表着之间存在通信，有向箭头上的数字表示权重，在面向片上网络的架构上就是节点之间的通信流量.在DVOPD图中，32个节点就对应着32的阶乘种可能性，这样形成的解空间是非常巨大的.在本文研究的三维片上网络映射问题上，我们使用智能优化的方法来求解.在巨大的解空间中，运用基于模拟退火的改进算法搜索较优解，取得较好的三维片上网络的映射方案.

2 NoC评估模型

2.1 目标函数

面向3D NoC的映射算法，我们定义一个适应值函数Cost=MAXFit-(dxwx+dywy+dz)，其中：MAXFit是预先设置好的最大适应值；dx、dy、dz代表的是通信节点在3个坐标轴方向距离；wx、wy代表的是权重.因为三维片上网络采用了TSV技术，在z轴方向的传输功耗要远远小于水平方向上的功耗[7-8]，所以这里就不再乘以权重.

2.2 功耗模型

节点i与节点j之间发送一个微片(flit)的功耗Ebit,(i-j)=μERbit+μHELHbit+μVELVbit,其中：μ表示节点i到节点j经过的路由器个数;μH和μV分别是信息传输到目的节点所经过的水平方向和垂直方向的条数；ERbit表示一个微片通过一个路由器时消耗的能量;ELHbit和ELVbit分别表示一个微片通过一条水平方向和垂直方向的线路时消耗的能量[9].

3 改进模拟退火算法

3.1 ISA的提出

3.1.1 改进温度下降函数 模拟退火算法是一种启发式的随机寻优的算法，在算法中我们使用温度下降函数来控制温度的下降方式，对应着SA算法中的外循环[8].具体来说就是温度决定着SA进行的是广域搜索还是局域搜索.当温度较高的时候，当前邻域内的解会以极大的可能性被接收，此时的SA算法相当于进行着广域搜索；当温度变低的时候，基于当前解生成的劣解被拒绝的可能性越来越大，这时候SA算法就从广域搜索变成了局域搜索.这里我们列出两种传统的温度下降函数：

Ti+1=Ti×r，

(1)

Ti+1=Ti-ΔT，

(2)

其中：Ti+1代表下一时刻的温度；Ti代表当前时刻的温度；ΔT代表每一步温度下降的大小；T0代表初始的温度.为了便于理解和叙述，这里我们记基于传统温度下降函数(1)的模拟退火算法为SA-1,基于传统温度下降函数(2)的模拟退火算法SA-2.

传统模拟退火算法SA-1，在温度较高的时候，温度下降较快，模拟退火算法的全局性没有得到实现，导致算法极容易陷入局部最优的困境；而SA-2算法，由于每次下降的温度相同，在算法运行中，温度函数的斜率是不变的.这样在温度高的时候，我们要求的全局性搜索与温度低的时候的充分的局部性搜索得不到实现，实验效果也是最差的[10-11].鉴于此我们提出了新的温度下降函数：

Tcount=exp(-(count/DIM)2)×(T0-TN)+TN，

(3)

其中：count代表外循环次数，温度每下降一次count自增1；DIM代表3D NoC的规模大小(节点数目)；TN代表终止温度；T0代表着初始温度.对于温度下降方式，我们使用自然数e的幂函数来构造了本文中新的温度下降函数，将温度的下一时刻的改变在与外循环相关的基础上，建立与片上网络规模的关联.构造了一个根据不同规模的片上网络映射问题而改变的温度下降函数，目的在于在算法初始阶段和接近算法结束这两个阶段可以取得平滑的温度下降方式.从而可以保证算法初始阶段的全局性和终止阶段局部搜索的充分性实现.

本文取初始温度为100 ℃，终止温度是0.000 1 ℃.从图2中可以看出当温度较高的时候，式(3)下降的速度比式(1)和(2)慢，更加有利于实现模拟退火算法的全局性.3个函数在接近终止温度的时候，可以看出式(3)先收敛，式(1)其次，式(2)最后收敛.我们将在后面用仿真实验来证明此结论.

图2 三种温度下降函数的曲线Fig.2 Curves of 3 temperature functions

3.1.2 邻域解的生成方法的改进 SA算法是基于邻域搜索的，邻域定义的出发点应该是满足其中的解尽可能地遍布整个解的空间，以防止算法只能实现局部最优.传统的模拟退火算法所使用的方法虽然可以有效地生成邻域解，但由于本身策略的局限性，新解与当前解的曼哈顿距离(hi,j)是相对较小的[12].这不利于在算法运行初期实现算法的全局性.鉴于此种情况，本文提出利用概率p来选择邻域解的生成方法.

改进的邻域生成策略：

1) 初始设p=1,当p>rand( )时，我们采用向左循环移动一位的方法生成新解，否则执行2).

2) 采用传统随机确定两个节点的位置，然后互换两个节点从而生成新解.

3.3 ISA算法的流程

本文将提出的新的温度下降函数(3)和自适应的邻域解的生成方法应用到传统的模拟退火算法中，提出ISA(improved simulated annealing algorithm)算法.ISA算法的总体流程如下：

第1步：设置一个初始控制温度T0，TN，i=0,p=1，产生Xi通过目标函数计算f(Xi).

第2步：在可行解空间中通过改进邻域生成算法来生成新解Xi +1, 并计算其相应的目标函数值f(Xi+1)，算出Δf=f(Xi)-f(Xi+1).

第3步：如果Δf<0，则把新解作为当前解；否则，新解就按Metropolis准则判断是否接受.若p>rand(),接受，其中p=exp(-Δf/Ti)，则把Xi+1作为当前解；否则让Xi继续作为当前解.

第4步：判断该温度下是否已经充分搜索，若充分搜索，执行第5步;否则执行第2步.

第5步：判断Ti是否小于TN，若小于，则循环终止，跳到第6步；否则，i自动加1，跳转到第2步.

第6步：返回当前解和当前解的适应值.

4 仿真实验与结果分析

4.1 不同算法的收敛速度对比

在基于Ubuntu操作系统下，本文使用Access Noxim仿真器针对经典的通信轨迹图VOPD和DVOPD进行仿真实验.实验结果如图3和4所示，图中纵坐标轴代表着适应值，横坐标代表迭代次数，适应值大小与NoC的性能成正相关，适应值越大代表着性能越好.图中3条折线分别代表着ISA、SA-1、SA-2 3种基于不同温度下降函数的模拟退火算法对应的实验结果.

图3 3种温度下降函数下VOPD收敛速度

图4 3种温度下降函数下DVOPD收敛速度

其中ISA算法的收敛速度最好，SA-1的收敛速度居中，可以收敛到最优解，但收敛速度与ISA相比明显存在差距.SA-2收敛速度最差，且不能迭代到最优解.对DVOPD的仿真实验进一步证明了ISA算法在面向通信任务规模较大时，算法的性能更是优于基于两种传统的温度下降函数的模拟退火算法.

4.2 功耗对比

本文用DVOPD来做有关功耗的仿真实验，在Code Blocks软件上，分别采用ISA、SA-1和SA-2 3种模拟退火算法来生成通信文件.我们进行10次实验，共生成10个通信文件，对每个通信文件在仿真器上进行仿真实验.基于3种算法的10次功耗结果如表1所示.

在实验中我们主要比较了总功耗、最低功耗和最高功耗.其中总功耗代表着三维片上网络的整体耗能情况，直观地反映了3种算法下的优劣情况.最低功耗表示算法获得最优解的能力.这里比较最高功耗是为了验证在最坏情况下ISA性能依旧优于另外两种算法.功耗对比如图5所示.

表1 DVOPD 3种算法的10次功耗Tab.1 Power consumption of DVOPD in three algorithms J

图5 3种温度函数对应算法的功耗对比图

如图5中，在最高功耗、最低功耗和总功耗上，ISA所对应的结果都要优于其他两种.ISA算法对比SA-1和SA-2两种基于传统温度下降函数的模拟退火算法，总功耗分别减少了2.5%和6.89%；最低功耗分别下降了2.83%和13.83%；最高功耗分别下降了5.59%和7.21%.综合3种结果的对比可知，提出的ISA算法在三维片上网络的映射问题上可以得到更优的映射结果.

[1] DALLY W J，TOWLES B.Route packets, not wires: on-chip interconnection networks[C]// Proceedings of the 38th Design Automation Conference. Las Vegas,2001:684-689.

[2] KUMAR S，JANTSCH A，SOININEN J P,et al. A network on chip architecture and design methodology[C]// Proc Symp VLSI. Monterey,2002:105-112.

[3] PAVLIDIS V F, FRIEDMAN E G. 3-D topologies for networks-on-chip[J].Very large scale integration systems IEEE transactions on, 2007, 15(10):1081-1090.

[4] 黄翠, 张大坤, 宋国治. 三维片上网络映射算法研究综述[J]. 小型微型计算机系统, 2016,37(2):193-201.

[5] SAHNI S，GONZALES T．P-complete approximation problems[J]. Journal of the association for computing machinery (ACM), 1976，23(3):555-565．

[6] 张振.基于3D-MESH的CMP片上网络映射方法研究[D].广州：广东工业大学，2012.

[7] KIM J, PAK J S, CHO J. High-frequency scalable electrical model and analysis of a through silicon via (TSV)[J]. IEEE transactions on components packaging and manufacturing technology, 2011, 1(2): 181-195.

[8] 江鹏. TSV功耗建模与3D NoC功耗分析[D]. 西安：西安电子科技大学, 2012.

[9] HU J, MARCULESCU R. Energy and performance-aware mapping for regular noc architectures[J]. IEEE Trans Comput Aided Des Integr Circuits Syst, 2010, 24(4):551-562.

[10]ZHONG L, SHENG J, JING M, et al. An optimized mapping algorithm based on simulated annealing for regular NoC architecture[C]//ASIC (ASICON), 2011 IEEE 9th International Conference on IEEE.Xiamen, 2011:389-392.

[11]RADU C, VINTAN L. Domain-knowledge optimized simulated annealing for network-on-chip application mapping[M]. Berlin: Springer Berlin Heidelberg, 2013:473-487.

[12]LEI T, KUMAR S. A two-step genetic algorithm for mapping task graphs to a network on chip architecture[C]// 2003 Euromicro Symposium on Digital System Design. Belek-Antalya，2003:180-180.

(责任编辑：王海科)

Research on Mapping for Three-dimensional Network-on-Chip Based on Improved Simulated Annealing Algorithm

MA Yue, SONG Guozhi, ZHANG Dakun

(SchoolofComputerScience&SoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387,China)

A new method to improve the declined function of temperature and the adaptive generation of neighborhood solution was proposed based on the simulated annealing algorithm (SA). The algorithm mades the decline of temperature in the higher initial temperature more smooth by the new function, and it adopted the new way of generating neighborhood solution, thus fully realized the global convergence. So it could overcome the plight of the local optimal solution. And in the condition of low temperature, it could sufficiently find the optimal solution by this function. The experimental results showed that the improved simulated annealing algorithm(ISA) significantly improved the performance of power consumption and the speed of convergence compared with the SA.

3D network-on-chip；simulated annealing algorithm；declined function of temperature；neighborhood solution

2016-11-24

国家自然科学基金项目(61272006)；国家大学生创新创业训练计划项目(201510058050).

马悦(1993—)，男，安徽亳州人，主要从事三维片上网络映射拓扑优化研究，E-mail: 1508011127@qq.com;通信作者：宋国治(1977—)，男，黑龙江哈尔滨人，副教授，主要从事三维片上网络、无线传感器网络及异构网络融合研究,Email:guozhi.song@googlemail.com．

TP305

A

1671-6841(2017)03-0009-05

10.13705/j.issn.1671-6841.2016325