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

still a working view ended · each leads to its entry below

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

  1. 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
  2. Single instruction, multiple data, Wikipedia
  3. Vector processor, Wikipedia
  4. Systolic array (History), Wikipedia
  5. Dataflow architecture, Wikipedia
  6. Instruction-level parallelism, Wikipedia
  7. Instruction pipelining (History), Wikipedia
  8. Superscalar processor (History), Wikipedia
  9. Symmetric multiprocessing, Wikipedia
  10. Cache coherence, Wikipedia
  11. Directory-based cache coherence, Wikipedia
  12. Multi-core processor, Wikipedia
  13. CUDA (introduction, History), Wikipedia
  14. 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.

  1. 1970-1995

    Dataflow architecture

    When should an instruction execute?

    Fly to its tower in Nousfarer

  2. 1970-Present

    SIMD architectures

    How can one instruction act on many data?

    Fly to its tower in Nousfarer

  3. 1976-1995

    Vector processor

    How can whole arrays be processed in one step?

    Fly to its tower in Nousfarer

  4. 1978-1990

    Systolic array

    How can data pulse through a fixed grid of processors?

    Fly to its tower in Nousfarer

  5. 1985-2005

    Instruction-level parallelism

    How many independent instructions can run per cycle?

    Fly to its tower in Nousfarer

  6. 1985-Present

    Symmetric multiprocessing

    How can several processors share one memory safely?

    Fly to its tower in Nousfarer

  7. 1990-2010

    Directory-based cache coherence

    How do caches stay consistent without a shared bus?

    Fly to its tower in Nousfarer

  8. 1990-Present

    Message passing

    How do processors with private memories communicate?

    Fly to its tower in Nousfarer

  9. 1994-Present

    Cluster computing

    How can ordinary computers be linked into a supercomputer?

    Fly to its tower in Nousfarer

  10. 1995-Present

    Simultaneous multithreading

    How can one core keep several threads busy?

    Fly to its tower in Nousfarer

  11. 2001-Present

    Multi-core processor

    How can several complete cores share one chip?

    Fly to its tower in Nousfarer

  12. 2007-Present

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.

Dataflow architectureSIMD architecturesVector processorSystolic arrayInstruction-level parallelismSymmetric multiprocessingDirectory-based cache coherenceMessage passingCluster computingSimultaneous multithreadingMulti-core processorGeneral-purpose computing on graphics…

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Computing

Related fields

Fields its ideas are linked to

More in Computer Architecture

See where Parallel Computing sits on the Map of Human Knowledge