Leslie Valiant and Bulk Synchronous Parallelism
Leslie Valiant's BSP model organized parallel computation into local work, communication, and global barriers, aiming to bridge portable algorithms and diverse parallel hardware.
Parallel computing lacked a common machine model comparable to the sequential von Neumann abstraction
Sequential programmers benefited from a conceptual machine whose basic costs and control structure could be compiled onto many real processors. Parallel computing was more fragmented: algorithms were often described for idealized PRAMs or tuned directly to one network topology. Leslie Valiant argued that widespread parallel programming needed a bridging model that was abstract enough for software yet faithful enough to the costs real machines could not avoid.[1]
The model had to be both portable and predictive
An abstraction that hides all communication cost is easy to program but poor for performance reasoning; a model that exposes every switch and link is too machine-specific to support durable algorithms.
Valiant’s 1990 paper proposed the bulk synchronous parallel model as that bridge
“A Bridging Model for Parallel Computation” introduced BSP as a candidate interface between parallel algorithms and hardware.[1] The model assumes multiple processors with local computation, a communication network, and periodic global synchronization. Rather than pretending communication is free, BSP assigns numerical parameters that summarize the machine’s ability to move information and synchronize.
Computation proceeds through supersteps
A BSP program is organized into supersteps. During a superstep, processors perform local computation and issue communications. A global barrier then completes the communication phase and synchronizes participants before the next superstep. Later explanations of BSP describe this structure as independent local work followed by communication and a barrier.[4] The regular rhythm turns a complicated asynchronous network into a sequence of phases whose cost can be estimated.
Synchronization is deliberate rather than continuous
BSP does not require processors to coordinate after every operation. It batches communication and synchronization so that algorithms can reason about large units of parallel work.
The p, g, and L parameters make communication cost explicit
Direct BSP algorithm work by Alexandros Gerbessiotis and Valiant describes the standard parameters as p for processor count, g for the cost or inverse bandwidth of communication, and L for the synchronization periodicity or barrier cost.[2] Algorithms can be analyzed as functions of these parameters rather than one machine name. The goal is transportability: software should remain efficient across systems with different processor counts, network bandwidths, and synchronization costs.
BSP tried to make parallel algorithms portable without pretending architectures were identical
Valiant’s research program was explicitly about transportable software. His publication record includes both the original bridging-model paper and later work on direct BSP algorithms and transportable parallel software.[3] The approach accepts that machines differ, but compresses the relevant differences into a few measurable quantities. An algorithm can then choose strategies according to those quantities instead of being rewritten around every network topology.
Parameter awareness replaces topology awareness
A programmer does not need to encode the physical route between every processor pair if the model captures the aggregate cost of communication well enough for algorithmic decisions.
BSPlib translated the model into a concrete programming interface
The BSP community developed BSPlib, a C and Fortran library supporting initialization, processor identification, communication, and global synchronization through operations such as bsp_sync().[4] The library used a single-program-multiple-data style and provided both remote-memory and message-passing operations. This step mattered because a computational model becomes more influential when programmers can test its abstractions in running software rather than only analyze them on paper.
The Oxford BSP toolset turned the model into a portable development environment
Oxford researchers released implementations and profiling tools conforming to the BSPlib standard, with an official release in 1997 after earlier beta versions.[5] Tooling included libraries for multiple machines plus performance analysis support. The effort showed how the BSP idea could guide not only theoretical cost models but practical compilation, debugging, and performance tuning across heterogeneous parallel systems.
Performance models become more useful when tools can measure their parameters
Estimating g and L on a target machine lets the abstract algorithm model connect back to observed hardware behavior.
Why BSP belongs in the history of parallel computation
BSP belongs in parallel-computing history because it confronted one of the field’s persistent problems: how to design algorithms that are neither unrealistically machine-independent nor trapped in one architecture. Valiant proposed a simple phase structure and a small set of cost parameters; later researchers built algorithms, libraries, and toolsets around that idea.[1][2][5]
The model also anticipated later data-parallel systems that organize computation into synchronized rounds, even when they do not use BSP terminology. Bulk processing, communication phases, and barrier-like coordination recur in graph processing, distributed analytics, and accelerator programming.
BSP’s deepest contribution was conceptual. Portable parallel performance requires exposing some costs while hiding others. Valiant’s model offered a disciplined compromise: enough structure to reason about computation and communication, but not so much machine detail that every new supercomputer invalidates the algorithm. That balance gave researchers a common language for comparing algorithms across changing hardware generations and for asking whether communication or synchronization, rather than arithmetic alone, determined scalability.
Works Cited
- 01
- 02
- 03Leslie Valiant — Parallel Computing Publications people.seas.harvard.edu
- 04
- 05Oxford BSP Toolset — Release and Implementation History bsp-worldwide.science.uu.nl
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead