A routing algorithm and a router architecture for 3D NoC

• Autorzy: Kanagasabapathi Somasundaram , Calicut Chythanya

Identyfikatory

DOI

10.7494/csci.2019.20.3.3303

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

3D topology; router; network on chip; routing algorithm

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2019
• Tom: Vol. 20 (3)
• Strony: 369--383
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Kanagasabapathi Somasundaram

• Amrita School of Engineering-Coimbatore, Department of Mathematics, Amrita VishwaVidyapeetham, India

autor

Calicut Chythanya

• Amrita School of Engineering-Coimbatore, Department of ECE, Amrita VishwaVidyapeetham, India

Bibliografia

• [1] Ahmed A.B., Abdallah A.B.: Graceful deadlock-free fault-tolerant routing algorithm for 3D Network-on-Chip architectures, Journal of Parallel Distributed Computing, vol. 74, pp. 2229–2240, 2014.
• [2] Banner R., Orda A.: Mutlipath Routing Algorithms for Congestion Minimization, IEEE Transection on Networking, vol. 15(2), pp. 413–424, 2007.
• [3] Ben-Itzhak Y., Cidon I., Kolodny A., Shabun M., Shmuel N.: Hetrogeneous NoC Router Architecture, IEEE Transactions on Parallel and Distributed Systems,vol. 26(9), pp. 2479–2492, 2015.
• [4] Bjerregaard T., Mahadevan S., A Survey of Research and Practices of Networkon Chip, ACM Computing Survey, vol. 38, pp. 1–51, 2006.
• [5] Davis W.R., Wilson J., Mick S., Xu J., Hua H., Mineo C., Sule A.M., Steer M., Franzon P.D.: Demystifying 3D ICs: the pros and cons of going vertical, IEEEDesign and Test of Computers, vol. 22(6), 498–510, 2005.
• [6] De Micheli G., Benini L.:Network on Chips: Technology and Tools, MorganKaufmann Publishers, San Francisco CA, 2006.
• [7] Dubois F., Sheibanyrad A., Pétrot F., Bahmani M.: Elevator-First: A Deadlock-Free Distributed Routing Algorithm for Vertically Partially Connected 3D-NoCs,IEEE Transactions on Computers, vol. 62, pp. 609–615, 2013.
• [8] Eghbal A., Yaghini P.M., Bagherzadeh N., Khayamb M.: Analytical Fault Toler-ance Assessment and Metrics for TSV-Based 3D Network-on-Chip,IEEE Transactions on Computers, vol. 64(12), pp. 3591–3604, 2015.
• [9] Feero B.S., Pande P.P.: Networks-on-Chip in a Three-Dimensional Enviroment: A Performance Evaluation,IEEE Transactions on Computers, vol. 58(1),pp. 32–45, 2009.
• [10] Hesham S., Rettkowski J., Goehringer D., Abd El Ghany M.A.: Survey on Real-Time Networks-on-Chip, IEEE Transactions on Parallel and Distribute Systems,vol. 28(5), pp. 1500–1517, 2017.
• [11] Holsmark R., Palesi M., Kumar S.: Deadlock free routing algorithms for irreg-ular mesh topology NoC systems with rectangular regions, Journal of System Architecture, vol. 54, pp. 427–440, 2008.
• [12] Kahng A.B., Li B., Peh L.-S., Samadi K.: ORION 2.0: A fast and accurate NoC power and area model for early stage design space exploration. In:Proceedings of 2009 Design, Automation&Test in Europe Conference&Exhibition, pp. 423–428, 2009.
• [13] Luo W., Xiang D.: An Efficient Adaptive Deadlock-Free Routing Algorithmfor Torus Networks, IEEE Transactions on Parallel and Distributed Systems,vol. 23(5), pp. 800–808, 2012.
• [14] Mamaghani S.M., Jamali M.A.J., 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, vol. 97, pp. 25–37,2018.
• [15] Oveis-Gharan M., Khan G.N.: Efficient Dynamic Virtual Channel Organizationand Architecture for NoC Systems,IEEE Transactions on Very Large Scale Integration Systems, vol. 24(2), pp. 465–478, 2016.
• [16] Poluri P., Louri A.: Shield: A Reliable Network-on-Chip Router Architecture for Chip Microprocessors, IEEE Transactions on Parallel and Distributed Systems,vol. 27(10), pp. 3058–3070, 2016.
• [17] Rusu C., Anghel L., Avresky D.: Adaptive inter-layer message routing in3D networks-on-chip,Journal of Microprocessors and Microsystems, vol. 35,pp. 613–831, 2011.
• [18] Sahu P.K., Chattopadhyay S.: A survey on application mapping strategies forNetwork-on-Chip design, Journal of System Architecture, vol. 59, pp. 60–76, 2013.
• [19] Seitanidis I., Psarras A., Chrysanthou K., Nicopoulos C., Dimitrakopoulos G.:ElastiStore: Flexible Elastic Buffering for Virtual-Channel-Based Networks onChip,IEEE Transactions on Very Large Scale Integration Systems, vol. 23(12),pp. 3015–3028, 2014.
• [20] Silva Jr. L., Nedjah N., De Macedo Mourelle L.: Efficient routing in network-on-chip for 3D topologies,International Journal of Electronics, vol. 102(10),pp. 1695–1712, 2015.
• [21] Somasundaram K., Plosila J.: Deadlock Free Routing Algorithm for Minimizing Data Packet Transmission in Network on Chip, International Journal of Embedded and Real Time Communication Systems, vol. 3(1), pp. 70–81, 2012.
• [22] Somasundaram K., Plosila J., Vishwanathan N., Deadlock free routing algorithmfor minimizing congestion in a Hamiltonian connected recursive 3D-NoCs, Microelectronics Journal, vol. 45, pp. 989–1000, 2014.
• [23] Tatas K., Siozios K., Soudris D., Jantsch A.:Designing 2D and 3D Network-on-Chip Architectures, Springer-Verlag, New York, 2014.
• [24] Tran A.T., Baas B.M., Achieving High Performance On-Chip Networks WithShared-Buffer Routers,IEEE Transactions on Very Large Scale Integration Systems, vol. 22(6), pp. 1391–1403, 2014.
• [25] Valinataj M., Mohammadi S., Plosila J., Liljeberg P., Tenhunen H.: A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip,AEU International Journal of Electronics and Communications, vol. 65(7),pp. 630–640, 2011.
• [26] Viswanathan N., Paramasivan K., Somasundaram K.: An optimised 3D topology for on-chip communications,International Journal of Parallel, Emergent and Distributed Systems, vol. 29(4), pp. 346–362, 2013.
• [27] Wang Y., Han Y.-H., Zhang L., Fu B.-Z., Liu C., Li H.-W., Li X.: Economizing TSV Resources in 3-D Network-on-Chip Design,IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23(3), pp. 493–506, 2015.