An Ω(√ log log n) lower bound for routing in optical networks

ABSTRACT

Optical communication is likely to significantly speed up parallel computation because the vast bandwidth of the optical medium can be divided to produce communication networks of very high degree. However, the problem of contention in high-degree networks makes the routing problem in these networks theoretically (and practically) difficult. In this paper we examine Valiant's h-relation routing problem, which is a fundamental problem in the theory of parallel computing. The h-relation routing problem arises both in the direct implementation of specific parallel algorithms on distributed-memory machines and in the general simulation of shared memory models such as the PRAM on distributed-memory machines. In an h -relation routing problem each processor has up to h messages that it wishes to send to other processors and each processor is the destination of at most h messages. We present a lower bound for routing an h-relation (for any h > 1) on a complete optical network of size n. Our lower bound applies to any randomized distributed algorithm for this task. Specifically. we show that the expected number of communication steps required to route an arbitrary h-relation is Wh+loglogn . This is the first known lower bound for this problem which does not restrict the class of algorithms under consideration.

REFERENCES

• 1: RICHARD J. ANDERSON and GARY L. MILLER, Optical Communication for Pointer Based Algorithms, Technical Report CRI 88-14, Computer Science Department, University of Southern California, Los Angeles, CA 90089-0782 USA, 1988.
• 2: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• 3: Patrick W. Dowd, High performance interprocessor communication through optical wavelength division multiple access channels, Proceedings of the 18th annual international symposium on Computer architecture, p.96-105, May 27-30, 1991, Toronto, Ontario, Canada
• 4: P. ERD6S and R. RADO, Intersection theorems for systems of sets, Journal of the London Mathematical Society 35 (1960) 85-90.
• 5: Mary Mehrnoosh Eshaghian, Parallel Algorithms for Image Processing on OMC, IEEE Transactions on Computers, v.40 n.7, p.827-833, July 1991 [doi>10.1109/12.83620]
• 6: FAITH E. FICH, FRIEDHELM MEYER AUF DER HEIDE and AvI WIGDERSON, Lower bounds for parallel random-access machines with unbounded shared memory, Advances in Computing Research 4 (F. Preparata, ed.), JAI Press 1987, 1-15.
• 7: Faith E. Fich , Prabhakar Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal on Computing, v.17 n.3, p.606-627, June 1988 [doi>10.1137/0217037]
• 8: M. Furst, J.B. Saxe and M. Sipser, Parity, Circuits, and the Polynomial Time Hierarchy, Mathematical Systems Theory 17(1)(1984)13-28.
• 9: Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct Bulk-Synchronous Parallel Algorithms, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.1-18, July 08-10, 1992
• 10: Mihály Geréb-Graus , Thanasis Tsantilas, Efficient optical communication in parallel computers, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.41-48, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140906]
• 11: Leslie Ann Goldberg , Mark Jerrum , Tom Leighton , Satish Rao, A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.300-309, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.166108]
• 12: VINCE GROLMUSZ and PRABHAKAR RAGDE, Incomparability in parallel computation, Proceedings of the IEEE Symposium on Foundations of Computer Science 28 (1987) 89-98.
• 13: Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
• 14: Russell Impagliazzo , Ramamohan Paturi , Michael E. Saks, Size-depth trade-offs for threshold circuits, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.541-550, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167233]
• 15: Philip D. MacKenzie, Load balancing requires &OHgr;(log*n) expected time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.94-99, September 1992, Orlando, Florida, United States
• 16: P. D. MacKenzie , C. G. Plaxton , R. Rajaraman, On contention resolution protocols and associated probabilistic phenomena, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.153-162, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195122]
• 17: PHILIP D. MACKENZIE and VIJAYA RAMACHAN- DRAN, Optical Communication and ERCW PRAMs, Pre-print (1994).
• 18: SATISH B. RAO, Properties of an interconnection architecture based on wavelength division multiplexing, Technical Report TR-92-009-3-0054-2, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540 USA, 1992.
• 19: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

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

General Terms:
Algorithms, Theory, Verification