A ROUTING ALGORITHM AND A ROUTER ARCHITECTURE FOR 3D NOC

Somasundaram Kanagasabapathi, Chythanya Calicut

Abstract


In recent years, the enhancement of microchip technologies has enabled large scale Systems-on-Chip (SoC). Due to sharp increase in number of processing elements, SoC faces various challenges in design and testing.  Network on Chip (NoC) is an alternative technology to overcome the challenges in SoC design and testing. NoC emerged as a key architecture that allows one to optimize the parameters like power and area. In spite of its applications, NoC faces some real time challenges like designing an optimum topology, routing scheme and application mappings. In this paper, we address the main three issues on NoC, namely, designing of an optimal topology, routing algorithm and a router design for the topology. First, we propose a topology and a routing algorithm. We prove that our recursive network topology is Hamiltonian connected and we propose an algorithm for data packet transmissions, which is free from cyclic deadlocks and the algorithm maximizes the congestion factor. Our experimental results show that the proposed topology gives better performance in terms of average latency and power than the other topologies. Finally, we propose a router architecture for our 3D-NoC. The router architecture is based on shared buffers. Also, our experimental results indicate that the proposed router architecture consumes less area and power than the Virtual Channel architecture.

Keywords


Network on Chip; 3D topology; Router.

Full Text:

PDF

References


bibitem{IEEEhowto:Dubois} F. Dubois, A. Sheibanyrd, F. Petrot, M. Bahmani, Elevator-First: a Dealock-free distributed routing algorithm for vertically partially connected 3d-Nocs, IEEE Transactions on Computers 2013; 62(3): 609-615.

bibitem{IEEEhowto:Michel} G.De. Michel, L. Benini, Network on Chips: Technology and Tools, Morgan Kaufmann Publishers, 2006.

bibitem{IEEEhowto:Rantala} V. Rantala, T. Lehtonen, J. Plosila, Network on Chip Routing Algorithms. TUCS Technical Report, Turku Centre for Computer Science, 2006.

bibitem{IEEEhowto:Feero} B.S. Feero, P.P. Pande, Networks-on-Chip in a three-Dimensional Enviroment: A Performance Evaluation, IEEE Transactions on Computers 2009; 58(1): 32-45.

bibitem{IEEEhowto:Hsieh} A. C. Hsieh, T. T. Hwang, M. T. Chang, M. H. Tsai, C. M. Tseng, H. C. Li, TSV Redundancy: Architecture and Design Issues in 3D IC, in:Proceeding of the conference Design, Automation and Test in Europe (DATE) 2010, 166-171.

bibitem{IEEEhowto:Davis} W.R. Davis, J. Wilson, S. Mick, J. Xu, H. Hua, C. Mineo, A.M. Sule, M. Steer, P.D. Franzon, Demystifying 3D Ics: The Pros and cons of going vertical, IEEE Design and Test of Computers 2005; 22(6): 498-510.

bibitem{IEEEhowto:Anido} G.J. Anido, A.W. Seeto, Multipath Interconnection: A Technique for Reducing Congestion within Fast Packet Switching Fabrics, IEEE Journal on Selected Areas in Communications 1988; 6(9): 1480-1488.

bibitem{IEEEhowto:Banner} R. Banner, A. Orda, Multipath Routing Algorithms for Congestion Minimization, IEEE Transaction on Networking 2007; 15(2): 413-424.

bibitem{IEEEhowto: Faloutsos} M. Faloutsos, P. Faloutsos, C. Faloutsos, On power-law relationships of the Internet topology, in:Proceedings of ACM SIGCOMM 1999, pp.251-262.

bibitem{IEEEhowto:Wang} H. Wang, X. Zhu,, L.S Peh, S. Malik, Orion: A Power Performance Simulator for Interconnection Networks, in:Proceeding of the MICRO Conference-2002; 294-305.

bibitem{IEEEhowto:Bjerregaard} T. Bjerregaard, S. Mahadevan, A Survey of Research and Practices of Network on Chip, ACM computing survey 2006; 38: 1-51.

bibitem{IEEEhowto:Somasundaram} K. Somasundaram, J.Plosila, Deadlock free Routing Algorithm for Minimizing Data Packet Transmission in Network on Chip, International Journal of Embedded and Real Time Communication Systems 2012; 3(1): 70-18.

bibitem{IEEEhowto:Hanssson} A. Hanssson, K. Goossens, A. Radulescu, A Unified Approach to Mapping and Routing on a Network-on-Chip for both Best-Effort and Guaranteed Service Traffic, VLSI Design 2007; 2007: 1- 16.

bibitem{IEEEhowto:Jia} Y. Jia, I. Nikolaidis, P. Gburzynki, Multiple path QoS routing, in:Proceedings of the ICC-2001, 2583-2587.

bibitem{IEEEhowto:Rusu} C. Rusu, L. Anghel, D. Avresky, Adaptive inter-layer message routing in 3D etworks-on-chip, Journal of Microprocessors and Microsystems 2012; 35: 613-631.

bibitem{IEEEhowto:Vishwanathan} N. Vishwanathan, K. Paramasivan, K. Somasundaram, An Optimized 3D topology for On Chip Communications, International Journal of Parallel, Emergent and Distributed Systems (submitted).

bibitem{IEEEhowto:Zhou} P. Zhou, P. H. Yuh, S. S. Sapatnekar, Optimized 3D Network-on-Chip Design using simulated allocation, ACM Transactions on Design Automation of Election Systems 2012; 17(2); 12.1-12.19.

bibitem{IEEEhowto:Chen} Y. Chen, J. Hu, X. Ling, T. Huang, A novel 3D NoC architecture based on De Bruijn Graph, Journal of Computer and Electrical Engineering 2012; 38: 801-810.

bibitem{IEEEhowto:Holsmark} R. Holsmark, M. Palesi, S. Kumar, Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions, Journal of System Architecture 2008; 54:427-440.

bibitem{IEEEhowto:Luo} W. Luo, D. Xiang, An Efficient Adaptive Deadlock-Free Routing algorithm for Torus Networks, IEEE Transactions on Parallel and Distributed Systems 2012; 23(5): 800-808.

bibitem{IEEEhowto:Fu} J.S. Fu, Hamiltonian connectivity of the WK-recursive network with faulty nodes, Information Sciences 2008; 178: 2573-2584.

bibitem{IEEEhowto:Gross} Gross, J.L., and Yellen J, Graph Theory and its Applications. Hchapman and Hall/CRC publications, 2006.

bibitem{r23} R.K. Ahuja, T.L. Mananti, J.B. Orlin, Network Flows: Theory, Algorithm, and Applications, Englewood Cliffs, NJ: Printice-Hall, 1993.

bibitem{IEEEhowto:Murali} S. Murali, D. Atienza, L. Benini, G. De Micheli, A Method for Routing Packets Across Multiple paths in NoCs with In-Order Delivery and Fault-Tolerance Guarantees, VLSI Design, Special issue on Network on Chip 2007; Vol.2007: 1-11.

bibitem{IEEEhowto:Orlin} J. B. Orlin, Kamesh Madduri, K. Subramani, M. Williamso, A faster algorithm for the single source path problem with few distinct positive lengths, Journal of Discrete Algorithm 2010; 8(2), 189-198.

bibitem{IEEEhowto:Dally} W.J. Dally, C.L. Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE Transactions on Computers 1987; 36(5): 547 – 553.

bibitem{Sahu} P K Sahu and S Chattopadhyay, A survey on application mapping strategies for Network-on-Chip design, Journal of System Architecture, 2013, Vol.59, 60-76.

bibitem{Salma} Salma Hesham, Jens Rettkowski, Diana Goehringer, and Mohamed A. Abd El Ghany, Survey on Real-Time Networks-on-Chip, IEEE Transactions on Parallel and Distribute Systems, 2017, Vol28(5), 1500-1517.

bibitem{Wang} Y Wang, Y HeHan, L Zhang, B Z Fu, C Liu, H WeiLi, and X Li, Economizing TSV Resources in 3-D Network-on-Chip Design, IEEE Transaction on VLSI Systems, 2015, Vol.23 (3), 493-506.

bibitem{Silva} L Silva, N Nedjahb and L De M Mourellec, Efficient routing in network-on-chip for 3D topologies, International Journal of Electronics, 2015, Vol. 102 (10), 1695–1712.

bibitem{Ahmed} A B Ahmed and A B Abdallah, Graceful deadlock-free fault-tolerant routing algorithm for 3D Network-on-Chip architectures, Journal of Parallel Distributed Computing, 2014, Vol.74, 2229–2240.

bibitem{Eghbal} A Eghbal, P M Yaghini, N Bagherzadeh and M Khayamb, Analytical Fault Tolerance Assessment and Metrics for TSV-Based 3D Network-on-Chip, IEEE Transactions on Computers, 2015, Vol.64 (12), 3591-3604.

bibitem{IEEEhowto:Tatas} K Tatas, K Siozios, D Soudris and A Jantsch, Designing 2D and 3D Network-on-Chip Architectures, Springer, 2014.

bibitem{IEEEhowto:Somasundaram} K Somasundaram, J plosila and N Vishwanathan, Deadlock free routing algorithm for minimizing congestion in a Hamiltonian connected recursive 3D-NoCs, Microelectronics Journal, 2014, Vol.(45), 989-1000.

bibitem{IEEEhowto:Tram} Ann T. Tram and Bevan M. Baas, Achieving high performance on-chip networks with Shared-Buffer Routers, IEEE Transactions on Very Large Scale Integration Systems, 2014, Vol.22 (6), 1391-1403.

bibitem{IEEEhowto:} W. J. Dally, Virtual-channel flow control, IEEE Transactions on Parallel Distributive Systems, 1992, Vol 3(2), 194–205.

bibitem{IEEEhowto:Itzhak} Y B Itzhak, I Cidon, A Kolodny, M Shabun and N Shmuel, Hetrogeneous NoC Router Architecture, IEEE Transactions on Parallel and Distributed Systems, 2015, Vol26 (9), 2479-2492.

bibitem{IEEEhowto:Gharan} M O Gharan and G N Khan, Efficient Dynamic Virtual channel Organization and Architecture for NoC Systems, IEEE Transactions on Very Large Scale Integration Systems, 2016, Vol.24 (2), 465-478.

bibitem{IEEEhowto:Seitanidis} I Seitanidis, A Psarras, K Chrysanthou, C Nicopoulos and G Dimitrakopoulos, ElastiStore: Flexible Elastic Buffering for Virtual Channel Based Network on chip, IEEE Transactions on Very Large Scale Integration Systems, 2014, Vol.23 (12), 3015 - 3028.

bibitem{IEEEhowto:ABKahng} Andrew B. Kahng, Bin Li, Li-Shiuan Peh and Kambiz Samadi, ORION 2.0: A Fast and Accurate NoC Power and Area Model for Early stage Design Space Exploration, In proceedings of EDAA 2009, 423-428.

bibitem{IEEEhowto:PPoluri} Pavan Poluri and Ahmed Louri, Shield: A Reliable Network-on-Chip Router Architecture for Chip Microprocessors, IEEE Transactions on Parallel and Distributed Systems, 2016, Vol.27 (10), 3058 - 3070.

bibitem{MaMo} Mamaghani, Shokoofeh Mikaeeli, and Mohammad Ali Jabraeil Jamali. "An adaptive congestion-aware routing algorithm based on network load for wireless routers in wireless network-on-chip." AEU-International Journal of Electronics and Communications 97 (2018): 25-37.

bibitem{VMPLT} Valinataj, M., Mohammadi, S., Plosila, J., Liljeberg, P., & Tenhunen, H. (2011). A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip. AEU-International Journal of Electronics and Communications, 65(7), 630-640.




DOI: https://doi.org/10.7494/csci.%25Y.%25v.%25i.3303

Refbacks

  • There are currently no refbacks.