Instruction-level vs thread-level parallelism: Exercises

These exercises climb a ladder. L1 Recognition (can you name it?) → L2 Application (can you plug into the formula?) → L3 Analysis (can you explain why a number comes out?) → L4 Synthesis (can you combine ideas?) → L5 Mastery (can you design and defend a choice?).

Every problem has a full worked solution hidden inside a collapsible callout — cover it, try yourself, then reveal. This page is your self-test for the parent topic.

Before we start, one shared toolbox. We will lean on Amdahl's Law repeatedly, so let us make sure every symbol is earned.

A picture of why the serial part is the villain:

Level 1 — Recognition

Recall Solution 1.1

(a) ILP — many independent instructions, one stream. This is the superscalar idea. (b) TLP — many independent streams (tabs), different cores. (c) DLP — one instruction, many data. See SIMD-Vector-Processing. It is NOT ILP (only one instruction!) and NOT TLP (only one thread!). (d) TLP — two threads share one core. Sharing execution units within a core is still thread-level, because the streams are independent programs.

Recall Solution 1.2

False. Issue width $n$ is an ILP knob — it lets one thread finish faster by executing more of its own independent instructions per cycle. The number of threads is a TLP knob (cores / hardware contexts). They are orthogonal dials: you can raise one while the other stays fixed.

Level 2 — Application

Recall Solution 2.1

Plug in: serial fraction $1 - f = 0.2$ , parallel part $f / n = 0.8/4 = 0.2$ . $S_{I L P} = \frac{1}{0.2 + 0.2} = \frac{1}{0.4} = 2.50 \times$ Notice the serial 0.2 already equals the whole parallel part — that is why we do not get anywhere near $4 \times$ .

Recall Solution 2.2

(a) $S = \frac{1}{0.05 + 0.95/8} = \frac{1}{0.05 + 0.11875} = \frac{1}{0.16875} = 5.93 \times$ . (b) $S = \frac{1}{0.05 + 0.95/64} = \frac{1}{0.05 + 0.0148438} = \frac{1}{0.0648438} = 15.42 \times$ . Eight-fold more cores (8 → 64) gave only ~2.6× more speedup. The serial 0.05 is choking us.

Recall Solution 2.3

ILP and TLP are independent multiplicative factors here (each thread individually enjoys the ILP win): $S_{co mbin e d} = S_{I L P} \times S_{T L P} = 2.11 \times 7.46 = 15.74 \times$ (matches the parent's $15.7 \times$ ).

Level 3 — Analysis

Recall Solution 3.1

(a) $S = \frac{1}{0.9 + 0.1/4} = \frac{1}{0.925} = 1.081 \times$ . ✓ (b) The serial dependency chain (pointer chasing — you cannot load next until the current load returns) pins $1 - f = 0.9$ ; that 0.9 term dominates the denominator no matter how wide the machine is. $n = 16$ : $S = \frac{1}{0.9 + 0.1/16} = \frac{1}{0.90625} = 1.103 \times$ . Going 4→16 wide bought us from 1.081 to 1.103 — a rounding error. This is why Memory-Level-Parallelism and pointer-chasing latency dominate such code.

Recall Solution 3.2

Design A (pure ILP): $S_{A} = \frac{1}{0.4 + 0.6/6} = \frac{1}{0.4 + 0.1} = \frac{1}{0.5} = 2.00 \times$ .

Design B (TLP × per-thread ILP): Per-thread ILP: $S_{I L P} = \frac{1}{0.4 + 0.6/2} = \frac{1}{0.7} = 1.4286 \times$ . TLP across 4 cores: $S_{T L P} = \frac{1}{0.1 + 0.9/4} = \frac{1}{0.325} = 3.0769 \times$ . Combined: $1.4286 \times 3.0769 = 4.396 \times$ .

Design B wins ( $4.40 \times$ vs $2.00 \times$ ) because deep ILP hits diminishing returns (that $f = 0.6$ ceiling), whereas spreading work across cores exploits the abundant algorithmic parallelism $p = 0.9$ . This is the industry's swing toward multicore — see Power-Performance-Tradeoffs.

Level 4 — Synthesis

Recall Solution 4.1

For each: $S_{I L P} (n) = \frac{1}{0.3 + 0.7/ n}$ , $S_{T L P} (N) = \frac{1}{0.1 + 0.9/ N}$ , total $= S_{I L P} \cdot S_{T L P}$ .

$(N, n)$	$S_{I L P}$	$S_{T L P}$	Total
$(1, 8)$	$\frac{1}{0.3875} = 2.581$	$\frac{1}{1.0} = 1.000$	$2.581$
$(2, 4)$	$\frac{1}{0.475} = 2.105$	$\frac{1}{0.55} = 1.818$	$3.827$
$(4, 2)$	$\frac{1}{0.65} = 1.538$	$\frac{1}{0.325} = 3.077$	$4.734$
$(8, 1)$	$\frac{1}{1.0} = 1.000$	$\frac{1}{0.2125} = 4.706$	$4.706$

Best: $(4, 2)$ → $4.73 \times$ . Because $p > f$ (more parallel fraction lives in threads than in instructions), the optimum leans toward more cores — but not all the way to $(8, 1)$ , since a little ILP width still pays. The sweet spot is interior.

Recall Solution 4.2

Ceiling first: as $N \to \infty$ , $\frac{p}{N} \to 0$ , so $S_{ma x} = \frac{1}{1 - p} = \frac{1}{0.1} = 10 \times$ . Good — $6 \times$ is below the ceiling, so it is reachable.

Solve $\frac{1}{0.1 + 0.9/ N} \geq 6 \Rightarrow 0.1 + \frac{0.9}{N} \leq \frac{1}{6} = 0.16 \overline{6}$ $\Rightarrow \frac{0.9}{N} \leq 0.06 \overline{6} \Rightarrow N \geq \frac{0.9}{0.066 6} = 13.5$ . So $N = 14$ cores (must round up to an integer). Check: $S (14) = \frac{1}{0.1 + 0.9/14} = \frac{1}{0.164286} = 6.087 \times$ ✓; $S (13) = \frac{1}{0.169231} = 5.909 \times$ (short).

Level 5 — Mastery

Recall Solution 5.1

$S_{I L P} (n) = \frac{1}{0.85 + 0.15/ n}$ , $S_{T L P} (N) = \frac{1}{0.3 + 0.7/ N}$ .

$(N, n)$	$S_{I L P}$	$S_{T L P}$	Total
$(1, 8)$	$\frac{1}{0.86875} = 1.151$	$1.000$	$1.151$
$(4, 2)$	$\frac{1}{0.925} = 1.081$	$\frac{1}{0.475} = 2.105$	$2.276$
$(8, 1)$	$1.000$	$\frac{1}{0.3875} = 2.581$	$2.581$

(a) $(8, 1)$ wins ( $2.58 \times$ ). ILP is nearly useless here ( $f = 0.15$ ceiling $\approx 1.18 \times$ ), so wide cores are wasted silicon. Thread count is the only lever with headroom.

(b) Yes, SMT plausibly beats all three. The bottleneck is latency, not throughput: each thread stalls waiting for a memory load to return (pointer chasing). SMT lets a core, while thread T1 is stalled on a load miss, execute thread T2's ready instructions — filling otherwise-dead cycles. This converts memory latency into useful work without needing the algorithm to be more parallel. It directly attacks the exact weakness (load-to-use stalls) that both ILP and naive multicore fail to hide. This is Memory-Level-Parallelism harvested through threading.

Recall Solution 5.2

Set $S = 100$ , $N = 128$ : $\frac{1}{( 1 - p ) + p /128} = 100 \Rightarrow (1 - p) + \frac{p}{128} = 0.01$ . $1 - p + 0.0078125 p = 0.01 \Rightarrow 1 - 0.9921875 p = 0.01 \Rightarrow p = \frac{0.99}{0.9921875} = 0.997797$ .

So $p \approx 0.9978$ — 99.78% of the work must be parallel; only 0.22% may be serial. In plain words: the code must be almost perfectly dividable with essentially no setup, synchronization, or final-merge step. Real reason it fails: synchronization and shared-data overhead (locks, cache-coherence traffic between 128 cores, thread spawn/join) easily eat more than 0.22%, pushing the effective serial fraction up and the speedup far below the claim.