Multithreading: fine-grained, coarse-grained, SMT, and the exam’s per-thread CPI

Forty slots, sixteen used: what one thread leaves empty

Lessons 8 to 21 asked one question: how many instructions of one thread can run at the same time? A superscalar answers it at run time, with Tomasulo, renaming and the reorder buffer; a VLIW at compile time, in bundles. Both meet the same wall (p. 371). A true RAW dependence makes an instruction wait for its producer; a branch wastes cycles when the guess is wrong; a load that misses waits for memory — "a cache miss that takes 200 cycles" (p. 372). So even a core able to issue eight instructions per cycle rarely finds eight ready ones in one thread; lesson 8 counted the walls.

Fig. 1 makes it concrete. It redraws the notes' Figure 29, a quad-issue core watched for ten cycles, C0 to C9. The left panel runs one thread. Count it: 16 of the 40 slots are filled. The 24 empty ones come in two shapes, and a good exam answer names both.

In the left grid rows C5–C7 are empty: 3 × 4 = 12 slots of vertical waste, typically a miss. The other 12 empty slots are horizontal: the thread was running, but its ILP gave one, two or three ready instructions instead of four. A handful of numbers summarise any grid. The first is the formula sheet's code efficiency, counted on issue slots:

For the left grid: \(U = 16/40 = 0.40\), IPC = 1.6, CPI = 10/16 = 0.625 — two and a half times the ideal \(1/w = 0.25\) of lesson 8. Sixty per cent of a core that was paid for in area and power does nothing.

The way out is the notes' next question: "If one thread alone cannot keep the machine busy, why not let another thread provide instructions in the meantime?" (p. 372). Instruction-level parallelism (ILP) is parallelism inside one instruction stream; thread-level parallelism (TLP) is parallelism across streams, and multithreading "does not replace ILP, it complements it". The threads must already exist — written by the programmer, or separate programs run by the operating system. The hardware interleaves them; it does not create them.

The right panel shows the gain and the price. Four threads fill 32 slots: the core's CPI halves to 10/32 = 0.3125. But T1, the same thread as on the left, now issues 8 instructions in the ten cycles instead of 16: its own CPI doubles from 0.625 to 1.25. Multithreading is throughput-oriented (p. 377): the core completes more instructions per cycle, and each thread may finish later. A web server with hundreds of independent requests gains; a single-threaded program gains nothing.

Multithreading fills the slots one thread leaves empty with other threads' instructions: the core's throughput rises, while a single thread's latency does not fall and may rise.

A thread lives in a context: what is copied, what is shared, why the OS is too slow

A program in execution is a process: its own address space (code, heap, stack, data) and operating-system resources such as open files. Inside a process run one or more threads (p. 373).

Take one loop and run it in two threads, T1 over an array A and T2 over an array B:

LOOP: LD    F2, 0(R1)
      FADD  F4, F2, F2
      SD    F4, 0(R1)
      ADDUI R1, R1, 8
      BNE   R1, R2, LOOP

Both threads write R1 and F2. If they shared one R1, each ADDUI would move the other thread's pointer too. So each thread needs its own program counter, its own registers and its own status bits: its hardware context. "If one core supports 4 hardware threads, it will contain 4 PCs and 4 register files" (p. 378). Everything expensive stays shared — the functional units, the caches, the TLB and the memory system — because duplicating them "would make multithreading as expensive as adding more cores" (p. 378). A context costs registers and a little control logic; a core costs a datapath and its caches.

The operating system can already run T1 and T2 one after the other. A context switch saves the old thread's registers, program counter and status to memory, restores the new thread's and, between two processes, changes the memory mappings: "thousands of CPU cycles" (p. 375). That is fine for multitasking at the OS level, and useless against a 200-cycle miss. Hardware multithreading keeps all the contexts inside the core at once: changing thread means selecting another program counter and another set of registers, "a few cycles or even just one cycle", with no OS call and nothing copied (p. 375). The widget weighs the two.

The rule the widget draws fits in one line: a switch hides a stall of L cycles only if it costs less than the stall.

With S in the thousands, the OS cannot hide any cache miss. With a drain of a few cycles, a 200-cycle DRAM miss is worth a switch and a 3-cycle RAW stall is not. With S = 0 every stall is worth hiding. The three hardware schemes of the next section are three answers to one question: when, and how cheaply, to change thread.

Three ways to share one pipeline: coarse, fine, simultaneous

The notes define three schemes (pp. 380–381). They differ in two rules: when the core changes thread, and how many threads may issue in the same cycle. Look at the textbook's four grids before reading the rules: each tab writes one of them in the form the papers ask for, one row per cycle and one column per issue slot.

Coarse-grained multithreading runs one thread until it hits a long-latency stall, typically a miss to DRAM, then switches to another thread. The switch drains and refills the pipeline — a few cycles, "negligible compared to hundreds of cycles of stall" (p. 380). In the coarse-grained tab T1 runs from C0 to C4; when it stalls, T2 takes over at C5, and in C9 nobody issues: a switch is not free. It is the simplest scheme — duplicate the PC and the registers and leave the per-cycle logic alone, "run until we hit a brick wall, then switch" (p. 374) — and it is useless against short stalls such as data hazards and mispredictions, where the switch costs as much as the stall. It pays where the notes place it (p. 374): stalls of hundreds of cycles, a drain that is short beside them, and a core narrow enough that one thread per cycle keeps it fed. The machines usually cited are IBM's RS64-II "Northstar" (1998) and Intel's Itanium 2 "Montecito" (2006). The notes' "some GPUs in specific modes" (p. 374) points the wrong way: a GPU's warp scheduler changes thread every cycle (lesson 32).

Fine-grained multithreading switches thread every cycle, usually round robin: "If one thread is stalled, it's skipped" (p. 380). In the fine-grained tab the threads rotate T1, T2, T3, T4, T1 …, one per row: no row is empty, and no row is full. While any thread is ready the pipeline never idles, so short stalls are hidden as well as long ones, at no switch cost. Each thread now issues only every few cycles, and the core needs selection logic fast enough to decide every cycle. Sun's Niagara (2005) is the commercial case: eight single-issue pipelines with four threads each, whose second stage is literally called "thread select", "with a zero cycle switch penalty" (Kongetira and others, 2005).

Simultaneous multithreading (SMT) runs on a superscalar whose issue slots one thread rarely fills — 4 to 8 of them in the notes, 2 or 4 in the papers' questions — and issues "instructions from different threads in the same cycle" (p. 381). The notes' smallest example has two cycles (p. 383): in the first T1 issues three instructions and T2 one; in the second T1 is stalled and T2 fills all four slots. In the SMT tab C0 already holds T1 and T2, and C1 holds T2 and T3. It combines ILP, several instructions per thread, with TLP, several threads. The price: the threads compete for caches, functional units and branch predictors, the speed of one thread depends on what its siblings do, and the issue logic must decide every cycle "which thread's instructions win each slot" (p. 381).

Back to the opening puzzle. Coarse-grained gives the three empty cycles of T1's long stall to T2, but leaves an empty cycle at C9 and does nothing about the holes inside T1's cycles: vertical waste falls from 12 to 4, horizontal waste grows from 12 to 15. Fine-grained removes every empty cycle, but each cycle still belongs to one thread and is only as full as that thread's ILP: horizontal waste grows to 19. The same 21 slots, reached in two different ways. Only SMT puts several threads in one cycle, and the 11 extra slots are horizontal waste turned into work: 19 becomes 8. Tullsen, Eggers and Levy put it in one sentence: traditional multithreading "converts much of the vertical waste to horizontal waste, rather than eliminating it."

Coarse- and fine-grained multithreading reassign whole cycles and attack only vertical waste; SMT fills the empty slots inside a cycle and attacks both.

Which stalls does each scheme hide? It follows from the switch rule of section 2 and from who may use a cycle.

SMT on an out-of-order core, and the exam’s ideal CPIs

Why does SMT live on a dynamically scheduled superscalar (lessons 11–18)? Because that core already has the two mechanisms SMT needs. Register renaming gives every instruction in flight a destination nobody else names — the ROB number of lesson 17, or a physical register — so T1's F2 and T2's F2 cannot be confused. And the scheduler already issues whatever is ready, whichever thread it comes from. "The SMT logic is added to the existing wide superscalar design" (p. 383). A VLIW's bundles, by contrast, are fixed by the compiler for one thread.

What SMT adds is short. Hennessy and Patterson list it in one line — a renaming table per thread, separate PCs, and the ability to commit instructions of several threads — and the notes' answer to the February 2025 paper expands it (pp. 576–577):

• One rename map per thread over one shared, larger physical register file, which holds the architectural registers of every thread.
• A thread-ID tag on every instruction in the reservation stations, the ROB and the load/store queues, so that results, commits and exception squashes reach the right thread.
• Thread-aware fetch and issue: several PCs, and a policy that picks the thread to fetch each cycle — round robin, or ICOUNT, which favours the thread with the fewest instructions in the front end (Tullsen's group, 1996) — so that a stalled thread cannot clog the shared queues.
• Per-thread commit and exceptions: a fault squashes only the faulting thread's instructions.

The first commercial SMT, Intel's Hyper-Threading in the Xeon of 2002, sorted the core's resources into three groups (Marr and others, 2002): duplicated, partitioned while two threads run, and shared. Partitioning a buffer guarantees that a stalled thread cannot fill it all, and the halves are "recombined when only one software thread is active". The price was "less than 5% to the relative chip size and maximum power requirements", the gain "up to 30% on common server application benchmarks". The notes give the same order of magnitude: a 2-way SMT core "often achieves 20-30% more throughput", not 2× (p. 383), and a single thread may run slightly slower because it now shares caches and predictors. The gain is largest when one thread stalls on memory while the other computes, or when the two use different units, one integer-heavy and one floating-point-heavy (p. 378); and since the same datapath does more work, the energy per instruction improves (p. 384).

The arithmetic of the three papers

Each of the three official papers asks two numbers for a w-issue SMT core with n threads. Start from a concrete case, a dual-issue core with 4 threads, and draw the ideal: no grey cell anywhere, the slots handed out in turn. In 8 cycles there are 2 × 8 = 16 slots for 4 threads, 4 each, so T1 issues every second cycle. The general rule takes four steps, and a fifth checks it on the papers.

1. Ideal means every one of the w slots is filled in every cycle: the core completes w instructions per cycle.

   \[ \mathrm{IPC}_{ideal} = w \;\Rightarrow\; \mathrm{CPI}_{ideal} = \frac{1}{w} \]

   It depends on the width only. Threads are how the core gets close to it, not a way to lower it.

2. The n threads share the w slots evenly, so each completes w/n instructions per cycle.

   \[ \mathrm{IPC}_{thread} = \frac{w}{n} \]

3. Invert to get the cycles per instruction of one thread.

   \[ \mathrm{CPI}_{thread} = \frac{n}{w} = n \cdot \mathrm{CPI}_{ideal} \]

   Sharing stretches a thread's cycles per instruction: its CPI is a multiple of the core's, never a fraction.

4. A chip of c such cores completes c·w instructions per cycle, while a thread still shares only its own core's slots.

   \[ \mathrm{CPI}_{chip} = \frac{1}{c \cdot w} \] \[ \mathrm{CPI}_{thread} = \frac{n}{w} \ \text{(unchanged)} \]

5. Check on the papers. Dual-issue, 4 threads: 1/2 = 0.5 and 4/2 = 2 (July 2024 quiz, June 2026). Quad-issue, 4 threads: 1/4 = 0.25 and 4/4 = 1 (July 2024, Question 2). Quad-issue, 8 threads: 1/4 = 0.25 and 8/4 = 2 (June 2025). Dual-core, dual-issue, 2 threads per core: 0.5 per core, 1/(2·2) = 0.25 for the chip, 2/2 = 1 per thread (June 2025).

Cores times threads: what lscpu counts, who shares which cache, and the dual-core question

Real chips combine both ideas: several cores, each running several hardware threads. The count is the notes' formula (81), p. 385:

An Intel Core i7 with 8 cores and 2-way SMT has 16 hardware threads; an IBM POWER9 with 24 cores and 4-way SMT has 96 (p. 385). The operating system sees each hardware thread as a logical CPU. The notes' own laptop, a ThinkPad T430, reports it through lscpu; these are the lines that matter:

CPU(s):              8
Model name:          Intel(R) Core(TM) i7-3632QM CPU @ 2.20GHz
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1

A socket is the connector that holds one processor package. One socket × 4 cores × 2 threads gives 8 logical CPUs, so Linux can schedule eight software threads at once. The second thread of each core, however, "doesn't double performance. It just helps keep the core busy when one thread is stalled" (p. 385). The two ways of adding hardware threads are not equivalent (p. 386): more cores add execution resources and help threads that are truly independent and each need compute; more SMT threads per core help when a core has idle slots that one thread's ILP cannot fill.

Threads that share a core also share its caches (p. 386). The L1 is "almost always shared between SMT threads of the same core": simple, nothing duplicated, but the siblings can evict each other's lines — cache thrashing. The L2 is private to each core in most Intel and AMD designs and shared by a cluster of cores in others; the L3 is usually shared by all cores. Two active threads double the working set competing for the L1 and L2, so designers add partitioning of the cache space, quality-of-service mechanisms that keep one thread from starving the other, and replacement policies aware of the thread ID.

The June 2025 paper strings all of this into one question: a single-chip dual-core shared-memory processor, each core a dual-issue superscalar with up to 2 threads. Each core runs SMT. The chip completes 2 × 2 = 4 instructions per cycle, while T1 shares only its own core's two slots with T2:

Inside each thread the instructions are scheduled dynamically — Tomasulo with renaming and a reorder buffer, lessons 11–18 — and the two cores' private caches are kept coherent by a snooping protocol such as MESI, lessons 35–36. The full answer, schedule included, is the second exam question below.

Multithreading is the smallest scale of thread-level parallelism. The same parallelism also runs on many cores sharing one memory, the multiprocessors of lessons 33–36, and on clusters of computers that share no memory at all.