DyAD: smart routing for networks-on-chip

ABSTRACT

In this paper, we present and evaluate a novel routing scheme called DyAD which combines the advantages of both deterministic and adaptive routing schemes. More precisely, we envision a new routing technique which judiciously switches between deterministic and adaptive routing based on the network's congestion conditions. The simulation results show the effectiveness of DyAD by comparing it with purely deterministic and adaptive routing schemes under different traffic patterns. Moreover, a prototype router based on the DyAD idea has been designed and evaluated. Compared to purely adaptive routers, the overhead of implementing DyAD is negligible (less than 7%), while the performance is consistently better.

REFERENCES

• 1: Ge-Ming Chiu, The Odd-Even Turn Model for Adaptive Routing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.729-738, July 2000 [doi>10.1109/71.877831]
• 2: W. J. Dally and C. L. Seitz. The torus routing chip. Distributed Computing, 1(3):187--196, 1986.
• 3: William J. Dally , Brian Towles, Route packets, net wires: on-chip inteconnectoin networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 4: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Journal of the ACM (JACM), v.41 n.5, p.874-902, Sept. 1994 [doi>10.1145/185675.185682]
• 5: J. Hu and R. Marculescu. Smart routing for networks-on-chip. Technical report, ECE Department, Carnegie Mellon University, March 2004. Available at http://www.ece.cmu.edu/.sld/pubs.
• 6: P. Kermani and L. Kleinrock. Virtual cut-through: a new computer communication switching technique. In Computer Networks, volume 3, pages 267--286, Sept. 1979.
• 7: Jian Liang , Sriram Swaminathan , Russell Tessier, aSOC: A Scalable, Single-Chip Communications Architecture, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.37, October 15-19, 2000
• 8: 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]
• 9: Erland Nilsson , Mikael Millberg , Johnny Oberg , Axel Jantsch, Load Distribution with the Proximity Congestion Awareness in a Network on Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.11126, March 03-07, 2003
• 10: E. Rijpkema , K. G. W. Goossens , A. Radulescu , J. Dielissen , J. van Meerbergen , P. Wielage , E. Waterlander, Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.10350, March 03-07, 2003
• 11: Kang G. Shin , Stuart W. Daniel, Analysis and Implementation of Hybrid Switching, IEEE Transactions on Computers, v.45 n.6, p.684-692, June 1996 [doi>10.1109/12.506424]
• 12: Girish V. Varatkar , Radu Marculescu, On-chip traffic modeling and synthesis for MPEG-2 video applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.108-119, January 2004 [doi>10.1109/TVLSI.2003.820523]
• 13: Walter Willinger , Vern Paxson , Murad S. Taqqu, Self-similarity and heavy tails: structural modeling of network traffic, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Algorithms, Design, Performance

Keywords:
networks-on-chip, router design, systems-on-chip