Exercises — Simultaneous multithreading (SMT - hyperthreading)

What we do: divide the busy units by the total units. Why: utilization is the fraction of the $N$ units in use, and IPC already tells us the average number busy. $\text{Utilization}=\frac{\text{IPC}}{N}=\frac{1.5}{4}=0.375=37.5\%$ Look at figure s01, left panel: on average only $1.5$ of $4$ lanes are filled — the rest are the hollow, wasted boxes.

Rule: duplicate what is cheap and per-thread state (a few registers), share what is big and expensive (the compute machinery).

• (a) Program Counter — duplicated (each thread needs its own "where am I" pointer).
• (b) ALUs — shared (this is the whole point: fill their idle slots).
• (c) L1 cache — shared (big SRAM, too costly to copy).
• (d) architectural register file — duplicated (each thread's variables must survive independently).

Throughput. SMT fills idle execution slots with a second thread, so more total work finishes per second. It does not make any single task faster — in fact one thread often slows slightly from contention.

$T=\frac{M}{\text{IPC}}=\frac{1000}{1.5}=666.\overline{6}\text{cycles}\approx 667$ Why divide: rate is instructions per cycle; to get cycles you flip it — cycles per instruction $\times$ instructions.

Throughput (rates add — same cycle, same units): ${\text{IPC}}_{\text{total}}=1.2+1.2=2.4$ Utilization: $\frac{2.4}{4}=0.60=60\%$ Compare to the single-thread $37.5\%$ from Ex 1.1 — the second thread coloured in many previously-hollow boxes (figure s01, right panel).

Old work-rate: one thread at $1.5$ IPC $\Rightarrow 1.5$ instructions/cycle. New work-rate: two threads $\Rightarrow 2.4$ instructions/cycle. $\text{Speedup}=\frac{2.4}{1.5}=1.6\times$ Why not $2\times$? Each thread dropped from $1.5$ to $1.2$ because they now share caches, the reorder buffer, and TLB — contention costs. So $2\times 1.2=2.4$, not $2\times 1.5=3.0$.

Plug in: $\text{Speedup}=\frac{1}{(1-0.6)+\frac{0.6}{2}}=\frac{1}{0.4+0.3}=\frac{1}{0.7}=1.43\times$ Why $(1-f)$ gets no help: during the CPU-bound fraction the units are already saturated — no idle slots for the second thread to steal, so that time is unchanged (coefficient $1$). Why $f/2$, not $f$: during memory-bound cycles the second thread fills in, but conservatively we assume it only reaches about half the idle capacity (it too stalls, competes for the same starved memory system). So the memory-bound time shrinks from $f$ to $f/2$.

$T_A=\frac{1000}{2.0}=500,T_B=\frac{1000}{0.5}=2000$ $T_{\text{seq}}=500+2000=2500\text{cycles}$

Each thread's finish time: $T_A=\frac{1000}{1.8}=555.\overline{5}\approx 556,T_B=\frac{1000}{0.6}=1666.\overline{6}\approx 1667$ Job done when the slower one finishes: $T_{\text{SMT}}=\max (556,1667)=1667\text{cycles}$ Speedup: $\frac{2500}{1667}=1.50\times$ What it looks like (figure s02): B's long memory stalls are hollow boxes; A's compute colours them in, so A finishes "for free" underneath B's wait. The long pole is B's memory latency, but the idle time now does useful A-work.

(a) Sequential: $T=\frac{1000}{2.5}+\frac{1000}{2.5}=400+400=800\text{cycles}$ (b) SMT (both at $1.4$, run together, take the max — but they are symmetric): $T_{\text{SMT}}=\frac{1000}{1.4}=714.28\dots \approx 714\text{cycles}$ (c) Speedup: $\frac{800}{714}=1.12\times$ (d) Why so small: both are CPU-bound, so there are almost no idle slots to fill — the units were already near-saturated. SMT can only donate idle capacity, and there is little here. Contrast Ex 3.3's $1.50\times$, where B's stalls left huge gaps.

Choose P (the memory-bound thread). Reasoning tied to the model: the resident CPU-bound thread already fills most lanes when it runs — but it doesn't run every cycle if it, too, occasionally stalls, and even a saturated thread leaves scattered hollow boxes. A memory-bound co-runner has complementary needs: it barely touches the ALUs (it's waiting on DRAM), so it slots into the hollow boxes without a fight. Q, being CPU-bound, wants the exact same ALUs — a head-on collision (this is Ex 4.1's $1.12\times$ situation). Lesson: SMT rewards complementary resource profiles.

Set the model equal to the target: $\frac{1}{(1-f)+\frac{f}{2}}=1.25$ Simplify the denominator: $(1-f)+\frac{f}{2}=1-\frac{f}{2}$. So $\frac{1}{1-\frac{f}{2}}=1.25⟹1-\frac{f}{2}=\frac{1}{1.25}=0.8$ $\frac{f}{2}=0.2⟹f=0.4(40\%)$ Interpretation: you need at least $40\%$ of cycles memory-bound before SMT reaches a $1.25\times$ throughput gain under this conservative model. Below that, gains fade toward $1\times$.

Take the limit $f\to 1$: $\text{Speedup}=\frac{1}{(1-1)+\frac{1}{2}}=\frac{1}{0.5}=2\times$ So the model's ceiling is exactly $2\times$, reached only in the idealised all-memory-bound limit. Why the model caps at $2\times$ (not higher): look at the denominator term $f/2$. The "$/2$" is the fill-half assumption — even in a fully idle stretch, the model lets the second thread reclaim only half the idle time, so memory-bound time shrinks from $f$ to $f/2$, never to $0$. If instead we assumed the second thread reclaimed all idle time ($f\to 0$ in the denominator), the limit would be $1/0=\infty$. It is precisely the conservative $f/2$ factor — the model's built-in acknowledgement that the second thread also stalls and competes — that pins the ceiling at $2\times$. (Real hardware lands below even this, at $1.2$–$1.4\times$, because the shared cache, ROB, and TLB add contention the model does not include.)

Cycle-by-cycle:

1. A mispredicts → its in-flight wrong-path instructions are squashed; A has nothing ready for ~15 cycles while the correct path refetches.
2. Without SMT, those 15 cycles are pure hollow boxes (figure s02, the same hollow-slot pattern as B's memory stalls) — wasted.
3. With SMT, the scheduler's ready-queue still holds B's instructions. Each of those 15 cycles, it issues from B, colouring the lanes A abandoned.
4. When A's correct path arrives, A rejoins the ready-queue and the two interleave again.

The two shared structures that erode the gain:

• Shared branch predictor — B's branches and A's branches update one predictor's history/tables; inter-thread interference (aliasing) can make both mispredict more, so A's flushes become more frequent in the first place.
• Shared cache / TLB (Memory Hierarchy) — B running during A's flush pulls in B's data, potentially evicting A's working set, so when A returns it faces fresh cache misses. The stolen slots were free, but the cache pollution imposes a delayed cost on A.

Net: SMT reclaims A's 15 flush cycles as useful B-work (the win), but the shared predictor and shared cache/TLB can quietly raise both threads' miss and mispredict rates (the tax). The gain is real but bounded — exactly the $1.2$–$1.4\times$ story of the whole page.

Time from work and rate ::: $T=M/\text{IPC}$. Why SMT speedup is under 2x ::: threads share caches, ROB, TLB → contention lowers each thread's IPC. Parallel finish time of two threads ::: $\max (T_A,T_B)$, not the sum. Which threads pair best under SMT ::: complementary resource needs (CPU-bound + memory-bound). Amdahl-SMT model ::: $\frac{1}{(1-f)+f/2}$, ceiling $2\times$ as $f\to 1$.