Locality-preserving randomized oblivious routing on torus networks

ABSTRACT

We introduce Randomized Local Balance (RLB), a routing algorithm that strikes a balance between locality and load balance in torus networks, and analyze RLB's performance for benign and adversarial traffic permutations. Our results show that RLB outperforms deterministic algorithms (25% more bandwidth than Dimension Order Routing) and minimal oblivious algorithms (50% more bandwidth than 2 phase ROMM [9]) on worst-case traffic. At the same time, RLB offers higher throughput on local traffic than a fully randomized algorithm (4.6 times more bandwidth than VAL (Valiant's algorithm) [15] in the best case). RLBth (RLB threshold) improves the locality of RLB to match the throughput of minimal algorithms on very local traffic in exchange for a 4% reduction in worst-case throughput compared to RLB. Both RLB and RLBth give better throughput than all other algorithms we tested on randomly selected traffic permutations. While RLB algorithms have somewhat lower guaranteed bandwidth than VAL they have much lower latency at low offered loads (up to 3.65 times less for RLBth).

REFERENCES

• 1: Brian Towles , William J. Dally, Worst-case Traffic for Oblivious Routing Functions, IEEE Computer Architecture Letters, v.1 n.1, p.4, January 2006 [doi>10.1109/L-CA.2002.12]
• 2: W. Dally. Aoki: Deadlock-free adaptive routing in multicomputer networks using virtual channels, 1993.
• 3: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 4: William Dally, Philip Carvey, and Larry Dennison. Architecture of the avici terabit switch/router. In Proceedings of Hot Interconnects Symposium VI, August 1998, pages 41--50, 1998.
• 5: William J. Dally and Charles L. Seitz. The torus routing chip. Distributed Computing, 1(4):187--196, 1986.
• 6: 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]
• 7: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, 25 years of the international symposia on Computer architecture (selected papers), p.441-450, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.286003]
• 8: 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]
• 9: 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]
• 10: G. Pfister. An introduction to the infiniband arechitecture. High Performance Mass Storage and Parallel I/O, IEEE Press, 2001., 2001.
• 11: Steven L. Scott , Greg Thorson, Optimized Routing in the Cray T3D, Proceedings of the First International Workshop on Parallel Computer Routing and Communication, p.281-294, May 16-18, 1994
• 12: S. Scott and G. Thorson. The cray t3e network: adaptive routing in a high performance 3d torus, 1996.
• 13: H. Sullivan, T. Bashkow, and D. Klappholz. A large scale, homogeneous, fully distributed parallel machine, ii, 1977.
• 14: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 15: G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing , 11(2):350--361, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

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

Keywords:
interconnection networks, k-ary n cubes, locality-preserving, oblivious packet routing, randomized