Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 67 ยท Parallel Architectures

Parallel Processing and Flynn's Taxonomy

Learn SISD, SIMD, MISD and MIMD, multicore designs, shared versus distributed memory, and the limits of speedup with Amdahl and Gustafson, with plots.

For decades, programs got faster simply because each new processor ran at a higher clock rate. Around 2005 that free ride ended: chips got too hot to clock much faster (you will see why in Power, Energy and Thermal Limits). Manufacturers kept adding transistors, but spent them on more cores instead of faster ones. Today a phone has eight cores and a server chip has over a hundred. To use them, work must run in parallel.

In this lesson you will learn the standard way to classify parallel machines (Flynn's taxonomy), the difference between shared and distributed memory, the classic hazard of sharing data, and the two laws that predict how much speedup parallel hardware can really give: Amdahl's and Gustafson's. You should know how to measure speedup from Measuring Performance.

Flynn's taxonomy

In 1966 Michael Flynn proposed a simple classification based on two questions: how many instruction streams does the machine follow at once, and how many data streams does it work on at once?

Single data Multiple data
Single instruction SISD SIMD
Multiple instruction MISD MIMD
flowchart TB
  subgraph SISD
    I1["Instruction"] --> P1["Processor"] --> D1["Data"]
  end
  subgraph SIMD
    I2["One instruction"] --> PA["Lane 1"] --> DA["Data 1"]
    I2 --> PB["Lane 2"] --> DB["Data 2"]
    I2 --> PC["Lane 3"] --> DC["Data 3"]
  end
  subgraph MIMD
    IA["Instructions A"] --> PX["Core 1"] --> DX["Data X"]
    IB["Instructions B"] --> PY["Core 2"] --> DY["Data Y"]
  end

Flynn's categories: one instruction on one datum, one instruction on many data, many instructions on many data.

  • SISD (single instruction, single data) is the classic sequential computer from the Von Neumann model. One instruction at a time works on one piece of data. A simple microcontroller is SISD. (Even a modern core hides a lot of internal parallelism, but its programming model is still sequential.)
  • SIMD (single instruction, multiple data) applies the same operation to many values at once: add 8 pairs of numbers with one instruction. Vector units in CPUs and the thousands of lanes of a GPU work this way. The next lesson, SIMD, Vector Processing and GPUs, covers them in depth.
  • MISD (multiple instruction, single data) is the rare corner: several different operations on the same data stream. It is mostly of theoretical interest. Some people point to redundant fault-tolerant systems (several units compute the same input and vote), such as flight computers, as the closest practical case.
  • MIMD (multiple instruction, multiple data) is the general parallel computer: independent processors, each running its own program on its own data. Multicore CPUs, clusters and data centers are all MIMD.

Flynn's scheme is coarse (a modern CPU is SISD per thread, SIMD inside vector instructions, and MIMD across cores), but it is a useful vocabulary. The next example classifies a few well-known machines and shows the three programming styles side by side.

Python SISD, SIMD and MIMD in miniature

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Multicore, multiprocessor and cluster

A multicore processor puts several cores on one chip, typically with private L1 (and often L2) caches and a shared last-level cache. A multiprocessor system has several such chips (sockets) in one machine. A cluster is many separate computers connected by a network. All of them are MIMD, but they differ in how the processors see memory.

Shared memory

In a shared-memory machine every core can read and write the same address space. Threads exchange data simply by reading and writing variables. This is convenient, and it is what multicore CPUs provide. Shared-memory machines come in two flavors:

  • UMA (uniform memory access): all cores take about the same time to reach any memory address. Typical for single-chip multicores.
  • NUMA (non-uniform memory access): memory is attached to individual sockets or chiplets, so a core reaches its local memory faster than memory attached to another socket. Operating systems try to keep a thread and its data on the same node.

The price of sharing is complexity. Each core has its own cache, so they must be kept consistent (see Cache Coherence and Memory Consistency), and programs must coordinate access to shared data.

Distributed memory

In a distributed-memory machine each processor has its own private memory. There is no shared variable; processors cooperate by sending messages across a network (MPI is the classic programming interface). This scales to thousands of machines because there is no global memory to keep coherent, but the programmer must decide explicitly where data lives and when it moves.

Shared memory Distributed memory
Communication Reads and writes of shared variables Explicit messages
Typical hardware Multicore CPU, multi-socket server Cluster, supercomputer
Programming Threads, locks Message passing, partitioned data
Scaling limit Memory bandwidth, coherence traffic Network bandwidth and latency

Many large systems are hybrid: shared memory inside each node, message passing between nodes.

The danger of sharing

When threads share a variable, the order in which their steps interleave matters. An increment such as counter += 1 is really three steps: load, add, store. If two cores interleave those steps, one update can overwrite the other (a race condition). We cannot rely on real threads here (the in-browser runner has none), but we can simulate the interleaving deterministically.

Python A lost update on shared memory

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The interleaved schedules print 1 instead of 2, even though each core did its job correctly. Real programs prevent this with locks or atomic instructions (the hardware provides a single indivisible read-modify-write), or avoid sharing by design, as the message-passing variant does.

The limits of speedup: Amdahl's law

Suppose a program spends a fraction p of its time in code that can be parallelized, and the remaining 1 - p must run serially. With n processors the parallel part shrinks by a factor of n, but the serial part does not:

TEXT
speedup(n) = 1 / ((1 - p) + p / n)

This is Amdahl's law. Even with infinitely many processors the speedup cannot exceed 1 / (1 - p). A program that is 95 percent parallel is limited to 20 times speedup, no matter how many cores you buy. Amdahl's law is the multicore version of the general speedup formula you met in Measuring Performance.

Python Amdahl's law table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table shows two things. Gains flatten quickly: for a program that is 90 percent parallel, 16 cores give about 6.4 times and 1,024 cores barely reach 9.9. And efficiency drops: most of those cores sit idle waiting for the serial part. This is the main argument for attacking the serial fraction, not just adding hardware.

Gustafson's law: scaling the problem

Amdahl assumes the problem size is fixed. In practice people with bigger machines solve bigger problems: finer weather grids, larger images, more data. Gustafson's law takes that view. If the serial part takes a fixed fraction s of the time on the parallel machine (and the parallel part grows with the machine), the scaled speedup is:

TEXT
scaled_speedup(n) = n - s * (n - 1)

With s = 0.05 and 64 processors you get about 60.9 times, a far more optimistic number. The two laws do not contradict each other: they answer different questions. Amdahl asks, "How much faster does this job finish?" Gustafson asks, "How much more work can I finish in the same time?" The plot below shows both for a 5 percent serial portion.

Python Plotting Amdahl against Gustafson

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Neither law counts the cost of parallelism itself: communication, synchronization, load imbalance (some cores finish early and wait) and memory bandwidth limits. Real speedups usually fall below both curves, which is why parallel programming is as much about data layout and communication as about splitting up the arithmetic.

UMA and NUMA in depth

Shared-memory multiprocessors come in two shapes, and the difference is how long it takes a core to reach a given piece of memory.

UMA (uniform memory access). All cores reach all memory through the same shared bus or crossbar, so every access takes about the same time. This is simple to program and to reason about, but the single path to memory becomes the bottleneck as cores are added, and a shared bus carries every cache-coherence message. UMA suits small systems: a typical four- or eight-core desktop chip with one memory controller behaves this way.

NUMA (non-uniform memory access). Memory is split into nodes, each attached to a group of cores (a socket or chiplet). A core reaches its local memory quickly and remote memory (attached to another node) through an interconnect, which is slower. NUMA scales much further, because each node brings its own memory bandwidth, but the speed of a program now depends on where its data lives.

UMA NUMA
Memory access time Same for every core Local fast, remote slower
Scalability Limited by the shared path Much better, bandwidth grows with nodes
Programming Simple, placement does not matter Placement matters
Coherence traffic One bus snoops everything Directory-based protocols are typical
Typical machines Small multicore chips Multi-socket servers, large chiplet CPUs

The average access time is a weighted mix: if a fraction r of accesses are remote,

Text
average = (1 - r) x T_local + r x T_remote

Operating systems therefore use a first-touch policy (a page is placed on the node of the thread that first writes it), keep a thread on the node holding its data, and allow programs to set affinity. A common bug on multi-socket servers is initializing a big array in one thread, which puts all of it on one node, and then reading it from threads on every node.

Python What remote accesses cost in a NUMA machine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which Flynn category describes adding eight pairs of numbers with one vector instruction?

    One instruction (add) is applied to multiple data elements at once, which is SIMD.
  2. 2. What is the key difference between shared-memory and distributed-memory machines?

    In shared memory, cores read and write the same addresses. In distributed memory each node has private memory and exchanges messages over a network.
  3. 3. Two cores each run load, add 1, store on the same counter that starts at 0, with the loads both happening first. What is the final value?

    Both cores load 0, both compute 1 and both store 1, so one update is lost. This is a race condition.
  4. 4. A program is 90% parallelizable. What is the maximum speedup Amdahl's law allows, however many processors you use?

    The limit is 1 / (1 - p) = 1 / 0.1 = 10, because the serial 10% never shrinks.
  5. 5. How does Gustafson's law differ from Amdahl's law?

    Gustafson measures scaled speedup: with more processors we do more work in the same time, so the serial fraction matters less.

Summary

  • Flynn's taxonomy classifies machines by instruction and data streams: SISD, SIMD, MISD and MIMD. Modern chips combine several of them.
  • Multicore CPUs and clusters are MIMD. Shared memory (UMA or NUMA) is easy to program but needs coherence and synchronization; distributed memory scales further and uses explicit messages.
  • Unsynchronized access to shared data causes race conditions such as lost updates; locks, atomics or message passing prevent them.
  • Amdahl's law: speedup = 1 / ((1 - p) + p / n), capped at 1 / (1 - p). Gustafson's law: scaled speedup = n - s(n - 1).
  • Real speedup is also limited by communication, synchronization, load imbalance and memory bandwidth.

Continue with SIMD, Vector Processing and GPUs.