A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip

ABSTRACT

In this paper we present a reconfigurable routing algorithm for a 2D-Mesh Network-on-Chip (NoC) dedicated to fault-tolerant, Massively Parallel Multi-Processors Systems on Chip (MP2-SoC). The routing algorithm can be dynamically reconfigured, to adapt to the modification of the micro-network topology caused by a faulty router. This algorithm has been implemented in a reconfigurable version of the DSPIN micro-network, and evaluated from the point of view of performance (penalty on the network saturation threshold), and cost (extra silicon area occupied by the reconfigurable version of the router).

REFERENCES

• 1: Alliance CAD.
• 2: Suresh Chalasani , Rajendra V. Boppana, Fault-Tolerant Wormhole Routing Algorithms for Mesh Networks, IEEE Transactions on Computers, v.44 n.7, p.848-864, July 1995 [doi>10.1109/12.392844]
• 3: Andrew A. Chien , Jae H. Kim, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, Journal of the ACM (JACM), v.42 n.1, p.91-123, Jan. 1995 [doi>10.1145/200836.200856]
• 4: C. M. Cunningham , D. R. Avresky, Fault-tolerant adaptive routing for two-dimensional meshes, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.122, January 22-25, 1995
• 5: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 6: W. J. Dally , C. L. Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 7: DSPIN. http://www.lip6.fr/Direction/2005-05-13-DSPIN.pdf.
• 8: José Duato, A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1055-1067, October 1995 [doi>10.1109/71.473515]
• 9: José Duato, A Theory of Fault-Tolerant Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.790-802, August 1997 [doi>10.1109/71.605766]
• 10: Steve Furber, Living with Failure: Lessons from Nature?, Proceedings of the Eleventh IEEE European Test Symposium, p.4-8, May 21-21, 2006 [doi>10.1109/ETS.2006.28]
• 11: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Proceedings of the 19th annual international symposium on Computer architecture, p.278-287, May 19-21, 1992, Queensland, Australia
• 12: C. Glass and L. Ni. Fault-tolerant wormhole routing in meshes. Fault-Tolerant Computing, 1993. FTCS-23. Digest of Papers., The Twenty-Third International Symposium on, pages 240--249, 1993.
• 13: Daniel H. Linder , Jim C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes, IEEE Transactions on Computers, v.40 n.1, p.2-12, January 1991 [doi>10.1109/12.67315]
• 14: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 15: I. Panades, A. Greiner, A. Sheibanyrad, and G. STMicroelcctronics. A Low Cost Network-on-Chip with Guaranteed Service Well Suited to the GALS Approach. Nano-Networks and Workshops, 2006. Nano Net '06. 1st International Conference on, pages 1--5, 2006.
• 16: Chien-Chun Su , Kang G. Shin, Adaptive Fault-Tolerant Deadlock-Free Routing in Meshes and Hypercubes, IEEE Transactions on Computers, v.45 n.6, p.666-683, June 1996 [doi>10.1109/12.506423]
• 17: S. Taktak, E. Encrenaz, and J. Desbarbieux. A Tool for Automatic Detection of Deadlock in Wormhole Networks on Chip. High-Level Design Validation and Test Workshop, 2006. Eleventh Annual IEEE International, pages 203--210, 2006.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Algorithms, Design, Reliability

Keywords:
2D-Mesh NoC, DSPIN, MP2-SoC, fault-tolerant, reconfiguration, routing algorithm