Formula sheet

The cheat boxes of 38 lessons on one page: 360 rows of formulas and rules, each a name and what you would write next to it.

Every box below is the cheat box from the "Key take-aways" of one lesson, copied here unchanged. A row is a name and a formula — CPI, speedup, AMAT, miss rate, code efficiency — or a name and a rule: when an instruction may issue in Tomasulo’s machine, what a cache does on a read miss, how the home directory answers a request. The heading above a box leads to the lesson that explains it with worked examples.

At the exam you may bring one A4 page, front side only, with formulas in 12-point type or larger and no copies of past exercises or slides (the rules are in the exam trainer). The 360 rows here will not fit on one side at that size, so this page is where you choose what goes on yours.

Revise with it like this. Read a name, cover what follows it, write the formula or the rule from memory, then compare. What you rebuild without effort can stay off your A4; what you get wrong twice goes on it. When a row does not match, open the lesson and redo its worked example.

Module 1 · Pipelining and performance

Notes, chapters 1 and 4 · the RISC-V pipeline, hazards, forwarding, the metrics every exercise ends with

Lesson 1 · The assembly line in silicon

Sequential time: $T_{\text{seq}} = n\,k\,T$ — $n$ instructions, $k$ stages, $T$ = stage time
Pipelined time: $T_{\text{pipe}} = (k + n - 1)\,T$; cycles = IC + (k − 1) = IC + 4 for five stages (no stalls)
Speedup: $S(n) = \dfrac{n\,k}{k + n - 1} \to k$ for $n \to \infty$
Clock period: $T_{\text{clk}} \ge \max_i d_i + t_{\text{reg}}$ — slowest stage delay $d_i$ plus register overhead; ceiling = $T_{\text{instr}} / T_{\text{clk}}$
Stages and resources: IF: I-memory, PC + 4 · ID: register read (2 ports) · EX: ALU · MEM: D-memory · WB: register write (1 port)
Where a value is born: ALU result: end of EX · loaded word: end of MEM · PC of a taken branch: MEM (basic pipeline)
Pipeline registers: IF/ID: instruction, PC + 4 · ID/EX: PC + 4, rs1, rs2, imm, rd, control EX/MEM/WB · EX/MEM: ALU result or address, store data, target, rd, control MEM/WB · MEM/WB: memory data or ALU result, rd, control WB
Rule: no stage is skipped: idle stages are traversed, latency is always 5 cycles

Lesson 2 · When the line jams: hazards and forwarding

Stalls without forwarding: $\max(0,\ 3 - d)$, $d$ = distance producer → consumer; without the split-cycle register file $\max(0,\ 4 - d)$
Stalls with forwarding: ALU producer: 0 at any distance; load → operand or address: $\max(0,\ 2 - d)$ (1 at $d = 1$); load → store data: 0 (MEM/MEM)
Paths: EX/EX: EX/MEM → ALU input · MEM/EX: MEM/WB → ALU input · MEM/MEM: MEM/WB → data-memory write input
Forwarding unit: forward from EX/MEM if EX/MEM.RegWrite, EX/MEM.rd ≠ R0, EX/MEM.rd = ID/EX.rs; else from MEM/WB under the same test; newest wins
Hazard detection: stall if ID/EX.MemRead and ID/EX.rd = IF/ID.rs1 or rs2 (a store's data register exempt: MEM/MEM serves it): hold PC and IF/ID, zero the controls into ID/EX
Clock cycles: $\text{cycles} = IC + 4 + \text{stalls}$ = cycle of the last WB; $\text{CPI} = \text{cycles} / IC$
Slots to insert: nops or independent instructions needed = stalls the hardware would insert

Lesson 3 · What “faster” means: the Iron Law, Amdahl and pipeline arithmetic

Performance: $1 / \text{Execution time}$
X is n% faster than Y: $\text{Time}(Y) = (1 + \tfrac{n}{100})\,\text{Time}(X)$
Clock: $f_{CLK} = 1/T_{CLK}$; 500 MHz = 2 ns, 200 MHz = 5 ns, 1 GHz = 1 ns
CPU time: $IC \times CPI \times T_{CLK}$, or $IC \times CPI / f_{CLK}$
Weighted CPI: $\sum_i CPI_i\, F_i$, with $F_i = I_i / IC$ the frequency of class $i$
IPC: $1 / CPI$
MIPS: $f_{CLK} / (CPI \times 10^6)$, or $IC / (\text{time} \times 10^6)$
Amdahl: $\text{Speedup} = 1 / \big((1 - F) + F/S\big)$; $\text{Speedup}_{\max} = 1/(1 - F)$; $F = (1 - 1/\text{Speedup}) / (1 - 1/S)$
5-stage pipeline cycles: $IC + \text{Stall cycles} + 4$; $CPI = \text{cycles} / IC$
Loop, one iteration: $\text{cycles} = m + k + 4$; $CPI_{iter} = (m + k + 4)/m$ ($m$ instructions, $k$ stalls per iteration)
Loop, n iterations: $\text{cycles} = n(m + k) + 4$; $CPI_{AS} = (m + k)/m = 1 + k/m$; $\text{MIPS}_{AS} = f_{CLK}/(CPI_{AS} \times 10^6)$
Ideal and realistic CPI: ideal 1 for single issue ($1/w$ for $w$-issue); realistic $1 + \text{stall cycles per instruction}$
Pipeline speedup: avg exec time unpipelined / pipelined = $CPI_{unp}/CPI_{pipe}$ = depth / (1 + stall cycles per instruction); branches only: $\text{depth}/(1 + b\,p)$

To the lesson list ↑

Module 2 · Branch prediction

Notes, chapter 2 · control hazards, static schemes and the delay slot, history tables, correlating predictors

Lesson 4 · Why the pipeline hates branches: static prediction and the delay slot

Branch penalty: $r - 1$ cycles, $r$ = stage at whose end the PC is written (ID: 1, EX: 2, ME: 3)
CPI with branches: $\text{CPI} = 1 + f_b \cdot \text{penalty} \cdot p_{\text{mis}}$; $f_b$ = branch fraction
Misprediction probability: stall: 1; always NT: $p_T$; always T (BTB hit): $1 - p_T$; BTFNT: $p_T$ of forward branches, $1 - p_T$ of backward ones
Loop of N iterations, branch at the bottom: always NT: $N - 1$ mispredictions; always T and BTFNT: 1 (the exit)
Exit test at the top, N iterations: executed $N + 1$ times: always NT 1 miss, always T $N$
Cycles of a program: $\text{IC} + 4 + \text{stalls}$; per iteration $m + k + 4$, $\text{CPI}_\infty = (m + k)/m$
Delay slot: always executed; from before: no condition; from target: harmless if not taken, copy at the label; from fall-through: harmless if taken; NOP = stall
Exam convention: branch solved in ID, ALU → branch latency 2, one counted delay slot "(delay slot)", no prediction

Lesson 5 · Learning from the past: 1-bit and 2-bit history tables, and the BTB

CPI with branches: $\text{CPI} = \text{CPI}_{\text{ideal}} + f_b (1 - a) P$ — $f_b$ branch fraction, $a$ accuracy, $P$ penalty (1 here)
Misprediction rate: $r = \dfrac{\text{mispredictions}}{\text{executions of the branch}}$, warm-up included; $a = 1 - r$
Executions of a loop branch: bottom-tested (BNE at the end): $N$; top-tested (BEQ exit at the top): $N + 1$
1-bit on a loop of $N$, re-run: 2 misses (exit + re-entry): accuracy $(N - 2) / N$
2-bit on the same loop: 1 miss (exit): $(N - 1) / N$; from SNT add 2 warm-up misses, from WNT add 1
2-bit rule: strong state: one anomaly moves to the weak state, prediction unchanged; weak state: one anomaly flips the prediction
BHT size: $2^k$ entries $\times$ $n$ bits, no tags
BTB entry: tag + predicted target address (+ T/NT bits); only taken branches, written at resolution
BTB cases: predict NT → PC + 4; predict T and hit → PTA, 0 cycles if taken; predict T and miss → PC + 4, then BTA in ID, 1 cycle if taken
Penalty per branch with a BTB: $p_{hit}(1 - p_{ok})P + (1 - p_{hit})\,p_{taken}P$

Lesson 6 · Branches that talk to each other: correlating and two-level predictors

(m, n) predictor: $2^m$ tables (m history bits) × $2^k$ entries (k PC bits) × n bits; storage $2^m \cdot n \cdot 2^k$ bits; the plain 2-bit BHT is (0, 2)
Single-table index: $\text{GHR} \,\Vert\, \text{PC}[k]$: m + k bits, GHR on top
GHR update: shift left, insert 1 (Taken) or 0 (Not Taken) on the right, keep m bits — notes: 01 = last T, penultimate NT
gshare index: $\text{BHR} \oplus \text{PC}[h]$, h bits each, $2^h$ entries
Local two-level size: $2^k h + 2^{h+1}$ bits: $2^k$ histories of h bits plus one PHT of $2^h$ 2-bit counters
Loop exit learnable: local history $h \ge N - 1$ (N iterations, N − 1 taken then not taken)
Misses per loop pass, steady state: 1-bit: 2 (exit + re-entry) · 2-bit and always Taken: 1 (exit) · two-level with h ≥ N − 1: 0
Branch executions: bottom-tested loop: N · top-tested loop: N + 1 (the exit test)
CPI with branches: $\text{CPI}_{\text{ideal}} + f_b (1 - a) P$: branch frequency × misprediction rate × penalty

To the lesson list ↑

Module 3 · Instruction-level parallelism

Notes, chapter 3.1–3.5 · dependences, multi-cycle pipelines and exceptions, multiple issue and the superscalar recipe

Lesson 7 · Three ways instructions collide, and pipelines where EX takes more than a cycle

Dependence table (EX1): true: nearest earlier writer of each source register · anti: every earlier reader of the destination · output: every earlier writer of the destination · SD, BNE: true only · intra-loop only
Two properties to preserve: data flow (each consumer gets the value program order designates) · exception behaviour (same exceptions, no new ones)
Renaming removes: WAR and WAW (names); never RAW (a value), never control
When a hazard is possible: RAW: always · WAR: never in the 5-stage pipeline (reads in ID, in order); with delayed operand reads (scoreboard) · WAW: once writes complete out of order (different latencies), even with in-order issue
RAW cost, back to back: unit of $n$ execution cycles, forwarding at the end: $n - 1$ stalls (ALU 0, load 1, 3-cycle adder 2); H&P call these stalls the "latency"
Latency / initiation interval: cycles to the result / cycles between two issues to the same unit (1 if fully pipelined, the execution time if not)
Exam latency: "LD latency 4": issue 1, start exec 2, write result 6; a consumer starts at write result + 1
Precise exception: all older instructions completed, no younger one has changed the state; restart at the faulting instruction · 5-stage pipeline: taken at WB, oldest first
Dynamic scheduling: issue in order · execute and write result out of order · commit in order (reorder buffer)
Loop-carried dependence: from an instruction of iteration $i$ to one of iteration $i + k$ (through a register like R1, or an array element written in an earlier iteration)

Lesson 8 · Doing more per cycle: superscalar, static vs dynamic scheduling, the limits of ILP

Ideal CPI, IPC: $\mathrm{CPI}_{ideal} = 1/w$, $\mathrm{IPC}_{ideal} = w$ ($w$ = issue width)
Instructions in flight: $w \times \text{depth}$
Real CPI: $\mathrm{CPI}_{ideal} + \text{stalls/instr}$
CPI with branches: $\mathrm{CPI}_{ideal} + f_b\, m\, P$ ($f_b$ branch frequency, $m$ misprediction rate, $P$ penalty)
SMT per-thread CPI: $\text{threads}/w$; core CPI $1/w$
Code efficiency: $\mathrm{IC}/(\#\text{cycles} \times \#\text{issues})$
Amdahl (notes): $1/\big(f + (1-f)/p\big)$, ceiling $1/f$ ($f$ serial fraction, $p$ speedup of the rest)
Amdahl (formula sheet): $1/\big((1-F) + F/S\big)$, ceiling $1/(1-F)$ ($F$ enhanced fraction, $S$ its speedup)
The ladder rule: issue and commit in order; only execution out of order; the width grows

To the lesson list ↑

Module 4 · Dynamic scheduling: scoreboard, Tomasulo, reorder buffer

Notes, chapter 3.6–3.9 and the past papers · the three algorithms the exam tables are built on

Lesson 9 · The chalkboard that beat the pipeline: the scoreboard

Issue (in order): unit not Busy and Result[D] empty; $I_n$ = max of $I_{n-1}+1$, $WB_U+1$, $WB_W+1$ — $U$ previous instruction on the unit, $W$ pending earlier writer of $D$
Read Operands: $R_j = R_k = \text{Yes}$; $RR_n = \max(I_n+1,\ WB_P+1)$ — $P$ producer of each source (no forwarding)
Execute: $E_n = RR_n + L$, $L$ latency of the unit; Time counts down from $L$
Write Result: no row with $F_j$ or $F_k = D$ and flag Yes; $WB_n = \max(E_n+1,\ RR_A+1)$ — $A$ earlier readers of $D$
Rj, Rk: source ready and not yet read: Yes when the producer writes, No at the read
Qj, Qk: the unit that will produce Fj, Fk; copied from Result[S] at issue
Unit Busy: from I through WB inclusive; free for a new issue at WB + 1
CPI: $\text{CPI} = \dfrac{\text{last } WB}{IC}$ — cycle of the last write result over the instruction count

Lesson 10 · 62 cycles, one at a time: the scoreboard example and the exam table

Basic scheme (WAW at Issue, no forwarding): $I_n$ = max of $I_{n-1}+1$, $WB_U+1$, $WB_W+1$; $RR_n = \max(I_n+1,\ WB_P+1)$; $E_n = RR_n + L$; $WB_n = \max(E_n+1,\ RR_A+1)$ — $U$ previous instruction on the unit, $W$ pending earlier writer of the destination, $P$ producer of each source, $A$ earlier readers of the destination
Forwarding: $RR_n = \max(I_n+1,\ WB_P)$: the consumer reads in the producer's write cycle
WAW check at write-back: drop $WB_W+1$ from $I_n$; add $WB_n \ge WB_W+1$ at Write Result (the WAR test stays)
Unit Busy: from I through WB inclusive; a new issue on it at WB + 1; the first free unit of the class is taken
Rj, Rk: ready and not yet read: Yes when the producer writes, No at the read — the WAR test looks for a Yes
CPI: $\text{CPI} = \dfrac{\text{last } WB}{IC}$: 62/6 ≈ 10.3; 25/7 ≈ 3.57; 21/7 = 3.0
Speedup: $\dfrac{\text{cycles}_{\text{basic}}}{\text{cycles}_{\text{opt}}}$ = 25/21 ≈ 1.19 (same IC, same clock)
Critical chain: the longest RAW chain plus its structural waits: LD F2 → FMUL → FDIV = 8 + 1 + 10 + 1 + 1 + 40 + 1 = 62

Lesson 11 · Names, not values: Tomasulo’s architecture

Reservation station: Busy · Op · Vj, Vk (operand values) · Qj, Qk (producer tags, 0 = ready) · A (load/store: immediate, then effective address)
Register status: Qi = tag of the newest pending writer of the register; Qi = 0 → use Vi
Issue: free station of the right type → copy values or tags from the register file; Qi[dest] ← this station
Execute: Qj = Qk = 0 (both operands as values) and the unit is free → compute for the latency
Write result: CDB free → broadcast <tag, value>; every Qj/Qk = tag fills; register written only if Qi = tag; station freed
Store: waits for address and data (either may be a tag) → writes memory; never uses the CDB
CDB capacity: one result per bus per cycle; in the exam the older instruction writes first
Scoreboard vs Tomasulo: stalls on WAR / WAW vs renames; data through the register file vs broadcast with a tag; central vs distributed control; waits for a register vs for a value or tag

Lesson 12 · Issue, execute, write result: the three stages and the exam table

Issue (in order): free RS of the class; $I_n = \max(I_{n-1} + 1,\ W_{\text{RS}} + 1)$ — $W_{\text{RS}}$ the WRITE RESULT that first frees a station of the class (if none is free at $I_{n-1} + 1$); Vj/Vk ← value if Qi = 0 else Qj/Qk ← Qi; Qi[dest] ← this RS
Start exec: $Q_j = Q_k = 0$ and unit free; $S_n$ = the latest of $I_n + 1$, $W_P + 1$, $W_U + 1$ — $P$ each producer, $U$ the unit's last occupant
Write result: $W_n = S_n + L$, $L$ the latency; one CDB per cycle, oldest first, the younger slips by one
Broadcast: ⟨tag, value⟩: every RS with Qj or Qk = tag fills; the register is written only if Qi = tag; the RS and the unit are freed
Store: starts when address and data are ready; $W = S + L$ = end of the memory write; no CDB broadcast, no CDB slot
Hazards column: RAW with I# for F; WAR / WAW with I# "solved by renaming" (optional); Structural (RS, unit, CDB); "issue delayed behind I#" for a row held up by in-order issue
Dependences: true: nearest earlier writer of a source; anti: every earlier reader of the destination; output: every earlier writer of the destination
CPI: $\text{CPI} = \dfrac{\text{last WRITE RESULT}}{IC}$ — the last write cycle over the instructions of one iteration

Lesson 13 · Tomasulo cycle by cycle, and what it fixes compared with the scoreboard

Start of execution: $S = \max(I + 1,\ W_{\text{prod}} + 1,\ U)$ — $I$ issue, $W_{\text{prod}}$ write of each pending producer, $U$ first cycle the unit is free (busy through the write cycle of its instruction)
Write result: $W = S + L$, $L$ the latency; execution occupies $S \dots S + L - 1$
Single CDB: one write per cycle; two ready → the older writes, the younger slips by one ("Structural on the CDB")
Register-file rule: a broadcast ⟨tag, value⟩ is written into F only if Qi[F] = tag; a station copies it into Vj / Vk if Qj / Qk = tag
Issue rule: in order, one per cycle, only into a free station; a station is busy from issue through write result; no station free → "Structural", everything behind waits
Stores: issue to a LOAD/STORE station; write result = end of the memory write; never on the CDB
CPI: $\text{CPI} = W_{\text{last}} / N$ (last WRITE RESULT over the instructions of one iteration)
The classic run: load 2, add 2, mult 10, div 40: one load unit 1-2-4 · 2-5-7 · 3-8-18 · 4-8-10 · 5-19-59 · 6-11-13 (CPI 59/6); two load units: LD F2 2-3-5, finish 57; scoreboard: 62 cycles, all issued at 13, FADD written at 22
What vanishes, what stays: WAR / WAW → "solved by renaming"; issue stalls on busy units → waits in stations; RAW → still waits (producer's write + 1); the critical chain → unchanged

Lesson 14 · Tomasulo under pressure: structural squeezes and CDB fights

Issue: in order, one per cycle, needs a free RS of the class; RS busy from ISSUE through WRITE RESULT inclusive, reusable the next cycle
Start Exec: the latest of ISSUE + 1, the producer's WRITE RESULT + 1, and the cycle after the unit's previous WRITE RESULT (a unit is busy through the WRITE RESULT of its instruction)
Write Result: $\text{START EXEC} + \text{latency}$, +1 per older result taking the single CDB in that cycle (oldest first); a store's write is its memory write
Tag: Qj / Qk = the RS of the producer; the CDB carries $\langle \text{tag}, \text{value} \rangle$; readers copy values at issue, so WAR and WAW never stall
CPI: $\dfrac{\text{last WRITE RESULT}}{\text{IC}}$: 22/8 = 2.75 (Feb 2025), 22/10 = 2.2 (midterm 2025), 22/8 = 2.75 (June 2025)
Hazards column: None · Structural (RSx, RSy busy, cycles a–b) · Structural (FPU1 busy until c) · Structural (CDB at c: I# first) · RAW with I# (Fx) · WAR/WAW with I# (Fx): renamed

Lesson 15 · Same names, no conflicts: unrolling, renaming and scheduling

Trip count: N = distance the index travels / step (R1: 0 → 400 by 4: N = 100; 80 → 0 by 8: N = 10)
Unrolled by u: $N/u$ iterations of $u\,w + o$ instructions, $N/u$ branches (w useful, o overhead instructions per original iteration); if u does not divide N: N mod u remainder iterations of the original body
Instructions executed: $IC_u = N w + N o / u$
Saving: $\dfrac{o\,(1 - 1/u)}{w + o}$, limit $\dfrac{o}{w + o}$ (midterm loop: 21.43 %, 32.14 %, limit 42.9 %)
Extra registers (static renaming): $(u - 1)\,\rho$, ρ = registers one copy writes (midterm: F2, F4, F6, ρ = 3; section 1: F0, F4, ρ = 2 — a register that is only read, like the scalar F2 there, is not renamed)
Overhead per element: $o / u$ (3 → 1.5 → 0.75)
Displacement below the index update: new = old − ΔR1 (ΔR1 = −32: −24 → +8, −16 → +16)
H&P latencies (stall cycles): LD → FP op 1 · LD → SD 0 · FP op → FP op 3 · FP op → SD 2 · SUBI → BNE 1
Loop on a pipeline: m instructions + k stalls per iteration: $CPI_{AS} = (m + k)/m$; cycles per element = (m + k)/u — 9 original, 7 scheduled, 6.75 unrolled, 3.5 unrolled + renamed + scheduled
Schedule order: loads first, FP operations next, stores last; at least one instruction between the index update and the branch
Table 20: Tomasulo: renaming yes (tags), scheduling yes (operand availability), unrolling no — it overlaps iterations

Lesson 16 · Tomasulo meets a loop: eighteen cycles of renaming in action

Issue: in program order, one per cycle, into a free station or buffer of the class; a missing operand becomes a tag (Qj, Qk, a store's FU), never a stall; no free station → the instruction and all behind it wait (Structural)
Start of execution: $S = \max(I + 1,\ W_{\text{prod}} + 1,\ U)$ — $I$ issue, $W_{\text{prod}}$ write cycle of the last producer, $U$ first cycle the unit is free
Write result: papers: $W = S + L$, $L$ the latency; notes: Exec Comp = $S + L - 1$, Write Res = Exec Comp + 1; one cycle later for every older result that takes the CDB first
CDB capture: one ⟨tag, value⟩ per cycle, oldest first; every entry whose Qj, Qk or FU equals the tag copies the value
Register write: F ← value only if F's status equals the tag (its youngest writer); otherwise the broadcast is ignored
Station lifetime: busy from ISSUE through WRITE RESULT; papers: free the next cycle; the notes refill it in the same cycle
Store: START EXEC = data's WRITE RESULT + 1; papers: WRITE RESULT = START EXEC + LDU latency, no CDB slot; notes: memory written the cycle after execution
Time field: execution cycles still to run after the current one (4, 3, 2, 1, 0 for FMUL)
CPI (papers): $\text{CPI} = W_{\text{last}} / N$: last WRITE RESULT over the instructions of one iteration; this loop: 15 / 5 = 3.0

Lesson 17 · Guess now, pay later: speculation, precise exceptions and the reorder buffer

Commit condition: at the head AND Ready = Yes AND Spec = No → write the register (or memory for a store), free the entry, head ← head + 1 (mod N)
Issue: needs a free reservation station of the right class AND a free ROB entry; the entry is the tail, tail ← tail + 1 (mod N); the destination register is mapped to this ROB#; Spec = Yes if an older branch is unresolved
Operand at issue: no mapping → value from the register file; mapped and ready → value from ROB[h]; mapped and not ready → tag h, wait for the CDB (the "RAW with I#" of the table)
Write Result: CDB carries (ROB#, value) to the waiting stations and to the entry: Ready = Yes; the station is freed; the register file is not touched
Full / empty: head = tail and busy → full, issue stalls; head = tail and not busy → empty
Misprediction: free every entry younger than the branch; tail ← branch + 1; rename table back to the older in-flight producer or "–"; fetch restarts; the branch commits normally; nothing to undo in the registers
Precise exception: stop at one instruction, all older ones committed, no younger one has changed the state; recorded in the entry, taken at the head; on a flushed path, discarded
Exam columns: ROB# | Instruction | Dest. | Res. Alloc. | Ready/Status | Spec.; status "No, issued" / "No, exec.(*)" / "Yes"; Res. Alloc. Load1…, FP1…, Int1… (branches too), "–" for a store; Rename Table Reg # → ROB # or "–"

Lesson 18 · The speculative Tomasulo algorithm, stage by stage — and the ROB exam table

Issue condition: free RS of the class AND free ROB entry; else stall (structural). Entry at the tail: Busy = Yes, Ready = No, Spec = Yes if an older branch is unresolved; rename[Dest] ← ROB#; tail + 1
Operand at issue: no mapping → register file; mapped to $h$, Ready → ROB[$h$].Value; mapped, not Ready → tag $h$, wait for the CDB
Execute: all operands in the RS (RAW served by the CDB); store: base register only; load: no earlier store with an unknown or equal address; branch: resolve, compare with the prediction
Write result: CDB ⟨ROB#, value⟩ → waiting RSs and ROB[#].Value, Ready = Yes; RS freed; register file untouched
Commit: head only, Ready = Yes, Spec = No → register file (or memory for a store); entry freed, head + 1; rename cleared only if it still points here
Misprediction: flush entries after the branch; tail ← branch + 1; squash their RSs / load buffers; rename ← older producer in flight, else "–"; fetch at the correct target
Full / empty: head = tail and busy → full (issue stalls); head = tail and not busy → empty
Res. Alloc.: lowest free Load$i$ / FP$i$ / Int$i$ of the class; branch → Int; store → "–"; status words: No, issued / No, exec.(*) / Yes
Trip count, unrolling: $N = (R2 - R1_0)/\Delta R1$; unrolled by $u$: $N/u$ iterations of $u\,b + 2$ instructions ($b$ body instructions, 2 overhead)

To the lesson list ↑

Module 5 · VLIW and static scheduling

Notes, chapter 5 and the past papers · bundles, dependence graphs, list scheduling, unrolling, software pipelining, trace scheduling

Lesson 19 · The compiler takes the wheel: what a VLIW is

Code efficiency: $ IC / (\#\text{cycles} \times \#\text{issues}) $: IC operations scheduled, cycles including the delay slot, issues = slots per bundle (LOOP1: 5 / 30 = 0.17)
Other VLIW table metrics: critical path = cycles of one iteration, delay slot included; CPI = cycles / IC; FP ops per cycle = FP operations / cycles (LOOP1: 10, 2, 0.1)
Register-file ports, k-issue: 2k read + k write (4-issue: 8 + 4)
Registers held by results in flight: results started per cycle × latency, summed over the kinds of unit (2 × 5 = 10)
RAW placement: issue(consumer) ≥ issue(producer) + L, with L: Memory 3, FP 3, Integer 1, Integer → branch 2
WAR placement: issue(writer) ≥ issue(last reader): the same cycle is allowed
WAW placement: the later result lands after the earlier one: issue(2nd) + L(2nd) > issue(1st) + L(1st)
Branch: at most one per bundle, last in the iteration; the delay slot counts as a cycle
Who handles what: compiler: RAW, WAR, WAW, structural; hardware: stall on a cache miss, flush on a misprediction

Lesson 20 · Graphs, critical paths and the exam table: list scheduling

Longest path (eq. 65): $\text{LP}(i) = \max_{p} \text{LP}(p) + \text{Lat}(i)$, $p$ = predecessors of $i$, Lat = latency; critical path $\text{CP} = \max_i \text{LP}(i)$
ASAP cycle: $t(i) = \max_p [\,t(p) + \ell(p \to i)\,]$, $t = 1$ for a source; $\ell$ = latency on the edge, 0 for WAR
Priority: $\text{prio}(i) = \text{Lat}(i) + \max_s \text{prio}(s)$, $s$ = successors of $i$: longest path to the end; exam: $\max_s[\ell(i \to s) + \text{prio}(s)]$, BNE = 2
Exam latencies: after LD 3, after FP 3, after integer 1, integer → BNE 2; WAR writer in the same cycle as its last reader or later
Iteration length: cycle of the BNE + 1 (delay slot) = "critical path for a single iteration"
CPI: $\text{CPI} = \#\text{cycles} / IC$, IC = instructions of one iteration
FP ops per cycle: $\#\text{FP operations} / \#\text{cycles}$
Code efficiency: $IC / (\#\text{cycles} \times \#\text{issues})$, issues = issue width
Bound: $\text{CP} \le$ list-schedule length; units close the gap, latencies move CP

Lesson 21 · Same loop, three shapes: unrolling, software pipelining and betting on the hot path

Unrolling by u: $N/u$ iterations of $u\,w + o$ instructions (N trip count, w useful, o overhead instructions per original iteration); $(u - 1)\,\rho$ extra registers, ρ = registers one copy writes
Execution time per iteration (66): cycles of the unrolled body / original iterations it covers
Code efficiency (67): $IC / (\#\text{cycles} \times \#\text{issues})$: instructions over issue slots, delay slot counted
CPI of one iteration (VLIW): cycles including the delay slot (the papers' "critical path for a single iteration") / instructions of the iteration; speed-up in CPI = $CPI_1 / CPI_2$
FP ops per cycle: FP operations of the iteration / cycles
Delayed-branch pipeline: LD → FADD 1 stall · FADD → SD 2 · SUBI → BNE 1 · one delay slot
Software-pipelined loop: body = SD x[i] at 0(R1) · FADD x[i+1] · LD x[i+2] at 2 × stride; prologue LD, FADD, LD; epilogue SD, FADD, SD at stride; body runs n − 2 times
Throughput: one element per body: every II cycles, $T \approx n \cdot II$
Compensation code: below a branch → copy on the exit path · above a join → copy on the entering path · above a branch → free only if dead elsewhere, no store, no exception
Superblock / if-conversion: one entry via tail duplication, repairs at exits only · predication pays for short, balanced, unpredictable branches

To the lesson list ↑

Module 6 · Memory hierarchy

Notes, chapter 6 and 4.4 · caches, the AMAT formulas of the formula sheet, nineteen optimisations, virtual memory

Lesson 22 · The memory wall and the illusion of a fast, big memory

Number of blocks: $\text{Cache size} / \text{Block size}$, both in the same unit
Hit rate, miss rate: $HR = \#\text{hits} / \#\text{accesses}$, $MR = \#\text{misses} / \#\text{accesses}$, $HR + MR = 1$; fractions, 5% = 0.05
Miss time: $MT = HT + MP$: Hit Time + Miss Penalty
AMAT, general form: $HR \times HT + MR \times MT$
AMAT: $HT + MR \times MP$: Hit Time + Miss Rate × Miss Penalty
Access shares: $\%\text{Instr} = 1/(1 + d)$, $\%\text{Data} = d/(1 + d)$; $d$ = loads/stores per instruction
AMAT Harvard (split L1): $\%\text{Instr} \times (HT + MR_{I\$} \times MP)$ + $\%\text{Data} \times (HT + MR_{D\$} \times MP)$
AMAT unified, one port: $HT + MR_U \times MP + \%\text{Data} \times 1$: every data access waits one cycle for the port
Miss rate of a split L1: $\%\text{Instr} \times MR_{I\$}$ + $\%\text{Data} \times MR_{D\$}$

Lesson 23 · Anatomy of a cache: the four questions and the exam cache table

Lesson 24 · Misses, penalties and the design space: the second level, the 3 C’s, from misses to seconds

Symbols: HT hit time, MR miss rate (a fraction: 5% = 0.05), MP miss penalty, in cycles; $CPI_{exec}$ CPI with every access a hit; IC instruction count; $T_{CLK}$ clock period
AMAT, two levels (formula sheet: Hierarchical): $HT_{L1} + MR_{L1} \times MP_{L1}$, with $MP_{L1} = HT_{L2} + MR_{L2} \times MP_{L2}$; $MR_{L2}$ local
AMAT, expanded: $HT_{L1} + MR_{L1}\, HT_{L2}$ + $MR_{L1}\, MR_{L2}\, MP_{L2}$
Local miss rate: misses of a level / accesses to that level; $MR_{L2}$ = L2 misses / L1 misses
Global miss rate: misses of a level / all CPU accesses; for L2: $MR_{L1} \times MR_{L2}$
CPU time with misses: $IC \times CPI \times T_{CLK}$, with CPI = $CPI_{exec} + MAPI \times MR \times MP$
Misses per instruction: $MAPI \times MR$; MAPI = memory accesses per instruction
Ideal cache · no cache: CPI = $CPI_{exec}$ · CPI = $CPI_{exec} + MAPI \times MP$ (miss rate 1)
With pipeline stalls: CPI = $CPI_{exec}$ + stalls per instruction + $MAPI \times MR \times MP$
Stall cycles per instruction, L1 + L2: $MAPI \times MR_{L1} \times HT_{L2}$ + $MAPI \times MR_{L1} MR_{L2} \times MP_{L2}$
Check: stall cycles per instruction = $MAPI \times (\text{AMAT} - HT_{L1})$
3 C's: compulsory = misses of an infinite cache; capacity = misses of a fully associative cache of the same size − compulsory; conflict = misses of the real cache − fully associative misses

Lesson 25 · Fewer misses: size, blocks, ways, victims, prediction, prefetching and the compiler

AMAT: $\text{AMAT} = \text{HT} + \text{MR} \times \text{MP}$ — HT hit time and MP miss penalty in cycles, MR miss rate; a knob pays only if its ΔMR × MP outweighs what it adds to HT or MP
Miss penalty vs block size: MP(B) = L + B / w: latency L plus B bytes at w bytes per cycle (textbook: 80 + 2 · B/16 = 82, 84, 88, 96, 112 for 16 … 256 bytes)
Blocks and sets: blocks = C / B; sets = C / (B × n) for a cache of C bytes, blocks of B bytes, n ways
Block-size optimum: B(AMAT-best) ≤ B(miss-rate-best), because MP grows with B
2:1 cache rule: MR of a direct-mapped cache of size N ≈ MR of a 2-way cache of size N/2; 8-way ≈ fully associative
Associativity price (textbook example): HT × 1.36 / 1.44 / 1.52 for 2 / 4 / 8 ways; compare AMAT, not MR
Way predictor table: bits = sets × ⌈log₂ n⌉ (1024 sets, 4-way: 2048 bits = 256 B); rewritten on every wrong guess, misses included
Way prediction hit time: $\text{HT}_{\text{eff}} = \text{HT} + (1 - p)\, t_m$ — $p$ prediction accuracy, $t_m$ extra cycles of a wrong guess (hits only)
Prefetch distance: d = ⌈miss latency / cycles per iteration⌉ iterations ahead (100 / 12 → 9)
Blocking, matrix multiply: N × N matrices, B × B tiles: words moved 2N³ + N² → 2N³/B + N² if the tile plus two strips of B words fit (≈ B² + 2B words)
Miss each knob removes: size → capacity; block → compulsory; ways, victim cache, pseudo-associativity → conflict; prefetching → compulsory (+ some capacity); compiler transformations → capacity, conflict; way prediction → none (hit time)

Lesson 26 · Cheaper misses: reads first, the critical word, caches that do not block, the second level

Two-level AMAT (A4 sheet): AMAT = L1 Hit Time + L1 Miss Rate × (L2 Hit Time + L2 Miss Rate × L2 Miss Penalty), L2 Miss Rate local
L1 miss penalty with an L2: $MP_{L1} = HT_{L2} + MR_{L2} \times MP_{L2}$: L2 hit time, local L2 miss rate, L2 miss penalty (the trip to memory)
Global miss rate of L2: $MR_{L1} \times MR_{L2}$: the fraction of all accesses that reach memory
Whole-block miss: $MP = L + n$: $L$ cycles of latency, then $n$ words, one per cycle
Early restart: $MP = L + k + 1$, word $k$ counted from 0
Critical word first: $MP = L + 1$
Read miss, write-through: compare with the write buffer: match → data from the buffer; no match → read before the buffered writes
Read miss, dirty victim: victim → write buffer; fetch the new block first; write the victim back afterwards
Merging write buffer: one entry and one transaction per block; full mask → full-block write, partial → byte-enabled write or read-merge-write
Non-blocking cache: hit under miss: one outstanding miss; miss under miss: one MSHR per outstanding miss

Lesson 27 · Virtual memory in one lesson, and VIPT: start the cache before the TLB answers

Symbols: P page size, C cache size, A associativity (ways), B block size, S number of sets; VPN virtual page number, PFN physical frame number
Virtual address: VA = VPN | page offset; page offset = $\log_2 P$ bits (12 for 4 KB), VPN = the rest
Physical address: PA = PFN | page offset, i.e. $\text{PFN} \times P + \text{offset}$; PT[VPN] = (PFN, valid, dirty, use, protection)
TLB hit / miss / page fault: hit: PFN in about 1 cycle; miss: page walk, tens of cycles, TLB refilled; invalid entry: page fault, the OS loads the page from the disk, millions of cycles
TLB reach: entries × page size (64 × 4 KB = 256 KB)
Hit time, physically indexed: $T_{\text{TLB}} + T_{\text{read}} + T_{\text{cmp}}$: TLB lookup, then index and read the set, then compare the tags
Hit time, VIPT: $\max(T_{\text{TLB}}, T_{\text{read}}) + T_{\text{cmp}}$: TLB and set read in parallel
AMAT: AMAT = Hit Time + Miss Rate × Miss Penalty: VIPT lowers the hit time only
Sets: $S = C / (A \times B)$; index $i = \log_2 S$, block offset $o = \log_2 B$
VIPT size law (80): $C / A \le P$, equivalently $i + o \le \log_2 P$
Bits taken from the VPN: $k = i + o - \log_2 P$; an alias may sit in $2^k$ sets
Largest cache, fewest ways: $C_{\max} = A \times P$, $A_{\min} = C / P$
PIPT · VIVT · VIPT: index and tag from PA (L2, L3) · both from VA (synonyms, homonyms) · index from VA page offset, tag from PA (L1)

Lesson 28 · Hit time is the critical path: small L1, pipelined writes, and the nineteen-technique scorecard

AMAT: Hit Time + Miss Rate × Miss Penalty; every access pays the hit time, a miss pays both
Small L1 against big L1 (same MP): small wins iff $(MR_s - MR_b)\,MP \lt HT_b - HT_s$
Break-even miss penalty: $MP^{*} = \frac{HT_b - HT_s}{MR_s - MR_b}$; the small L1 wins below it
Break-even miss rate: $MR_s^{*} = MR_b + \frac{HT_b - HT_s}{MP}$
L1 too slow for one cycle: stretch $T_{CLK}$ ($f_{CLK}$ down, every instruction slower) or add a stage ($f_{CLK}$ kept, CPI up: load-use stalls; for the I-cache also a larger branch penalty)
N writes, k-stage write path: kN cycles unpipelined; k + N − 1 pipelined; latency k either way
Read hit against write hit: read: tag and data in parallel, drop on mismatch; write: tag check first, then write
Pipelined-write hazard: a load checks the delayed-write buffer; on an address match it takes the data from there
Small sub-blocks, write-through: write word + tag at once; match: done (set valid); mismatch: new tag, only this word valid; never with write-back
Sorting rule: how many misses → miss rate; what one miss costs → miss penalty; what every access costs → hit time

To the lesson list ↑

Module 7 · Threads, vectors and GPUs

Notes, chapters 7–9 · multithreading, SIMD and vector machines, VMIPS and convoys, GPUs, tensor cores and NPUs

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

Slot utilisation: $U = \text{filled} / (C \cdot w)$: the code efficiency of the formula sheet on issue slots ($C$ cycles, $w$ issue width)
CPI of a grid: core $C/\text{filled}$; thread $i$: $C / (\text{slots of } T_i)$
Vertical waste: $w \times$ cycles with no issue
Horizontal waste: $C\,w - \text{filled} - \text{vertical}$
Ideal CPI (core): $1/w$
Ideal per-thread CPI: $n/w$ ($n$ threads sharing the core)
Ideal chip CPI: $1/(c \cdot w)$ ($c$ cores); per thread still $n/w$
Hardware threads: sockets × cores per socket × threads per core = logical CPUs
Switch pays when: $S \lt L$; cycles hidden $= \max(0, L - S)$
The three schemes: coarse: one thread until a long stall; fine: one thread per cycle, round robin; SMT: several threads per cycle

Lesson 30 · Why Cray threw away the cache: Flynn, SIMD and the vector idea

Lesson 31 · VMIPS and the art of counting convoys: chaining, lanes, lengths, masks and banks

Chime model (one lane): $T \approx m \times \mathrm{VL}$: m convoys, VL elements per register, one element per cycle, start-up ignored
Convoy rules: one instruction per unit per convoy (the load/store unit included); a RAW inside a convoy only with chaining; an independent instruction may join an earlier convoy (say so under the table)
Convoy floor: m ≥ instructions of the busiest unit (loads + stores on the one load/store unit); without chaining also m ≥ the longest RAW chain
Lanes: $T \approx m \times \lceil \mathrm{VL}/L \rceil$; element i in lane $i \bmod L$
Vector length: $0 \le \mathrm{VLR} \le \mathrm{MVL}$
Strip mining (84): $\lceil n/\mathrm{MVL} \rceil$ strips: $\lfloor n/\mathrm{MVL} \rfloor$ full + one of $n \bmod \mathrm{MVL}$
Bank of a word (85): (address / word size) mod #banks
Banks visited (86): #banks / gcd(stride, #banks); stall iff this is less than the bank busy time
Strided load time (H&P): no conflict: latency + n; every access in one bank: latency + 1 + busy time × (n − 1)

Lesson 32 · SIMD today: packed extensions, GPUs, tensor cores and NPUs

Packed-SIMD loop: $\lfloor n/W \rfloor$ SIMD adds $+\ (n \bmod W)$ scalar adds; $W$ = elements per register
Vector loop: $\lceil n/\mathrm{MVL} \rceil$ strips; one instruction takes $\lceil \mathrm{VL}/L \rceil$ cycles on $L$ lanes
GP-GPU warp: 32 threads = one SIMD instruction (VL = 32), each thread with private registers; host and device: separate address spaces
Warps to hide latency: $N_{warps} \approx 1 + t_{wait}/r$; $t_{wait}$ = wait in cycles, $r$ = instructions between stalls
Tensor core (Volta): $D = A \times B + C$, 4 × 4, FP16 in, FP16/FP32 out, 64 FMAs per clock
Roofline: $P_{att} = \min(P_{peak},\ BW \times AI)$; $AI$ = flops per DRAM byte
Intensities: DAXPY: $2/24 = 1/12$; $n \times n$ matrix product (FP64): $n/12$
TPU v1 peak: $2 \times 65\,536 \times 700$ MHz $\approx$ 92 TOPS (256 × 256 8-bit MACs)
Systolic stream: $B$ inputs through a $K \times N$ array: $B + K + N - 2$ cycles

To the lesson list ↑

Module 8 · Multiprocessors and cache coherence

Notes, chapter 10 and the past papers · interconnects, shared vs distributed memory, snooping MSI / MESI, directory protocols

Lesson 33 · One machine, many brains: multiprocessors, buses and topologies

Total network bandwidth: $\text{Total BW} = M \times b$, with $M$ links of bandwidth $b$ each
Bisection bandwidth: the minimum, over all cuts into two halves of $P/2$ nodes, of the bandwidth of the links that cross the cut
Single bus: total $b$, bisection $b$
Ring: total $P\,b$, bisection $2b$, diameter $P/2$, degree 2
2-D mesh, $N = \sqrt{P}$: total $2N(N-1)\,b$, bisection $N\,b$, diameter $2(N-1)$
Hypercube, $P = 2^N$: total $(NP/2)\,b$, bisection $(P/2)\,b = 2^{N-1} b$, diameter and degree $N$
Fully connected: total $P(P-1)/2 \cdot b$, bisection $(P/2)^2\,b$, degree $P - 1$
2-D torus: total $2P\,b$, bisection $2N\,b$
Crossbar switch: $P$ links, $P^2$ crosspoints, bisection $(P/2)\,b$
Bus ceiling: $P_{\max} \approx 1/d$, $d$ = share of the bus one processor uses alone
Amdahl, $P$ processors: $\text{Speedup} = 1 / \big((1-F) + F/P\big)$, at most $1/(1-F)$
CPI with remote accesses: $CPI = CPI_{\text{base}} + r \cdot t_{\text{remote}} / T_{CLK}$, $r$ = remote references per instruction

Lesson 34 · Where does the memory live? UMA, NUMA, DSM, clusters and programming models

Shared address space: one logical memory: any processor loads/stores any address; implicit communication (threads, OpenMP, Pthreads)
Private address spaces: one space per processor, the same number names different cells; explicit send/receive (MPI)
UMA = SMP: one centralized memory, same latency and bandwidth for every processor; snooping; about 32 processors at most (contention)
NUMA = DSM = cc-NUMA: node = processor(s) + caches + local memory; one global address space; local fast, remote slow; directory coherence
The four cells: shared + centralized: SMP · shared + distributed: DSM · private + centralized: MPI on one box · private + distributed: cluster
Home node, local node: home: the node whose memory holds the address — with 4 KiB per node, the top hex digit (0x2200 → N2); local: the node that issues the access
Average miss latency: $t = f\,t_{loc} + (1-f)\,t_{rem}$: $f$ = fraction of the misses homed in the local node, $t_{loc}$ and $t_{rem}$ = latency of a local and of a remote miss
CPI with memory misses: $CPI = CPI_{ideal} + m \times t \times f_{CLK}$: $CPI_{ideal}$ = CPI when every reference hits, $m$ = misses per instruction, $t \times f_{CLK}$ = the average miss latency in clock cycles
Programming models: shared memory (loads/stores + locks) · message passing (send/receive + collectives) · SPMD (same program, own slice; compute → barrier → next phase)

Lesson 35 · The day the caches disagreed: coherence, snooping and the MSI machine

Coherent memory: (1) a processor reads back its own last write; (2) a read after another processor's write returns it, given enough time and no other write; (3) writes to one location are seen in the same order by all
Coherence vs consistency: coherence: one location, which value; consistency: order and timing of writes across locations (sequential consistency vs relaxed)
Write-invalidate: first write → Invalidate on the bus, other copies Invalid, later writes silent; a later reader misses and gets the data from the owner
Write-update: every write broadcast to all copies (and memory); readers hit; one bus transaction per write
Traffic per round, w writes then one read: invalidate: 2 transactions (Invalidate + Read Miss); update: w
Snooping: bus = broadcast medium + single global order; every controller checks every transaction; limits: bandwidth, fan-out, serialization; 2–8 CPUs
Duplicate snoop tags: tag + state, no data; snoops checked every cycle without stalling the processor's lookups
MSI states: I: valid 0 · S: valid 1, dirty 0, clean, may be shared · M: valid 1, dirty 1, only copy
MSI, CPU side: I —PrRd / Read Miss→ S · I —PrWr / Write Miss→ M · S —PrWr / Invalidate→ M · hits silent
MSI, bus side: S —Read Miss→ S · S —Write Miss or Invalidate→ I · M —Read Miss / write-back→ S · M —Write Miss / write-back→ I
Replacement: M → I with write-back · S → I silently · then the new block enters through I
Memory up to date?: No exactly while some cache holds the block in M; write-back on M → S, M → I (snooped Write Miss) and M → I (replacement)

Lesson 36 · The E in MESI, and the exam table

MESI states: M: only copy, dirty, memory stale · E: only copy, clean · S: clean, maybe in other caches · I: not valid
Read miss: Read Miss on the bus; → E if no other cache holds the block (shared line low), else → S; an E holder → S; an M holder writes back, → S
Write miss: one Write Miss (fetch and invalidate) → M directly; every other copy → I; an M holder writes back first
Write hit: E → M, no bus · S → Invalidate on the bus, other copies → I, → M · M → M
Replacement (one block per cache): M → write-back, then I · E or S → silent; the other sharers stay S (no S → E)
Write-back happens: only from M: replacement, snooped Read Miss (→ S), snooped Write Miss (→ I)
Memory at bl. b up to date?: No exactly while some cache holds b in M; Yes otherwise
Cost of E: a shared line on the bus; the 4 states still fit in 2 bits per line

Lesson 37 · The librarian: directory-based protocols, roles and messages

Directory entry: one per memory block, at the block's home node (in its memory controller): State | Sharer Bits (+ owner)
Directory states: Uncached: no cached copy, memory fresh · Shared: one or more read-only copies, memory fresh · Modified: one owner with a dirty copy, memory stale
Sharer bits: one bit per node, N0 N1 N2 N3 left to right; 1 = that cache holds a copy; Uncached 0000, Shared one or more 1s, Modified exactly one 1 = the owner
Cache states: Invalid · Shared · Modified (never "Uncached")
Home node: its memory holds the block, fixed by the physical address; keeps the entry; every request passes through it
Local / remote node: local: issues the request · remote: holds a cached copy, Shared or Modified (the owner)
Local → home: Read Miss (P, A) · Write Miss (P, A) · Invalidate (A) = write hit on a Shared copy
Home → local: Data Value Reply (D), for every Read Miss and Write Miss
Home → remote: Invalidate (A): Shared → Invalid · Fetch (A): owner Modified → Shared · Fetch/Invalidate (A): owner Modified → Invalid
Remote → home: Data Write-Back (A, D): reply to Fetch or Fetch/Invalidate, or eviction of a Modified block; Shared copies send nothing
Directory overhead: $(P + 2)/(8B)$: $P$ nodes, 2 state bits, $B$ bytes per block; 64 nodes, 64 B → 12.9 %

Lesson 38 · Four nodes, one block: directory walkthroughs and the exam exercise

Roles: home: holds the block in MM and its entry (fixed by the address) · local: the requester · remote: any other node whose bit is 1 (or the owner), the home's own cache included
Read Miss, Uncached or Shared: L → H Read Miss; H → L Data Value Reply from memory; bits + L; state Shared
Write Miss, Uncached or Shared: L → H Write Miss; H → each sharer Invalidate; H → L Data Value Reply; state Modified, bits = L only; memory stale
Write Hit on Shared: L → H Invalidate (request); H → each other sharer Invalidate; no data; state Modified, bits = L only
Read Miss, Modified: L → H Read Miss; H → owner Fetch; owner → H Data Write-Back (owner Modified → Shared, memory up to date); H → L Data Value Reply; state Shared, bits = owner + L
Write Miss, Modified: L → H Write Miss; H → owner Fetch/Invalidate; owner → H Data Write-Back (owner Modified → Invalid); H → L Data Value Reply; state Modified, bits = L only
Evictions: owner: owner → H Data Write-Back, entry Uncached | 0000, memory fresh · clean copy: no message, its bit stays (harmless)
Remote → home: only Data Write-Back; clean sharers send nothing
Message count: 2 (memory answers) · 2 + k (write miss, k sharers) · 1 + k (write hit) · 4 (owner asked) · 1 (owner evicts)
Memory up to date?: Uncached or Shared: yes · Modified: no
States: cache: Invalid / Shared / Modified · directory: Uncached / Shared / Modified · sharer bits N0 N1 N2 N3, one bit in Modified = the owner

To the lesson list ↑