Parallel computing

Parallel computing divides a problem into smaller tasks that can be executed concurrently on multiple processors or cores. The primary goal is to reduce total execution time or to handle larger problems that would otherwise be infeasible. The theoretical foundation includes Amdahl's law, which states that the speedup of a parallel program is limited by the fraction of the program that must be executed sequentially.¹ Conversely, Gustafson's law argues that as problem size grows, the parallelizable portion can dominate, allowing near-linear speedup.² These laws guide the design of parallel algorithms and systems. The Flynn's taxonomy classifies parallel architectures into four categories based on instruction and data streams: SISD, SIMD, MISD, and MIMD.³ MIMD (Multiple Instruction, Multiple Data) is the most common in modern supercomputers and multicore processors.

Parallel computing emerged in the 1960s with projects such as the ILLIAC IV, which attempted to use a single-instruction multiple-data (SIMD) array of 64 processors.⁴ Although technically challenging, it demonstrated the feasibility of large-scale parallelism. The 1980s saw the rise of shared-memory multiprocessors like the Sequent Balance and the development of programming models such as Pthreads and OpenMP. In the 1990s, distributed-memory clusters using message-passing libraries like MPI became dominant, enabled by high-speed networking. The 2000s brought multicore processors, making parallel computing ubiquitous in consumer hardware. More recently, graphics processing units (GPUs) evolved into massively parallel accelerators, and heterogeneous computing—combining CPUs and GPUs—became standard for high-performance computing.⁵ The TOP500 list, which ranks supercomputers by performance, shows that all current systems exploit parallelism.

Parallel programming models abstract the underlying hardware and provide mechanisms for expressing concurrency. Shared-memory models (e.g., OpenMP, Pthreads) allow threads to access a common address space, while distributed-memory models (e.g., MPI) require explicit message passing between processes. A hybrid approach combining both is common in large clusters. Challenges include load balancing, synchronization overhead, data races, and deadlocks. Amdahl's law highlights the difficulty of scaling when a significant non-parallelizable fraction exists. Debugging and verification are also harder because of nondeterminism. To address these, researchers have developed formal methods, static analysis tools, and runtime systems that automatically manage parallelism. Domain-specific languages and frameworks, such as CUDA for GPU computing, offer high-level abstractions that simplify development for specific hardware.⁶

Beyond the mainstream narrative, parallel computing has several niche dimensions. The concept of instruction-level parallelism (ILP) exploits fine-grained parallelism within a single processor, using techniques such as pipelining and superscalar execution. Unlike explicit thread-level parallelism, ILP is often invisible to the programmer. Another overlooked area is bit-level parallelism, where multiple bits are processed in parallel—this is a key reason why 64-bit processors outperform 8-bit ones. Dataflow computing, an alternative to the von Neumann model, executes instructions as soon as their operands are available, offering a natural form of parallelism; it was explored in the 1980s but never became mainstream.⁷ Additionally, parallel computing in biology is used to simulate neural networks and protein folding, but also to model swarm intelligence and ant colony optimization—algorithms inspired by natural parallel systems. These examples show that parallel computing is not only a hardware or software technique but also a conceptual lens for understanding complex systems.

Amdahl's law

A formula that gives the theoretical speedup of a task when using parallel resources, showing the limit imposed by the sequential portion.

Flynn's taxonomy

A classification of computer architectures into SISD, SIMD, MISD, and MIMD based on instruction and data streams.

GPU computing

The use of a graphics processing unit to perform general-purpose computation, leveraging its many cores for parallel workloads.

OpenMP

An API for shared-memory parallel programming in C, C++, and Fortran, using compiler directives.

MPI

Message Passing Interface, a standard for communication between processes in distributed-memory parallel applications.