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

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: Luca Benini , Giovanni De Micheli, Networks on Chips: A New SoC Paradigm, Computer, v.35 n.1, p.70-78, January 2002 [doi>10.1109/2.976921]
• 2: Drew Wingard, Micronetwork-based integration for SOCs: 673, Proceedings of the 38th conference on Design automation, p.677, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379046]
• 3: Pierre Guerrier , Alain Greiner, A generic architecture for on-chip packet-switched interconnections, Proceedings of the conference on Design, automation and test in Europe, p.250-256, March 27-30, 2000, Paris, France [doi>10.1145/343647.343776]
• 4: Stergios Stergiou , Federico Angiolini , Salvatore Carta , Luigi Raffo , Davide Bertozzi , Giovanni De Micheli, ×pipes Lite: A Synthesis Oriented Design Library For Networks on Chips, Proceedings of the conference on Design, Automation and Test in Europe, p.1188-1193, March 07-11, 2005 [doi>10.1109/DATE.2005.1]
• 5: Jingcao Hu , Radu Marculescu, Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures, Proceedings of the conference on Design, Automation and Test in Europe, p.10688, March 03-07, 2003
• 6: Srinivasan Murali , Giovanni De Micheli, SUNMAP: a tool for automatic topology selection and generation for NoCs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996809]
• 7: S. Murali, G. De Micheli, "Bandwidth Constrained Mapping of Cores onto NoC Architectures", Vol. 2, pp. 20896--20899, DATE 2004.
• 8: Andreas Hansson , Kees Goossens , Andrei Rǎdulescu, A unified approach to constrained mapping and routing on network-on-chip architectures, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, p.75-80, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084857]
• 9: Jongman Kim , Dongkook Park , T. Theocharides , N. Vijaykrishnan , Chita R. Das, A low latency router supporting adaptivity for on-chip interconnects, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065726]
• 10: Jingcao Hu , Radu Marculescu, DyAD: smart routing for networks-on-chip, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996638]
• 11: Rajamohana Hegde , Naresh R. Shanbhag, Toward achieving energy efficiency in presence of deep submicron noise, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.4, p.379-391, Aug. 2000 [doi>10.1109/92.863617]
• 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.
• 13: Srinivasan Murali , Theocharis Theocharides , N. Vijaykrishnan , Mary Jane Irwin , Luca Benini , Giovanni De Micheli, Analysis of Error Recovery Schemes for Networks on Chips, IEEE Design & Test, v.22 n.5, p.434-442, September 2005 [doi>10.1109/MDT.2005.104]
• 14: Radu Marculescu, Networks-On-Chip: The Quest for On-Chip Fault-Tolerant Communication, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.8, February 20-21, 2003
• 15: Heiko Zimmer , Axel Jantsch, A fault model notation and error-control scheme for switch-to-switch buses in a network-on-chip, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944694]
• 16: Frédéric Worm , Paolo Ienne , Patrick Thiran , Giovanni De Micheli, An adaptive low-power transmission scheme for on-chip networks, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581221]
• 17: M. Pirretti et al.,"Fault Tolerant Algorithms for Network-On-Chip Interconnect", Proc. of ISVLSI, Feb 2004.
• 18: Sorin Manolache , Petru Eles , Zebo Peng, Fault and energy-aware communication mapping with guaranteed latency for applications implemented on NoC, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065648]
• 19: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 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: Yucel Aydogan , Craig B. Stunkel , Cevdet Aykanat , Bülent Abali, Adaptive Source Routing in Multistage Interconnection Networks, Proceedings of the 10th International Parallel Processing Symposium, p.258-267, April 15-19, 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Measurement, Performance

Keywords:
fault-tolerance, flow control, multi-path, networks on chip, re-order buffers, routing, systems on chip