1990 ABridgingModelforParallelComput

(Valiant, 1990) ⇒ Leslie G. Valiant. (1990). “A Bridging Model for Parallel Computation.” In: Communications of the ACM Journal, 33(8). doi:10.1145/79173.79181

Subject Headings: Bulk-Synchronous Parallel (BSP) Model.

Notes

Cited By

Quotes

Abstract

The success of the von Neumann model of sequential computation is attributable to the fact that it is an efficient bridge between software and hardware: high-level languages can be efficiently compiled on to this model; yet it can be effeciently implemented in hardware. The author argues that an analogous bridge between software and hardware in required for parallel computation if that is to become as widely used. This article introduces the bulk-synchronous parallel (BSP) model as a candidate for this role, and gives results quantifying its efficiency both in implementing high-level language features and algorithms, as well as in being implemented in hardware.

References

1. Alok Aggarwal, Ashok K. Chandra, Marc Snir, Communication Complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 doi:10.1016/0304-3975(90)90188-N
2. Aiello, B., Leighton, FT., Maggs, B., and Neumann, M. Fast Algorithms for Bit-serial Routing on a Hypercube. Manuscript, 1990.
3. Anderson, R.J. and Miller, G.L. Optical Communication for Pointer based Algorithms. Tech. Pep. CRI 88-14, Computer Science Dept~, Univ. of Southern California, 1988.
4. 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
5. Carter, J.L. and Wegman, M.N. Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18 (1979) 143-154.
6. David Eppstein, Zvi Galil, Parallel Algorithmic Techniques for Combinatorial Computation, Annual Review of Computer Science: Vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
7. P. B. Gibbons, A More Practical PRAM Model, Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States doi:10.1145/72935.72953
8. Gottlieb, A. Et Al. The NYU Ultracomputer-- Designing An MIMD Shared Memory Parallel Computer. IEEE 7~ans. Comput. 32, 2 (1983) 175-189.
9. Hoeffding, W. Probability Inequalities for Sums of Bounded Random Variables. Am. Stat. Assoc. J. 58 (1963) 13-30.
10. Anna R. Karlin, Eli Upfal, Parallel Hashing: An Efficient Implementation of Shared Memory, Journal of the ACM (JACM), v.35 n.4, p.876-892, Oct. 1988 doi:10.1145/48014.350550
11. Richard M. Karp, Vijaya Ramachandran, Parallel Algorithms for Shared-memory Machines, Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, MIT Press, Cambridge, MA, 1991
12. Clyde P. Kruskal, Larry Rudolph, Marc Snir, A Complexity Theory of Efficient Parallel Algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 doi:10.1016/0304-3975(90)90192-K
13. Richard E. Ladner, Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 doi:10.1145/322217.322232
14. Tom Leighton, Tight Bounds on the Complexity of Parallel Sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 doi:10.1109/TC.1985.5009385
15. Nick Littlestone, From on-line to Batch Learning, Proceedings of the Second Annual Workshop on Computational Learning Theory, p.269-284, December 1989, Santa Cruz, California, United States
16. Maniloff, E.S.,Johnson, K.M., and Reif, J.H. Holographic Routing Network for Parallel Processing Machines. Society of Photo Optical Instrumentation Engineers (SPIE), Paris, France 1989, V 1136, Holographic Optics II, Principles and Applications, 283-289.
17. Kurt Mehlhorn, Uzi Vishkin, Randomized and Deterministic Simulations of PRAMs by Parallel Machines with Restricted Granularity of Parallel Memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
18. Christos Papadimitriou, Mihalis Yannakakis, Towards An Architecture-independent Analysis of Parallel Algorithms, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States doi:10.1145/62212.62262
19. S. Rajasekaran, J. H. Reif, Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 doi:10.1137/0218041
20. Ranade, A.G. How to Emulate Shared Memory. In: Proceedings of the Twenty-eighth IEEE Symposium on Foundations of Computer Science (1987) Pp. 185-194.
21. 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
22. Siegel, A. On Universal Classes of Fast High Performance Hash Functions. In: Proceedings of the Thirtieth IEEE Symposium on Foundations of Computer Science (1989).
23. Lawrence Snyder, Type Architectures, Shared Memory, and the Corollary of Modest Potential, Annual Review of Computer Science Vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
24. Turing, A.M. On Computable Numbers with An Application to the Entscheidungs Problem. In: Proceedings of the London Mathematical Society 42 2 (1936) 230-265; Correction, Ibidem 43 (1937) 544-546.
25. 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
26. Valiant, L.G. A Scheme for Fast Parallel Communication. SIAM Jr. Comput. 11 (1982) 350-361.
27. Valiant, L.G. Optimally Universal Parallel Computers. Phil. Trans. R. Soc. Lond. A326 (1988) 373-376.
28. Valiant, L.G. Bulk-synchronous Parallel Computers. In Parallel Processing and Artificial Intelligence, M. Reeve and S.E. Zenith, Eds., Wiley, 1989 15-22.
29. L. G. Valiant, General Purpose Parallel Architectures, Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, MIT Press, Cambridge, MA, 1991
30. D. W. Walker, Portable Programming Within a Message-passing Model: The FFT As An Example, Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications, p.1438-1450, January 1989, Pasadena, California, United States doi:10.1145/63047.63100;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1990 ABridgingModelforParallelComput	Leslie G. Valiant			A Bridging Model for Parallel Computation				10.1145/79173.79181		1990