Leslie G. Valiant
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.
- 1 Aggarwal, A., Chandra, A., and Snir, M. Communication complexity of PRAMs. Theor. Comput. $ci. To be published. Google Scholar
Digital Library
- 2 Aiello, B., Leighton, FT., Maggs, B., and Neumann, M. Fast algorithms for bit-serial routing on a hypercube. Manuscript, 1990.Google Scholar
- 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.Google Scholar
- 4 Borodin, A. and Hopcroft, J.E. Routing merging and sorting on parallel models of computation. J. Comput. Syst. Sci 30 (1985) 130-145. Google ScholarDigital Library
- 5 Carter, J.L. and Wegman, M.N. Universal classes of hash functions. J. Comput. Syst. Sci. 18 (1979) 143-154.Google ScholarCross Ref
- 6 Eppstein, D. and Galil, Z. Parallel algorithmic techniques for combinatorial computation. Annu. Rev. Comput. Sci. 3 (1988) 233-83. Google ScholarDigital Library
- 7 Gibbons, P.B. A more practical PRAM model. In Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures. (1989) pp. 158-168. Google ScholarDigital Library
- 8 Gottlieb, A. et al. The NYU ultracomputer-- Designing an MIMD shared memory parallel computer. IEEE 7~ans. Comput. 32, 2 (1983) 175-189.Google Scholar
- 9 Hoeffding, W. Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J. 58 (1963) 13-30.Google ScholarCross Ref
- 10 Karlin, A. and Upfal, E. Parallel hashing-An efficient' implementation of shared memory. J. ACM 35, 4 (1988) 876-892. Google ScholarDigital Library
- 11 Karp, R.M. and Ramachandran, V. A survey of parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. North Holland, Amsterdam, 1990. Google ScholarDigital Library
- 12 Kruskal, C.P., Rudolph, L., and Snir, M. A complexity theory of efficient parallel algorithms. Theor. Comput. Sci. To be published. Google ScholarDigital Library
- 13 Ladner, R.E. and Fischer, M.J. Parallel prefix computation. J. ACM 27 (1980) 831-838. Google ScholarDigital Library
- 14 Leighton, FT. Tight bounds on the complexity of sorting. IEEE 7?ans. Comput. C-34, 4 (1985) 344-354. Google ScholarDigital Library
- 15 Littlestone, N. From on-line to batch learning. COLT 89, Morgan Kaufmann, San Mateo, CA., (1989) 269-284. Google ScholarDigital Library
- 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.Google Scholar
- 17 Mehlhorn, K. and Vishkin, U. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Inf. 21 (1984) 339-374. Google ScholarDigital Library
- 18 Papadimitriou, C.H. and Yannakakis, M. Towards an architecture-independent analysis of parallel algorithms. In Proceedings of the Twentieth ACM Symposium on Theory of Computing (1988) pp. 510-513. Google ScholarDigital Library
- 19 Rajasekaran, S. and Reif, J.H. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAMJ. Comput. 18, 3 (1989) 594-607. Google ScholarDigital Library
- 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.Google Scholar
- 21 Schwartz, J.T. Ultracomputers ACM TOPLAS 2 (1980) 484-521. Google ScholarDigital Library
- 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).Google Scholar
- 23 Snyder, L. Type architectures, shared memory, and the corollary of modest potential. Annu. Rev. Comput. Sci. 1, (1986)289-317. Google ScholarDigital Library
- 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.Google Scholar
- 25 Upfal, E. Efficient schemes for parallel cornmunication. J. ACM 31, 3 (1984) 507-517. Google ScholarDigital Library
- 26 Valiant, L.G. A scheme for fast parallel communication. SIAM jr. Comput. 11 (1982) 350-361.Google Scholar
- 27 Valiant, L.G. Optimally universal parallel computers. Phil. Trans. R. Soc. Lond. A326 (1988) 373-376.Google ScholarCross Ref
- 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.Google Scholar
- 29 Valiant, L.G. General purpose parallel architectures. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., North Holland, Amsterdam 1990. Google ScholarDigital Library
- 30 Walker, D.W. Portable programming within a message passing model: the FFT as an example. In Proc. 3rd Conference on Hypercube Concurrent Computers and Applications (1988), ACM Press. Google ScholarDigital Library
Index Terms
- A bridging model for parallel computation
Recommendations
Performance Evaluation of Practical Parallel Computation Model LogPQ
ISPAN '99: Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and NetworksMassively parallel computers consisting of a large number of processing elements have been developed and expected as high performance computers in advanced science and technology. Practical parallel computation model has been required to analyze ...
Reviews
Ronald J. Watro
Valiant observes that parallel processing has not made the expected progress in displacing sequential processing in computationally intensive domains. He attributes this failure to the lack of an appropriate bridging model for parallel computation, analogous to the von Neumann model for sequential computation. He then proposes the bulk-synchronous parallel (BSP) model as a candidate bridging model. The key claim concerning BSP is that it provides a fixed intermediate-level model through which high-level programs can be efficiently mapped to diverse machine architectures. The paper supports the claim with evidence of varying sorts: certain high-level constructs (such as memory hashing) and algorithms are efficiently implemented in BSP, and BSP is implemented in two low-level models. Most of the arguments are only sketched, with details left to the references. The BSP model consists of (1) components (each performing processing or memory functions or both), (2) a point-to-point routing mechanism for delivering messages between components, and (3) facilities for periodic synchronization of components. The efficiency of BSP as a bridging model is improved by parallel slackness in programs; that is, the number of virtual processes must be sufficiently larger than the number of processors. Another parameter important to BSP efficiency is the ratio <__?__Pub Fmt italic>g<__?__Pub Fmt /italic> of total local computation rate to total router delivery rate. Valiant states that existing machines have <__?__Pub Fmt italic>g<__?__Pub Fmt /italic>-values higher than ideal for BSP and investment in communication hardware to reduce <__?__Pub Fmt italic>g<__?__Pub Fmt /italic> (and keep it small as machine size increases) will result in more programmable machines. The paper is a brief, well-written introduction to a research topic. Whether a bridging model is needed for practical progress in parallel processing, or whether BSP is a suitable bridging model, remains unclear. The author does not discuss evidence against the existence of bridging models; for instance, parallel and distributed processing form a continuum with vastly different properties from one end to the other. Finally,<__?__Pub Caret> one might consider the analogous failure of nuclear fusion reactors to replace fission reactors—is something lacking in our understanding of fusion, or is fusion simply a more difficult engineering problem than was first expected__?__
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments