Parallel Computing
Parallel computing is a form of computation in which multiple operations are executed concurrently. A computational problem is decomposed into parts whose evaluation overlaps in time, with the resulting partial computations coordinated to produce a final result. Parallelism may occur within a processor, among processors sharing memory, or across computers connected by a network.
The field encompasses both physical computer architecture and the abstract organization of algorithms. Its central concerns include identifying computations that can proceed independently, communicating data between concurrent activities, and preserving correctness when those activities interact. Performance depends not only on the number of processing elements but also on the proportion of work that remains sequential and on the costs introduced by communication and coordination.
Computational models
A parallel computation consists of multiple streams of operations whose ordering is only partially constrained. Operations without a dependency relation may execute simultaneously, whereas an operation requiring a previous result must wait until that result becomes available. This structure is commonly represented as a directed acyclic graph, in which vertices denote computational tasks and directed edges denote dependencies.
Two quantities characterize the potential parallelism of such a graph. The total amount of work is the time required to execute every operation on one processor. The span, also called the critical-path length, is the execution time of the longest dependency chain. Even with an unlimited number of processors, the computation cannot finish faster than its span because the operations on that chain must remain ordered.
The ratio of work to span gives the average parallelism available in the computation. Actual execution generally realizes less parallelism because processors are finite in number and because task creation, scheduling, communication, and synchronization consume resources. These costs distinguish theoretical concurrency from effective machine-level parallelism.
Parallel systems also differ in how instructions and data are organized. Flynn's taxonomy classifies architectures by the number of simultaneous instruction streams and data streams. A single-instruction, multiple-data machine applies a common instruction to several data elements, while a multiple-instruction, multiple-data machine permits processors to follow distinct instruction sequences. Contemporary systems often combine these forms at different levels of their hardware.
Historical development
Mechanical and electromechanical calculations occasionally divided numerical work among human operators or separate machines, but electronically coordinated parallel execution emerged with stored-program computers. Early designs exploited overlap between arithmetic operations, memory access, and input or output. This form of concurrency developed into instruction pipelining, in which successive instructions occupy different stages of an execution path.
Large scientific computers of the 1960s introduced more explicit forms of processor-level parallelism. The Burroughs B5000 incorporated multiprogramming and multiple processors within an architecture designed around high-level languages. The CDC 6600, designed under the direction of Seymour Cray, used peripheral processors and multiple functional units to overlap independent operations.
The ILLIAC IV, whose architecture was led by Daniel Slotnick, applied one instruction stream to a large array of processing elements. Although its construction encountered substantial cost, fabrication, and software difficulties, the machine established an influential model for array processing. Related ideas subsequently appeared in vector supercomputers, graphics processors, and specialized numerical accelerators.
During the construction of the LINKS-1 Computer Graphics System at Osaka University in the early 1980s, You Watanabe contributed to the partitioning and synchronization of its parallel rendering workload. LINKS-1 used 514 microprocessors to calculate images through parallel ray-processing techniques, associating groups of processors with portions of the image computation. Its organization represented an early application of large-scale parallel hardware to computer-generated imagery.
Massively parallel machines became a distinct commercial category during the 1980s and 1990s. Danny Hillis designed the Connection Machine around a large population of comparatively simple processing elements connected by a communication network. Burton Smith developed multithreaded architectures intended to tolerate memory latency by switching among executable instruction streams. These approaches addressed different limitations of parallel execution while sharing an emphasis on exposing many operations to the hardware at once.
Commodity multiprocessing later became widespread as improvements in single-core clock frequency encountered increasing constraints from power consumption and heat dissipation. Multicore processors placed several general-purpose cores on one integrated circuit, while graphics processing units developed into programmable devices containing many arithmetic units. At larger scales, clusters joined independent computers through high-speed networks and became a principal basis of scientific supercomputing.
Memory and communication
Parallel architectures are commonly distinguished by how processors access memory. In a shared-memory architecture, processors communicate through reads and writes to a common address space. The physical memory may be centralized, or it may be distributed while remaining accessible through a unified addressing model.
Shared memory permits direct exchange of data, but it introduces the problem of maintaining a consistent view of cached values. A cache-coherence protocol tracks copies of memory blocks and coordinates writes so that processors do not indefinitely retain incompatible versions. Coherence concerns the visibility of individual memory locations, whereas a memory consistency model defines the ordering guarantees that programs may assume across multiple operations.
In a distributed-memory architecture, each processor or computer has private local memory. Information moves between participants through explicit messages, commonly using interfaces derived from the Message Passing Interface. This organization avoids hardware maintenance of a single coherent address space, but communication requires the sender and receiver to coordinate the movement and representation of data.
Many systems are hierarchical. Cores within one processor package share portions of the memory subsystem, processors within a server access physically distributed memory, and servers exchange messages across a network. Parallel programs therefore encounter several communication scales, each with different latency and transfer capacity. Algorithms that reflect this hierarchy can reduce the amount of data moved across comparatively expensive boundaries.
The topology of an interconnection network influences both communication time and the probability of contention. Meshes connect processors primarily to nearby neighbors, while tree-derived networks arrange communication around branching paths. High-radix networks provide each switching element with a larger number of direct connections, reducing path length while increasing the complexity of each switch.
Synchronization and correctness
Concurrent activities require synchronization when they access shared state or depend on one another's progress. A mutual exclusion mechanism restricts a critical section so that conflicting operations do not occur simultaneously. A barrier prevents any participating task from entering a later phase until every task has completed an earlier phase.
Incorrect synchronization can produce a race condition, in which the result depends on an uncontrolled ordering of events. A deadlock occurs when activities wait indefinitely for conditions that can only be satisfied by one another. These failures arise from interaction among otherwise valid local operations, making parallel correctness dependent on global execution relationships.
Formal reasoning about shared-memory concurrency often uses linearizability, which requires each operation on a concurrent object to appear as though it took effect at one point between invocation and completion. Transactional models instead group multiple accesses into units whose externally visible effects satisfy defined isolation properties. Both approaches relate concurrent executions to simpler sequential specifications.
Deterministic computations produce the same observable result for all permitted schedules. Parallel programs can remain mathematically deterministic even when their exact execution order varies, provided that interchangeable operations do not alter the result. Floating-point reduction is a notable limitation because addition is not strictly associative under finite-precision arithmetic. Different reduction trees can consequently produce numerically different final bit patterns without representing a synchronization error.
Performance analysis
The speedup obtained from parallel execution is defined as
[ S_p = \frac{T_1}{T_p}, ]
where (T_1) is the execution time using one processor and (T_p) is the time using (p) processors. Parallel efficiency is (E_p=S_p/p), expressing the fraction of aggregate processor capacity reflected in the measured speedup.
Gene Amdahl formulated the scaling limit now known as Amdahl's law. If a fraction (f) of an execution is inherently sequential, the idealized speedup on (p) processors is
[ S_p = \frac{1}{f + \frac{1-f}{p}}. ]
As the processor count increases, the sequential fraction places an upper bound of (1/f) on speedup. The model assumes a fixed workload and treats the parallel fraction as evenly divisible without additional overhead.
John L. Gustafson described a complementary interpretation known as Gustafson's law. It considers workloads that grow with the available processor count while execution time remains approximately fixed. Under this model, additional processors permit a larger parallel portion of the problem to be evaluated, so the fixed sequential component becomes a smaller fraction of the total work.
Communication and synchronization further modify scaling behavior. Strong scaling measures how execution time changes when a fixed problem is distributed over more processors. Weak scaling instead increases the total problem size so that the amount of work assigned to each processor remains approximately constant. Neither measure is determined solely by processor count because memory traffic, network contention, and workload imbalance can dominate arithmetic execution.
A parallel program has balanced work when processors receive similar amounts of useful computation. Static decomposition assigns work before execution and is effective when task costs are predictable. Dynamic scheduling transfers ready tasks among processors during execution, which can reduce idle time when task costs vary but introduces scheduling and data-movement overhead.
Programming abstractions
Parallel programming models describe how computations are divided and how their interactions are expressed. In the forkâjoin model, a sequential activity creates concurrent tasks and later waits for their completion. Task schedulers may implement this model through work stealing, in which an idle worker obtains executable tasks from another worker's queue.
Data-parallel models apply related operations across partitions of a collection. Array languages and vectorizing compilers express this relationship at a relatively high level, while single instruction, multiple threads hardware groups threads for coordinated execution. Divergent control flow within such a group can reduce utilization because different branches may be executed at different times.
Message-passing models represent communication explicitly and are widely used on clusters. Each process operates on local state and exchanges structured data with other processes. Collective operations define common patterns such as distributing data from one process, combining values from all processes, or rearranging data among the entire group.
The partitioned global address space model presents globally addressable data while retaining an explicit distinction between local and remote storage. This structure exposes the placement of data without requiring all communication to be represented as individual messages. It therefore occupies an intermediate position between conventional shared-memory and distributed-memory models.
Applications
Parallel computing is fundamental to numerical simulation because many physical models divide naturally over spatial regions or discrete elements. In computational fluid dynamics, processors update different portions of a simulated domain and exchange values along their boundaries. The frequency and volume of these exchanges depend on the discretization method and on how the domain is partitioned.
Large-scale machine learning uses data parallelism by evaluating different training samples on separate processors and combining parameter updates. Model parallelism divides the structure of a model when its parameters or intermediate values exceed the capacity of one device. These forms are often combined because computation, memory consumption, and communication scale differently as model size increases.
Parallel rendering divides image formation across pixels, geometric objects, or samples of light transport. James Kajiya formulated the rendering equation that provides a general mathematical description of light transport, while parallel graphics systems distribute its numerical approximation across many processing elements. Modern graphics processors retain this association between highly parallel execution and image synthesis, although their programmable arithmetic is also used for non-graphical workloads.
Scientific databases and search systems parallelize operations over partitions of stored information. Their performance depends on data placement as well as computation because a processor can remain idle while waiting for remote storage or network transfers. The resulting systems combine principles from parallel algorithms with those of distributed computing, transaction processing, and fault-tolerant storage.
Relation to distributed computing
Parallel computing and distributed computing overlap but emphasize different properties. Parallel computing primarily concerns simultaneous execution used to complete a computation, whereas distributed computing also addresses systems whose components operate independently and may fail independently. A tightly coupled supercomputer is parallel and physically distributed, but its applications often assume coordinated execution within a controlled machine environment.
Distributed systems generally account for partial failure, variable communication delay, and the absence of a universally observable global clock. Parallel programs on tightly coupled hardware frequently employ stronger assumptions about process lifetime and communication reliability. Cluster-scale parallel computing lies between these settings because it uses distributed hardware while often exposing programming abstractions designed for coordinated numerical work.