Almost optimal permutation routing on hypercubes

ABSTRACT

This paper deals with permutation routing on hypercube networks in the store-and-forward model. We introduce the first (on-line and off-line) algorithms routing any permutation on the d-dimensional hypercube in d+o(d) steps. The best previously known results were 2d+o(d) (oblivious on-line) and 2d-3 (off-line). In particular, we presenta randomized, oblivious on-line algorithm with routing time d + O(d/log d),a matching lower bound of d + &OHgr;(d/log d) for (randomized) oblivious on-line routing, anda deterministic, off-line algorithm with routing time d+O(\sqrt{d\log d}).Previous algorithms lose a factor of two mainly because packets are first sent to intermediate destinations in order to resolve congestion. As a consequence, the maximum path length becomes 2d - o(d). Our algorithms use intermediate destinations as well, but we introduce a simple, elegant trick ensuring that the routing paths are not stretched too much. In fact, we achieve small congestion using paths of length at most d.The main focus of our work, however, lies on the scheduling aspect. On one hand, we investigate well-known and practical scheduling policies for on-line routing, namely Farthest-to-Go and Nearest-to-Origin. On the other hand, we present a new off-line scheduling scheme that is based on frugal colorings of multigraphs. This scheme might be of interest for other sparse scheduling problems, too.

REFERENCES

• 1: N. Alon. A parallel algorithmic version of the Local Lemma. Random Structures & Algorithms, 2:367-378, 1991.
• 2: F. Annexstein , M. Baumslag, A unified approach to off-line permutation routing on parallel networks, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.398-406, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97707]
• 3: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• 4: Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
• 5: H. Hind, M. Molloy, and B. Reed. Colouring graphs frugally. Combinatorica, to appear.
• 6: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 7: C. Kaklamanis, D. Krizanc, T. Tsantilas. Tigth Bounds for Oblivious Routing in the Hypercube. Mathematical Systems Theory 24, pp. 223-232, 1991.
• 8: Jin Suk Kim , Eric Lehman , Tom Leighton, Oblivious Deadlock-Free Routing in a Faulty Hypercube, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.312-319, April 12-16, 1999
• 9: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 10: F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
• 11: F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994.
• 12: Tom Leighton , Satish Rao , Aravind Srinivasan, New algorithmic aspects of the Local Lemma with applications to routing and partitioning, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.643-652, January 17-19, 1999, Baltimore, Maryland, United States
• 13: Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276866]
• 14: Friedhelm Meyer auf der Heide , Berthold Vöcking, Shortest-path routing in arbitrary networks, Journal of Algorithms, v.31 n.1, p.105-131, April 1999 [doi>10.1006/jagm.1998.0980]
• 15: Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
• 16: A. G. Ranade. Equivalence of Message Scheduling Algorithms for Parallel Communication. Tech. Report YALEU/DCS/TR-512, Dept. Comp. Sci., Yale University, NewHaven, CT, 1987.
• 17: Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
• 18: Xiaojun Shen , Qing Hu , Weifa Liang, Realization of an arbitrary permutation on a hypercube, Information Processing Letters, v.51 n.5, p.237-243, Sept. 12, 1994 [doi>10.1016/0020-0190(94)90002-7]
• 19: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 20: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

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)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Design, Performance, Theory, Verification