- Atlas
- Computer Science
- Parallel Computing
Parallel Computing
Parallel computing is the practice of making many processors, or many parts of one processor, work on a problem at the same time.
12 frameworks, from 1970 to today · Computer Architecture · Computer Science
- Dataflow architecture 1970-1995
- SIMD architectures 1970-Present
- Vector processor 1976-1995
- Systolic array 1978-1990
- Instruction-level parallelism 1985-2005
- Symmetric multiprocessing 1985-Present
- Directory-based cache coherence 1990-2010
- Message passing 1990-Present
- Cluster computing 1994-Present
- Simultaneous multithreading 1995-Present
- Multi-core processor 2001-Present
- General-purpose computing on graphics processing units 2007-Present
Overview
Parallel computing is the practice of making many processors, or many parts of one processor, work on a problem at the same time1. The reason to do it is simple: a single processor core stopped getting dramatically faster around the mid-2000s, because clock speeds could not rise further without melting the chip, so the only way to keep gaining speed was to divide work across many execution units1. What is at stake is nothing less than how software is written and how machines are built: a parallel machine forces programmers to think about which tasks can run at once, how they share data, and how they stay consistent. The history of the field is a long argument about how tightly the cooperating units should be coupled, how they should communicate, and how much of the parallelism the hardware should find on its own.
Vector machines and the first SIMD idea
The earliest practical parallel machines did not use many processors. They used one processor that operated on many data items at once. This is SIMD, for single instruction, multiple data: one instruction, such as "add," applies to a whole array of numbers in a single step12. The idea traces to the ILLIAC IV, designed at the University of Illinois in the 1960s and finally operational in the early 1970s, which had 64 processing elements each working on its own slice of data under one control unit.
The commercial triumph of the approach was the vector processor, which added instructions that operate on a whole vector (an ordered list of numbers) held in special registers. Seymour Cray's machines at Cray Research made this the standard for scientific computing: the Cray-1, delivered in 1976, could stream through arrays of floating-point numbers far faster than any scalar machine, because one vector instruction did the work of a loop. Vector processing won because scientific codes are full of loops over arrays, and the hardware could overlap the elements of the loop without the programmer writing anything special. For two decades, "supercomputer" meant a vector machine3.
Systolic arrays and the dataflow alternative
Two other 1970s–80s ideas tried to restructure computation itself. Systolic arrays, promoted by H. T. Kung and Charles Leiserson around 1978, arranged simple processing elements in a regular grid so that data pulsed through them like a heartbeat, each element passing results to its neighbor4. The appeal was that such an array could be built cheaply and run at high speed for a fixed class of problems, such as matrix operations and signal processing; the limitation was that each array was specialized to one computation.
Dataflow computing attacked a different assumption: that instructions execute in a fixed program order5. In a dataflow machine, an instruction fires as soon as its input values are available, so any operations that do not depend on each other run at once automatically5. Several research machines were built in the 1970s and 1980s, notably at MIT and in Manchester, but dataflow struggled with memory access and with managing large numbers of ready instructions, and it never displaced the conventional stored-program design. Its legacy survives in the way modern compilers and out-of-order processors reason about which operations are independent.
Finding parallelism inside one instruction stream
While the big machines pursued many processors, a quieter revolution happened inside ordinary CPUs: instruction-level parallelism, or ILP, the overlap of independent instructions from a single program16. Pipelining, splitting instruction execution into stages so a new instruction starts before the last finishes, was standard by the 1980s17. The next step was to issue several instructions per cycle1. Superscalar processors, common from the early 1990s, fetch and dispatch multiple instructions at once. To keep those pipelines fed, hardware began reordering instructions dynamically, using techniques such as scoreboarding and Tomasulo's algorithm (developed at IBM in the 1960s for the System/360 Model 91) to let an instruction run as soon as its operands were ready rather than in program order18.
The limit of this approach became clear by the early 2000s: extracting more ILP from a single instruction stream requires ever more complex, power-hungry hardware, and returns diminish. That wall is what pushed the field toward thread-level and chip-level parallelism.
Shared memory and the coherence problem
The most natural way to build a parallel computer is to give several processors one shared memory, so any processor can read and write any location9. This is shared-memory multiprocessing, and it raises a hard question: if each processor keeps a local cache (a small fast copy of memory), how do you stop one processor from reading a stale value after another has written a new one110? The answer is cache coherence, a protocol that keeps the caches consistent10. Early snooping protocols had every cache watch a shared bus for writes; that works for a handful of processors but not for dozens111.
Directory-based cache coherence, developed in the 1980s and 1990s, solved the scaling problem by keeping a directory that records which caches hold which memory blocks, so a write need only notify the caches that actually have a copy. This made large shared-memory multiprocessors practical, and it remains the basis of coherence in today's multicore chips.
Message passing and clusters
Not every machine can share memory. Message passing is the alternative: processors have private memories and communicate by explicitly sending and receiving messages. This scales far better, because there is no shared bus or directory to bottleneck1. The idea matured into clusters, collections of ordinary computers linked by a network, which by the 1990s and 2000s let researchers build supercomputers from commodity parts. The standard programming interface, MPI (Message Passing Interface), appeared in the early 1990s and is still the backbone of most large scientific simulations. The trade-off is stark: shared memory is easier to program but hard to scale; message passing scales but forces the programmer to manage every communication.
Threads on a chip: multithreading and multicore
Two responses to the ILP wall put parallelism directly on the processor. Simultaneous multithreading (SMT), introduced in the 1990s and shipped commercially in Intel's Pentium 4 with Hyper-Threading in 2002, lets one physical core hold the state of several threads and fill its execution units from whichever thread has work ready. It extracts more use from existing hardware without adding cores.
Chip multiprocessing, now called multicore, went further: put several complete processor cores on one die112. This became the mainstream answer to the power wall, and by the mid-2000s nearly every desktop and server processor was multicore. The consequence for software was profound: ordinary programs no longer got faster automatically, and programmers had to write explicitly parallel code to benefit1.
Graphics processors become general-purpose
The most recent major shift came from an unexpected direction. Graphics processing units (GPUs) were built to shade millions of pixels in parallel, and their architecture—thousands of simple lanes executing the same operation on different data—is essentially SIMD at massive scale. Researchers realized that many non-graphics problems, from physics simulation to machine learning, fit the same pattern. General-purpose GPU computing, enabled by programming models such as CUDA (released by NVIDIA in 2007) and the open standard OpenCL, turned the GPU into a mainstream parallel co-processor11314. Today GPUs do much of the world's heavy numerical work, and the same many-lane design underlies the accelerators now driving artificial intelligence.
Where the field stands
Parallel computing today is layered. At the bottom, multicore CPUs with SMT and coherent caches handle general work. Beside them, GPUs and specialized accelerators supply massive data parallelism. Across machines, clusters and message passing stitch together the largest systems. The open questions are the old ones in new form: how to make parallel programming less error-prone, how to keep memory coherent and consistent as core counts climb, and how to divide work automatically between the tightly coupled and loosely coupled parts of a machine. The history is a record of moving that boundary—between what the hardware finds on its own and what the programmer must state explicitly—and that argument is not settled.
References
- Parallel computing (introduction, Background, Flynn's taxonomy, Instruction-level parallelism, Memory and communication, Multi-core computing, General-purpose computing on graphics processing units (GPGPU)), Wikipedia
- Single instruction, multiple data, Wikipedia
- Vector processor, Wikipedia
- Systolic array (History), Wikipedia
- Dataflow architecture, Wikipedia
- Instruction-level parallelism, Wikipedia
- Instruction pipelining (History), Wikipedia
- Superscalar processor (History), Wikipedia
- Symmetric multiprocessing, Wikipedia
- Cache coherence, Wikipedia
- Directory-based cache coherence, Wikipedia
- Multi-core processor, Wikipedia
- CUDA (introduction, History), Wikipedia
- OpenCL, Wikipedia
The frameworks of Parallel Computing
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1970-1995
- 1970-Present
- 1976-1995
- 1978-1990
- 1985-2005
Instruction-level parallelism
How many independent instructions can run per cycle?
- 1985-Present
Symmetric multiprocessing
How can several processors share one memory safely?
- 1990-2010
Directory-based cache coherence
How do caches stay consistent without a shared bus?
- 1990-Present
- 1994-Present
Cluster computing
How can ordinary computers be linked into a supercomputer?
- 1995-Present
- 2001-Present
- 2007-Present
General-purpose computing on graphics processing units
How can graphics chips do general numerical work?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Vector processor grew out of SIMD architectures
Vector processors are a commercial refinement of the SIMD idea: one control unit issues an instruction that operates on many data elements, as in the ILLIAC IV, but with vector registers and pipelined functional units suited to scientific loops.
Carried by Seymour Cray; Cray-1 (1976); ILLIAC IV.
Simultaneous multithreading grew out of Instruction-level parallelism
Simultaneous multithreading arose as a response to the diminishing returns of extracting more instruction-level parallelism from a single thread: instead of finding more independent instructions in one stream, SMT fills execution units from several threads at once.
Carried by Dean Tullsen; Susan Eggers; Hyper-Threading (2002).
Multi-core processor replaced Instruction-level parallelism
The multicore processor was a direct response to the power and complexity wall that ended the ILP era: rather than spend transistors on ever more aggressive superscalar extraction from one instruction stream, designers put several complete cores on a die.
Cluster computing grew out of Message passing
Cluster computing grew directly out of message passing: clusters are collections of commodity computers with private memories that communicate by explicit messages, and MPI became the standard interface for programming them.
Instruction-level parallelism influenced by Dataflow architecture
Dataflow research on firing instructions when operands are ready fed into the design of out-of-order superscalar processors, which use dynamic scheduling and register renaming to exploit instruction-level parallelism in a single stream.
Carried by MIT dataflow machines.
General-purpose computing on graphics processing units influenced by SIMD architectures
General-purpose GPU computing deliberately revived the SIMD execution model at massive scale: GPU lanes execute the same instruction on different data, and programming models like CUDA exposed this data-parallel style to non-graphics programmers.
Carried by CUDA (2007); NVIDIA.
Message passing rival of Symmetric multiprocessing
Shared-memory multiprocessing and message passing were contemporary rival answers to how parallel processors should communicate: shared memory is easier to program but hard to scale, while message passing scales but forces explicit communication management.
Multi-core processor grew out of Symmetric multiprocessing
Chip multiprocessing applied the symmetric multiprocessor model to a single die: multiple identical cores share coherent caches and memory, carrying the SMP programming model into mainstream microprocessors.
Multi-core processor influenced by Directory-based cache coherence
Multicore chips reused directory-based coherence protocols to keep the private caches of several cores on one die consistent, scaling the shared-memory model down to the processor level.
General-purpose computing on graphics processing units influenced by Vector processor
Vector processing demonstrated that operating on whole arrays with a single instruction could yield large speedups for scientific code; GPU programming models later adopted vectorized memory access and data-parallel kernels in the same spirit.
Beyond the field
Where Parallel Computing's ideas came from in other fields, and what they led to there: the strongest 12 of 65 links.
Dataflow architecture reacted against Von Neumann architecture in Digital Systems
Dataflow architecture was defined largely as a rejection of the von Neumann model's single program counter and shared mutable store, proposing instead token-driven execution with no central control.
Carried by Jack Dennis.
Dataflow architecture reacted against Von Neumann architecture in Computer Architecture
Dataflow architecture was defined largely as a rejection of the von Neumann model's single program counter and shared mutable store, proposing instead token-driven execution with no central control.
Carried by Jack Dennis.
Dataflow architecture reacted against Von Neumann architecture in Computer Systems
Dataflow architecture was defined largely as a rejection of the von Neumann model's single program counter and shared mutable store, proposing instead token-driven execution with no central control.
Carried by Jack Dennis.
SIMD architectures led to Data Parallelism in Parallel Algorithms
Data parallelism grew directly out of SIMD architectures, generalizing the idea of applying one operation to many data elements into a programming model. The term and concept were formulated as the software counterpart of SIMD hardware execution.
SIMD architectures led to SIMD instruction set extensions in Instruction Set Architecture
SIMD instruction set extensions are the direct descendant of SIMD architectures, bringing the data-parallel execution model into general-purpose processors as instruction-level extensions. The array-processor idea was reincarnated as packed registers and vector instructions.
Vector processor influenced Vectorized and compiled execution in Query Processing
Vectorized query execution borrowed the core idea of the vector processor: operating on batches of values with a single instruction to amortize per-element overhead. MonetDB/X100 explicitly drew on vector processing principles when it introduced vectorized execution for databases.
Carried by Marcin Zukowski; Peter Boncz.
Instruction-level parallelism grew out of Instruction pipelining in Microarchitecture
Instruction-level parallelism grew directly out of instruction pipelining: once pipelines overlapped stages, designers generalised to issuing and executing multiple instructions per cycle.
Instruction-level parallelism led to Simultaneous multithreading in Microarchitecture
SMT grew directly out of instruction-level parallelism research: it extends superscalar multiple issue by drawing instructions from several threads to fill the issue slots that a single thread leaves empty. The ILP analyses of available parallelism supplied the motivation and the model.
Symmetric multiprocessing led to Multi-core processor in Computer Architecture
The multi-core processor grew directly out of symmetric multiprocessing: the same shared-memory, cache-coherent programming model was moved onto a single die once power limits ended frequency scaling. SMP's coherence protocols and operating-system support carried over into chip multiprocessors.
Directory-based cache coherence influenced Cache-Coherent Shared Memory in Computer Systems
Large-scale cache-coherent shared memory systems adopted directory-based coherence, developed in the late 1980s and 1990s, because snooping cannot scale beyond a single bus.
Cluster computing influenced In-Memory Cluster Computing in Big Data Processing
In-memory cluster computing, as in Spark, was built directly on cluster computing infrastructure and its scheduling and fault-tolerance models, adding memory-resident datasets on top.
Carried by Apache Spark.
Cluster computing led to Warehouse-Scale Computing in Computer Systems
Warehouse-scale computing grew directly out of cluster computing: the same commodity-node architecture was scaled to tens of thousands of machines managed as one system, with the added concerns of power, cooling and fault tolerance at building scale.

Parallel Computing is a planet in Nousfarer
Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.
Land on Parallel ComputingRelated fields
Fields its ideas are linked to
- Parallel Algorithms 13 links
- Microarchitecture 8 links
- Computer Systems 8 links
- Hardware Accelerators 7 links
- Big Data Processing 4 links
- Distributed Systems 4 links
- Computer Architecture 3 links
- ML Systems 3 links
- Cloud Computing 2 links
- Operating Systems 2 links
- Distributed Algorithms 1 link
- Instruction Set Architecture 1 link
More in Computer Architecture
- Computer Architecture
- Embedded Systems
- Hardware Accelerators
- Instruction Set Architecture
- Memory Hierarchy
- Microarchitecture
See where Parallel Computing sits on the Map of Human Knowledge