一种面向功耗免死锁三维全动态3DNoC路由算法

doi:10.3969/j.issn.0372-2112.2013.02.019

电子学报 ›› 2013, Vol. 41 ›› Issue (2): 329-334.DOI: 10.3969/j.issn.0372-2112.2013.02.019

一种面向功耗免死锁三维全动态3DNoC路由算法

虞潇, 李丽, 张宇昂, 潘红兵, 王佳文, 韩平

南京大学电子科学与工程学院,江苏南京 210093

收稿日期:2012-04-23 修回日期:2012-08-20 出版日期:2013-02-25
- 通讯作者:
- 李丽
- 作者简介:
- 虞潇 男,1989年生于江苏南京,南京大学硕士生.主要研究方向为3D NoC系统路由算法. E-mail:littlefish520yx@163.com
- 基金资助:
- 国家自然科学基金 (No.61176024,No.60876017)

A Power-Aware Dead Lock Avoid Three-Dimensional Full-Adaptive Routing Algorithm for 3D NoC

YU Xiao, LI Li, ZHANG Yu-ang, PAN Hong-bing, WANG Jia-wen, HAN Ping

School of Electronic Science and Engineering Nanjing University, Nanjing, Jiangsu 210093, China

Received:2012-04-23 Revised:2012-08-20 Online:2013-02-25 Published:2013-02-25

摘要/Abstract

摘要： 随着近年来三维片上网络(3D NoC)技术的提出及不断发展,功耗问题已成为3D NoC设计中面临的严峻挑战之一.本文为3D NoC提出一种面向功耗免死锁三维全动态路由算法TFRA (Three-dimensional Full-adaptive Routing Algorithm).其以传统二维NoC奇偶拐弯模型为基础,将三维路由空间划分为8个象限,针对每个象限制定相应的路由策略,从而实现免死锁.采用SystemC系统级建模语言搭建的3D NoC仿真平台进行验证,结果显示TFRA算法在功耗性能指标方面较现有的三维路由算法有大幅提升.

关键词: 三维片上网络, 图论, 功耗, 路由算法, 三维全动态路由算法

Abstract: With the proposal and development of the technology of 3D NoC in these years,the power issue has become one of the serious challenges in the design of 3D NoC.This paper proposed a power-aware deadlock avoid three-dimensional full-adaptive routing algorithm called TFRA for 3D NoC.The new routing strategy is based on the even-odd turning model of the conventional 2D NoC.The routing space is divided into eight different quadrants in which corresponding routing strategy is used.We use a systematic modeling language SystemC to build the platform of 3D NoC to test and verify the performance.The result shows that great improvement can be achieved considering every kind of index of power performance using our TFRA when compared to the traditional 3D routing algorithm.

Key words: 3D NoC, graph theory, power issue, routing algorithm, three-dimensional full-adaptive routing algorithm(TFRA)

中图分类号:

TP391.7

虞潇, 李丽, 张宇昂, 潘红兵, 王佳文, 韩平. 一种面向功耗免死锁三维全动态3DNoC路由算法[J]. 电子学报, 2013, 41(2): 329-334.

YU Xiao, LI Li, ZHANG Yu-ang, PAN Hong-bing, WANG Jia-wen, HAN Ping. A Power-Aware Dead Lock Avoid Three-Dimensional Full-Adaptive Routing Algorithm for 3D NoC[J]. Acta Electronica Sinica, 2013, 41(2): 329-334.

参考文献

[1] Bryan Black,Murali Annavaram,Ned Brekelbaum,et al.Die stacking (3D) microarchitecture[A].IEEE/ACM International Symposium on Microarchitecture 2006[C].America:IEEE,2006.469-479.
[2] G M Chiu.The odd-even turn model for adaptive routing[J].IEEE Transaction on Parallel and Distributed Systems,2000,11(7):729-738.
[3] Khan,M A,et al.Quadrant-Based XYZ dimension order routing algorithm for 3-D asymmetric torus routing chip[A].International Conference on Networks and Computer Communications (ETNCC) 2011[C].India:IEEE,2011.121-124.
[4] Lafi W,Lattard D,Jerraya A.An efficient hierarchical router for large 3D NoCs[A].21st IEEE International Symposium on Rapid System Prototyping (RSP) 2010[C].America:IEEE,2010.1-5.
[5] Holcomb D,Brady B,Seshia S.Abstraction-based performance verification of NoCs[A].48th ACM/EDAC/IEEE Design Automation Conference(DAC) 2011[C].America:IEEE,2011.492-497.
[6] Viswanathan N,Paramasivam K,Somasundaram K.Performance analysis of cluster based 3D routing algorithms for NoC[A].IEEE Recent Advances in Intelligent Computational Systems (RAICS) 2011[C].India:IEEE,2011.157-162.
[7] Rusu C,et al.Message routing in 3D networks-on-chip .NORCHIP 2009[A].Norway:IEEE,2009.1-4.
[8] Shu-Yen Lin,Tzu-Chu Yin,Hao-Yu Wang,et al.Traffic-and thermal-aware routing for throttled three-dimensional networkon-chip systems[A].International Symposium on VLSI Design Automation and Test (VLSI-DAT) 2011[C].Taiwan:IEEE,2011.1-4.
[9] Rahmani A M,Latif K,Vaddina K R,et al.Power-efficient inter-layer communication architectures for 3D NoC[A].IEEE Computer Society Annual Symposium on VLSI (ISVLSI) 2011[C].India:IEEE,2011.355-356.
[10] 杨盛光,李丽,高明伦,等.面向能耗和延时的NoC映射方法[J].电子学报,2008,36(5):937-942. YANG Sheng-guang,LI Li,GAO Ming-lun et al.An energy-and delay-aware mapping method of NoC[J].Acta Electronica Sinica,2008,36(5):937-942.(in Chinese)
[11] 易伟,王佳文,潘红兵,等.基于蚁群混沌遗传算法的片上网络映射[J].电子学报,2011,39(8):1832-1836. Yi Wei,Wang Jia-wen,Pan Hong-bing et al.Ant colony chaos genetic algorithm for mapping task graphs to a network on chip[J].Acta Electronica Sinica,2011,39(8):1832-1836.(in Chinese)
[12] 朱红雷,彭元喜,等.一种动态分配输入队列的片上虫孔路由器结构[J].电子学报,2010,38(5):1032-1038. Zhu Hong-lei,Peng Yuan-xi,et al.An on-chip wormhole router architecture with dynamically allocated input-queues[J].Acta Electronica Sinica,2010,38(5):1032-1038.(in Chinese)
[13] Kodi A,Morris R,Ditomaso D,et al.Co-design of channel buffers and crossbar organizations in NoCs architectures .IEEE/ACM International Conference on Computer-Aided Design(ICCAD) 2011 .America:IEEE,2011.219-226.
[14] W R Davis,J Wilson,S Mick,et al.Demystifying 3D ICs:the pros and cons of going vertical[J].Design & Test of Computers IEEE,2005,22(6):498-510.
[15] Xu T C,Liljeberg P,Tenhunen H.A study of through silicon via impact to 3D network-on-chip design[A].International Conference on Electronics and Information Engineering (ICEIE) 2010[C].Japan:IEEE,2010.V1-333-V1-337.
[16] Wegner T,Cornelius C,Gag M,et al.Simulation of thermal behavior for networks-on-chip[A].NORCHIP 2010[C].Finland:IEEE,2010.1-4.
[17] Sheng-guang Yang,et al.A power-aware adaptive routing scheme for network on a chip[A].International Conference on ASIC,ASICON'07[C].China:IEEE,2007.1301-1304.

一种面向功耗免死锁三维全动态3DNoC路由算法

A Power-Aware Dead Lock Avoid Three-Dimensional Full-Adaptive Routing Algorithm for 3D NoC

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张旭东, 雷倩倩, 张芳玲, 李弦, 李连碧. 3阶FLFB低通滤波器的最小可接受功耗分析[J]. 电子学报, 2022, 50(6): 1480-1486.
[2]	王强, 李森, 王天施, 刘晓琴. 辅助电路损耗低的并联谐振直流环节逆变器[J]. 电子学报, 2022, 50(11): 2813-2816.
[3]	蒋万春, 廖凯琴. 节能以太网的节能策略综述[J]. 电子学报, 2021, 49(9): 1830-1839.
[4]	欧阳一鸣, 张鹏, 王奇, 安鑫, 梁华国. WiNoC中交叉开关仲裁及路由算法设计[J]. 电子学报, 2021, 49(3): 518-526.
[5]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[6]	张泰江, 李勇军, 赵尚弘, 郑永兴, 辛宁. 基于代数连通度优化的空间信息网络分布式拓扑控制方法[J]. 电子学报, 2020, 48(6): 1162-1168.
[7]	邓飞飞, 解光军, 王晓旸, 程心, 张永强. 量子元胞自动机共面五输入择多门结构的分析与设计[J]. 电子学报, 2020, 48(5): 861-869.
[8]	欧阳一鸣, 贾博远, 李建华, 黄正峰, 梁华国. WiNoC中无线通信拥塞与故障感知的容错路由算法[J]. 电子学报, 2020, 48(4): 662-669.
[9]	魏松杰, 王佳贺, 刘沛龙, 程浩. LEO星座中基于不完全信息的路由联盟博弈策略[J]. 电子学报, 2020, 48(10): 1923-1927.
[10]	刘威, 蒋烈辉, 常瑞. 强物理不可克隆函数的侧信道混合攻击[J]. 电子学报, 2019, 47(12): 2639-2646.
[11]	唐晓庆, 谢桂辉, 佘亚军, 俞杨. 基于MCU的无源Wi-Fi散射通信方法[J]. 电子学报, 2019, 47(10): 2069-2075.
[12]	孙海洋, 陈珍, 杨冠男, 高波. 基于采样精度切换的毫米波无线通信空闲侦听机制研究[J]. 电子学报, 2018, 46(9): 2115-2122.
[13]	卜登立. 基于概率表达式的MPRM电路功耗计算方法[J]. 电子学报, 2018, 46(12): 3060-3067.
[14]	马学彬, 王应彪, 高瑞超, 张晓娟. 具有传输成功率保证的概率路由算法的TTL预测模型[J]. 电子学报, 2018, 46(11): 2679-2687.
[15]	周新平, 孙德刚, 王竹, 欧长海. 一种基于奇异值分解的功耗轨迹筛选方法[J]. 电子学报, 2017, 45(9): 2250-2255.