Parallel algorithm

A parallel algorithm divides a problem into parts that can be executed concurrently and specifies how those parts exchange information. Unlike merely running several programs at once, it exposes computational dependencies and assigns work to processors, threads, vector lanes, or separate machines. Typical stages are partitioning input, computing local results, communicating boundary or summary data, synchronizing, and reducing the results into an output. Algorithms for sorting, matrix multiplication, graph traversal, simulation, and image processing are common examples.

Parallelism can be data parallel, in which the same operation is applied to many data elements, or task parallel, in which different operations proceed concurrently. A design may also be deterministic or nondeterministic: floating-point reductions, for example, can produce slightly different rounding results when additions occur in different orders.

Parallel performance is governed by useful work, critical-path length, communication, and synchronization. The speedup of a parallel version is its serial running time divided by its parallel running time, while efficiency divides speedup by the number of processors. Amdahl's law shows that a fixed serial portion places an upper bound on speedup, even when unlimited processors are available. Gustafson's law describes a different regime in which the problem grows with the machine, making scalable speedups possible.

Parallel algorithm analysis therefore often reports work and span: work is the total operations, and span is the longest dependency chain. Good algorithms keep both low, balance the workload, minimize data movement, and preserve locality in the memory hierarchy. More processors can otherwise make an algorithm slower through contention, idle time, cache misses, or network traffic.

Programming models determine how a parallel algorithm expresses ownership, communication, and synchronization. Shared-memory programs commonly use threads and directives such as OpenMP, whereas distributed-memory programs exchange messages through the Message Passing Interface (MPI).¹² Accelerators favor kernels that expose thousands of lightweight data-parallel operations, as in CUDA programming for GPUs.³

The same algorithm can require different implementations on a multicore workstation, a GPU, and a cluster. Shared memory makes data access convenient but introduces races and cache-coherence costs; distributed memory scales to many nodes but makes communication explicit. Hybrid programs combine MPI between nodes with threads or accelerator kernels within each node. Correctness depends on avoiding data races, deadlock, livelock, and unsafe assumptions about execution order.

Parallel algorithms often trade mathematical simplicity for favorable movement of data, making memory traffic a first-class design concern. A graph algorithm may be theoretically parallel yet perform poorly because irregular adjacency lists cause scattered accesses and severe load imbalance. Conversely, parallel prefix sums, reductions, and stencil computations are valuable building blocks because they recur in compilers, scientific models, databases, and graphics.

Some algorithms tolerate faults or changing resources by using redundant work, checkpointing, or work stealing. Others deliberately use approximate or randomized computation when exact coordination is too expensive. Reproducible numerical results can require deterministic reduction trees, compensated arithmetic, or specialized reproducibility modes. Large-scale benchmarks such as the TOP500 evaluate complete systems rather than algorithms alone, so their rankings also reflect interconnects, memory systems, software libraries, and energy efficiency.⁴

Theoretical models clarify what parallelism an algorithm can exploit independently of a particular machine. The PRAM model treats processors as synchronized units with shared memory and has variants that charge differently for concurrent reads and writes. Real systems depart from this abstraction because caches, memory bandwidth, message latency, and synchronization are not uniform. Research in parallel algorithms consequently connects asymptotic work and span with architecture-aware concerns such as locality and communication complexity.

Parallel algorithms have shaped both supercomputing and ordinary software engineering. Matrix operations underpin climate models and machine learning; parallel search supports databases and artificial intelligence; and image pipelines exploit regular grids. The central challenge remains selective exposure of concurrency: too little leaves hardware idle, while too much creates coordination overhead and makes correctness harder to establish.

Data parallelism

Applying the same operation independently to many data elements.

Task parallelism

Executing different tasks or functions concurrently.

Speedup

The serial execution time divided by the parallel execution time.

Span

The length of the longest dependency chain in a parallel computation.

Race condition

A correctness error caused by results depending on uncontrolled timing between concurrent operations.

PRAM

Parallel Random Access Machine, an idealized theoretical model of synchronized processors sharing memory.