Loading field map
The systematic study of parallel algorithms emerged as a distinct subfield in theoretical computer science during the 1970s and 1980s, driven by the advent of early multiprocessor systems. Its foundational goal was to develop a rigorous theory of computational speedup—understanding how problems could be solved faster by using multiple processors concurrently. This required abstract models to reason about costs and feasibility independent of specific hardware. The Parallel Random Access Machine (PRAM) model became the dominant early paradigm, providing a simplified shared-memory abstraction that enabled clean complexity analysis and a vast taxonomy of algorithms based on memory contention classes (EREW, CREW, CRCW). Alongside PRAM, the Boolean Circuit Model offered a more fine-grained, hardware-oriented perspective, directly connecting parallelism to circuit depth and establishing fundamental lower bounds.
While powerful for theory, the PRAM model's idealized assumptions faced criticism regarding its realism, prompting the development of alternative computational models that better reflected architectural constraints. The Bulk Synchronous Parallel (BSP) model, introduced in the late 1980s, became a highly influential paradigm by explicitly modeling computation as a sequence of supersteps alternating between parallel local computation and global synchronization/communication. This provided a more portable cost model than PRAM. Concurrently, the LogP Model and related frameworks like Queuing Shared Memory (QSM) emerged as refined, parameterized models focusing on communication latency, overhead, and gap, offering a more nuanced view of distributed-memory machines.
The rise of large-scale data processing and commodity clusters in the 2000s shifted focus toward practical programming paradigms and scalability. The MapReduce framework, while technically a programming model, ascended to a paradigm-level agenda by establishing a durable template for fault-tolerant, data-intensive parallel computation on unreliable hardware, emphasizing data locality and simple functional primitives. This era also saw the consolidation of Data-Parallel Programming as a core paradigm, encompassing both high-level language abstractions and runtime systems designed for structured parallelism over large collections.
Modern parallel algorithmics integrates insights from across these historical layers while confronting new hardware realities. The GPU Computing paradigm, centered on massive thread-level parallelism and hierarchical memory models, has established itself as a primary architectural target, demanding new algorithmic strategies distinct from classical CPU-centric designs. Furthermore, the growth of extremely large and decentralized systems has renewed interest in paradigms emphasizing communication efficiency and asynchrony, such as Communication-Avoiding Algorithms and models for Asynchronous Distributed Computation, which seek to minimize synchronization barriers. The field continues to evolve by refining its abstract models to capture the constraints of emerging architectures while preserving its core mission of developing provably efficient methods for concurrent computation.