- Atlas
- Computer Science
- Parallel Algorithms
Parallel Algorithms
A parallel algorithm is a procedure that solves a problem by doing many things at once.
10 frameworks, from 1968 to today · Algorithms · Computer Science
- Sorting network 1968-Present
- Work-Span Analysis 1974-Present
- Parallel algorithmic primitives 1975-Present
- Data Parallelism 1976-Present
- Parallel RAM 1978-Present
- Circuit complexity 1981-Present
- Bulk synchronous parallel 1990-Present
- Message Passing 1990-Present
- Distributed and Scalable Machine-Learning Parallelism 2004-Present
- General-purpose computing on graphics processing units 2006-Present
Overview
A parallel algorithm is a procedure that solves a problem by doing many things at once1. The point is not merely speed but scale: a task that would take one processor years may take a thousand processors hours, and some problems—simulating a galaxy, training a language model, sorting a billion records—are practical only if the work is divided2. The history of parallel algorithms is the history of learning how to divide work well: what can be split, how the pieces should talk to each other, what it costs to coordinate, and which problems resist splitting altogether1. It is a history of models as much as machines, because to reason about many processors at once, theorists had to invent simplified pictures of what a parallel computer is1.
Sorting Networks and the First Parallel Ideas
Long before electronic computers, engineers reasoned about doing computation in parallel. The clearest early case is the sorting network: a fixed pattern of comparison-exchange units, each taking two inputs and emitting them in order, wired so that any input emerges sorted3. The idea grew out of telephone switching and relay logic in the mid-twentieth century. In 1968, Ken Batcher, working at IBM, published the odd-even mergesort and bitonic sorters—networks of striking elegance built from a simple merge step, sorting n items with on the order of log²n layers of comparators. These networks are data-oblivious: the sequence of comparisons does not depend on the input, which makes them natural for hardware and, later, for graphics processors3.
Sorting networks raised a theoretical question that shaped the field: how few comparators does sorting require? The answer came from an unexpected direction. In 1983, Ajtai, Komlós, and Szemerédi constructed the AKS network, sorting in O(log n) depth—asymptotically optimal—though with enormous constants that made it useless in practice. The gap between the optimal network and the practical ones became a recurring theme: parallel algorithms often trade theoretical efficiency for constant factors that matter enormously on real machines.
The PRAM: A Model for Thinking in Parallel
The decisive move in turning parallelism into a theory came in the late 1970s and early 1980s with the Parallel Random Access Machine, or PRAM. The PRAM imagines many processors sharing one large memory, each able to read or write any cell in a single step, with variants distinguished by how they handle simultaneous access to the same cell (exclusive read/write, concurrent read, concurrent write). It is a deliberately unrealistic model—real machines cannot have thousands of processors hit one memory bank at once without cost—but it made parallel complexity analyzable in the same style as sequential algorithms: count steps, ignore communication4.
The PRAM produced a golden age of parallel algorithm design. Work by researchers including Richard Karp, Uzi Vishkin, Gary Miller, John Reif, and many others showed that problems long thought inherently sequential—list ranking, prefix sums, connected components, tree contraction—could be solved in polylogarithmic time with polynomial work. The key technique was parallel algorithmic primitives: small, reusable building blocks such as the prefix sum (computing all running totals of a list in parallel), list ranking (assigning each element of a linked list its distance from the end), and parallel tree contraction. These primitives were the parallel analogue of the basic data structures of sequential programming, and whole families of graph and string algorithms were built on them.
The PRAM also gave the field its central yardstick, work-span analysis in embryo: an algorithm was judged by its total work (roughly, the sequential time) and its span or depth (the longest chain of dependent steps)5. A good parallel algorithm keeps work close to the best sequential algorithm while driving span down. Brent's theorem, from 1974, made the link explicit: a computation with work W and span S runs on P processors in time roughly W/P + S. This simple inequality remains the backbone of parallel performance reasoning.
Lower Bounds and the Limits of Parallelism
Not everything parallelizes1. The theory of circuit complexity supplied the field's deepest negative results6. A parallel computation of bounded depth is, in effect, a circuit of bounded depth, and circuit lower bounds therefore translate into statements about what cannot be done fast in parallel6. The most famous is the 1987 result of Furst, Saxe, and Sipser (with a simpler proof soon after by Håstad) that parity cannot be computed by constant-depth circuits of bounded fan-in—so parity is not in the class AC⁰. This anchored a hierarchy of parallel complexity classes (NC, AC, and their relatives) and gave the field a precise language for asking which problems have efficient parallel algorithms at all6. The open question of whether P equals NC—whether every efficiently sequential problem is efficiently parallel—remains unresolved and is one of the field's defining puzzles7.
Shared Memory in Practice and the Rise of Work-Span
The PRAM's unrealistic memory model met reality in the 1980s and 1990s as shared-memory multiprocessors arrived, and with them the problem of synchronization and contention: processors fighting over the same data, and the cost of locking. Practical parallel programming languages and libraries—from early threads packages to OpenMP in the late 1990s—gave programmers tools to express parallelism, but performance was fragile8.
The theoretical response was multithreaded work-span analysis, crystallized in the 1990s and 2000s by Charles Leiserson, Robert Blumofe, Matteo Frigo, and others around the Cilk project at MIT. Cilk introduced the spawn and sync primitives and a provably efficient scheduler: a randomized work-stealing scheduler that runs any computation with work W and span S on P processors in expected time O(W/P + S), with near-optimal space. This was a landmark because it made the abstract work-span model a practical guarantee: programmers could write natural recursive parallel code and trust the runtime to schedule it well. The model, now standard, underlies Java's Fork/Join framework, Intel's Threading Building Blocks, and many task-parallel systems.
Data Parallelism and the Vector Machines
A different tradition ran alongside the shared-memory one: data parallelism, in which the same operation is applied to every element of a large array at once9. It began with vector supercomputers such as the Cray-1 (1976), whose vector instructions processed streams of numbers, and with SIMD (single instruction, multiple data) architectures. The intellectual appeal was that data-parallel code is simple and scales with array size; the practical appeal was that hardware could be built to exploit it. The Connection Machine of the 1980s pushed this to tens of thousands of tiny processors. Data parallelism later became the dominant idiom of graphics processors and, through them, of modern machine learning.
Message Passing and Bulk Synchronous Parallelism
Machines built from many separate computers needed a model without shared memory. Message passing—processes communicating by explicit send and receive—became the standard, codified in the MPI standard in the early 1990s, which remains the backbone of scientific supercomputing. Its theoretical companion was the Bulk Synchronous Parallel (BSP) model, proposed by Leslie Valiant in 1990. BSP divides a computation into supersteps: in each, every processor does local work, sends messages, and then waits at a barrier for all messages to arrive. The model charges for computation, communication, and synchronization separately, giving a portable way to predict performance across very different machines. BSP and its descendants (such as the "bridging model" used in later performance analysis) gave parallel algorithm designers a way to reason about communication cost, which the PRAM had ignored10.
GPGPU and Many-Thread Programming
The graphics processing unit, built to shade millions of pixels in parallel, turned out to be a general-purpose parallel computer. Around 2006–2007, NVIDIA's CUDA and the cross-vendor OpenCL made it possible to program GPUs directly1112. The GPGPU (general-purpose computing on graphics processing units) model is a distinctive one: thousands of lightweight threads organized into warps and blocks, with a memory hierarchy of registers, shared memory, and global memory, and a strong preference for regular, branch-free, data-parallel code. Algorithms had to be redesigned for this shape—sorting networks and scan (prefix sum) primitives, familiar from the PRAM era, proved ideally suited. The GPU became the workhorse of deep learning, and many-thread programming models became the practical face of parallelism for a generation of programmers.
Distributed and Scalable Machine Learning
The most recent turning point is the rise of distributed and scalable machine-learning parallelism, driven by models too large for any single machine. Two broad strategies emerged. Data parallelism splits a training batch across workers, each computing gradients on its share and then averaging them—simple, but communication-heavy. Model parallelism splits the model itself across devices, necessary when a single layer exceeds one device's memory. Frameworks such as Google's MapReduce (2004) and its successors, parameter-server architectures, and later systems like Horovod and Megatron-LM made these patterns practical at scale. The field now blends classical concerns—work-span, communication cost, synchronization—with new ones: numerical stability under reduced precision, straggler tolerance, and the trade-off between batch size and convergence.
The Present
Parallel algorithms today are designed against a spectrum of models that descend directly from this history: work-span analysis for multicore task parallelism, BSP-style cost models for clusters, the SIMT (single instruction, multiple threads) model for GPUs, and hybrid schemes for machine learning at scale. The PRAM survives as a teaching and lower-bound tool; sorting networks and scan primitives, once curiosities of hardware design, are now everyday GPU idioms313. The open questions are old and new: whether P equals NC, how to schedule irregular computations without losing provable efficiency, how to reason about communication as it increasingly dominates cost, and how far the work-span and bulk-synchronous frameworks can be stretched to cover heterogeneous machines and enormous learned models7.
References
- Parallel algorithm (introduction, Parallelizability), Wikipedia
- Parallel computing, Wikipedia
- Sorting network, Wikipedia
- Parallel RAM, Wikipedia
- Analysis of parallel algorithms (Background), Wikipedia
- Circuit complexity, Wikipedia
- P-complete, Wikipedia
- OpenMP (introduction, History), Wikipedia
- Data parallelism, Wikipedia
- Bulk synchronous parallel, Wikipedia
- General-purpose computing on graphics processing units (History), Wikipedia
- CUDA (introduction, History), Wikipedia
- Prefix sum, Wikipedia
The frameworks of Parallel Algorithms
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1968-Present
- 1974-Present
- 1975-Present
Parallel algorithmic primitives
What small building blocks make parallel algorithms possible?
- 1976-Present
- 1978-Present
- 1981-Present
- 1990-Present
Bulk synchronous parallel
How should communication and synchronization be charged?
- 1990-Present
Message Passing
How do separate computers coordinate without shared memory?
- 2004-Present
Distributed and Scalable Machine-Learning Parallelism
How can training be scaled across many machines?
- 2006-Present
General-purpose computing on graphics processing units
How can graphics chips be used for general computation?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
General-purpose computing on graphics processing units grew out of Data Parallelism
Data parallelism, developed on vector machines and SIMD architectures, is the direct ancestor of GPU programming: CUDA and OpenCL apply one operation across many threads, the same idiom as vector and SIMD processing. GPGPU is the generalization of data parallelism to thousands of lightweight threads.
Carried by NVIDIA CUDA (2007).
Distributed and Scalable Machine-Learning Parallelism grew out of Message Passing
Distributed and scalable machine-learning parallelism grew out of message-passing practice: parameter servers, all-reduce and gradient exchange are message-passing protocols over clusters. MPI-style communication remains the substrate of large-scale training.
Circuit complexity influenced by Sorting network
Sorting networks are fixed-depth comparator circuits, and the question of how few comparators sorting requires became a canonical problem in circuit complexity. The AKS network (1983) and the depth/width tradeoffs of sorting networks fed directly into the study of bounded-depth circuits and the NC/AC hierarchy.
Carried by Miklós Ajtai; János Komlós; Endre Szemerédi.
General-purpose computing on graphics processing units influenced by Sorting network
Sorting networks are data-oblivious and branch-free, which made them ideally suited to GPU execution; GPU sorting implementations (e.g. bitonic sort) reused Batcher's networks directly. The GPGPU community adopted sorting networks as a standard primitive.
Carried by Ken Batcher.
Parallel RAM influenced by Work-Span Analysis
The PRAM's step-counting model and its work/depth measures were taken up by multithreaded work-span analysis, which kept the abstraction of counting steps and dependencies while adding a scheduler guarantee. Cilk's work-stealing analysis is explicitly framed against the PRAM tradition.
Carried by Charles Leiserson; Robert Blumofe; Matteo Frigo.
General-purpose computing on graphics processing units influenced by Parallel algorithmic primitives
The prefix-sum (scan) primitive developed in the PRAM era became a core GPU building block, implemented as a work-efficient scan on many-thread hardware. GPU algorithm designers explicitly revived PRAM primitives such as scan and list ranking.
Circuit complexity influenced by Parallel RAM
The PRAM's parallel time classes motivated the definition of circuit complexity classes NC and AC as their circuit analogues, and PRAM simulations of bounded-depth circuits established the correspondence. Circuit lower bounds were then read as limits on PRAM parallelism.
Bulk synchronous parallel reacted against Parallel RAM
BSP was proposed by Valiant as a model that charges for communication and synchronization, precisely the costs the PRAM ignored. It defined itself against the PRAM's unrealistic shared-memory assumption.
Carried by Leslie Valiant.
Distributed and Scalable Machine-Learning Parallelism influenced by Bulk synchronous parallel
BSP's superstep structure, with local computation followed by a barrier and message exchange, is the template for synchronous distributed training with all-reduce and parameter-server barriers. Distributed ML systems adopted the bulk-synchronous execution pattern directly.
Message Passing rival of Parallel RAM
Message passing arose for machines without shared memory, rejecting the PRAM's single-memory abstraction in favor of explicit send and receive. MPI codified this alternative model in the early 1990s.
Beyond the field
Where Parallel Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 41 links.
Data Parallelism grew out of SIMD architectures in Parallel Computing
Data parallelism grew directly out of SIMD architectures, generalizing the idea of applying one operation to many data elements into a programming model. The term and concept were formulated as the software counterpart of SIMD hardware execution.
Distributed and Scalable Machine-Learning Parallelism led to Model and Data Parallelism with Mixed Precision in ML Systems
Model and data parallelism with mixed precision is a direct refinement of distributed and scalable ML parallelism, extending its parameter-server and collective-communication schemes with mixed-precision arithmetic. The later work grew out of the earlier scaling methods as a branch specialized for deep networks.
Sorting network influenced by Switching circuit theory in Digital Systems
Sorting networks were conceived as comparator networks built from switching elements, and their theory drew on the Boolean circuit and switching-circuit formalism developed by Shannon and later switching theorists. The model of a network of two-input comparators is a direct descendant of the switching circuit model.
Carried by Claude Shannon.
Work-Span Analysis influenced by Asymptotic Analysis in Algorithms
Work-span analysis applies asymptotic (big-O) reasoning to parallel algorithms, measuring work and span as functions of input size. The Brent-style scheduling bound and the work-span model were formulated using the asymptotic notation and worst-case analysis conventions of algorithm analysis.
Parallel algorithmic primitives influenced Parallel Query Processing in Query Processing
Parallel query processing built its operators on parallel algorithmic primitives such as parallel scan, sort, and hash partitioning. These primitives supplied the implementation techniques for intra-query parallelism.
Parallel algorithmic primitives influenced Parallel and distributed query processing in Query Processing
Parallel query processing reused parallel algorithmic primitives such as parallel scan, sort, and hash partitioning developed in parallel algorithms research. These primitives became the building blocks of parallel join and aggregation operators.
Parallel algorithmic primitives influenced by SIMD architectures in Parallel Computing
Parallel primitives like scan and reduction were designed to map onto SIMD architectures, where the same operation is applied across many data elements. The primitive model reflects the SIMD execution style of applying uniform operations to vectors of data.
Parallel algorithmic primitives influenced by Parallel and Vector Computing in Computer Systems
Parallel algorithmic primitives such as scan, reduction and parallel prefix were developed in the context of parallel and vector computing, where they were implemented as hardware and library operations. The primitives abstracted operations that vector and parallel machines provided.
Data Parallelism influenced MapReduce in Data Science
MapReduce is a restricted data-parallel model, and its map and reduce phases generalise the data-parallel primitives developed in parallel algorithms research.
Data Parallelism influenced Parallel Query Processing in Query Processing
Data parallelism supplied the partitioning-and-replication model that parallel query processing adopted for executing relational operators across many processors. This shaped shared-nothing parallel database designs.
Data Parallelism influenced Parallel and distributed query processing in Query Processing
Data parallelism, the idea of applying the same operation across partitioned data, was taken up in parallel query processing as the basis for partitioning and parallel operator execution. This shaped the design of shared-nothing parallel database systems.
Data Parallelism influenced Parallel database in Big Data Processing
Parallel database design borrowed the idea of data parallelism, partitioning relations across processors so the same operation runs on each partition, from parallel algorithm research of the 1970s.

Parallel Algorithms is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Parallel AlgorithmsRelated fields
Fields its ideas are linked to
- Parallel Computing 13 links
- Query Processing 5 links
- Computer Systems 5 links
- ML Systems 3 links
- Big Data Processing 2 links
- Data Science 2 links
- Distributed Databases 2 links
- Distributed Systems 2 links
- Complexity Theory 2 links
- Algorithms 1 link
- Streaming Algorithms 1 link
- Digital Systems 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Online Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
- String Algorithms
See where Parallel Algorithms sits on the Map of Human Knowledge