Article

A multi-path routing strategy with guaranteed in-order packet delivery and fault-tolerance for networks on chip

Authors:

Srinivasan Murali,

Giovanni De MichelAuthors Info & Claims

DAC '06: Proceedings of the 43rd annual Design Automation Conference

Pages 845 - 848

https://doi.org/10.1145/1146909.1147124

Published: 24 July 2006 Publication History

Abstract

In this work we present a multi-path routing strategy that guaran-tees in-order packet delivery for Networks on Chips (NoCs). We present a design methodology that uses the routing strategy to opti-mally spread the traffic in the NoC to minimize the network band-width needs and power consumption. We also integrate support for tolerance against transient and permanent failures in the NoC links in the methodology by utilizing spatial and temporal redundancy for transporting packets. Our experimental studies show large re-duction in network bandwidth requirements (36.86% on average) and power consumption (30.51% on average) compared to single-path systems. The area overhead of the proposed scheme is small (a modest 5% increase in network area). Hence, it is practical to be used in the on-chip domain.

References

[1]

L.Benini and G.De Micheli, "Networks on Chips: A New SoC Paradigm", IEEE Computers, pp. 70--78, Jan. 2002.

Digital Library

[2]

D.Wingard,"MicroNetwork-Based Integration for SoCs", Design Automation Conference DAC 2001, pp. 673--677, Jun 2001.

Digital Library

[3]

P.Guerrier, A.Greiner,"A generic architecture for on-chip packet switched interconnections", DATE 2000, pp. 250--256, March 2000.

Digital Library

[4]

S. Stergiou et al., " x pipesLite: a Synthesis Oriented Design Library for Networks on Chips", pp. 1188--1193, Proc. DATE 2005.

Digital Library

[5]

J. Hu, R. Marculescu, 'Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures', Proc. DATE, March 2003.

Digital Library

[6]

S. Murali, G. De Micheli, "SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs", Proc. DAC 2004.

Digital Library

[7]

S. Murali, G. De Micheli, "Bandwidth Constrained Mapping of Cores onto NoC Architectures", Vol. 2, pp. 20896--20899, DATE 2004.

[8]

A. Hansson et al., "A unified approach to constrained mapping and routing on network-on-chip architectures", pp. 75--80, Proc. ISSS 2005.

Digital Library

[9]

J. Kim et al., "A low latency router supporting adaptivity for on-chip interconnects", Proc. DAC, June 2005.

Digital Library

[10]

J. Hu, R. Marculescu, 'DyAD - Smart Routing for Networks-on-Chip', Proc. DAC, June 2004.

Digital Library

[11]

R. Hegde, N. R. Shanbhag. "Towards Achieving Energy Efficiency in Presence of Deep Submicron Noise". IEEE Trans. on VLSI Systems, 8(4):379--391, August 2000.

Digital Library

[12]

D. Bertozzi et al., "Error Control Schemes for On-Chip Communication Links: The Energy-Reliability Trade-off", IEEE Trans. on CAD, Vol. 24, No. 6, pp. 818--831, June 2005.

Digital Library

[13]

S. Murali et al., "Analysis of Error Recovery Schemes for Networks on Chips", IEEE Design and Test of Computers, Vol. 22, No. 5, pp. 434--442, Sep/Oct 2005.

Digital Library

[14]

R. Marculescu, "Networks-On-Chip: The Quest for On-Chip Fault-Tolerant Communication", Proc. of IEEE ISVLSI, 2003.

Digital Library

[15]

H. Zimmer et al.,"A Fault Model Notation and Error-Control Scheme for switch-to-Switch Buses in a Network-on-Chip", ISSS/CODES, 2003.

Digital Library

[16]

F. Worm et al., "An Adaptive Low-power Transmission Scheme for On-chip Networks", ISSS, October 2002, pp. 92--100

Digital Library

[17]

M. Pirretti et al.,"Fault Tolerant Algorithms for Network-On-Chip Interconnect", Proc. of ISVLSI, Feb 2004.

[18]

S. Manolache et al., "Fault and Energy-Aware Communication Mapping with Guaranteed for Applications Implemented on NoC", Proc. DAC 2005.

Digital Library

[19]

W. J. Dally, B. Towles, "Principles and Practices of Interconnection Networks", Morgan Kaufmann, Dec 2003.

Digital Library

[20]

W. J. Dally et al., "The Avici terabit switch/router", Proc. Hot Interconnects, Aug. 1998.

[21]

Graig B. Stunkel, et al.; "The SP2 Communication Subsystem, " IBM Technical Report, August 22, 1994.

[22]

Y. Aydogan et al., "Adaptive Source Routing in Multistage Interconnection Networks", Proc. International Parallel Processing Symposium, 1996.

Digital Library

Cited By

Dhavlle AAhmed MMansoor NBasu KGanguly APudukotai Dinakarrao S(2023)Defense Against On-Chip Trojans Enabling Traffic Analysis Attacks Based on Machine Learning and Data AugmentationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327861842:12(4681-4694)Online publication date: Dec-2023
https://doi.org/10.1109/TCAD.2023.3278618
Nambinina RWiese VMuoka POnwuchekwa DObermaisser R(2023)Adaptive Time-Triggered Network-on-Chip Architecture: Enhancing Safety2023 3rd International Conference on Smart Generation Computing, Communication and Networking (SMART GENCON)10.1109/SMARTGENCON60755.2023.10442582(1-10)Online publication date: 29-Dec-2023
https://doi.org/10.1109/SMARTGENCON60755.2023.10442582
Chen HChen PLuo XHuai SLiu W(2022)LAMP: Load-Balanced Multipath Parallel Transmission in Point-to-Point NoCsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.315102141:12(5232-5245)Online publication date: Dec-2022
https://doi.org/10.1109/TCAD.2022.3151021
Show More Cited By

Index Terms

A multi-path routing strategy with guaranteed in-order packet delivery and fault-tolerance for networks on chip
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. General and reference
  1. Cross-computing tools and techniques
    1. Design

Recommendations

Fault Tolerance and Packet Latency of Peer Fat-Trees
Parallel and Distributed Computing, Applications and Technologies
Abstract
Clos- or fat-tree-based interconnection networks are widely used in data center and supercomputer designs. Both Clos and fat-tree are non-blocking multistage switch networks. The non-blocking property improves path diversity but meanwhile ...
Buffered deflection routing for networks-on-chip
INA-OCMC '12: Proceedings of the 2012 Interconnection Network Architecture: On-Chip, Multi-Chip Workshop

Bufferless deflection routing works surprisingly well when the network traffic is light or medium, and can outperform a virtual channel router with a small number of buffers, but when the network is working closer to saturation, classic buffered virtual ...
A Hierarchical Routing and Flow Control Policy (HRFC) for Packet Switched Networks

A new policy that can effectively handle message routing and flow control simultaneously in a packet switched computer network is presented. In such a policy, a traffic threshold level is assigned for each channel in the network. If all the channels ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '06: Proceedings of the 43rd annual Design Automation Conference

July 2006

1166 pages

ISBN:1595933816

DOI:10.1145/1146909

General Chair:
Ellen M. Sentovich
Cadence Berkeley Labs, Berkeley, CA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC06

Sponsor:

DAC06: The 43rd Annual Design Automation Conference 2006

July 24 - 28, 2006

CA, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
723
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dhavlle AAhmed MMansoor NBasu KGanguly APudukotai Dinakarrao S(2023)Defense Against On-Chip Trojans Enabling Traffic Analysis Attacks Based on Machine Learning and Data AugmentationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327861842:12(4681-4694)Online publication date: Dec-2023
https://doi.org/10.1109/TCAD.2023.3278618
Nambinina RWiese VMuoka POnwuchekwa DObermaisser R(2023)Adaptive Time-Triggered Network-on-Chip Architecture: Enhancing Safety2023 3rd International Conference on Smart Generation Computing, Communication and Networking (SMART GENCON)10.1109/SMARTGENCON60755.2023.10442582(1-10)Online publication date: 29-Dec-2023
https://doi.org/10.1109/SMARTGENCON60755.2023.10442582
Chen HChen PLuo XHuai SLiu W(2022)LAMP: Load-Balanced Multipath Parallel Transmission in Point-to-Point NoCsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.315102141:12(5232-5245)Online publication date: Dec-2022
https://doi.org/10.1109/TCAD.2022.3151021
Li YLouri A(2021)ALPHA: A Learning-Enabled High-Performance Network-on-Chip Router Design for Heterogeneous Manycore ArchitecturesIEEE Transactions on Sustainable Computing10.1109/TSUSC.2020.29813406:2(274-288)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TSUSC.2020.2981340
Meraj Ahmed MDhavlle AMansoor NSutradhar PPudukotai Dinakarrao SBasu KGanguly A(2020)Defense Against on-Chip Trojans Enabling Traffic Analysis Attacks2020 Asian Hardware Oriented Security and Trust Symposium (AsianHOST)10.1109/AsianHOST51057.2020.9358250(1-6)Online publication date: 15-Dec-2020
https://doi.org/10.1109/AsianHOST51057.2020.9358250
Wu JWu YJiang GLam S(2019)Algorithms for Reconfiguring NoC-Based Fault-Tolerant Multiprocessor ArraysJournal of Circuits, Systems and Computers10.1142/S021812661950111128:07(1950111)Online publication date: 27-Jun-2019
https://doi.org/10.1142/S0218126619501111
Das TGhosal PNath A(2019)Addressing Out-of-order Issue of Congestion-aware Adaptive Routing in Subnet based NoCTENCON 2019 - 2019 IEEE Region 10 Conference (TENCON)10.1109/TENCON.2019.8929408(1584-1589)Online publication date: Oct-2019
https://doi.org/10.1109/TENCON.2019.8929408
Yang YDeshpande HChoi GGratz P(2018)SDPR: Improving Latency and Bandwidth in On-Chip Interconnect Through Simultaneous Dual-Path RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.257042837:3(545-558)Online publication date: Mar-2018
https://doi.org/10.1109/TCAD.2016.2570428
Zhao HWang YXiong KSong L(2018)An efficient Manhattan‐distance‐constrained disjoint paths algorithm for incomplete mesh networkConcurrency and Computation: Practice and Experience10.1002/cpe.479931:1Online publication date: 14-Aug-2018
https://doi.org/10.1002/cpe.4799
Basu PJayashankara Shridevi RChakraborty KRoy S(2017)IcoNoClast: Tackling Voltage Noise in the NoC Power Supply Through Flow-Control and Routing AlgorithmsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2017.267380825:7(2035-2044)Online publication date: Jul-2017
https://doi.org/10.1109/TVLSI.2017.2673808
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten