杨微

（广州大学华软软件学院软件工程系，广州 510990）

低功耗片上网络映射算法研究

杨微

（广州大学华软软件学院软件工程系，广州 510990）

提出改进的片上网络蚁群映射算法，并为验证该映射算法对低功耗片上网络性能的提升，结合具体应用进行仿真实验。比较该改进蚁群算法与一般蚁群算法、粒子群算法的映射结果的优劣。仿真实验选取5组实验结果进行性能对比分析。实验结果显示改进的蚁群算法能够在收敛速度、停滞现象等方面都有取得较好的性能，获得的映射解在功耗函数下可以取得更低的功耗。

片上网络；低功耗；片上网络映射；粒子群算法；蚁群算法

0 引言

功耗问题作为阻碍集成电路不断发展的主要问题，对未来集成电路（IC）设计带来多方面挑战，例如对芯片的封装和散热方面的设计的挑战，对芯片的性能以及稳定性方面的挑战等，因此功耗问题也越来越受到工业界和学术界的关注。而NoC（Network-on-Chip）作为未来大规模并行处理器的首选架构，是未来芯片设计的发展方向，它不仅被广泛应用于高性能服务器等大规模计算系统，也被移动和无线通信终端等嵌入式高性能SoC设计所采用，因此对NoC功耗进行低功耗设计意义重大。目前国内外很多研究机构和学者都从不同方面对NoC的功耗问题进行了研究，并提出了改进优化NoC的方案。例如在物理硬件方面，文献[1]在NoC中采用低摆幅信号，并通过实验证明低摆幅信号不仅在功耗方面有优化作用；在软件应用方面，文献[2]对硬件实现开关链路进行了研究，他们通过设置硬件计数器获取网络运行时的链路的实时状态，并以此为依据选择关闭或者开启链路。这种方法可以有效降低静态功耗，但是相比于硬件实现，软件编译指导可以获得更好的性能；在拓扑结构上，文献[3]中基于对应用的通信量分析所得的数据的基础上，对规则拓扑结构进行裁剪的技术，即把不用的多余的I/O、路由单元进行裁剪，给通信量比较频繁、路由单元更多的资源，实验数据表明这种技术可以有效减少面积消耗以及NoC能耗等。

本文是在算法应用的层面对低功耗片上网络进行研究，基于改进蚁群算法的片上网络低功耗映射方案研究，在分析片上网络功耗的基础上，对蚁群算法进行了改进，提出基于改进蚁群算法的片上网络低功耗映射算法。

1 改进低功耗片上网映射算法研究

1.1 低功耗片上网络映射问题建模

片上网络的映射，有定义：

本文研究的重点是低功耗片上网络映射，因此这里的目标函数设定为功耗的约束。在这里我们研究中以文献[4]提出的基于单个路由节点功耗模型为目标函数。依据文献[4]，NoC片上网络映射在功耗模型下的目标函数如公式（1）所示：

即低功耗片上网络映射模型为：

在上面片上网络的映射模型中，对于有N个任务的应用输入，对应有N!种排列方式，构成映射模型的解空间，显然片上网络映射问题属于组合优化即二次分配问题（QAP）的范畴。二次分配属于NP难问题，所谓NP难，就是对于一个问题除了穷举该问题所有解域内的解以外，找不到一种多项式的解决方法。利用群体智能算法在合理的时间里得到NP问题较满意的解，即以“解的精确性”换取“时间的合理性”一直以来成为学术界研究的重点。论文中引入蚁群算法作为NoC映射的基本算法，并在此基础上对算法进行了改进。

1.2 改进低功耗片上网络映射算法设计

（1）问题描述及改进

蚁群算法是模拟自然界中蚂蚁寻找食物的过程来解决问题。在自然界中，蚂蚁觅食过程中，蚁群总能够寻找到一条从蚁巢和食物源的最优路径。论文中结合低功耗片上网络的特点，对基本蚁群算法的改进如下：

①一般的蚁群算法是在每次迭代后依次更新信息素矩阵，改进蚁群算法设立了更新集用来更新信息素矩阵。从每次迭代后解中以一定的概率择优选择加入到更新集中，这有助于加快算法的收敛速度。

②改进蚁群算法更新集的更新方案：当蚁群内所有的蚂蚁完成一轮搜索后取得解集称为候选集，记为C={Antk(ck-ek)|1≤k≤M}，ck为蚂蚁完成搜索后得到的一个解，ek为功耗函数的值。按照一定的方案从候选集中选取解加入到更新集中，信息素矩阵的更新依据更新集中的元素进行，更新集记为CR={Antk(ck-ek)|1≤k≤M}。令比较参数к=0.5（参数值的选择考虑到概率事件的平等性）。构造更新解的代码为：

③一般蚁群算法为每只蚂蚁选择下一个节点的方法是：以某种概率搜索节点，每搜到一个，就将该节点加入到OpenK中，并且从ClosedK中删除该节点。该过程重复n-1次，直到所有的节点都遍历过一次。改进蚁群算法蚂蚁下一个访问节点的确立方案：为了避免算法在寻优过程中陷入局部搜索，保证蚂蚁的全局搜索空间，以一部分概率使蚂蚁在选择下一个位置结点时放弃对当前高期望解的追逐而转向其他低期望的位置结点。这可以提高算法的全局搜索能力，避免陷入局部最优解。

（2）基于改进蚁群算法的低功耗NoC映射算法步骤

改进蚁群算法在功耗函数的限制下求解NoC映射问题的过程为：

①初始化设置：蚂蚁数M=2n/3、控制参数（α，β，ρ= 0.6，Q）、算法迭代的次数NC、最优解Antmin为无穷大、信息素矩阵所有元素初始化为0、OpenK为空、ClosedK表中加入所有的拓扑结构节点（n个）、M只蚂蚁的位置并在OpenK中加入起始节点，ClosedK中去掉该起始节点。

③蚁群得到的解集为候选集，更新目标函数（公式1）的值得到候选集内最优个体为Ant局部最优，算法当前最优解Ant最优，更新Ant最优，按照概率决定是否把候选解集中的解加入到更新集中。

④更新信息素矩阵，以更新集中的解来更新信息素矩阵。

⑤检查终止条件：是否有蚂蚁没有完成一次循环？是，转到步骤②继续执行；是否达到算法最大迭代的次数NC？否，转到步骤②；转到步骤⑤输出最优值Ant全局最优。

⑥输出最优值Ant全局最优。

基于改进蚁群算法的低功耗NoC映射算法流程如图1：

图1 低功耗NoC映射算法流程图

2 仿真测试及结果分析

2.1 仿真测试实例以及实验环境介绍

（1）硬件平台：AMD Athlon P360 Dual-Core CPU @2.3.0GHz 2.00GB内存；

（2）软件平台：操作系统Windows 7旗舰版；映射算法的开发语言为C++语言；实验仿真环境是在Dev-C++5.4.1环境下进行。在实验中选择2D-Mesh结构作为映射拓扑结构。

仿真实验中选择MPEG4译码器作为测试实例来验证本文提出的低功耗片上网络映射算法的性能。MPEG4任务流图如图2所示。

图2 MPEG-4译码器任务流程图

各个参数的选择如表1所示，在仿真实验中最大迭代次数NC设置为300。

表1 改进蚁群算法的实验参数表

2.2 实验结果及其结果分析

仿真实验对改进的蚁群算法、一般蚁群算法以及粒子群算法（分别独立执行50次，并从中选择5次进行对比）在收敛速度、功耗等方面的性能。

如表2，通过比较以上五组实验仿真数据数据，可以看到改进的蚁群算法所得的解功耗函数在309.84 (mW)左右浮动，粒子群算法获得的解功耗函数值在522.74(mW)左右浮动，相对比粒子群算法，在功耗方面改进蚁群算法优化比例的平均值为59%，证明了改进的蚁群算法具有更好的低功耗性。

表2 改进蚁群算法和一般蚁群算法性能对比

如表3，通过比较以上五组仿真实验数据，,可以看到基本蚁群算法获得的解在446.68（mW）左右浮动，这说明一般蚁群算法相比于粒子群算法能够获得更好的解，同时在功耗方面改进蚁群算法的算法优化比例的平均值为69%，证明具有比基本蚁群算法更好的低功耗性。

表3 改进蚁群算法和粒子群算法功耗对比

仿真实验还比较这三类算法的收敛趋势，其收敛趋势对比如图3所示。

从算法的收敛趋势图上可以看到改进蚁群算法相对比于基本蚁群算法以及粒子群算法，具有更好的收敛性，可以用更少的时间获得全局最优解。其中，改进的蚁群算法相对比于基本蚁群算法，算法的停滞现象得到了改善，算法的收敛速度更快，并能获得更优的功耗函数值。

图3 算法的收敛趋势图

3 结语

近年来，一方面，节能意识的增强推动低功耗片上网络设计技术的发展，另一方面，由于能耗上升导致的芯片温度上升，进而对芯片性能和稳定性的影响也推进了工业界和学术界对低功耗片上网络研究。而更巧妙的片上网络架构设计、更多地集成处理核心、更低的片上网络功耗、更优的性能等都是未来片上网络技术发展的主要方向[5]。论文从片上网络映射问题分析以及片上网络低功耗建模入手，提出改进的蚁群算法；通过仿真实验证明改进的低功耗算法获得的映射解具有更好的低功耗性，接下的工作是从更多的层面去研究片上网络（NoC）的功耗问题并进行低功耗设计，提出更加准确完善的功耗函数作为性能评估依据，综合功耗、延时、吞吐量等多性能指标去提升片上网络的性能，并平衡片上网络的功耗问题。

[1] Lee K,Lee S J,Yoo H J.Low-Power Network-on-Chip for High-Performance SoC Design[J].Very Large Scale Integration(VLSI)Systems,IEEE Transactions on,2006,14(2):148～160

[2] L.Benini,G.D.Micheli.Networks on Chips:A New SOC Paradigm[J].IEEE Computer，35,1(Jan.),2002：70～78

[3] Jalabert A,Murali S,Benini L,et al.×PipesCompiler:A Tool for Instantiating Application Specific Networks on Chip[C].Design,Automation and Test in Europe Conference and Exhibition,2004.Proceedings.IEEE,2004,2:884～889

[4] 杨微,张振,刘怡俊.基于改进粒子群的3D-Mesh CMP片上网络映射算法[J].计算机应用研究,2013,30(5):1345～1348

[5] 李丽,许居衍.片上网络技术发展现状及趋势浅析[J].电子产品世界,2009,16(1):32～37

[6] 沈剑良,严明,李思昆,等.NoC低功耗技术研究综述[J].计算机工程与科学,2009,31(A01):88～92[7] Networks-on-Chips:Theory and Practice[M].CRC Press,2011

[8] Lee K,Lee S J,Yoo H J.SILENT:Serialized Low Energy Transmission Coding for On-Chip Interconnection Networks[C].Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design.IEEE Computer Society,2004:448～451

[9] 骆祖莹.芯片功耗与工艺参数变化:下一代集成电路设计的两大挑战[J].计算机学报,2007,30(7):1054～1063

Research on the Low-Power Mapping Algorithm of NoC

YANG Wei
（School of Software Engineer，South China Institute of Software Engineering，GZU，Guangzhou 510990）

Presents the improved ant colony algorithm for network on chip,and to verify the mapping algorithm on network performance and low power on chip,combined with the practical application of the simulation experiment.Compares the mapping results of the improved ant colony algorithm and general ant colony algorithm and PSO's.Analyzes the comparative performance of 5 groups selected simulation results which show that the improved ant colony algorithm has achieved better performance in convergence speed,stagnation,etc,and mapping solution obtained in power function can be achieved at lower power consumption.

Network-on-Chip;Low Power Consumption;Mapping of NoC;Particle Swarm Optimization;Ant Colony Algorithm

1007-1423（2015）03-0010-05

10.3969/j.issn.1007-1423.2015.03.003

杨微（1987－），女，江西抚州人，硕士，研究方向为计算机体系结构、NoC基础

2014-12-09

2014-12-30

国家自然科学基金项目（No.61106019）、广东省“省部产学研结合项目”（No.2011B090400408、No.2011A090200022）