Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs

• Published in: IEEE transactions on very large scale integration (VLSI) systems 2009-03, Vol.17 (3), p.356-369
• Main Authors: Mejia, A., Palesi, M., Flich, J., Kumar, S., Lopez, P., Holsmark, R., Duato, J.
• Format: Article
• Language: English
• Subjects: adaptive routing algorithm; Algorithms; application specific routing algorithm; Application-specific routing; Applied sciences; Circuit properties; Communication switching; Computer networks; Computer science; Datavetenskap; deadlock-free routing; Degradation; Design. Technologies. Operation analysis. Testing; Electric, optical and optoelectronic circuits; Electrical engineering, electronics and photonics; Electronic circuits; Electronics; Elektronik; Elektroteknik, elektronik och fotonik; Energy consumption; Exact sciences and technology; Failure; Fault tolerance; Hardware; Information technology; Informationsteknik; Input-output equipment; Integrated circuits; large on-chip networks; Links; Network topology; Network-on-a-chip; network-on-chip; Networks; networks-on-chip (NoC); Reconfigurable logic; region-based router (RBR); region-based routing mechanism; router architecture; Routing; Routing (telecommunications); routing algorithms; segment-based routing; Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices; Strontium; Studies; Switches; Switching theory; Switching, multiplexing, switched capacity circuits; table-based router; table-based switches; TECHNOLOGY; TEKNIKVETENSKAP; Very large scale integration
• ISSN: 1063-8210; 1557-9999; 1557-9999
• DOI: 10.1109/TVLSI.2008.2012010

An efficient routing algorithm is important for large on-chip networks [network-on-chip (NoC)] to provide the required communication performance to applications. Implementing NoC using table-based switches provide many advantages, including possibility of changing routing algorithms and fault tolerance, due to the option of table reconfigurations. However, table-based switches have been considered unsuitable for NoCs due to their perceived high area and power consumption. In this paper, we describe the region-based routing (RBR) mechanism which groups destinations into network regions allowing an efficient implementation with logic blocks. RBR can also be viewed as a mechanism to reduce the number of entries in routing tables. RBR is general and can be used in conjunction with any adaptive routing algorithm. In particular, we have evaluated the proposed scheme in conjunction with a general routing algorithm, namely segment-based routing (SR) and an application specific routing algorithm (APSRA) using regular and irregular mesh topologies. Our study shows that the number of entries in the table is significantly reduced, especially for large networks. Evaluation results show that RBR requires only four regions to support several routing algorithms in a 2-D mesh with no performance degradation. Considering link failures, our results indicate that RBR combined with SR is able to tolerate up to 7 link failures in an 8times8 mesh. RBR also reduces area and power dissipation of an equivalent table-based implementation by factors of 8 and 10, respectively. Moreover, the degradation in performance of the network is insignificant when using APSRA combined with RBR.