Universal schemes for parallel communication

ABSTRACT

In this paper we isolate a combinatorial problem that, we believe, lies at the heart of this question and provide some encouragingly positive solutions to it. We show that there exists an N-processor realistic computer that can simulate arbitrary idealistic N-processor parallel computations with only a factor of O(log N) loss of runtime efficiency. The main innovation is an O(log N) time randomized routing algorithm. Previous approaches were based on sorting or permutation networks, and implied loss factors of order at least (log N)2.

REFERENCES

• 1: D. Angluin and L.G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. of Comp. and Syst. Sci. (1979) 155-193.
• 2: K. Batcher. Sorting networks and their applications. AFIPS Spring Joint Comp. Conf. 32 (1968) 307-314.
• 3: V.E. Benes. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York (1965).
• 4: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. of Math. Stat. 23 (1952) 493-507.
• 5: Z. Galil and W.J. Paul. A practical general purpose parallel computer, (this volume).
• 6: W. Hoeffding. On the distribution of the number of successes in independent trials. Ann. of Math. Stat. 27 (1956) 713-721.
• 7: G. Lev, N. Pippenger and L.G. Valiant. A fast parallel algorithm for routing in permutation networks. IEEE Trans. on Computers (1981).
• 8: D. Nassimi and S Sahni Parallel algorithms to set-up the Benes permutation networks. Manuscript, University of Minnesota.
• 9: F.P. Preparata and J. Vuillemin. The cube-connected cycles. IEEE Symp. on Foundations of Comp. Sci, 20 (1979) 140-147.
• 10: M.O. Rabin. Probabilistic algorithms. In "Algorithms and Complexity", J.F. Traub (ed.) Academic Press, New York, 1976.
• 11: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 12: H.J. Siegel. Interconnection networks for SIMD machines, Computer, June 1979, 57-65.
• 13: R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM J. on Computing 6(1977) 84-85.
• 14: H. Stone. Parallel processing with the perfect shuffle. IEEE Transactions on Computers, C-20:2, (1971) 153-161.
• 15: C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]
• 16: L.G. Valiant. A scheme for fast parallel communication. Report CSR-72-80, Computer Science Department, Edinburgh University, (1980).
• 17: L.G. Valiant. Experiments with a parallel communication scheme. In Proc. of 18th Allerton Conference on Communication Control and Computing, University of Illinois, Oct. 8-10, (1980).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory