Loading field map
Parallel computing is the study and practice of using multiple processing elements simultaneously to solve a computational problem. Its central premise is that many problems can be broken into smaller pieces, which can then be solved concurrently, potentially reducing the total time to completion. The field spans the design of hardware, the algorithms that run on it, and the software systems that coordinate them, all in service of the single goal of increasing computational throughput beyond what a single processor can achieve.
For decades, the performance of a single processor improved steadily, driven by increases in clock frequency and architectural efficiency. Software written for a single processor automatically ran faster with each new generation. This era, however, encountered fundamental physical limits. Heat dissipation, power consumption, and the speed of light within a chip impose hard constraints on how fast a single core can operate. Around the turn of the 21st century, the industry shifted from making single cores faster to placing multiple cores on a single chip. This shift transformed parallel computing from a specialized niche used in scientific supercomputing into a general concern for all computing: a modern laptop, smartphone, or cloud server is a parallel machine.
The core challenge of the field is not simply "having many processors," but organizing computation so that those processors are usefully occupied. If processors spend their time waiting for data, communicating, or contending for shared resources, the theoretical speedup of adding more processors is quickly eroded. Parallel computing is therefore the discipline of managing this complexity: designing algorithms with sufficient independent work, structuring data so it can be accessed without bottlenecks, and building programming models that let humans express concurrency without introducing subtle errors.
Parallel systems are most fundamentally classified by the interaction of memory and processing elements. This classification, while often the first thing a newcomer learns, remains the most useful high-level map of the hardware landscape.
Shared memory systems have multiple processors that access a single, global address space. A processor can read and write a variable that another processor created, simply by referring to its address. The difficulty lies in coordinating these accesses; if two processors write to the same location, the result is unpredictable unless explicit synchronization is used, typically through locks or atomic operations. Because the memory is shared, the hardware must manage coherency—ensuring that all processors see a consistent view of memory, even though each has its own local cache. The cost of maintaining this consistency grows with the number of processors, placing practical limits on the scale of shared-memory machines. Multicore laptops and many servers are shared-memory systems.
Distributed memory systems, in contrast, have processors that are paired with their own private memory, connected by a network. No processor can directly read another processor's memory. To exchange data, processors must explicitly send and receive messages over the network. This model scales to enormous sizes—the largest supercomputers in the world are distributed-memory systems—but places the burden of data movement on the programmer, who must decide what data to send, to whom, and when. The latency of the network, even the fastest available, is many times slower than memory access, so an efficient distributed-memory program is one that minimizes communication frequency while maximizing message size.
A third category, hybrid systems, combines both models. A modern supercomputer is typically a distributed-memory machine in which each node is itself a shared-memory multicore processor, and some nodes also include accelerators like graphics processing units (GPUs) with their own private memory. Writing code for these systems requires nesting multiple parallel paradigms—for example, shared-memory threading within a node and message passing between nodes.
Within each of these categories, a further distinction concerns the granularity of parallelism. Data parallelism applies the same operation to many distinct pieces of data simultaneously. This is the natural model for GPUs, which consist of thousands of small cores designed to execute identical instructions on arrays of data. Data-parallel problems—image processing, matrix multiplication, training neural networks—have abundant, regular parallelism that maps well to such hardware. Task parallelism, by contrast, distributes different, often irregular, functions across processors. A web server handling many simultaneous requests demonstrates task parallelism, as do simulations where different processors compute different physical regions. Many real applications use both: a program might break its overall work into tasks, each of which is internally data-parallel.
A recurring theme across all parallel systems is the tension between useful calculation and the overhead of coordination. The theoretical best-case speedup is given by Amdahl's Law, which states that the speedup from parallelization is limited by the fraction of the program that must run sequentially. If 10% of a program is sequential, no number of processors can achieve a speedup greater than ten. The law is a simple mathematical statement—$speedup = 1$ / (sequential fraction + parallel fraction / N)—but its implication is profound: adding processors yields diminishing returns unless the sequential fraction shrinks. Amdahl's Law describes a fixed problem size, but in practice, larger problems often present a much greater share of parallel work; Gustafson's Law formulates this observation, noting that as problems are scaled up, the achievable speedup typically grows with the number of processors, because the parallel workload grows while the sequential part often stays constant.
Beyond the sequential fraction, the most significant barrier to speedup is data movement. In modern machines, moving data from memory to a processor is enormously more expensive, in time and energy, than performing a floating-point operation on that data. The entire practice of parallel algorithm design can be seen as the art of maximizing the ratio of computation to data movement. On shared-memory systems, this means designing algorithms that are "cache-friendly"—reusing data that is already in a processor's local cache rather than repeatedly fetching it from main memory. On distributed-memory systems, it means partitioning data so that each processor works for a long time on its local piece before needing to communicate.
An important negative result, the Ping-Pong problem, illustrates this trade-off in miniature: if two processors must alternately exchange a tiny piece of data to proceed, the cost of the communication latency dominates entirely, and the program runs at the speed of the network, not the processors. Efficient parallel programs are therefore those that communicate in large batches and as infrequently as possible, a principle known as "bulk synchronous" or "data-parallel" organization.
Because the hardware is complex, parallel computing relies on programming models that abstract some of that complexity. These models are not merely libraries; they embody different assumptions about how the programmer thinks about concurrency.
The dominant model for distributed memory is the Message Passing Interface (MPI) . MPI is not a single programming language but a standard library specification, implemented in C, C++, and Fortran. A program written with MPI is a collection of independent processes, each with its own memory, that perform computations and exchange data via explicit function calls. The programmer must decide how to decompose the problem and insert communication calls at the right points. MPI is explicit, expressive, and unwieldy; it is both the highest-performance and the most labor-intensive way to write parallel code. Its durability stems from its universality: because it makes no assumptions about a shared address space, it runs on essentially any parallel machine.
For shared memory, the most common model is threading, typically expressed with an API called OpenMP. In the OpenMP model, a single program is executed by multiple threads that share an address space. The programmer annotates regions of code (typically loops) as parallel, and the runtime system divides the iterations among the threads. The programmer can also use synchronization constructs like critical sections or atomic operations to protect shared variables. OpenMP is far easier to use than MPI because the hardware handles data sharing, but it requires the programmer to reason carefully about race conditions—situations where the outcome depends on the unpredictable timing of concurrently running threads.
A more recent and increasingly important model is CUDA (and its more portable counterpart, OpenCL), a programming model for GPUs. GPU programming follows a data-parallel "single instruction, multiple thread" model: the programmer writes a small function, called a kernel, that will be executed by thousands of threads simultaneously, each handling one element of a large array. The programmer must explicitly manage the transfer of data between the CPU's memory and the GPU's separate memory. The programming model is strict—threads are arranged in blocks, and only threads within a block can communicate efficiently—but it maps directly onto the hardware's design, enabling enormous throughput for regular, data-intensive problems.
Beyond these established models, a variety of higher-level abstractions exist, including parallel functional languages (which exploit the fact that pure functions have no side effects, making them automatically safe to run concurrently) and dataflow models (where a program is a graph of operations that execute as soon as their inputs are available). These newer models aim to free the programmer from the manual orchestration required by MPI or OpenMP, but they must still contend with the same underlying hardware trade-offs.
Given a problem and a machine, the programmer must decide how to divide the work. This is the problem of partitioning. For a data-parallel operation, partitioning is trivial: give each processor a contiguous block of the data. For irregular problems—parsing a document, searching a graph, simulating interacting bodies—partitioning is itself a hard algorithmic problem. The goal is load balance: each processor should receive roughly the same amount of work, or else the total runtime will be dictated by the slowest processor, a phenomenon known as the "tail effect," where the overall speedup is limited by a straggler.
In some cases, the workload is dynamic; a processor may spawn new work as it proceeds. The scheduling problem is then to assign tasks to processors at runtime to maintain balance. A common technique is work stealing, where idle processors "steal" work from busy processors' queues. This is the mechanism behind many shared-memory task-based systems, and it is also used in large-scale distributed frameworks.
A closely related issue is decomposition strategy. Some problems, like finite-element simulations of a physical domain, decompose cleanly into spatial regions. Others, like Monte Carlo simulations where each trial is independent, are "embarrassingly parallel" and require almost no communication. Still others, like the fast Fourier transform or sorting, have complicated global data dependencies that require careful algorithmic restructuring to parallelize efficiently. The design of parallel algorithms often means finding a different ordering of operations than the natural sequential version—a parallel sort, for example, may use a more communication-tolerant approach than a textbook quicksort.
The promise of parallel computing is speedup, but measuring whether that speedup is real, and understanding why it is imperfect, is a core activity. The primary metric is parallel efficiency, defined as speedup divided by the number of processors; a perfectly efficient program runs N times faster with N processors. Without profiling—measurement of where time is spent—a parallel program might run slower than its sequential version, defeated by communication overhead or imbalanced load.
A common obstacle is serialization, where a lock or a shared resource forces threads to wait for each other. Often the wait is for a single "hot" data structure, such as a counter that every thread increments. A more subtle bottleneck is contention for memory bandwidth: even with no explicit locks, all processors trying to read different parts of the same array may saturate the memory bus, so adding processors provides no benefit. The hardware's memory hierarchy—with its levels of cache and main memory—means that the physical layout of data in memory, and the pattern of access, can matter as much as the logical algorithm.
A crucial reality is that performance is not portable. A program that runs efficiently on one machine may be terrible on another, due to differences in the number of cores, the cache sizes, the network topology, or the speed of synchronization primitives. The performance of a parallel program is a property of the combination of code, input, and machine, not of the code alone.
The modern practice of parallel computing is marked by heterogeneity. A single task—say, training a large machine-learning model—may run on distributed CPU clusters, GPUs, or specialized tensor-processor chips. The most demanding applications, such as climate modeling, astrophysics, or drug discovery, run on the world's largest supercomputers, which are ranked by the performance of a benchmark called LINPACK. Yet a web service handling millions of requests per day is likewise a parallel system, even if its workload is latency-sensitive rather than throughput-oriented.
The field currently faces several deep problems. One is the programmability gap: the hardware continues to evolve rapidly, but the abstractions for programming it lag behind. The most successful programming models, such as MPI and OpenMP, are decades old, and they predate today's GPU-accelerated, memory-bandwidth-limited machines. The search for a more productive model—one that can express both data and task parallelism, hide the memory hierarchy, and guarantee correctness—remains open.
Another frontier is fault tolerance at scale. As systems grow to millions of cores, the probability that at least one component fails during a run becomes significant. Traditional distributed-memory programs, checkpointed periodically to disk, halt entirely upon a single failure; restarting a two-day simulation from a checkpoint wastes hours. Newer techniques, such as algorithmic-based fault tolerance and task replay, attempt to make programs resilient to partial failure, but they are not yet standard practice.
Finally, energy efficiency has emerged as a constraint that shapes design choices. A supercomputer consumes megawatts; a mobile phone chip cannot dissipate more than a few watts. Many modern parallel designs allocate power not to increase peak speed but to improve performance per watt, which is often achieved by running more moderately clocked cores rather than fewer fast ones. The energy cost of moving data has become a dominant consideration, reinforcing the field's central precept: parallel computing is not about having more processors, but about organizing computation so that data stays near the computation, communication is minimized, and every hardware resource is kept as usefully busy as possible.