L. G. Valiant
G. J. Brebner
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.
- 1.D. Angluin and L.G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. of Comp. and Syst. Sci. (1979) 155-193.Google Scholar
Cross Ref
- 2.K. Batcher. Sorting networks and their applications. AFIPS Spring Joint Comp. Conf. 32 (1968) 307-314.Google Scholar
- 3.V.E. Benes. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York (1965).Google Scholar
- 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.Google Scholar
- 5.Z. Galil and W.J. Paul. A practical general purpose parallel computer, (this volume).Google Scholar
- 6.W. Hoeffding. On the distribution of the number of successes in independent trials. Ann. of Math. Stat. 27 (1956) 713-721.Google ScholarCross Ref
- 7.G. Lev, N. Pippenger and L.G. Valiant. A fast parallel algorithm for routing in permutation networks. IEEE Trans. on Computers (1981).Google Scholar
- 8.D. Nassimi and S Sahni Parallel algorithms to set-up the Benes permutation networks. Manuscript, University of Minnesota.Google Scholar
- 9.F.P. Preparata and J. Vuillemin. The cube-connected cycles. IEEE Symp. on Foundations of Comp. Sci, 20 (1979) 140-147.Google Scholar
- 10.M.O. Rabin. Probabilistic algorithms. In "Algorithms and Complexity", J.F. Traub (ed.) Academic Press, New York, 1976.Google Scholar
- 11.J.T. Schwartz. Untracomputers. ACM TOPLAS 2(1980) 484-521. Google ScholarDigital Library
- 12.H.J. Siegel. Interconnection networks for SIMD machines, Computer, June 1979, 57-65.Google ScholarDigital Library
- 13.R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM J. on Computing 6(1977) 84-85.Google ScholarDigital Library
- 14.H. Stone. Parallel processing with the perfect shuffle. IEEE Transactions on Computers, C-20:2, (1971) 153-161.Google ScholarDigital Library
- 15.C.D. Thomson and H.T. Kung. Sorting on a mesh- connected parallel computer. CACM 20:4 (1977) 263-271. Google ScholarDigital Library
- 16.L.G. Valiant. A scheme for fast parallel communication. Report CSR-72-80, Computer Science Department, Edinburgh University, (1980).Google Scholar
- 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).Google Scholar
Index Terms
- Universal schemes for parallel communication
Recommendations
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers
In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected ...
Communication-Efficient Parallel Sorting
We study the problem of sorting n numbers on a p-processor bulk-synchronous parallel (BSP) computer, which is a parallel multicomputer that allows for general processor-to-processor communication rounds provided each processor sends and receives at most ...
Scheduling interval orders with communication delays in parallel
We investigate the complexity of computing an optimal m-processor schedule for a system of n unit execution time tasks constrained by an interval order, subject to unit delays for interprocessor communication. Our results are twofold. First, we show ...
Comments