Loading field map
Parallel algorithms are procedures designed to solve computational problems using multiple processing elements simultaneously. Where a sequential algorithm performs one operation at a time, a parallel algorithm coordinates many operations that proceed concurrently, exchanging data when needed. The subfield studies how to decompose problems into tasks that can run at once, how to organize communication and synchronization among those tasks, and how to reason about the speed and efficiency gains—and losses—that parallelism introduces.
The foundational question is deceptively simple: given a problem, how much faster can it be solved with many processors than with one? The answer is rarely linear. Doubling the number of processors rarely halves the running time, because of communication overhead, load imbalance, and the inherently sequential portions of many computations. This observation is captured in Amdahl's Law, which states that the speedup achievable by parallelization is bounded by the fraction of the computation that must remain sequential. If 10% of a computation is sequential, the maximum speedup is tenfold, no matter how many processors are added. A later refinement, Gustafson's Law, argues from a different scaling perspective: if the problem size grows with the number of processors, the sequential fraction becomes proportionally less significant, allowing near-linear speedup on large enough instances.
Beyond raw speedup, parallel algorithm designers ask structural questions. What is the minimum time required to solve a problem with unlimited processors? This leads to the notion of parallel time complexity, often measured in terms of the number of parallel steps. What is the work—the total number of operations performed across all processors? A parallel algorithm is work-efficient if it performs no more total operations than the best sequential algorithm for the same problem. A central goal is to find algorithms that are both fast (low parallel time) and work-efficient, a combination that is often difficult to achieve.
Another fundamental question concerns which problems are inherently parallelizable and which are not. Some problems, like matrix multiplication or image filtering, decompose naturally into independent subtasks. Others, like computing the nth Fibonacci number or traversing a linked list, appear to require sequential dependencies. Yet even seemingly sequential problems can sometimes be reorganized. The parallel prefix (or scan) operation—computing all prefix sums of an array—appears sequential at first glance, but can be computed in logarithmic time with a clever tree-based scheme. Understanding which problems admit such restructuring is a core theoretical concern.
The intellectual roots of parallel algorithms predate modern parallel computers. In the 1960s and 1970s, researchers studying cellular automata, sorting networks, and VLSI (very-large-scale integration) circuit design developed techniques for organizing concurrent computation. Sorting networks, for example, are fixed circuits of comparators that sort inputs without any central control, and their study produced early insights into parallel comparison and exchange patterns.
The field crystallized as a distinct discipline in the 1980s with the development of theoretical models for parallel computation. The most influential was the Parallel Random Access Machine (PRAM), an idealized model in which any number of processors share a single memory and can access it in one time step. The PRAM abstracts away communication costs, allowing researchers to focus purely on the logical structure of parallel algorithms. Variants of the PRAM differ in how simultaneous memory accesses are handled: the Exclusive Read, Exclusive Write (EREW) model forbids any concurrent access; the Concurrent Read, Exclusive Write (CREW) model allows simultaneous reads; and the Concurrent Read, Concurrent Write (CRCW) model allows both, with different conventions for resolving write conflicts. These distinctions matter because algorithms that work on stronger models may not port directly to weaker ones.
The PRAM model produced a rich body of algorithmic results—efficient parallel algorithms for sorting, graph problems, and computational geometry—but it also drew criticism for being unrealistic. Real parallel machines have memory hierarchies, communication networks with finite bandwidth, and synchronization costs that the PRAM ignores. This gap between theory and practice motivated the development of more realistic models, including the Bulk Synchronous Parallel (BSP) model, which explicitly accounts for communication costs and synchronization barriers, and the LogP model, which captures latency, overhead, bandwidth, and processor count as separate parameters.
The PRAM tradition treats parallel algorithm design as a branch of complexity theory. The goal is to classify problems by their parallel time and work requirements, and to discover algorithms that achieve optimal trade-offs. A landmark result in this tradition is the parallel computation thesis: the class of problems solvable in polynomial time on a PRAM with polynomially many processors corresponds to the class solvable in polynomial space on a sequential machine. This connection links parallel complexity to classical complexity theory.
Within the PRAM tradition, a key concept is parallelizability classes. Problems solvable in polylogarithmic time with polynomial work are said to be in the class NC (Nick's Class, named after Nick Pippenger). Problems that are P-complete—complete for the class of problems solvable in polynomial time on a sequential machine—are believed not to be in NC, meaning they are probably inherently sequential. The P-complete problems include many linear programming variants and certain circuit value problems. The conjecture that P ≠ NC is one of the central open questions in parallel complexity theory, analogous to the P vs. NP question but less widely known.
The PRAM tradition also produced important algorithmic techniques. Divide and conquer adapts naturally to parallelism: split a problem, solve the halves concurrently, then combine results. Pointer jumping (also called path doubling) replaces sequential traversal of a linked structure with repeated halving of distances, reducing time from linear to logarithmic. Doubling techniques underlie parallel prefix computation and many graph algorithms. Randomization also plays a role: some problems, like finding a maximal independent set, have simple randomized parallel algorithms that are faster than any known deterministic ones.
While the PRAM tradition assumes shared memory, the distributed memory approach models processors that each have their own local memory and communicate by passing messages over a network. This approach is closer to how most large-scale parallel machines actually work. The central design problem is data distribution: deciding which processor holds which portion of the data, and how to route communication between processors.
A major sub-problem is communication-avoiding algorithm design. Since message passing is typically orders of magnitude slower than local computation, algorithms that minimize communication volume and the number of communication rounds often outperform algorithms that minimize total operations. This insight has led to a reformulation of classical algorithms. For example, the standard matrix multiplication algorithm can be reorganized so that each processor performs many local multiplications between communication steps, reducing the communication-to-computation ratio. The Communication-Avoiding (CA) approach, developed in the 2000s and 2010s, provides lower bounds on communication for many problems and designs algorithms that achieve those bounds.
The distributed memory approach also grapples with load balancing: ensuring that all processors have roughly equal amounts of work. Static load balancing assigns work before execution, based on estimates of task sizes. Dynamic load balancing redistributes work during execution, often using work-stealing queues where idle processors take tasks from busy ones. Work-stealing is particularly effective for irregular problems like tree search or adaptive mesh refinement, where task sizes are unpredictable.
A third major approach organizes parallelism around operations on entire data structures rather than around individual tasks. In the data-parallel style, a single instruction stream applies the same operation to many data elements simultaneously. This style is natural for array-based computations, image processing, and linear algebra, and it maps directly onto Single Instruction, Multiple Data (SIMD) hardware, including graphics processing units (GPUs). The programming model is simple—the programmer writes what looks like sequential code over arrays, and the system parallelizes the element-wise operations—but it requires that the problem be expressible as uniform operations over regular data structures.
The Bulk Synchronous Parallel (BSP) model, proposed by Leslie Valiant in 1990, generalizes the data-parallel style to a broader setting. A BSP computation proceeds in supersteps: each processor performs local computation, then exchanges messages with other processors, then waits at a global synchronization barrier before the next superstep. The BSP model makes the cost of synchronization explicit and provides a clean cost formula: the time for a superstep is the sum of the maximum local computation time, the maximum communication time, and the synchronization overhead. This model has been influential both as a theoretical framework and as the basis for practical programming systems like the Pregel system for graph processing, which uses a "think like a vertex" model where each vertex of a graph is a computational unit that communicates with its neighbors in supersteps.
For irregular and dynamic problems, a different approach has proven effective: task-based parallelism. The problem is decomposed into a collection of tasks with dependencies between them, forming a directed acyclic graph (DAG). A runtime system schedules these tasks onto available processors, respecting dependencies. The key challenge is scheduling: deciding which task each processor should execute next to minimize idle time and communication.
Work-stealing is the dominant scheduling strategy. Each processor maintains a queue of ready tasks. When a processor runs out of work, it "steals" a task from another processor's queue. This simple policy has strong theoretical guarantees: for many task graphs, work-stealing achieves near-optimal load balance with bounded communication overhead. The approach underlies modern parallel programming systems like Cilk, Intel's Threading Building Blocks, and the OpenMP task construct. It is particularly well suited to recursive algorithms, where the task DAG is naturally tree-shaped, and to applications with unpredictable task durations, such as branch-and-bound search or sparse matrix factorization.
These approaches are not mutually exclusive; they emphasize different aspects of the same underlying challenge. The PRAM tradition focuses on the logical structure of parallel computation, abstracting away machine details to discover algorithmic ideas. The distributed memory approach focuses on the physical realities of communication and data placement. The data-parallel and BSP styles occupy a middle ground, providing structured ways to organize computation and communication. The task-based approach addresses the scheduling problem that the others often assume away.
In practice, modern parallel algorithms often combine elements from multiple approaches. A large-scale computation might use a data-parallel formulation for the inner loops, a distributed memory decomposition for the outer structure, and work-stealing to handle load imbalance. The theoretical insights from the PRAM tradition—such as pointer jumping or parallel prefix—often appear as building blocks within these larger frameworks, even though the final implementation bears little resemblance to the idealized PRAM.
The contemporary study of parallel algorithms is shaped by the hardware landscape. Multicore processors are universal, GPUs provide massive data-level parallelism, and large-scale clusters and supercomputers connect thousands of nodes. This diversity means that no single model dominates. Algorithm designers must consider the target architecture: a GPU algorithm that exploits thousands of lightweight threads differs fundamentally from a cluster algorithm that coordinates a few hundred heavyweight processes.
Several enduring concerns organize current research. Scalability—the ability of an algorithm to use increasing numbers of processors effectively—remains central. Energy efficiency has become a new constraint: communication consumes far more energy than computation, reinforcing the communication-avoiding design philosophy. Heterogeneous computing, where different processors have different capabilities, complicates load balancing and scheduling. Fault tolerance is increasingly important at extreme scales, where the probability of a processor failure during a long computation is non-negligible.
The theoretical study of parallel algorithms continues alongside these practical concerns. The P vs. NC question remains open, and the search for work-efficient, polylogarithmic-time algorithms for important problems continues. The relationship between parallel time and work is now understood through more refined measures, such as the parallel slack—the ratio of available parallelism to the number of processors—which determines how well an algorithm can utilize a fixed machine.
The field has also expanded beyond traditional numerical and combinatorial problems. Parallel algorithms for machine learning, graph analytics, and scientific simulation are active research areas. These applications often involve irregular data structures, streaming inputs, or iterative refinement, requiring new algorithmic techniques that go beyond the classical repertoire.
The enduring contribution of the subfield is a set of conceptual tools: ways to decompose problems, to reason about the trade-offs between time, work, and communication, and to identify which problems are amenable to parallelism and which are not. These tools remain valuable even as specific hardware models evolve, because they address the fundamental constraints that any parallel computation must respect.