一种低能耗的片上网络映射算法

doi:10.3969/j.issn.1001-2400.2011.04.017

Abstract

Abstract:

A mapping algorithm based on catastrophic genetic annealing is proposed, aiming at the mapping problem of low-energy consumption network-on-chip (NoC) that satisfies bandwidth constraints. Derived from a standard genetic algorithm, the proposed algorithm introduces the Boltzmann selection method and optimizes the optimum individuals upon genetic manipulation by the multi-neighborhood simulated annealing operation. Besides, some poor individuals belonging to the population in stagnation are re-initialized by catastrophic operations to jump out of local extreme values. Experimental results suggest that the presented algorithm has the advantages over the standard genetic algorithm of better optimizing performance and faster convergence. The algorithm can also save 21.7% energy on average compared to the chaos genetic algorithm in mapping results, thus effectively reducing the energy consumption of NoC system communications.

Key words: network-on-chip, mapping algorithm, low-energy consumption, genetic annealing, catastrophe

CLC Number:

TP301.6

ZHANG Jianxian;ZHOU Duan;YANG Yintang;LAI Rui;GAO Xiang. Low energy consumption mapping algorithm for the network-on-chip[J].J4, 2011, 38(4): 95-100.

References

［1］ Dally W J, Towles B. Route Packets, Not Wires: On-chip Interconnection Networks ［C］//Proceedings of Design Automation Conference (DAC). Las Vegas: ACM, 2001: 683-689.
［2］刘毅, 杨银堂, 梅伟锋, 等. 一种片上网络路由器间互连线的自适应驱动方法［J］. 西安电子科技大学学报, 2010, 37(1): 28-32.
Liu Yi, Yang Yintang, Mei Weifeng, et al. Adaptive Drive Approach for Interconnection Lines between NoC Routers［J］. Journal of Xidian University, 2010, 37(1): 28-32.
［3］ Hu J, Marculescu R. Energy-aware Mapping for Tile-based NoC Architectures under Performance Constraints ［C］//Proceedings of Asia South Pacific Design Automation Conference. Kitakyushu: ACM, 2003: 233-239.
［4］ Bhardwaj K, Jena R K. Energy and Bandwidth Aware Mapping of IPs onto Regular NoC Architectures Using Multi-Objective Genetic Algorithms ［C］//Proceedings of the 11th International Conference on System-on-chip. Tampere: IEEE, 2009: 27-31.
［5］ 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: IEEE Computer Society, 2003: 180-187.
［6］ Moein-Darbari F, Khademzade A, Gharooni-Fard G. CGMAP: a New Approach to Network-on-Chip Mapping Problem ［J］. IEICE Electronics Express, 2009, 6(1): 27-34.
［7］ Shi H. An Improved Hybrid Genetic Algorithms Using Simulated Annealing ［C］//2009 Second International Symposium on Electronic Commerce and Security. Nanchang: IEEE Computer Society, 2009: 462-465.
［8］金希东, 李治. 遗传-灾变算法及其在非线性控制系统中的应用［J］. 系统仿真学报, 1997, 9(2):111-115.
Jin Xidong, Li Zhi. Genetic-catastrophic Algorithms and Its Application in Nonlinear Control System［J］. Proceedings of System Simulation, 1997, 9(2): 111-115.
［9］韩丽霞, 王宇平. 图着色问题的新遗传算法［J］. 西安电子科技大学学报, 2008, 35(2): 309-313.
Han Lixia, Wang Yuping. Novel Genetic Algorithm for the Graph Coloring Problem ［J］. Journal of Xidian University, 2008, 35(2): 309-313.
［10］高延峰, 许瑛. 混沌遗传模拟退火组合算法性能研究［J］. 计算机应用与软件, 2008, 25(11): 238-267.
Gao Yanfeng, Xu Ying. Study on the Performance of Chaos Genetic Simulated Annealing hybrid Algorithm ［J］. Computer Applications and Software, 2008, 25(11): 238-267.
［11］ Dick R P, Rhodes D L, Wolf W. TGFF: Task Graphs for Free ［C］//Proceedings of the 6th International Workshop on Hardware/Software Codesign. Seattle: IEEE Computer Society, 1998: 97-101.

[1]	ZANG Mingxiang;WANG Meng;ZHOU Wenhong;CHEN Huicang. Improved shuffled frog-leaping algorithm for low-power network-on-chip mapping [J]. J4, 2015, 42(1): 118-123.
[2]	ZANG Mingxiang;WANG Ting;ZHOU Wenhong. Low energy consumption NoC mapping algorithm based on the modified electromagnetism-like mechanism [J]. J4, 2014, 41(4): 82-86+93.
[3]	CUI Yuanyuan;QIU Xuehong;ZHANG Jianxian;ZHOU Duan. SoC hardware/software partitioning algorithm for multi-performance index constraints [J]. J4, 2013, 40(5): 92-98.
[4]	LIU Yi;CHEN Bo;YANG Yintang;LIU Gang. High-speed low-power clock network design for NoC [J]. J4, 2013, 40(3): 115-120.
[5]	DENG Zhi;GU Huaxi;YANG Yintang;ZENG Daibing. Artificial bee colony based low-energy consumption high-performance mapping in NoC [J]. J4, 2012, 39(2): 114-119.
[6]	LIU Yi;YANG Yintang;ZHOU Donghong. Multi-clock router designed for the network-on-chip [J]. J4, 2011, 38(2): 146-150.
[7]	YANG Lu;LI Ming;ZHANG Peng. New improved particle filter algorithm [J]. J4, 2010, 37(5): 862-865+883.
[8]	LIU You-yao;HAN Jun-gang. Star-cluster double-loop topology for the network-on-chip [J]. J4, 2009, 36(6): 1063-1069.
[9]	Lü Ling;YU Hong-yi;GUO Jin-huai. Performance analysis of physical-layer network coding based on the MAP mapping algorithm [J]. J4, 2007, 34(7): 55-58.

Low energy consumption mapping algorithm for the network-on-chip

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 9

Metrics

Comments

Recommended 10