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

doi:10.3969/j.issn.1001-2400.2011.04.017

J4 ›› 2011, Vol. 38 ›› Issue (4): 95-100.doi: 10.3969/j.issn.1001-2400.2011.04.017

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

张剑贤¹;周端²;杨银堂¹;赖睿¹;高翔¹

(1. 西安电子科技大学微电子学院，陕西西安 710071；
2. 西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2010-05-24 出版日期:2011-08-20 发布日期:2011-09-28
通讯作者: 张剑贤
作者简介:张剑贤(1983-)，男，西安电子科技大学博士研究生，E-mail: jianxianzhang@mail.xidian.edu.cn．
基金资助:
国家杰出青年科学基金资助项目(60725415);国家自然科学资金资助项目(60676009，90407016，60902080)

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

ZHANG Jianxian¹;ZHOU Duan²;YANG Yintang¹;LAI Rui¹;GAO Xiang¹

(1. School of Microelectronic, Xidian Univ., Xi'an 710071， China;
2. School of Computer Science and Technology, Xidian Univ., Xi'an 710071， China)

Received:2010-05-24 Online:2011-08-20 Published:2011-09-28
Contact: ZHANG Jianxian

摘要/Abstract

摘要：

对于满足带宽约束的低能耗片上网络映射问题，提出一种基于灾变遗传退火的映射算法．该算法以标准遗传算法为基础，引入Boltzmann选择方法，对遗传操作后的较优个体采用多邻域的模拟退火操作进行优化，对处于停滞状态的种群使用灾变操作重新初始化部分较差个体，跳出局部极值．实验结果表明: 与标准遗传算法相比，该算法具有优化性能好，收敛速度快的优点，映射结果比混沌遗传算法平均节能21.7%，有效地降低了片上网络系统通信能耗．

关键词: 片上网络, 映射算法, 低能耗, 遗传退火, 灾变

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

中图分类号:

TP301.6

张剑贤;周端;杨银堂;赖睿;高翔. 一种低能耗的片上网络映射算法[J]. J4, 2011, 38(4): 95-100.

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.

参考文献

［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]	臧明相;王勐;周文宏;陈会仓. 改进混合蛙跳优化的片上网络低功耗映射算法[J]. J4, 2015, 42(1): 118-123.
[2]	臧明相;王婷;周文宏. 类电磁优化的片上网络低功耗映射算法[J]. J4, 2014, 41(4): 82-86+93.
[3]	崔媛媛;裘雪红;张剑贤;周端. 多性能指标约束的SoC软硬件划分算法[J]. J4, 2013, 40(5): 92-98.
[4]	刘毅;陈博;杨银堂;刘刚. 一种高速低功耗的NoC时钟网络设计[J]. J4, 2013, 40(3): 115-120.
[5]	姚磊;蔡觉平;李赞;张海林;王韶力. 2D-Mesh结构片上网络无虚通道容错路由算法[J]. J4, 2012, 39(6): 26-33.
[6]	邓植;顾华玺;杨银堂;曾代兵. 基于人工蜂群算法的低能耗高性能NoC映射[J]. J4, 2012, 39(2): 114-119.
[7]	杨延飞;朱樟明;周端;杨银堂. 用于片上网络的延时无关异步动态优先级仲裁器[J]. J4, 2012, 39(1): 42-48+110.
[8]	管旭光；杨银堂；朱樟明. 用于片上网络的准延时不敏感全异步仲裁器[J]. J4, 2011, 38(3): 83-89.
[9]	刘毅;杨银堂;周东红. 一种面向片上网络的多时钟路由器设计[J]. J4, 2011, 38(2): 146-150.
[10]	刘有耀;韩俊刚. 一种星簇双环片上网络拓扑结构[J]. J4, 2009, 36(6): 1063-1069.
[11]	吕凌;于宏毅;郭金淮. 基于MAP映射算法的物理层网络编码性能分析 [J]. J4, 2007, 34(7): 55-58.

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

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

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

Metrics

本文评价

推荐阅读 10