research-article

Region-based routing: a mechanism to support efficient routing algorithms in NoCs

Authors:

Maurizio Palesi,

Rickard Hoismark,

José DuatoAuthors Info & Claims

IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 17, Issue 3

Pages 356 - 369

Published: 01 March 2009 Publication History

Abstract

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 8 × 8 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.

References

[1]

P. Guerrier and A. Greiner, "A generic architecture for on-chip packet-switched interconnections," in Proc. Conf. Des., Autom. Test Eur. (DATE), NY, 2000, pp. 250-256.

[2]

S. Kumar, A. Jantsch, M. Millberg, J. Oberg, J.-P. Soininen, M. Forsell, K. Tiensyrja, and A. Hemani, "A network on chip architecture and design methodology" in Proc. ISVLSI, 2002, p. 0117.

[3]

J. Balfour and W. J. Dally, "Design tradeoffs for tiled cmp on-chip networks," in Proc. 20th Ann. Int. Conf. Supercomput. (ICS), NY, 2006, pp. 187-198.

[4]

E. Bolotin, A. Morgenshtein, I. Cidon, R. Ginosar, and A. Kolodny, "Automatic hardware-efficient soc integration by qos network on chip," in Proc Electron, Circuits Syst. (ICECS), 2004, pp. 479-482 {Online}. Available: citeseer.ist.psu.edu/dally01route.html.

[5]

E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny, "Qnoc: Qos architecture and design process for network on chip," J. Syst. Arch., vol. 50, no. 2-3, pp. 105-128, 2004.

Digital Library

[6]

T. Bengtsson, S. Kumar, R. Ubar, and A. Jutman, "Off-line testing of crosstalk induced glitch faults in noc interconnects," in Proc. 24th Norchip Conf., Linkoping, Sweden, 2006, pp. 221-225.

[7]

W.J. Dally and B. Towles, Principles and Practices of Interconnection Networks. San Mateo, CA: Morgan Kaufman, 2004.

[8]

M. Palesi, S. Kumar, and R. Holsmark, "A method for router table compression for application specific routing in mesh topology NoC architectures," in Proc. SAMOS, 2006, pp. 373-384.

[9]

J. Flich, A. Mejia, P. Lopez, and J. Duato, "Region-based routing. An efficient routing mechanism to tackle unreliable hardware in network on chips," presented at the 1st Int. Symp. Netw.-on-Chips, Princeton, NJ, May 2007.

[10]

E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny, "Routing table minimization for irregular mesh NoCs," in Proc. Conf Des., Autom. Test Eur. (DATE), NY, 2007, pp. 942-947.

[11]

A. Mejia, J. Flich, J. Duato, S. Reinemo, and T. Skeie, "Segment-based routing: An efficient fault-tolerant routing algorithm for meshes and tori," presented at the 20th Int. Parallel Distrub. Process. Symp. (IPDPS), Rhodos, Grece, Apr. 2006.

[12]

M. Palesi, R. Holsmark, S. Kumar, and V. Catania, "A methodology for design of application specific deadlock-free routing algorithms for NoC systems," in Proc. 4th Int. Conf. Hardw./Softw. Codes. Syst. Synth. (CODES+ISSS), NY, 2006, pp. 142-147.

[13]

C. J. Glass and L. M. Ni, "The turn model for adaptive routing," J. ACM, vol. 41, no. 5, pp. 874-902, 1994.

Digital Library

[14]

G.-M. Chiu, "The odd-even turn model for adaptive routing," IEEE Trans. Parallel Distrib. Syst., vol. 11, no. 7, pp. 729-738, Jul. 2000.

Digital Library

[15]

T. Skeie, O. Lysne, and I. Theiss, "Layered shortest path (lash) routing in irregular system area networks," in Proc. Commun. Arch. Clusters, 2002, pp. 162-169.

[16]

J. Flich, P. Lopez, J. Sancho, A. Robles, and J. Duato, "Improving infiniband routing through multiple virtual networks," in Proc. 4th Int. Symp. High Perform. Comput. (ISHPC), London, U.K., 2002, pp. 49-63.

Digital Library

[17]

O. Lysne and T. Skeie, "Load balancing of irregular system area networks through multiple roots," in Proc. Int. Conf. Commun. Comput., Jun. 2001, pp. 165-171.

[18]

T. Skeie, O. Lysne, J. Flich, P. Lopez, A. Robles, and J. Duato, "Lashtor: A generic transition-oriented routing algorithm," in Proc. IEEE Int. Conf. Parallel Distrib. Syst. (ICPADS), 2004, pp. 595-604.

[19]

M. Koibuchi, A. Jouraku, K. Watanabe, and H. Amano, "Descending layers routing: A deadlock-free deterministic routing using virtual channels in system area networks with irregular topologies," in Proc. Int. Conf. Parallel Process. (ICPP), Oct. 2003, pp. 527-536.

[20]

L. Cherkasova, V. Kotov, and T. Rokicki, "Designing fibre channel fabrics," in Proc. Int. Conf. Comput. Des. (ICCD), Washington, DC, 1995, p. 346.

[21]

J. C. Sancho, A. Robles, and J. Duato, "New methodology to compute deadlock-free routing tables for irregular networks," in Proc. Workshop Commun., Arch., Appl. Netw.-Based Parallel Comput. (CANPC), Jan. 2000, pp. 45-60.

[22]

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: A high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun., vol. 9, no. 8, pp. 1318-1335, Oct. 1991.

Digital Library

[23]

J. Sancho, A. Robles, and J. Duato, "A flexible routing scheme for networks of workstations," in Proc. 3rd Int. Symp. High Perform. Comput. (ISHPC), London, U.K., 2000, pp. 260-267.

[24]

M. Koibuchi, A. Funahashi, A. Jouraku, and H. Amano, "L-turn routing: An adaptive routing in irregular networks," in Proc. Int. Conf. Parallel Process. (ICPP), Washington, DC, 2001, pp. 383-392.

[25]

G. Ascia, V. Catania, and M. Palesi, "A multi-objective genetic approach for system-level exploration in parameterized systems-on-a-chip," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 24, no. 4, pp. 635-645, Apr. 2005.

Digital Library

[26]

L. Benini, A. Macii, E. Macii, M. Poncino, and R Scarsi, "Architectures and synthesis algorithms for power-efficient bus interfaces," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 19, no. 9, pp. 969-980, Sep. 2000.

Digital Library

[27]

W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Trans. Comput., vol. C-36, no. 5, pp. 547-553, May 1987.

Digital Library

[28]

J. Hu and R. Marculescu, "Energy- and performance-aware mapping for regular NoC architectures," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 24, no. 4, pp. 551-562, Apr. 2005.

Digital Library

[29]

S.-R. Yoon, J. Lee, and S.-C. Park, "Case study: NoC based next-generation wlan receiver design in transaction level," in Proc. Int. Conf. Adv. Commun. Technol., Feb. 2006, vol. 2, pp. 1125-1128.

[30]

K. Srinivasan and K. S. Chatha, "A technique for low energy mapping and routing in network-on-chip architectures," in Proc. Int. Symp. Low Power Electron. Des., San Diego, CA, 2005, pp. 387-392.

[31]

G. Ascia. V. Catania, and M. Palesi. "Multi-objective mapping for mesh-based NoC architectures," in Proc. 2nd IEEE/ACM/IFIP Int. Conf. Hardw./Softw. Codes. Syst. Synth., Stockholm, Sweden, Sep. 2004, pp. 182-187.

Digital Library

[32]

Sourceforge.net, "Noxim: Network-on-chip simulator," 2008. {Online}. Available: http://noxim.sourceforge.net.

[33]

G. Varatkar and R. Marculescu, "Traffic analysis for on-chip networks design of multimedia applications," in Proc. ACM/IEEE Des. Autom. Conf., Jun. 2002, pp. 510-517.

[34]

P. P. Pande, C. Grecu, M. Jones, A. Ivanov, and R. Saleh, "Performance evaluation and design trade-offs for network-on-chip interconnect architectures." IEEE Trans. Comput., vol. 54, no. 8, pp. 1025-1040, Aug. 2005.

Digital Library

[35]

T.T. Ye, L. Benini, and G. D. Micheli, "Packetization and routing analysis of on-chip multiprocessor networks," J. Syst. Arch., vol. 50, no. 2-3, pp. 81-104, 2004.

Digital Library

[36]

G. Ascia. V. Catania, M. Palesi, and D. Patti, "Neighbors-on-path: A new selection strategy for on-chip networks," in Proc. IEEE/ACM/IFIP Workshop Embed. Syst. Real Time Multimedia, Seoul, Korea, 2006, pp. 79-84.

Digital Library

[37]

A. S. Vaidya, A. Sivasubramaniam, and C. R. Das, "Lapses: A recipe for high performance adaptive router design," in Proc. HPCA, 1999, p. 236.

Cited By

Punhani AKumar PNitin Mishra K(2017)Optimal extra links placement in mesh interconnection network using improved environmental adaptation methodJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-16927132:5(3285-3295)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/JIFS-169271
Milfont RMota RFerreira JCortez PMarcon CTavares DSilveira JSilveira J(2017)Latency reduction of fault-tolerant NoCs by employing multiple pathsProceedings of the 30th Symposium on Integrated Circuits and Systems Design: Chip on the Sands10.1145/3109984.3109985(72-78)Online publication date: 28-Aug-2017
https://dl.acm.org/doi/10.1145/3109984.3109985
Werner SNavaridas JLuján M(2016)A Survey on Design Approaches to Circumvent Permanent Faults in Networks-on-ChipACM Computing Surveys10.1145/288678148:4(1-36)Online publication date: 18-Mar-2016
https://dl.acm.org/doi/10.1145/2886781
Show More Cited By

Region-based routing: a mechanism to support efficient routing algorithms in NoCs

Recommendations

Variability-tolerant routing algorithms for Networks-on-Chip

Display Omitted Modifying XY, West-First, Negative-First, and Odd-Even algorithms to consider link failure probability when routing.Proposing the NoC failure rate as a measure of tolerance against process-induced random and systematic delay ...
Leveraging partially faulty links usage for enhancing yield and performance in networks-on-chip

The communication infrastructure of a complex multicore system-on-a-chip is getting an increasing fraction of the overall chip area. According to the International Technology Roadmap for Semiconductors, killer defect density does not decrease over ...
An efficient routing scheme for scalable hierarchical networks
SPDP '93: Proceedings of the 1993 5th IEEE Symposium on Parallel and Distributed Processing

Future generation supercomputers are expected to have increased use of cluster-based hierarchy. This paper specifies the connection method in a recently introduced hierarchical topology called de Bruijn-Cube (dBCube), which connects clusters of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 17, Issue 3

March 2009

137 pages

ISSN:1063-8210

Issue’s Table of Contents

Copyright © 2009.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 March 2009

Revised: 02 April 2008

Received: 08 December 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Punhani AKumar PNitin Mishra K(2017)Optimal extra links placement in mesh interconnection network using improved environmental adaptation methodJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-16927132:5(3285-3295)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/JIFS-169271
Milfont RMota RFerreira JCortez PMarcon CTavares DSilveira JSilveira J(2017)Latency reduction of fault-tolerant NoCs by employing multiple pathsProceedings of the 30th Symposium on Integrated Circuits and Systems Design: Chip on the Sands10.1145/3109984.3109985(72-78)Online publication date: 28-Aug-2017
https://dl.acm.org/doi/10.1145/3109984.3109985
Werner SNavaridas JLuján M(2016)A Survey on Design Approaches to Circumvent Permanent Faults in Networks-on-ChipACM Computing Surveys10.1145/288678148:4(1-36)Online publication date: 18-Mar-2016
https://dl.acm.org/doi/10.1145/2886781
Dehghani AJamshidi K(2016)A Novel Approach to Optimize Fault-Tolerant Hybrid Wireless Network-on-Chip ArchitecturesACM Journal on Emerging Technologies in Computing Systems10.1145/281457212:4(1-37)Online publication date: 15-Mar-2016
https://dl.acm.org/doi/10.1145/2814572
Liu JHarkin JLi YMaguire L(2016)Fault-Tolerant Networks-on-Chip Routing With Coarse and Fine-Grained Look-AheadIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.245905035:2(260-273)Online publication date: 18-Jan-2016
https://dl.acm.org/doi/10.1109/TCAD.2015.2459050
Valinataj MShahiri M(2016)A low-cost, fault-tolerant and high-performance router architecture for on-chip networksMicroprocessors & Microsystems10.1016/j.micpro.2016.04.00945:PA(151-163)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.micpro.2016.04.009
Li YMei KLiu Y(2016)Improving the Area Efficiency of ACO-Based Routing by Directional Pheromone in Large-Scale NoCsMicroprocessors & Microsystems10.1016/j.micpro.2016.04.00145:PA(81-94)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.micpro.2016.04.001
Silveira JMarcon CCortez PBarroso GFerreira JMota R(2016)Scenario preprocessing approach for the reconfiguration of fault-tolerant NoC-based MPSoCsMicroprocessors & Microsystems10.1016/j.micpro.2015.08.00540:C(137-153)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.micpro.2015.08.005
Silveira JCortez PCadore AMota RMarcon CBrahm LFernandes Rde Lima RCunha APlett Cde Oliveira W(2015)Smart Reconfiguration Approach for Fault-Tolerant NoC Based MPSoCsProceedings of the 28th Symposium on Integrated Circuits and Systems Design10.1145/2800986.2801027(1-6)Online publication date: 31-Aug-2015
https://dl.acm.org/doi/10.1145/2800986.2801027
Minghua Tang Xiaola Lin Palesi M(2015)An Offline Method for Designing Adaptive Routing Based on Pressure ModelIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2014.237964934:2(307-320)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TCAD.2014.2379649
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents