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

still a working view ended · each leads to its entry below

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

  1. Parallel algorithm (introduction, Parallelizability), Wikipedia
  2. Parallel computing, Wikipedia
  3. Sorting network, Wikipedia
  4. Parallel RAM, Wikipedia
  5. Analysis of parallel algorithms (Background), Wikipedia
  6. Circuit complexity, Wikipedia
  7. P-complete, Wikipedia
  8. OpenMP (introduction, History), Wikipedia
  9. Data parallelism, Wikipedia
  10. Bulk synchronous parallel, Wikipedia
  11. General-purpose computing on graphics processing units (History), Wikipedia
  12. CUDA (introduction, History), Wikipedia
  13. 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.

  1. 1968-Present

    Sorting network

    How few comparators can sort any input?

    Fly to its tower in Nousfarer

  2. 1974-Present

    Work-Span Analysis

    How fast can a task run on many processors?

    Fly to its tower in Nousfarer

  3. 1975-Present

    Parallel algorithmic primitives

    What small building blocks make parallel algorithms possible?

    Fly to its tower in Nousfarer

  4. 1976-Present

    Data Parallelism

    How can one operation apply to many data at once?

    Fly to its tower in Nousfarer

  5. 1978-Present

    Parallel RAM

    What is a simple model of a parallel computer?

    Fly to its tower in Nousfarer

  6. 1981-Present

    Circuit complexity

    Which problems cannot be solved fast in parallel?

    Fly to its tower in Nousfarer

  7. 1990-Present

    Bulk synchronous parallel

    How should communication and synchronization be charged?

    Fly to its tower in Nousfarer

  8. 1990-Present

    Message Passing

    How do separate computers coordinate without shared memory?

    Fly to its tower in Nousfarer

  9. 2004-Present
  10. 2006-Present

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.

Sorting networkWork-Span AnalysisParallel algorithmic primitivesData ParallelismParallel RAMCircuit complexityBulk synchronous parallelMessage PassingDistributed and Scalable Machine-Lear…General-purpose computing on graphics…

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Parallel Algorithms sits on the Map of Human Knowledge