基于MMAS的NoC低功耗映射

刘蓓

(安徽工程大学现代教育技术中心, 安徽 芜湖 241000)

基于MMAS的NoC低功耗映射

刘蓓

(安徽工程大学现代教育技术中心, 安徽 芜湖 241000)

随着芯片集成度的提高, 网络通信流量与通信功耗也随之递增.片上网络在设计阶段就要考虑到通信功耗问题,因此提出一种可以降低通信功耗的映射方法, 该方法是一种改进的最大最小蚁群算法, 通过优化权重系数、状态转移规则以及信息素更新来提高算法的性能.实验表明, 该方法能加速搜索进化过程, 避免搜索的停滞, 具有较好的收敛性,能有效的降低系统的映射功耗.

片上网络; 低功耗; 映射

1 引言

随着半导体技术的发展, 人们开始研究将越来越多的晶体管集成在单一芯片上, 通过构建多个IP核(处理器、存储器、输入输出控制器等)来提高系统整体性能, 然而, 芯片性能的提高也使得设计复杂度不断加大, 片上系统(System on Chip, SoC)的发展遇到了难以逾越的障碍.片上网络(Network on Chip, NoC)的出现彻底解决了SoC所面临的可扩展性差、并行通信能力低、时钟不同步等问题, 为芯片的设计提供了一种新的范例[1-4].

NoC设计包括平台设计和映射技术两方面内容, 低功耗映射NoC系统是促进NoC应用发展的关键技术之一, 旨在将各个并行化子任务分配到各个网络节点上, 使得系统通信成本或能耗最低.文献[5]提出一种分枝定界算法, 将任务映射到NoC的IP核, 在满足带宽约束下, 最小化系统功耗, 但是这种方法的通信成本很高; 文献[6]提出了一种启发式随机搜索算法, 通过构造禁忌表来避免陷入循环, 最终找到NoC低功耗映射方案, 但是该算法的收敛性效果不太理想.文献[7]提出了一种NoC 低功耗映射遗传算法, 该算法的复杂度较高, 全局搜索能力低.本文提出一种改进的最大最小蚁群算法(Max Min Ant Colony Optimization Algorithm, MMAS), 通过优化权重系数、状态转移规则以及信息素更新来提高算法的性能.实验表明, 该方法能加速搜索进化过程, 避免搜索的停滞, 具有较好的收敛性, 能有效的降低系统的映射功耗.

2 NoC映射

2.1 映射过程

NoC映射就是在给定通信任务图上, 把处理单元P通过映射函数分配到NoC结构特征图资源节点IP核上的过程[8], 如图1所示.任务特征图中有4个处理单元, 连接各处理单元之间有向边上的权值为通信量, 通过映射函数构建NoC的结构特征图, 在NoC结构特征图中各IP核之间通过路由器R进行通信.不同的映射函数会产生不同的映射结果, 而映射结果对于系统的硬件代价、性能以及芯片功耗[9]等都有不同的影响, 因此要根据具体需求定义映射函数.

2.2 映射函数

定义2： 给定NoC结构特征图NAV(V, P), 顶点为图中的一个资源节点, 通信路径为节点到节点的通信路径, 边上的权值是节点到节点的通信流量.

文献[10]定义了NoC通信功耗模型, 每bit通信数据从节点vi到节点vj通信功耗为：

综上所述, 确定低功耗映射模型的关键在于找到合适的映射算法, 映射算法的优劣直接影响到系统的通信流量.本文从低功耗映射算法入手, 通过对映射算法的优化计算出映射时最小通信流量, 从而降低NoC的映射功耗.

3 基于MMAS优化的映射算法

蚁群算法是一种在图中寻找优化路径的几率型算法, 通过蚂蚁在寻找食物过程中发现路径的行为演变而来.当一只蚂蚁找到食物后, 会采用向周边环境释放信息素的方式来吸引其他蚂蚁过来, 经过一段时间后, 会有越来越多的蚂蚁找到食物.但总有些蚂蚁会重新寻找新的路径, 开辟新的道路, 如果新开辟的道路比之前找到食物的路径更短, 那么蚂蚁就会被渐渐吸引到新路上来, 一段时间之后可能会出现一条最短路径.

本文提出的低功耗NoC映射问题采用最大最小蚁群算法(MMAS)实现, 为了统计数据的可靠性, 采用MPEG4[11]真实用例作为模型.算法为了抑制搜索路径过早陷入局部最优解, 使用轮盘机制, 并对环境信息素设臵了上下限.整个算法的主要步骤如下：

3.1 初始化

将M只蚂蚁分别随机放在N个节点上, 初始时刻各条路径上的信息素为τ设臵为一常数1, 其他参数详见表1.

表1 初始化参数分配Table1 Initialization Parameter

3.2 状态转移规则

蚂蚁k根据信息素和启发式信息, 采用轮盘机制在第i个IP核节点选择第j个IP核的规则为式(6)所示：

Pijk (t)代表节点i的第k个蚂蚁选择下个节点j的概率,(t)是节点i和j之间的信息素值,是残留信息的重要程度,是启发式因子的重要程度,表示蚂蚁k可选择的资源节点,用于记录蚂蚁k已经分配过的IP核, {1,2,…, n}表示所有可映射的n个节点的全集.

轮盘选择算法是根据适应度的大小进入下一代的概率, 可以避免贪婪方式选择造成的映射解陷入局部最优,算法流程图见图2所示：

通过轮盘选择算法, 蚂蚁虽然选择概率值大的路径可能性大, 但是也有一定的可能性往概率小的路径走,这样就可以使蚂蚁探索新的路径, 避免算法停滞或者陷入局部最优解.

3.3 信息素更新

随着进化的不断推进, 以前留下的信息素会逐渐消失, 在所有蚂蚁完成一次循环后要更新信息素.每次循环之后, 只有最优的蚂蚁进行信息素更新.最优解可以是迭代最优解, 也可以是全局最优解, 还可以是两者的混合策略, 本文中采用全局最优解更新信息素, 更新公式如下, 其中是最优蚂蚁走过的路径长度

图2 轮盘选择算法Fig.2 Roulette Algorithm

为了防止某条路径上的信息素出现过大或过小导致的搜索停滞状况发生, 本方案采用将每个解元素的信息素浓度限制在内, 一旦超过上限或者低于下限时, 就采用强制手段对其调整, 以提高算法的有效性.为蚂蚁一次搜索找到最优解的概率, 本文中设臵为0.05[12].

本算法采用了信息素平滑策略, 当算法的迭代次数较多的时候, 算法容易陷入停滞状态, 式(11)可以重新设臵环境信息素：

4 实验结果与分析

为了证明本文提出的算法可以有效的降低通信功耗, 本文在Microsoft Visual C++ 6.0环境下完成一系列实验.

4.1 MPEG4解码器任务图

考虑到实际应用, 本文提出的验证方案为采用任务规模为12的MPEG4真实用例, 将MPEG4解码器任务划分成12个子任务, 并将其划分到12个IP核上, 通信状况如图3所示.考虑到实验具有随机性, 本文将实验重复20次, 迭代次数设臵为1000,

图3 MPEG4解码器各IP核间通信图Fig.3 Communications between IP cores on MPEG4 Decoder

4.2 本方案实验结果

本方案由于采用了轮盘选择算法, 避免陷入局部最优, 随着迭代次数的增加每次实验后得到的映射功耗都是逐步收敛的, 并最终趋于一个稳定的结果.

图4是本方案和文献[13]所提方案实验20次的结果, 相比文献[13], 虽然两种方案都具有一定的随机性, 但是本方案在实验中得到的映射功耗变化幅度更小, 全局搜索能力更强, 算法整体稳定性更好.此外, 从图中可以看出, 本方案能调整解的生成方式, 通过设臵信息素浓度的范围以及调整信息素平滑策略, 能更快搜索到最优解, 有效降低映射功耗, 相比文献[13]提出的模拟退火映射算法SASA相比, 映射功耗至少低了5.1%.

图4 本方案与SASA算法性能比较Fig.4 Energy consumption comparisons

5 小结

NoC的出现为越来越多IP核集成在单颗芯片上提供了有效的解决方案.为了降低通信功耗, 在NoC映射设计阶段需要采用特定的映射算法来实现通信任务图与NoC结构图的匹配.因此低映射功耗已成为NoC设计的关键技术之一.本文通过分析NoC的通信功耗与通信流量, 得到它们之间的数学关系模型, 利用最大最小蚁群算法的状态转移规则和信息素更新策略来优化映射函数, 并在算法实现阶段引入轮盘选择算法避免映射结果陷入局部最优等一系列方案来降低映射过程的通信量.实验通过MPEG4真实用例进行验证, 结果表明本文提出的方法具有智能搜索、全局优化、稳健性强等优点, 可以有效降低NoC的通信功耗, 确保片上系统的服务质量, 为即将步入应用的NoC平台设计提供了有益的参考.

[1]LUCA BENINI, GIOVANNI DE MICHELI.Network on chips: A new SoC paradigm[J].IEEE Computer, 2002, 35(1): 70-78.

[2]AXEL JANTSCH, HANNU TENHUNENTORS.Networks on Chip[M].Kluwer Academic Publishers, 2003, 38: 3-18.

[3]WILLIAM J, DALLY, BRIAN, TOWLEs.Route Packets, Not Wires: On-Chip Inter-connection Networks[C].DAC Proceedings, Las Vegas, Nevada, USA: IEEE, 2001.684-689

[4]SHASHI, KUMAR.A network on chip architecture and design methodology[C].VLSI Proceedings, IEEE Computer Society Annual Symposium, Pittsburgh, PA, USA: IEEE, 2002.

[5]HU J, MARCULESCU R.Energy-Aware Mapping for Tile-Based NoC Architectures Under Performance Constraints[C].DAC Proceedings, Anaheim, CA, USA: IEEE, 2003.

[6]CHANG ZHENGWEI, XIE XIAONA, SANG NAN, et al.An Improved Tabu Search Algorithm for Network-on—Chip Mapping[J].Journal of Computer-Aided Design and Computer Graphics, 2008, 20(2): 155-160.

[7]孙榕, 林正浩.基于遗传算法的NoC处理单元映射研究[J].计算机科学, 2008, 35(4): 51-54

[8]BJERREGARD T, MAHADEVAN S.A Survey of Research and Practice of Network on Chip[J].ACM, 2006, 38(1):1-51.

[9]HU JINGCAO.Design Methodologies for Application Specific Network-on-Chip[C].Proceedings of IEEE Computer Society Annual Symposium, Washington, DC, USA,2002.

[10] LEI T, KUMAR S.A two-step genetic algorithm for mapping task graphs to a network on chip architecture[C].Proceedings of the Euromicro Symposium on Digital System Design, Belek-Antalya, Turkey , 2003.

[11] ZHOU H, TIE L, LI J, et al.Improved proxy multi-signature scheme[J].Journal of Shanghai JiaoTong University, 2004, 38(1): 83-86.

[12] 吴春明, 陈治, 姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报, 2006, 34(8): 1530-1534.

[13] 车晶, 张瑛.基于自适应模拟退火的NoC映射算法[J].计算机工程与应用, 2012, 48(23): 58-62.

Mapping method with low power for NoC based on MMAS

LIU Bei
(Modern Education Technology Center, Anhui Polytechnic University, Wuhu 241000, P.R.C.)

Traffic and power of communication on chips has been increasing with the improvement of chip integration.The power consumption must be considered in the stage of design.The new mapping algorithm is proposed on how to reduce the communication power on NoC.The improved max-min ant system method can get a better performance by updating the pheromone, optimizing the weight coefficients and the state transition rules.Experimental results showed that the proposed algorithm could reduce the power consumption of the system with the compared method and had a good convergence which could accelerate the search process and avoid the stagnation.

network on chip; low power; mapping algorithm

TN47;TP18

A

1003-4271(2014)06-0889-06

10.3969/j.issn.1003-4271.2014.06.16

2014-09-23

刘蓓(1980-), 女, 汉族, 安徽芜湖人, 助理工程师, 硕士.

安徽省教育厅教研基金资助项目(2012jyxm280、2012jyxm870); 高校省级自然科学研究基金资助项目(KJ2012B022); 安徽工程大学青年科研基金资助项目(2013YQ32)