---
title: Processes, Threads, and Parallelism
module: Multithreading & Multicore
moduleNumber: 9
lessonNumber: 1
order: 901
summary: >
  Around 2004 the single core stopped getting faster, and the industry's answer
  was to hand programmers more cores instead. This lesson builds the vocabulary
  that shift demands: process versus thread and exactly which hardware state each
  one owns, concurrency versus parallelism, the three kinds of parallelism a
  machine can exploit, why Dennard scaling ended and forced the multicore turn,
  and Amdahl's law — the arithmetic that bounds the speedup those cores can
  deliver.
topics: [Multithreading & Multicore]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §1.9.1 Thread-Level Concurrency; §5.14.3 Amdahl's Law; §12.3–12.6 Concurrent Programming with Threads"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §1.3.2 Quantitative Aspects (Amdahl's Law)"
---

Every processor this course has built so far runs **one** instruction stream.
[SEQ](/computer-architecture/processor-design/assembling-seq) executed it one
instruction at a time; [PIPE](/computer-architecture/pipelining/the-complete-pipe-processor)
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](/computer-architecture/virtual-memory/address-spaces-and-translation),
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.

> **Definition (Thread).** An independent stream of execution inside a process.
> Each thread has private architectural state — program counter, general-purpose
> registers, condition codes, and a stack of its own — while sharing the
> process's address space: code, globals, heap, and open files.

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](/computer-architecture/multithreading-and-multicore/cache-coherence).

$$
% caption: One process, two threads. Code, globals, and the heap live in the shared
% caption: address space; each thread privately owns a PC, a register set, and a
% caption: stack. Sharing is by ordinary load/store into the common region.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  box/.style={draw, minimum width=24mm, minimum height=7mm, inner sep=2pt, align=center},
  priv/.style={draw, minimum width=20mm, minimum height=6mm, inner sep=2pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  % shared column (center)
  \node at (0,2.6) {shared by all threads};
  \node[box, fill=acc!8] (code) at (0,1.8) {code};
  \node[box, fill=acc!8] (glob) at (0,0.95) {globals};
  \node[box, fill=acc!8] (heap) at (0,0.1) {heap};
  % thread 1 (left)
  \node at (-4.2,2.6) {thread 1: own state};
  \node[priv] (pc1) at (-4.2,1.8) {PC};
  \node[priv] (rf1) at (-4.2,0.95) {registers};
  \node[priv] (st1) at (-4.2,0.1) {stack};
  % thread 2 (right)
  \node at (4.2,2.6) {thread 2: own state};
  \node[priv] (pc2) at (4.2,1.8) {PC};
  \node[priv] (rf2) at (4.2,0.95) {registers};
  \node[priv] (st2) at (4.2,0.1) {stack};
  % access arrows into the shared heap/globals
  \draw[->, acc, thick] (rf1.east) -- (glob.west);
  \draw[->, acc, thick] (rf2.west) -- (glob.east);
\end{tikzpicture}
$$

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.

```c [threads.c]
#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](/computer-architecture/multithreading-and-multicore/memory-consistency-and-synchronization).
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`.

$$
% caption: A losing interleaving of two shared += arg operations. Both threads
% caption: read shared = 0 before either stores, so thread 2's store of 2
% caption: overwrites thread 1's store of 1: the final value is 2, and thread 1's
% caption: increment vanished. The expected 3 requires the steps not to overlap.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  ev/.style={draw, minimum width=34mm, minimum height=6mm, inner sep=1pt, align=left}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=east] at (-0.4,2.4) {thread 1};
  \node[anchor=east] at (-0.4,-0.3) {thread 2};
  \node[ev, fill=acc!8]  (a1) at (1.6,2.4)  {load: reg1 = shared = 0};
  \node[ev, fill=acc!8]  (a2) at (1.6,1.6)  {add:  reg1 = 0 + 1 = 1};
  \node[ev, fill=acc!25] (b1) at (6.6,0.5)  {load: reg2 = shared = 0};
  \node[ev, fill=acc!25] (b2) at (6.6,-0.3) {add:  reg2 = 0 + 2 = 2};
  \node[ev, fill=acc!8]  (a3) at (1.6,0.8)  {store: shared = 1};
  \node[ev, fill=acc!25] (b3) at (6.6,-1.1) {store: shared = 2 (overwrites)};
  \draw[->, black] (-0.3,-1.9) -- (9.2,-1.9) node[anchor=west] {time};
\end{tikzpicture}
$$

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](/computer-architecture/multithreading-and-multicore/memory-consistency-and-synchronization)
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.

> **Definition (Concurrency vs. parallelism).** Two activities are **concurrent**
> if their executions overlap in time — neither finishes before the other starts.
> They are **parallel** if they execute _simultaneously_, on hardware that runs
> both at the same instant. Parallelism implies concurrency; the converse fails.

A single core has been running concurrent threads since long before multicore:
the OS timer interrupt from the
[exceptions lesson](/computer-architecture/exceptions-and-io/interrupts-and-the-kernel)
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](/computer-architecture/multithreading-and-multicore/hardware-multithreading)
shows, a second hardware thread context) so that two instruction streams
genuinely advance in the same cycle.

$$
% caption: Concurrency without parallelism (top): one core time-slices threads A
% caption: and B, so they overlap in time but never in the same cycle. Parallelism
% caption: (bottom): two cores advance A and B simultaneously.
\begin{tikzpicture}[font=\footnotesize,
  sl/.style={draw, minimum width=12mm, minimum height=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=east] at (-0.85,1.5) {one core};
  \foreach \i/\l in {0/A, 1/B, 2/A, 3/B, 4/A}
    \node[sl, fill=acc!8] at (\i*1.3,1.5) {\l};
  \node[anchor=east] at (-0.85,0.0) {core 0};
  \foreach \i in {0,...,4} \node[sl, fill=acc!8] at (\i*1.3,0.0) {A};
  \node[anchor=east] at (-0.85,-0.8) {core 1};
  \foreach \i in {0,...,4} \node[sl, fill=acc!20] at (\i*1.3,-0.8) {B};
  \draw[->, black] (-0.2,-1.5) -- (5.6,-1.5) node[anchor=west] {time};
\end{tikzpicture}
$$

## 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](/computer-architecture/pipelining/pipelining-principles) is
its simplest form; superscalar issue and the out-of-order machinery sketched in
the [capstone](/computer-architecture/capstone/the-whole-machine) 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](/computer-architecture/pipelining/control-hazards-and-branch-prediction)
and [data hazards](/computer-architecture/pipelining/data-hazards-stalling-and-forwarding)
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.

$$
% caption: Three grains of parallelism. ILP: one stream, overlapped stages inside
% caption: a pipeline. DLP: one instruction, several data lanes. TLP: independent
% caption: streams on independent cores.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  c/.style={draw, minimum width=7mm, minimum height=6mm, inner sep=0pt},
  hd/.style={anchor=base}]
  \definecolor{acc}{HTML}{2348F2}
  % ILP panel
  \node[hd] at (1.0,1.7) {ILP};
  \foreach \r/\y in {0/0.9, 1/0.45, 2/0.0}
    \foreach \i in {0,1,2} \node[c, fill=acc!8] at (\r*0.35+\i*0.75,\y) {};
  % DLP panel
  \node[hd] at (5.4,1.7) {DLP};
  \node[c, minimum width=30mm, fill=acc!8] at (5.4,0.9) {one instruction};
  \foreach \i in {0,...,3} {
    \draw[->, acc] (4.35+\i*0.7,0.55) -- (4.35+\i*0.7,0.15);
    \node[c] at (4.35+\i*0.7,-0.15) {};
  }
  % TLP panel
  \node[hd] at (9.6,1.7) {TLP};
  \foreach \r/\y in {0/0.9, 1/0.0} {
    \node[anchor=east] at (8.75,\y) {\scriptsize core \r};
    \foreach \i in {0,1,2} \node[c, fill=acc!20] at (9.05+\i*0.75,\y) {};
  }
\end{tikzpicture}
$$

## 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](/computer-architecture/multithreading-and-multicore/hardware-multithreading):
if you cannot clock one stream faster, keep the hardware busy with more streams.

$$
% caption: The power wall. Clock rates climbed for three decades under Dennard
% caption: scaling, then voltage stopped shrinking near 2004 and frequency froze
% caption: around 3 to 4 GHz. Transistor budgets kept growing and went into cores.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, black] (0,0) -- (9.2,0) node[anchor=north west] {year};
  \draw[->, black] (0,0) -- (0,3.6) node[anchor=south] {clock rate};
  \foreach \x/\l in {0.6/1990, 3.0/1997, 5.4/2004, 7.8/2011}
    \node[anchor=north] at (\x,-0.05) {\scriptsize \l};
  \draw[acc, very thick]
    plot[smooth] coordinates {(0.6,0.3) (2.0,0.7) (3.4,1.4) (4.6,2.4) (5.4,2.9)
                              (6.4,3.0) (7.6,3.0) (8.8,3.05)};
  \draw[black, dashed] (5.4,0) -- (5.4,2.6);
  \node[anchor=north, text=acc] at (7.4,2.6) {\scriptsize about 3-4 GHz since};
  \node[anchor=east] at (4.85,0.75) {\scriptsize power wall};
  \draw[->, black] (4.95,0.85) -- (5.32,1.4);
\end{tikzpicture}
$$

## 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},
\qquad
S(N) = \frac{T}{T_N} = \frac{1}{(1-p) + \dfrac{p}{N}}.
$$

> **Theorem (Amdahl's law).** If a fraction $p$ of a computation is
> parallelizable across $N$ processors and the rest is serial, the overall
> speedup is $S(N) = 1 / \big((1-p) + p/N\big)$, and even with unlimited
> processors $S(\infty) = 1/(1-p)$.

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.

$$
% caption: Amdahl speedup S(N) = 1 / ((1-p) + p/N). At p = 0.9 the curve reaches
% caption: only 4.7 on 8 cores and flattens toward its ceiling of 10; at p = 0.5
% caption: the ceiling is 2. The serial fraction, not the core count, is in charge.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % axes: x = cores (N/4), y = speedup (S/2)
  \draw[->, black] (0,0) -- (8.8,0) node[anchor=north west] {cores};
  \draw[->, black] (0,0) -- (0,5.4) node[anchor=south] {speedup};
  \foreach \x/\l in {0.25/1, 2/8, 4/16, 8/32}
    \node[anchor=north] at (\x,-0.05) {\scriptsize \l};
  \foreach \y/\l in {1/2, 2.35/4.7, 5/10}
    \node[anchor=east] at (-0.1,\y) {\scriptsize \l};
  % ceiling for p=0.9 at S=10 -> y=5
  \draw[black, dashed] (0,5) -- (8.6,5);
  \node[anchor=south west] at (5.2,5.02) {\scriptsize ceiling 1/(1-p) = 10};
  % p = 0.9 curve: (N, S/2): 1,0.5  2,0.909  4,1.538  8,2.353  16,3.2  24,3.6  32,3.902
  \draw[acc, very thick]
    plot[smooth] coordinates {(0.25,0.5) (0.5,0.909) (1,1.538) (2,2.353)
                              (4,3.2) (6,3.6) (8,3.902)};
  \node[text=acc, anchor=west] at (5.1,3.15) {p = 0.9};
  % p = 0.5 curve: 1,0.5  2,0.667  4,0.8  8,0.889  16,0.941  32,0.970
  \draw[black, thick]
    plot[smooth] coordinates {(0.25,0.5) (0.5,0.667) (1,0.8) (2,0.889)
                              (4,0.941) (8,0.970)};
  \node[anchor=west, text=black] at (5.1,0.62) {p = 0.5};
  % guide at 8 cores
  \draw[black, dashed] (2,0) -- (2,2.353);
  \draw[black, dashed] (0,2.353) -- (2,2.353);
\end{tikzpicture}
$$

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/\big((1-p) + p/k\big)$; 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.9N$ |
|:---:|:---:|:---:|
| 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.

> **Takeaway.** A process owns an address space; its threads share that space
> and privately own only PC, registers, and a stack. Concurrency is overlap in
> time, parallelism is overlap in hardware, and machines mine it at three
> grains: ILP within a stream, DLP across data, TLP across streams. Dennard
> scaling's end froze clocks and forced transistor budgets into cores, and
> Amdahl's law prices what those cores can return: the serial fraction sets a
> ceiling of $1/(1-p)$ that no core count breaks.

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](/computer-architecture/multithreading-and-multicore/hardware-multithreading),
is still why the logical CPUs on a machine come in pairs.