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

doi:10.3969/j.issn.0372-2112.2013.02.019

PDF(3253 KB)

ACTA ELECTRONICA SINICA ›› 2013, Vol. 41 ›› Issue (2) : 329-334. DOI: 10.3969/j.issn.0372-2112.2013.02.019

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

Author information +

History +

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)

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

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. https://doi.org/10.3969/j.issn.0372-2112.2013.02.019

References

[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.