基于动态自适应离散粒子群算法的3D NoC低功耗映射方法

doi:10.11959/j.issn.1000-436x.2016215

通信学报 ›› 2016, Vol. 37 ›› Issue (11): 23-30.doi: 10.11959/j.issn.1000-436x.2016215

基于动态自适应离散粒子群算法的3D NoC低功耗映射方法

刘勤让,戴启华,沈剑良,赵博

国家数字交换系统工程技术研究中心，河南郑州 450000

出版日期:2016-11-25 发布日期:2016-11-30
基金资助:
国家高技术研究发展计划（“863”计划）基金资助项目;国家自然科学基金创新群体基金资助项目;国家自然科学基金面上基金资助项目

Dynamic adaptive discrete particle swarm optimization algorithm based method on low-power mapping in network-on-chip

Qin-rang LIU,Qi-hua DAI,Jian-liang SHEN,Bo ZHAO

National Digital Switching System Engineering＆Research Center, Zhengzhou 450000, China

Online:2016-11-25 Published:2016-11-30
Supported by:
The National High Technology Research and Development Program of China (863 program);The Innovation Group Program Project of National Natural Science Foundation of China;The General Program of National Natural Science Foundation of China

摘要/Abstract

摘要：

相对于2D NoC,3D NoC具有更好的集成度和系统性能，是解决低功耗映射的一个可靠途径。在传统粒子群算法(PSOA, particle swarm optimization algorithm)的基础上，提出了一种动态自适应离散粒子群算法(DADPSOA, dynamic adaptive discrete particle swarm optimization algorithm)。该算法基于早熟收敛程度和个体适应度值变化动态调整参数ω，不断靠近最优解；同时对粒子进行合理的解构造，减小了算法时间复杂度。仿真结果表明，与随机映射、遗传算法(GA, genetic algorithm)、PSOA和动态蚁群算法(DACA, dynamic ant colony algorithm)相比，DADPSOA可以缩短执行时间，减小映射结果通信功耗；在面向任务图映射的时候，其通信功耗下降。

关键词: 3DNoC, 低功耗映射, 解构造, 自适应离散粒子群算法

Abstract:

Compared to 2D NoC, 3D NoC has better integrated density and system performance, which was a reliable method to solve the problem about low-power mapping. On the basis of the traditional particle swarm optimization algo-rithm (PSOA), a dynamic adaptive discrete particle swarm optimization algorithm (DADPSOA) was proposed . Parame-ter in this algorithm was adjusted dynamically based on the degree of early convergence and the charge of individual adap-tive value to approach the optimal solution. At the same time, the reasonable structure of the particles was made aiming at reducing the time complexity of this algorithm. Experimental results show that comparing with the random mapping, genetic algorithm (GA), PSOA and dynamic ant colony algorithm (DACA), DADPSOA can save the execution time, reduce the communication power consumption of mapping results. The power consumption of the task graph is reduced.

Key words: 3D NoC, low-power mapping, deconstruction, adaptive discrete particle swarm optimization algorithm

刘勤让,戴启华,沈剑良,赵博. 基于动态自适应离散粒子群算法的3D NoC低功耗映射方法[J]. 通信学报, 2016, 37(11): 23-30.

Qin-rang LIU,Qi-hua DAI,Jian-liang SHEN,Bo ZHAO. Dynamic adaptive discrete particle swarm optimization algorithm based method on low-power mapping in network-on-chip[J]. Journal on Communications, 2016, 37(11): 23-30.

图/表 11

图1

图2

图3

表1

算法复杂度对比"

算法	算法复杂度
ILP	$\frac{N_{4}!}{(N_{4} - N_{2})!}$
GA	N₁N₂²N₄
DACA	N₁N₂²N₃
PSOA	N₄⁵ln N₄+ N₁N₂N₄²ln N₄
DADPSOA	N₁N₂N₃

表1

表2

图4

图6

图5

表3

表4

图7

参考文献 18

[1]	LE Q , YANG G , HUNG W N N , et al. Pareto optimal mapping for tile-based network-on-chip under reliability constraints[J]. Interna-tional Journal of Computer Mathematics, 2015,92(1):41-58.
[2]	KUMAR S , JANTSCH A , SOININEN J P , et al. A network on chip architecture and design methodology[C]// VLSI, 2002. IEEE Computer Society Annual Symposium. IEEE, Pittsburgh, Pennsylvania, 2012:105-112.
[3]	SAHU P K , CHATTOPADHYAY S . A survey on application mapping strategies for network-on-chip design[J]. Journal of Systems Architec-ture, 2013,59(1):60-76.
[4]	BJERREGAARD T , MAHADEVAN S . A survey of research and practices of network-on-chip[J]. ACM Computing Surveys (CSUR), 2006,38(1):1.
[5]	ELMILIGI H , EL-KHARASHI M W , GEBALI F . Power consumption of 3D networks-on-chips: modeling and optimization[J]. Microproc-essors and Microsystems, 2013,37(6):530-543.
[6]	CHENG Y , ZHANG L , HAN Y , et al. Thermal-constrained task allo-cation for interconnect energy reduction in 3D homogeneous mpsocs[J]. Very Large Scale Integration (VLSI) Systems, IEEE Transactions, 2013,21(2):239-249.
[7]	TOSUN S , OZTURK O , OZEN M . An ILP formulation for application mapping onto Network-on-Chips[C]// Application of Information and Communication Technologies, 2009. AICT 2009. International Con-ference IEEE, Baku, Azerbaijan. 2009:1-5.
[8]	PLANIVELOO V A , AMBROSE J A , SOWMYA A , et al. Improving GA-based NoC mapping algorithms using a formal model[C]// VLSI (ISVLSI), 2014 IEEE Computer Society Annual Symposium. IEEE, Florida, USA, 2014:344-349.
[9]	王佳文，李丽，易伟，等． 3D NoC 映射问题的动态蚁群算法[J]. 计算机辅助设计与图形学学报, 2011,23(9):1614-1620. WANG J W , LI L , YI W , et al. A dynamic ant colony optimization al-gorithm for 3D NoC mapping[J]. Journal of Computer-Aided Design＆ Computer Graphics. 2011,23(9):1614-1620.
[10]	杨盛光，李丽，高明伦，等．面向能耗和延时的 NoC 映射方法[J]. 电子学报, 2008,36(5):937-942. YANG S G , LI L , GAO M L , et al. An energy-and delay-aware map-ping method of NoC[J]. Acta Electronic Sinica, 2008,36(5):937-942.
[11]	RAHMANI A M , LILJEBERG P , PLOSILA J , et al. Developing a power-efficient and low-cost 3D NoC using smart GALS-based verti-cal channels[J]. Journal of Computer and System Sciences, 2013,79(4):440-456.
[12]	ZHANG T , WU N , ZHOU F , et al. A traffic equilibrium mapping method with energy minimization for 3D NoC-Bus mesh architec-ture[J]. IAENG International Journal of Computer Science, 2015,42(1):1-7.
[13]	WANG X , PALESI M , YANG M , et al. Power-aware run-time incre-mental mapping for 3-D networks-on-chip[C]// Network and Parallel Computing. Springer Berlin Heidelberg, 2011:232-247.
[14]	李东生，刘琪 . 面向通信能耗的3D NoC映射研究[J]. 半导体技术, 2012,37(7):504-507. LI D S , LIU Q . Research on mapping 3D network on chip for commu-nication energy-aware[J]. Semiconductor Technology, 2012,37(7):504-507.
[15]	史峰，王辉，郁磊，等． Matlab 智能算法30个案例分析[M]. 北京航空航天大学出版社, 2011. SHI F , WANG H , YU L , et al. Matlab intelligent algorithm analusis of 30 cases[M]. Beihang University Press, 2011.
[16]	SAHU P K , SHAH T , MANNA K , et al. Application mapping onto mesh-based network-on-chip using discrete particle swarm optimiza-tion[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014,22(2):300-312.
[17]	DICK R P , RHODES D L , WOLF W . TGFF: task graphs for free[C]// The 6th International Workshop on Hardware/Software codesign. IEEE Computer Society. 1998:97-101.
[18]	Available online[EB/OL]. , 2015.4.29.

任务图	逻辑IP核数	通信边	通信总量/(Mbit·s^?1)
MPEG-4	12	13	3 466
VOPD	16	21	3 471
263 Enc	12	12	230.214

TGFF任务图	逻辑IP核数	ARCG大小			通信功耗比例
			DADPSOA	DADPSOA		DADPSOA	DADPSOA
			Random	GA		PSOA	DACA
G1	27	3×3×3	42.53%	78.68%		84.31%	93.26%

任务图		链路负载方差
	DADPSOA	DADPSOA	DADPSOA
	GA	PSOA	DACA
MPEG-4	84.64%	88.16%	93.12%
G1	86.83%	91.45%	96.62%

基于动态自适应离散粒子群算法的3D NoC低功耗映射方法

Dynamic adaptive discrete particle swarm optimization algorithm based method on low-power mapping in network-on-chip

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 18

相关文章 0

Metrics

推荐阅读 0