Increasing the throughput of an adaptive router in network-on-chip (NoC)

ABSTRACT

In this paper, we propose a simple and efficient mechanism to increase the throughput of an adaptive router in Network-on-Chip (NoC). One of the most serious disadvantages of fully adaptive wormhole routers is its performance degradation due to the routing decision time. The key idea to overcome this shortcoming is the use of different clocks in a head flit and body flits, because the body flits can be forwarded immediately and the FIFO usually operates faster than route decision logic in an adaptive router. The major contributions of this paper are: 1) a proposal of a simple and efficient mechanism to improve the performance of fully adaptive wormhole routers, 2) a quantitative evaluation of the proposed mechanism showing that the proposed one can support higher throughput than a conventional one, and 3) an evaluation of hardware overhead for the proposed router. In summary, the proposed clock boosting mechanism enhances the throughput of the original adaptive router by increasing the accepted load and decreasing the average latency in the region of effective bandwidth.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
• 4: Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215455]
• 5: Daeho Seo , Akif Ali , Won-Taek Lim , Nauman Rafique , Mithuna Thottethodi, Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.432-443, June 04-08, 2005
• 6: 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]
• 7: 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]
• 8: José Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1320-1331, December 1993 [doi>10.1109/71.250114]
• 9: 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]
• 10: C. J. Glass and L. M. Ni. Adaptive Routing in Mesh-connected Networks. In Proc of the 12th Int'l Conference on Distributed Computing Systems(ICDCS '92), pages 12--19, June 1992.
• 11: 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]
• 12: V. Puente , R. Beivide , J. A. Gregorio , J. M. Prellezo , J. Duato , C. Izu, Adaptive Bubble Router: A Design to Improve Performance in Torus Networks, Proceedings of the 1999 International Conference on Parallel Processing, p.58, September 21-24, 1999
• 13: Se-Joong Lee , Kangmin Lee , Hoi-Jun Yoo, Analysis and Implementation of Practical, Cost-Effective Networks on Chips, IEEE Design & Test, v.22 n.5, p.422-433, September 2005 [doi>10.1109/MDT.2005.103]
• 14: Kees Goossens , John Dielissen , Andrei Radulescu, Æthereal Network on Chip: Concepts, Architectures, and Implementations, IEEE Design & Test, v.22 n.5, p.414-421, September 2005 [doi>10.1109/MDT.2005.99]
• 15: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003

INDEX TERMS

Primary 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, Performance, Verification

Keywords:
adaptive router, chip-multiprocessor, interconnection network, network-on-chip (NoC), wormhole routing