Mesh-of-tree deterministic routing for network-on-chip architecture

ABSTRACT

Network-on-Chip (NoC) is a new paradigm for designing future SoCs. It supports high degree of reusability, scalability, and parallelism in communication. Here, we present Mesh-of-Tree (MoT) based deterministic routing for NoC architecture. MoT interconnection has the advantage of having small diameter as well as large bisection width. The routing algorithm ensures that the packet will always reach the destination through the shortest path and it is deadlock and livelock free.

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: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 3: A Network on Chip Architecture and Design Methodology, Proceedings of the IEEE Computer Society Annual Symposium on VLSI, p.117, April 25-26, 2002
• 4: W. J. Dally et al, "The Torus Routing Chip", Journal of Distributed Computing, pp. 187--196, Oct 1986.
• 5: Yuan-Long Jeang , Jer-Min Jou , Win-Hsien Huang, A Binary Tree Based Methodology for Designing an Application Specific Network-on-Chip (ASNOC), IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E88-A n.12, p.3531-3538, December 2005 [doi>10.1093/ietfec/e88-a.12.3531]
• 6: 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]
• 7: Faraydon Karim , Anh Nguyen , Sujit Dey, An Interconnect Architecture for Networking Systems on Chips, IEEE Micro, v.22 n.5, p.36-45, September 2002 [doi>10.1109/MM.2002.1044298]
• 8: Pande et al., "High-Throughput Switch-based Interconnect for future SoCs", Proc. Third IEEE Int?l Workshop System-on-Chip for real time Applications, pp. 304--310, 2003.
• 9: Partha Pratim Pande , Cristian Grecu , Michael Jones , Andre Ivanov , Resve Saleh, Performance Evaluation and Design Trade-Offs for Network-on-Chip Interconnect Architectures, IEEE Transactions on Computers, v.54 n.8, p.1025-1040, August 2005 [doi>10.1109/TC.2005.134]
• 10: Aydin O. Balkan , Gang Qu , Uzi Vishkin, A Mesh-of-Trees Interconnection Network for Single-Chip Parallel Processing, Proceedings of the IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, p.73-80, September 11-13, 2006 [doi>10.1109/ASAP.2006.6]
• 11: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 12: Interconnection Network architectures, Jan 2001, pp. 26--49. www.wellesley.edu/cs/courses/cs331/notes/notesnetworks.pdf
• 13: Cesar Albenes Zeferino , Altamiro Amadeu Susin, SoCIN: A Parametric and Scalable Network-on-Chip, Proceedings of the 16th symposium on Integrated circuits and systems design, p.169, September 08-11, 2003
• 14: William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
• 15: S. Kundu et al., "Interfacing Cores and Routers in Network-on-Chip Using GALS", IEEE International Symposium on Integrated Circuits (ISIC), Singapore, 2007.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.m MISCELLANEOUS

General Terms:
Design

Keywords:
deterministic routing., interconnection networks, mesh-of-tree (mot), network-on-chip (noc), system-on-chip (soc)