Tight bounds for oblivious routing in the hypercube
Tóm tắt
We prove that in anyN-node communication network with maximum degreed, any deterministic oblivious algorithm for routing an arbitrary permutation requires Ω(√N/d) parallel communication steps in the worst case. This is an improvement upon the Ω(√N/d
3/2) bound obtained by Borodin and Hopcroft. For theN-node hypercube, in particular, we show a matching upper bound by exhibiting a deterministic oblivious algorithm that routes any permutation in Θ(√N/logN) steps. The best previously known upper bound was Θ(√N). Our algorithm may be practical for smallN (up to about 214 nodes).
Tài liệu tham khảo
B. Aiello and T. Leighton, Coding Theory, Hypercube Embeddings, and Fault Tolerance, inProc. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991, pp. 125–136.
R. Aleliunas, Randomized Parallel Communication, inProc. ACM Symposium on Principles of Distributed Computing, 1982, pp. 60–72.
J. Aubert and B. Schneider, Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens,Discrete Math.,38 (1982), 7–16.
A. Borodin and J. Hopcroft, Routing, Merging and Sorting on Parallel Models of Computation,J. Comput. System Sci.,30 (1985), 130–145.
J. Bosák,Decompositions of Graphs, Kluwer, Boston 1990.
D. Krizanc, Oblivious Routing with Limited Buffer Capacity,J. Comput. System Sci. (to appear).
D. Krizanc, D. Peleg, and E. Upfal, A Time-Randomness Tradeoff for Oblivious Routing, inProc. 20th ACM Symposium on Theory of Computing, 1988, pp. 93–102.
I. Parberry, An Optimal Time Bound for Oblivious Routing,Algorithmica,5 (1990), 243–250.
M. O. Rabin, Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance,J. Assoc. Comput. Mach.,36 (1989), 335–348.
S. Rajasekaran and Th. Tsantilas, Optimal Routing Algorithms for Mesh-Connected Processor Arrays,Algorithmica (to appear). Preliminary version inProc. AWOC '88, Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, Berlin, 1988, pp. 411–422.
G. Ringel, Über drei kombinatorische Probleme amn-dimensionalen Würfel und Würfelgitter,Abh. Math. Semi. Univ. Hamburg,20 (1955), 10–19.
J. Ullman,Computational Aspects of VLSI, Computer Science Press, Rockville, MD, 1984.
E. Upfal, Efficient Schemes for Parallel Communication,J. Assoc. Comput. Mach.,31 (1984), 507–517.
L. G. Valiant, A Scheme for Fast Parallel Communication,SIAM J. Comput.,11 (1982), 350–361.
L. G. Valiant, General Purpose Parallel Architectures, inHandbook of Theoretical Computer Science (ed. J. van Leeuwan), Elsevier, Amsterdam, and MIT Press, Cambridge, MA, 1990, pp. 943–971.
L. G. Valiant and G. J. Brebner, Universal Schemes for Parallel Communication, inProc. 13th ACM Symposium on Theorry of Computing, 1981, pp. 263–277.
D. H. Wiedemann, Hamming Geometry, Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, 1986.