If one person takes 8 hours to paint a house, can 8 people paint it in 1 hour? Partly. They can paint different walls at the same time, but only one person can stand on the ladder by the front door, someone has to buy the paint first, and the team has to agree on the colour. Some work splits nicely, some does not, and coordination itself costs time.
Computers face exactly the same situation. In Instruction-Level Parallelism & Superscalar Processors we squeezed parallelism out of a single instruction stream and saw that it runs out quickly. The next step is to use many processing elements working together.
Parallel processing is the simultaneous use of multiple processing elements (processors, cores, ALUs or vector lanes) to perform a computation faster, or to perform a bigger computation in the same time.
In this chapter we classify parallel computers using Flynn's taxonomy, look at how processors share or exchange data (shared vs distributed memory, UMA vs NUMA) and how they are connected (interconnection networks), and learn the two laws that predict how much faster a parallel machine can actually go: Amdahl's law and Gustafson's law.
Levels of Parallelism
Parallelism can be found at many granularities, from tiny to huge:
| Level | What runs in parallel | Who exploits it | Example |
|---|---|---|---|
| Bit-level | Bits of a word | ALU width | A 64-bit adder adds 64 bits at once |
| Instruction-level | Independent instructions | Pipelining, superscalar hardware, compiler | Two independent adds issued together |
| Data-level | Same operation on many data items | Vector units, SIMD instructions, GPUs | Adding two arrays of 1000 numbers |
| Thread/task-level | Different threads or tasks | Multicore CPUs, multiprocessors | A web server handling many requests |
| Job/program-level | Independent programs | Clusters, OS scheduler | A cluster running many separate jobs |
Flynn's Classification
In 1966, Michael J. Flynn proposed classifying computers by two simple questions:
- How many instruction streams (sequences of instructions being executed) are active at once?
- How many data streams (sequences of operands being operated on) are active at once?
Each answer is "single" or "multiple", giving four classes.
| Single data stream | Multiple data streams | |
|---|---|---|
| Single instruction stream | SISD | SIMD |
| Multiple instruction streams | MISD | MIMD |
In the diagrams below, CU = control unit (fetches and decodes instructions, producing an instruction stream IS), PE = processing element (an ALU that operates on a data stream DS), and MM = memory module.
1. SISD: Single Instruction, Single Data
IS IS DS
+----+ ----> +----+ ----> +----+ <----> +----+
| MM | | CU | | PE | | MM |
+----+ +----+ +----+ +----+A classic uniprocessor: one control unit fetches one instruction stream and one ALU works on one stream of data. This is the von Neumann model. Note that a pipelined or even a superscalar uniprocessor is still usually counted as SISD, because it executes a single program's instruction stream; the parallelism inside it is hidden from the programmer.
Examples: early PCs and mainframes, simple microcontrollers, any single-core processor.
2. SIMD: Single Instruction, Multiple Data
IS (same instruction broadcast to all PEs)
+---------------+---------------+---------------+
| | | |
+----+ +----+ +----+ +----+ +----+
| CU | -> | PE1| | PE2| | PE3| ... | PEn|
+----+ +----+ +----+ +----+ +----+
| DS1 | DS2 | DS3 | DSn
+----+ +----+ +----+ +----+
| M1 | | M2 | | M3 | | Mn |
+----+ +----+ +----+ +----+One control unit broadcasts each instruction to many processing elements, and each PE applies it to its own data, in lock-step. This is ideal for data-level parallelism: the same operation on every element of an array, every pixel of an image, every neuron in a layer.
Examples:
- Array processors such as ILLIAC IV, and the Connection Machine CM-2.
- Vector processors (Cray-1 style): one vector instruction operates on a whole vector register, with the elements streamed through deeply pipelined functional units.
- SIMD instruction-set extensions in ordinary CPUs: x86 SSE and AVX, ARM NEON and SVE, RISC-V "V" extension.
- GPUs: NVIDIA calls its model SIMT (single instruction, multiple threads): groups of threads (warps) execute the same instruction on different data. GPUs are usually placed under SIMD, though a full GPU with many independent multiprocessors is also MIMD at the top level.
Why SIMD is efficient: one instruction fetch and decode does the work of many, so less energy and hardware go into control. For example, adding two arrays of 1024 floats with 8-wide AVX instructions takes 1024 / 8 = 128 vector add instructions instead of 1024 scalar adds (plus the loads, stores and loop overhead, which shrink by the same factor).
The weakness: branches. If different elements need different operations (an if-else on the data), PEs must take turns, with some idle (masked off), and efficiency drops.
3. MISD: Multiple Instruction, Single Data
+-----+ IS1 +-----+
| CU1 | ---> | PE1 | --+
+-----+ +-----+ |
+-----+ IS2 +-----+ | single data stream flows
| CU2 | ---> | PE2 | --+ through (or is shared by)
+-----+ +-----+ | all the PEs
+-----+ IS3 +-----+ |
| CU3 | ---> | PE3 | --+
+-----+ +-----+Several different instruction streams operate on the same data stream. Very few machines fit this class, and none is a commercial general-purpose computer. Commonly cited examples (each is debated):
- Fault-tolerant redundant systems, where several computers process the same input and vote on the result (for example, the Space Shuttle's flight control computers). Strictly, these often run the same program, so some authors disagree.
- Systolic arrays, where data pulses through a chain of cells, each doing a different step. Many authors instead call these SIMD or MIMD.
- A pipeline where each stage applies a different operation to the same data item is sometimes given as an intuitive example.
For exams, the safe answer is: MISD is mostly of theoretical interest; no practical general-purpose MISD computer has been built, with redundant fault-tolerant systems and systolic arrays as the usual examples.
4. MIMD: Multiple Instruction, Multiple Data
+-----+ IS1 +-----+ DS1
| CU1 | ---> | PE1 | <--+
+-----+ +-----+ |
+-----+ IS2 +-----+ DS2| +-----------------------------+
| CU2 | ---> | PE2 | <--+----> | shared memory, or a network |
+-----+ +-----+ | | of private memories |
+-----+ ISn +-----+ DSn| +-----------------------------+
| CUn | ---> | PEn | <--+
+-----+ +-----+Several independent processors, each with its own control unit, each running its own instruction stream on its own data. This is the most general and by far the most common class of parallel computer today.
Examples: multicore CPUs in phones and laptops, multi-socket servers, clusters and supercomputers. Most MIMD programs are written in SPMD style (single program, multiple data): every processor runs the same program, but on different data and possibly taking different branches, which is different from SIMD's lock-step execution.
Flynn's Classes Compared
| Class | Instruction streams | Data streams | Synchronisation | Typical examples |
|---|---|---|---|---|
| SISD | 1 | 1 | Not applicable | Single-core uniprocessor |
| SIMD | 1 | Many | Lock-step, every cycle | Vector/array processors, AVX/NEON, GPUs |
| MISD | Many | 1 | Varies | Rare: redundant fault-tolerant systems, systolic arrays (debated) |
| MIMD | Many | Many | Asynchronous, explicit (locks, messages) | Multicore CPUs, servers, clusters |
Flynn's taxonomy is simple and still the standard vocabulary, but it is coarse: it says nothing about memory organisation, and modern chips mix classes (a multicore CPU is MIMD, and each core also has SIMD units). Other classifications exist, such as Feng's (based on word length and the number of bits processed in parallel) and Handler's (based on the number of control units, ALUs and bit-level circuits), but Flynn's is the one asked most often.
MIMD Memory Organisation
The most important question about a MIMD machine is: how do processors share data?
Shared-Memory Multiprocessors
All processors share a single address space. They communicate by simply reading and writing shared variables, using locks or other synchronisation (see the OS tutorial's synchronisation chapters). These machines are called multiprocessors or tightly coupled systems.
- UMA (Uniform Memory Access): every processor takes the same time to access any memory location, usually through a shared bus or crossbar. A UMA machine with identical processors is a symmetric multiprocessor (SMP). Simple to program, but the shared bus or memory becomes a bottleneck beyond a modest number of processors.
- NUMA (Non-Uniform Memory Access): memory is physically divided among the processors (or sockets). Each processor reaches its local memory quickly and remote memory more slowly, through an interconnect, but the address space is still shared. Scales better; the OS tries to place a thread's data in its local memory. Multi-socket servers today are NUMA.
- COMA (Cache-Only Memory Architecture): a less common variant where all local memories act as large caches and data migrates to wherever it is used.
UMA (SMP) NUMA
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| P1 | | P2 | | P3 | | P4 | | P1 | | P2 | | P3 | | P4 |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
| | | | \ / \ /
===+======+======+======+=== bus +-----------+ +-----------+
| | local mem | | local mem |
+-------------+ +-----------+ +-----------+
| shared mem | | |
+-------------+ +====== interconnect ====+Distributed-Memory Multicomputers
Each processor has its own private memory and address space. A processor cannot directly load another's memory; data is exchanged by sending messages over a network (for example with MPI). These are multicomputers or loosely coupled systems; clusters and most supercomputers are built this way.
| Aspect | Shared memory (multiprocessor) | Distributed memory (multicomputer) |
|---|---|---|
| Address space | Single, shared | Separate per node |
| Communication | Load/store to shared variables | Explicit send/receive messages |
| Programming | Easier (threads, OpenMP) | Harder (MPI), data placement explicit |
| Scalability | Limited (tens to a few hundred cores) | Very high (thousands to millions of cores) |
| Main hardware issue | Cache coherence, memory contention | Network latency and bandwidth |
| Coupling | Tightly coupled | Loosely coupled |
Shared-memory machines with private caches raise a new problem: two caches may hold different copies of the same location. That is the cache coherence problem, covered in Multicore Processors & Cache Coherence.
Interconnection Networks
Processors and memories must be connected. Networks are compared using a few standard measures:
- Degree: number of links at each node (hardware cost per node).
- Diameter: the largest number of hops between any two nodes, along a shortest path (worst-case latency).
- Bisection width: the minimum number of links that must be cut to split the network into two equal halves (a measure of total bandwidth; bigger is better).
Static (Direct) Networks
Fixed point-to-point links between nodes.
Ring (N = 8) 2D mesh (4 x 4) Hypercube (d = 3, N = 8)
0 - 1 - 2 - 3 o - o - o - o 110 ------ 111
| | | | | | / | / |
7 - 6 - 5 - 4 o - o - o - o 010 ------ 011 |
| | | | | 100 ----|- 101
o - o - o - o | / | /
| | | | 000 ------ 001
o - o - o - o
neighbours differ in exactly one bit| Network (N nodes) | Degree | Diameter | Links | Bisection width | Values for N = 16 |
|---|---|---|---|---|---|
| Ring | 2 | floor(N/2) | N | 2 | diameter 8, 16 links, bisection 2 |
| 2D mesh (k x k, N = k2) | up to 4 | 2(k - 1) | 2k(k - 1) | k | diameter 6, 24 links, bisection 4 |
| 2D torus (k x k) | 4 | 2 floor(k/2) | 2N | 2k | diameter 4, 32 links, bisection 8 |
| Hypercube (N = 2d) | d | d | d 2d-1 | 2d-1 | diameter 4, 32 links, bisection 8 |
| Fully connected | N - 1 | 1 | N(N - 1)/2 | (N/2)2 | diameter 1, 120 links, bisection 64 |
(The mesh and torus bisection formulas assume k is even, and the torus formulas assume k >= 3. For N = 16, the 4 x 4 torus and the 4-dimensional hypercube have identical numbers; in fact they are the same graph drawn differently.)
Dynamic (Indirect) Networks
Switches set up paths between processors and memories as needed.
- Shared bus: cheapest; only one transfer at a time, so it saturates quickly. Used in small SMPs.
- Crossbar switch: an N x N grid of N2 crosspoint switches. Any processor can connect to any free memory module, and all N pairs can talk simultaneously (non-blocking). Cost grows as N2 (256 crosspoints for N = 16).
- Multistage networks such as the omega network: log2N stages of 2 x 2 switches, N/2 switches per stage, so (N/2) log2N switches in total (4 stages and 32 switches for N = 16). Much cheaper than a crossbar, but blocking: two transfers may need the same internal link at the same time.
How Much Faster? Speedup and Efficiency
Speedup S(N) = T(1) / T(N) T(1): time on 1 processor, T(N): time on N
Efficiency E(N) = S(N) / N fraction of the processors' time doing useful workIdeal (linear) speedup is S(N) = N, efficiency 100%. In practice speedup is lower because of serial parts of the program, communication, synchronisation and load imbalance.
Amdahl's Law
Gene Amdahl (1967) pointed out that the part of a program that cannot be parallelised limits the overall speedup. Let f be the fraction of the original execution time that can be parallelised (so 1 - f is serial). With N processors, the parallel part runs N times faster and the serial part does not:
1
S(N) = ---------------------
(1 - f) + f / N
As N -> infinity: S(max) = 1 / (1 - f)The same formula works for any enhancement: replace N by the speedup of the enhanced part. If 40% of the time is made 10x faster, overall speedup = 1 / (0.6 + 0.4/10) = 1/0.64 = 1.5625.
Solved Problem 1
Question. 90% of a program can be parallelised. Find the speedup and efficiency on 8 and 16 processors, and the maximum possible speedup.
N = 8 : S = 1 / (0.1 + 0.9/8) = 1 / 0.2125 = 4.71 E = 4.71 / 8 = 58.8%
N = 16: S = 1 / (0.1 + 0.9/16) = 1 / 0.15625 = 6.40 E = 6.40 / 16 = 40.0%
Max : S = 1 / 0.1 = 10 (no matter how many processors)Doubling from 8 to 16 processors raised speedup only from 4.71 to 6.40, and efficiency fell from 59% to 40%. Just 10% serial code caps the speedup at 10.
Solved Problem 2
Question. You want a speedup of 50 on 64 processors. What fraction of the program must be parallel?
50 = 1 / ((1 - f) + f/64)
(1 - f) + f/64 = 1/50 = 0.02
1 - f(63/64) = 0.02
f = 0.98 x 64/63 = 224/225 = 0.99556More than 99.55% of the program must be parallel: the serial part must be under 0.45%. This is why Amdahl's law made people pessimistic about massive parallelism.
Gustafson's Law
John Gustafson (1988) observed that people do not use a bigger machine to solve the same problem faster; they solve a bigger problem in the same time (finer weather grids, bigger simulations). The serial part (setup, I/O) usually stays about the same while the parallel part grows with N.
Let s be the serial fraction of the time measured on the parallel machine with N processors. The same work on one processor would take s + N(1 - s), so the scaled speedup is:
S(N) = s + N(1 - s) = N - s(N - 1)
s = 0.1, N = 8 : S = 8 - 0.1 x 7 = 7.3
s = 0.05, N = 64: S = 64 - 0.05 x 63 = 60.85| Aspect | Amdahl's law | Gustafson's law |
|---|---|---|
| Problem size | Fixed (strong scaling) | Grows with N (weak scaling) |
| Question asked | How much faster can I solve this problem? | How much more work can I do in the same time? |
| Serial fraction measured on | The single-processor run | The parallel run |
| Speedup as N grows | Saturates at 1/(1 - f) | Grows roughly linearly with N |
| Outlook | Pessimistic | Optimistic |
The two laws do not contradict each other: they answer different questions.
Common Mistakes
- Calling a pipelined or superscalar uniprocessor MIMD. It runs one instruction stream, so in Flynn's terms it is SISD.
- Confusing SIMD with SPMD. SIMD executes one instruction in lock-step on all data; SPMD (a MIMD programming style) runs copies of one program independently on each processor.
- Giving a modern multicore CPU as an MISD example. It is MIMD. MISD has essentially no general-purpose examples.
- Using f as the serial fraction in Amdahl's formula. Check which fraction the question gives you: S = 1 / (serial + parallel/N).
- Mixing up UMA and NUMA. NUMA still has a shared address space; only the access time differs. A distributed-memory multicomputer has no shared address space at all.
- Crossbar vs omega. The crossbar is non-blocking with N2 switches; the omega network uses (N/2) log2N switches but is blocking.
GATE and Interview Questions
Q1. Classify: (a) a GPU running a shader on all pixels, (b) a 16-core server running different programs, (c) a single-core in-order microcontroller, (d) an AVX-512 instruction adding 16 floats.
(a) SIMD (SIMT). (b) MIMD. (c) SISD. (d) SIMD.
Q2. 75% of a program is parallelisable. What is the speedup on 4 processors, and the upper limit?
S = 1 / (0.25 + 0.75/4) = 1 / 0.4375 = 2.29. Limit = 1 / 0.25 = 4.
Q3. For a hypercube of 64 nodes, find the degree, diameter, number of links and bisection width.
64 = 26, so d = 6. Degree 6, diameter 6, links = 6 x 25 = 192, bisection width = 25 = 32.
Q4. How many 2 x 2 switches does an 8 x 8 omega network need?
log28 = 3 stages, 8/2 = 4 switches per stage, total 12 switches. (An 8 x 8 crossbar would need 64 crosspoints.)
Q5. What is the difference between UMA and NUMA?
In UMA all processors see the same latency to every memory location (usually through a shared bus or crossbar). In NUMA memory is distributed among processors; access to local memory is faster than access to remote memory, but all memory is still in one shared address space.
Q6. Why does Gustafson's law predict much higher speedups than Amdahl's law?
Amdahl assumes a fixed problem, so the serial part's share of time grows as the parallel part shrinks. Gustafson assumes the problem grows with N while the serial part stays fixed, so the serial share stays small and speedup grows almost linearly.
Summary
- Parallel processing uses many processing elements at once; parallelism exists at bit, instruction, data, thread and job levels.
- Flynn's taxonomy (1966) counts instruction and data streams: SISD (uniprocessor), SIMD (vector/array processors, SIMD extensions, GPUs), MISD (rare, mostly theoretical), MIMD (multicores, clusters).
- MIMD machines are either shared memory (UMA/SMP, NUMA) communicating through loads and stores, or distributed memory communicating through messages.
- Interconnection networks are judged by degree, diameter and bisection width: ring, mesh, torus, hypercube, fully connected (static); bus, crossbar, omega (dynamic).
- Amdahl's law: S = 1 / ((1 - f) + f/N), capped at 1/(1 - f). Gustafson's law: scaled speedup S = N - s(N - 1).
- Shared memory with private caches creates the coherence problem, solved in Multicore Processors & Cache Coherence.