A bridging model for parallel computation
Communications of the ACMPublished 1 August 1990Open access
Leslie G. Valiant
Citations3,680
SJR quartileQ1
SJR score1.15
SNIP3.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The bulk-synchronous parallel (BSP) model is introduced as a candidate for this role, and results quantifying its efficiency both in implementing high-level language features and algorithms, as well as in being implemented in hardware.
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.
Keywords
Computer Science
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
4,750 Citations1963Wassily Hoeffding
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
Journal of Computer and System SciencesUniversal classes of hash functions
2,573 Citations1979J.Lawrence Carter, Mark N. Wegman
An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.
Journal of the ACMParallel Prefix Computation
1,282 Citations1980Richard E. Ladner, Michael J. Fischer
A recurstve construction is used to obtain a product circuit for solving the prefix problem and a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n is obtained for n-bit binary addmon.
IEEE Transactions on ComputersThe NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
745 Citations1983Gottlieb, Grishman +4 more
SIAM Journal on ComputingA Scheme for Fast Parallel Communication
643 Citations1982Leslie G. Valiant
There is a distributed randomized algorithm that can route every packet to its destination without two packets passing down the same wire at any one time, and finishes within time $O(\log N)$ with overwhelming probability for all such routing requests.
SIAM Journal on ComputingTowards an Architecture-Independent Analysis of Parallel Algorithms
387 Citations1990Christos H. Papadimitriou, Mihalis Yannakakis
IEEE Transactions on ComputersTight Bounds on the Complexity of Parallel Sorting
371 Citations1985Tom Leighton
Journal of Computer and System SciencesRouting, merging, and sorting on parallel models of computation
325 Citations1985Allan Borodin, John E. Hopcroft
Within a spectrum of shared memory models, it is shown that loglog n is asymptotically optimal for n processors to merge two sorted lists containing n elements.
A Survey of Parallel Algorithms for Shared-Memory Machines
322 Citations1988Richard M. Karp
A survey of the growing body of theory concerned with parallel algorithms and the complexity of parallel computation, which considers the parallel random-access machine (PRAM), in which it is assumed that each processor has random access in unit time to any cell of a global memory.
ACM Transactions on Programming Languages and SystemsUltracomputers
288 Citations1980Jacob T. Schwartz
Theoretical Computer ScienceCommunication complexity of PRAMs
246 Citations1990Alok Aggarwal, Ashok K. Chandra +1 more
A model for the concurrent read exclusive write PRAM that captures its communication and computational requirements is proposed and several results are presented, including the following.
Theoretical Computer ScienceA complexity theory of efficient parallel algorithms
228 Citations1990Clyde P. Kruskal, Larry Rudolph +1 more
The relationship between various models of parallel computation is investigated, using a newly defined concept of efficient simulation, and it is proved that the class PE is invariant across the shared memory models (PRAM's) and fully connected message passing machines.
A more practical PRAM model
228 Citations1989Phillip B. Gibbons
This paper introduces the Asynchronous PRAM model of computation, a variant of the PRAM in which the processors run asy ~chronously and there is an explicit charge for synchronization.
How to emulate shared memory
219 Citations1987Abhiram Ranade
This work presents a simple algorithm for emulating an N processor CRCW PRAM on an N node butterfly that improves the result of Pippenger by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock.
Acta InformaticaRandomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
211 Citations1984Kurt Mehlhorn, Uzi Vishkin
The present paper provides a comprehensive study of algorithms which are designed for shared memory models of parallel computation (PRAMs) in which processors are allowed to have fairly unrestricted access patterns to the shared memory.
SIAM Journal on ComputingOptimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
174 Citations1989Sanguthevar Rajasekaran, John H. Reif
The main result is an optimal randomized parallel algorithm for INTEGER_SORT, the first known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size.
General Purpose Parallel Architectures.
150 Citations1990Leslie G. Valiant
Journal of the ACMEfficient Schemes for Parallel Communication
137 Citations1984Eli Upfal
It is proved that this network topology enables a fully distributed probabilistic algorithm to execute a variety of communication requests efficiently and suggests an efficient solution to a fundamental problem in the design of parallel computers.
Annual Review of Computer ScienceType Architectures, Shared Memory, and the Corollary of Modest Potential
108 Citations1986L. Snyder
The fact that Babbage considered parallelism allows us to conjure that nearly a century and a half ago he understood the obvious, but nevertheless, Fundamental Law of Parallel Computation: A parallel solution utilizing p processors can improve the best sequential solu tion by at most a factor of p.
Towards an architecture-independent analysis of parallel algorithms
102 Citations1988Christos H. Papadimitriou, Mihalis Yannakakis
A simple and efficient method for evaluating the performance of an algorithm, rendered as a directed acyclic graph, on any parallel computer is presented and its application to several common algorithms shows that it is surprisingly accurate.
Annual Review of Computer ScienceParallel Algorithmic Techniques For CombinationalComputation
100 Citations1988David Eppstein, Zvi Galil
On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications
99 Citations1989Andrew F. Siegel
A mechanism is provided for constructing log-n-wise-independent hash functions that can be evaluated in O(1) time, and double hashing using these universal functions has (constant factor) optimal performance in time, for suitably moderate loads.
Journal of the ACMParallel hashing
52 Citations1988Anna R. Karlin, Eli Upfal
A probabilistic scheme for implementing shared memory on a bounded-degree network of processors that enables n processors to store and retrieve an arbitrary set of n data items in O(logn) parallel steps is presented.
Fast algorithms for bit-serial routing on a hypercube
31 Citations1990Bill Aiello, Frank Thomson Leighton +2 more
Optimally Universal Parallel Computers
27 Citations1989Leslie G. Valiant
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEHolographic Routing Network For Parallel Processing Machines
13 Citations1989Eric S. Maniloff, Kristina M. Johnson +1 more
A holographic router for connecting four originator processors to four destination processors is presented and the design and experimental results of a holographic routers involving spatial light modulators and volume holograms are presented.
Philosophical Transactions of the Royal Society of London Series A Mathematical and Physical SciencesOptimally universal parallel computers
12 Citations1988Leslie G. Valiant
It is shown that any program written for the idealized shared-memory model of parallel computation can be simulated on a hypercube architecture with only constant factor inefficiency, provided that the original program has a certain amount of parallel slackness.
Portable programming within a message-passing model: the FFT as an example
10 Citations1988David Walker
A portable programming environment for MIMD concurrent processors based on an object-oriented, message-passing paradigm using the Virtual Machine Loosely Synchronous Communication System (VMLSCS), which is designed to be used for loosely synchronous problems.