Evaluation of on-chip networks using deflection routing

ABSTRACT

Deflection routing is being proposed for networks on chips since it is simple and adaptive. A deflection switch can be much smaller and faster than a wormhole or virtual cut-through switch. A deflection-routed network has three orthogonal characteristics: topology, routing algorithm and deflection policy. In this paper we evaluate deflection networks with different topologies such as mesh, torus and Manhattan Street Network, different routing algorithms such as random, dimension XY, delta XY and minimum deflection, as well as different deflection policies such as non-priority, weighted priority and straight-through policies. Our results suggest that the performance of a deflection network is more sensitive to its topology than the other two parameters. It is less sensitive to its routing algorithm, but a routing algorithm should be minimal. A priority-based deflection policy that uses global and history-related criterion can achieve both better average-case and worst-case performance than a non-priority or priority policy that uses local and stateless criterion. These findings are important since they can guide designers to make right decisions on the deflection network architecture, for instance, selecting a routing algorithm or deflection policy which has potentially low cost and high speed for hardware implementation.

REFERENCES

• 1: P. Baran. On distributed computing networks. IEEE Transactions on Communication Systems, March 1964.
• 2: Allan Borodin , Yuval Rabani , Baruch Schieber, Deterministic Many-to-Many Hot Potato Routing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.6, p.587-596, June 1997 [doi>10.1109/71.595575 ]
• 3: Jack T. Brassil , Rene L. Cruz, Bounds on Maximum Delay in Networks with Deflection Routing, IEEE Transactions on Parallel and Distributed Systems, v.6 n.7, p.724-732, July 1995 [doi>10.1109/71.395401 ]
• 4: 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]
• 5: Tudor Dumitras , Radu Marculescu, On-Chip Stochastic Communication, Proceedings of the conference on Design, Automation and Test in Europe, p.10790, March 03-07, 2003
• 6: A. G. Greenberg and J. Goodman. Sharp approximate models of deflection routing in mesh networks. IEEE Transactions on Communications, 41(1), January 1993.
• 7: W. D. Hills. The Connection machine. Scientific American, 256(6), June 1987.
• 8: K. Keutzer, S. Malik, A. R. Newton, J. M. Rabaey, and A. Sangiovanni-Vincentelli. System-level design: Orthogonalization of concerns and platform-based design. IEEE Transaction on Computer-Aided Design of Integrated Circuits, 19(12):1523--1543, December 2000.
• 9: Zhonghai Lu , Axel Jantsch, Traffic Configuration for Evaluating Networks on Chips, Proceedings of the Fifth International Workshop on System-on-Chip for Real-Time Applications (IWSOC'05), p.535-540, July 20-24, 2005 [doi>10.1109/IWSOC.2005.107]
• 10: Mikael Millberg , Erland Nilsson , Rikard Thid , Axel Jantsch, Guaranteed Bandwidth Using Looped Containers in Temporally Disjoint Networks within the Nostrum Network on Chip, Proceedings of the conference on Design, automation and test in Europe, p.20890, February 16-20, 2004
• 11: Erland Nilsson , Johnny Öberg, Reducing power and latency in 2-D mesh NoCs using globally pseudochronous locally synchronous clocking, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016764]
• 12: Dinesh Pamunuwa , Johnny Öberg , Li-Rong Zheng , Mikael Millberg , Axel Jantsch , Hannu Tenhunen, A study on the implementation of 2-D mesh-based networks-on-chip in the nanometre regime, Integration, the VLSI Journal, v.38 n.1, p.3-17, October 2004 [doi>10.1016/j.vlsi.2004.03.005]
• 13: Terry Tao Ye , Luca Benini , Giovanni De Micheli, Packetization and routing analysis of on-chip multiprocessor networks, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.2-3, p.81-104, February 2004 [doi>10.1016/j.sysarc.2003.07.005]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

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

General Terms:
Design, Performance

Keywords:
deflection routing, network-on-chip, performance evaluation, system-on-chip communication network