Processes, Threads, and Parallelism

Every processor this course has built so far runs one instruction stream. SEQ executed it one instruction at a time; PIPE overlapped five instructions but still drew them from a single sequential program. For thirty years that model kept getting faster on its own: the same binary ran at 25 MHz in 1990, 500 MHz in 1998, 3 GHz in 2004. Then the clock stopped climbing, and it has barely moved since. What changed was not ambition but physics, and the industry's response — put several complete processors on one die and ask software to use them — is the subject of this module. Before any of the hardware makes sense, we need precise names for the things that run on it.

Program, process, thread

A program is a dead artifact: an executable file of code and initialized data sitting on disk. Nothing about it executes. A process is a program brought to life by the operating system: the program's code and data mapped into a fresh virtual address space, plus everything the OS needs to run and suspend it: a register snapshot, a page table, open file descriptors. Two processes are isolated by construction; each has its own address space, and neither can read the other's memory even by accident.

A thread is a unit of execution within a process, and it is deliberately much lighter. All threads of a process share one address space: the same code, the same global data, the same heap. What each thread owns privately is the state that defines a point of execution: a program counter, a set of register values including its own stack pointer, and therefore its own stack.

The split is worth stating from the hardware's point of view, because it determines both what threads are good at and what makes them dangerous. The address space is shared, so two threads communicate by ordinary loads and stores to the same variables, with no OS help and no copying. The register file and PC are private, so switching a core between two threads of one process means swapping only the register state; the page table stays put and the caches stay warm. Caches sit in between: they hold memory, and memory is shared, so cache contents are common property too, a fact that will do a great deal of work (and damage) in the coherence lesson.

One process, two threads. Code, globals, and the heap live in the shared address space; each thread privately owns a PC, a register set, and a stack. Sharing is by ordinary load/store into the common region.

The sharing is literal. A global variable written by one thread is readable by every other thread with a plain mov; a local variable lives on one thread's private stack and is invisible to the rest unless its address is handed over explicitly.

threads.cc

#include <pthread.h>
#include <stdio.h>

long shared = 0;                 /* one copy, visible to every thread   */

void *worker(void *arg) {
  long local = 42;               /* on THIS thread's stack: private     */
  shared += (long) arg;          /* plain store into common memory      */
  return (void *) local;
}

int main(void) {
  pthread_t t1, t2;
  pthread_create(&t1, NULL, worker, (void *) 1);
  pthread_create(&t2, NULL, worker, (void *) 2);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  printf("%ld\n", shared);       /* probably 3 ... but see lesson 4     */
}

The shared += ... line is a read-modify-write, and two threads doing it at once can interleave badly; the probably in the comment is the entire subject of lesson 4. For now the point is the memory model: shared has one address, local has one address per thread.

To see why probably and not certainly, unroll shared += arg into the three machine steps it really is — load shared into a register, add arg, store the sum back — and pick the interleaving that loses an update. Both threads start with shared holding 0; thread 1 carries arg = 1, thread 2 carries arg = 2.

A losing interleaving of two shared += arg operations. Both threads read shared = 0 before either stores, so thread 2's store of 2 overwrites thread 1's store of 1: the final value is 2, and thread 1's increment vanished. The expected 3 requires the steps not to overlap.

Read down the time axis: thread 1 reads 0 and computes 1, thread 2 then reads the still-unchanged 0 and computes 2, thread 1 stores 1, and thread 2 stores 2 on top of it. The program prints 2, not 3. Nothing is broken — each instruction did exactly what it was told — but the two read-modify-writes overlapped on one address, and one increment was lost. Serialize the six steps any other way and you may get 3; the outcome depends on timing the source never mentions. This is a data race, and the fourth lesson restores determinism with atomic instructions and locks.

Concurrency and parallelism

Two words that get used interchangeably name different things, and the distinction matters for the rest of the module.

A single core has been running concurrent threads since long before multicore: the OS timer interrupt from the exceptions lesson suspends one thread, saves its registers, restores another's, and resumes. Sliced finely enough this looks simultaneous to a human, but at any instant exactly one thread's instructions are in the pipeline. Parallelism requires more hardware: a second core (or, as the next lesson shows, a second hardware thread context) so that two instruction streams genuinely advance in the same cycle.

Concurrency without parallelism (top): one core time-slices threads A and B, so they overlap in time but never in the same cycle. Parallelism (bottom): two cores advance A and B simultaneously.

Three kinds of parallelism

Parallelism is also too coarse a word, because machines exploit it at three distinct grains, and this course has already built two of them.

Instruction-level parallelism (ILP) is overlap between instructions of one stream. Pipelining is its simplest form; superscalar issue and the out-of-order machinery sketched in the capstone push it further. ILP is invisible to software, since the machine finds it in the program you already wrote, and by the early 2000s it was mined out: wider issue bought little because real programs carry limited independent work per instruction window, while the branch and data hazards that pipelines must dodge grow costlier as pipelines deepen.

Data-level parallelism (DLP) is one operation applied to many data elements at once. SIMD vector units execute it: one AVX instruction adds eight pairs of 32-bit floats in a single go. The parallelism must exist in the data layout, and compilers or programmers must expose it.

Thread-level parallelism (TLP) is overlap between different instruction streams: separate threads, each with its own PC, scheduled onto separate cores or hardware thread contexts. TLP is the coarsest grain, the one this module is about, and the only one of the three that changes the programming model: someone must write, synchronize, and debug those threads.

Three grains of parallelism. ILP: one stream, overlapped stages inside a pipeline. DLP: one instruction, several data lanes. TLP: independent streams on independent cores.

The power wall

Multicore was a retreat forced by physics, and the reason is one equation. Switching power in CMOS scales as $P \approx C V^{2} f$ : capacitance times voltage squared times frequency. For decades Dennard scaling kept that equation favorable — each process generation shrank transistors, and the smaller devices ran at a proportionally lower voltage, so designers could raise $f$ every generation while power per square millimeter held constant. Around the 90 nm node (~2004) voltage stopped scaling: below roughly a volt, transistor leakage current grows so fast that lowering $V$ further loses more than it saves. With $V$ pinned, every further increase in $f$ raises power directly, and chips were already at the limit of what air cooling removes. Clock frequency froze near 3–4 GHz, and it is still there.

Transistor counts, however, kept doubling; Moore's law outlived Dennard scaling by decades. The industry had billions of new transistors per generation and no way to spend them on a faster single core. What worked was replication: two complete cores per die in 2005, four by 2008, and today's server parts carry dozens. The same reasoning favors SMT: if you cannot clock one stream faster, keep the hardware busy with more streams.

The power wall. Clock rates climbed for three decades under Dennard scaling, then voltage stopped shrinking near 2004 and frequency froze around 3 to 4 GHz. Transistor budgets kept growing and went into cores.

Amdahl's law

More cores only help the part of a program that can use them, and the part that cannot sets a hard ceiling. Suppose a program takes time $T$ on one core, and a fraction $p$ of that time is perfectly parallelizable while the remaining $1 - p$ is inherently serial. On $N$ cores the parallel part shrinks to $pT / N$ ; the serial part does not move. The new time and the resulting speedup are

T_{N} = (1 - p) T + \frac{p T}{N}, S (N) = \frac{T}{T _{N}} = \frac{1}{( 1 - p ) + \frac{p}{N}} .

The numbers are worse than the formula suggests. Take a program that is 90 % parallel ( $p = 0.9$ ) on 8 cores:

S (8) = \frac{1}{0.1 + 0.9/8} = \frac{1}{0.1 + 0.1125} = \frac{1}{0.2125} \approx 4.7.

Eight cores, less than a factor of five. On 16 cores the same program reaches $S (16) = 1/ (0.1 + 0.05625) = 6.4$ ; on infinitely many, $1/0.1 = 10$ and no more. Half the theoretical machine is already gone at 8 cores, and each doubling buys less than the one before. Run the same arithmetic at $p = 0.5$ and the ceiling is 2: a program that is half serial can never even double, no matter what you buy.

Amdahl speedup S(N) = 1 / ((1-p) + p/N). At p = 0.9 the curve reaches only 4.7 on 8 cores and flattens toward its ceiling of 10; at p = 0.5 the ceiling is 2. The serial fraction, not the core count, is in charge.

Amdahl's law generalizes past cores: it is the arithmetic of optimizing any part of a system. Speed up a component that takes fraction $p$ of the time by a factor $k$ and the whole improves by $1/ ((1 - p) + p / k)$ ; the lesson, there as here, is that a big speedup of a small piece is a small speedup.

Gustafson's counterpoint. Amdahl fixes the problem size and asks how much faster it runs; that is the right question for a fixed workload, and the answer is grim. Gustafson observed that people with bigger machines run bigger problems. Fix the time instead, let the parallel work grow with $N$ , and the scaled speedup is $S (N) = (1 - p) + pN$ : linear, because the serial fraction shrinks relative to an expanding parallel part. At $p = 0.9$ and $N = 8$ that is $0.1 + 7.2 = 7.3$ , against Amdahl's 4.7. Neither law is wrong; they answer different questions. Amdahl governs latency on a fixed problem, Gustafson throughput on a scalable one, and honest performance claims say which regime they live in.

The gap between the two widens fast, and it is worth seeing side by side at $p = 0.9$ . Amdahl's speedup climbs toward its ceiling of 10 and stalls; Gustafson's climbs without bound because the serial 10 % is a shrinking slice of a growing job:

cores $N$	Amdahl $1/ (0.1 + 0.9/ N)$	Gustafson $0.1 + 0.9 N$
1	1.0	1.0
8	4.7	7.3
16	6.4	14.5
64	8.8	57.7
256	9.6	230.5
$\infty$	10.0	grows without bound

The question asked decides the answer. If you must finish this job faster, the serial fraction is a wall at $1/ (1 - p)$ and buying cores past a handful gains almost nothing. If instead a bigger machine lets you tackle a bigger job in the same wall-clock time — a finer simulation grid, a larger training batch, more independent web requests — the serial fraction fades and near-linear scaling returns. Most real large-scale computing lives in Gustafson's regime, which is why supercomputers keep getting bigger even though Amdahl says they shouldn't.

The laws behind the multicore turn

The arithmetic of this lesson comes from a handful of named papers, and the history is short enough to state exactly.

Amdahl's law is from Gene Amdahl's 1967 AFIPS paper, a two-page argument against the then-fashionable belief that parallel machines would soon overtake fast serial ones. Amdahl's point was rhetorical — the serial fraction dooms that hope — and the formula that carries his name was extracted from the argument later. Gustafson's rebuttal is equally specific: John Gustafson, then at Sandia, published Reevaluating Amdahl's Law (1988, CACM) after his group won the first Gordon Bell Prize by scaling problems on a 1024-processor hypercube. His observation was empirical before it was mathematical: the users of his machine did not run the same problem faster, they ran bigger problems in the same time, and under that discipline speedup was very nearly linear.

The end of Dennard scaling has its own foundational paper: Robert Dennard's 1974 IEEE JSSC article laid out the scaling rules that let each process generation shrink transistors and lower voltage in lockstep, holding power density constant. When that broke around 2004, the consequences were named in The Landscape of Parallel Computing Research: A View from Berkeley (Asanović et al., 2006), the report that popularized the phrase power wall and argued the industry had no choice but to go parallel. The companion diagnosis, that even the parallel path faces its own limit, is Esmaeilzadeh et al.'s dark silicon result (2011, ISCA): at fixed power, a chip cannot switch on all its transistors at once, so a growing fraction of every future die must sit dark, and simply adding cores stops paying around a few tens of them for general-purpose work. That result is the modern reason architectures have turned toward specialization — GPUs, tensor units, fixed-function accelerators — rather than ever more identical cores, a turn the rest of this module's cores set the stage for.

The next lesson descends into the core itself: before machines had many cores, they learned to run several threads on one — and that mechanism, hardware multithreading, is still why the logical CPUs on a machine come in pairs.