Instruction-level vs thread-level parallelism: Worked examples

This page is the "no scenario left behind" companion to the parent topic. Before we start, one promise: every symbol used here is defined the first time it appears. If you have not yet met Amdahls-Law, do not worry — we rebuild it below.

Look at the picture: the amber block is the serial part $(1 - x)$ — it never shrinks. The cyan blocks are the parallel part $x$ — those we cut into $k$ pieces. The total time is amber + (one cyan slice). No matter how big $k$ grows, the amber block is a floor you can never dig below. That single idea drives every surprise on this page.

The scenario matrix

Every parallelism problem you will meet falls into one of these cells. The examples that follow are labelled with the cell(s) they cover, and together they hit all of them.

Cell	What makes it special	Covered by
A. High- $x$ , high- $k$	Almost everything parallel, many workers (best case)	Ex 1
B. Low- $x$ (serial chain)	Dependencies dominate; parallelism fails	Ex 2
C. $x = 0$ (degenerate)	Purely serial — sanity floor	Ex 3
D. $x = 1$ (degenerate)	Perfectly parallel — sanity ceiling	Ex 3
E. $k \to \infty$ (limiting)	Infinite hardware — where's the ceiling?	Ex 4
F. Combining ILP × TLP	Two speedups multiply	Ex 5
G. Word problem	Real workload, must extract $x$ and $k$ yourself	Ex 6
H. Exam twist	"Given the speedup, find $x$ " — solve backwards	Ex 7
I. Wrong category	SIMD mislabelled as ILP/TLP (the classic trap)	Ex 8

Forecast (guess first): eight cores — do you expect exactly 8×? Write your guess down.

Identify the pieces. Why this step? The master formula needs $x$ and $k$ ; name them so we don't mix ILP and TLP numbers. Here $x = p = 0.99$ and $k = N = 8$ .
Serial part $= 1 - p = 1 - 0.99 = 0.01$ . Why? This is the amber floor — the 1% that runs no matter what.
Parallel part shrunk $= \frac{p}{N} = \frac{0.99}{8} = 0.12375$ . Why? The cyan block cut into 8 slices; we only wait for one slice.
Add and invert. $S_{T L P} = \frac{1}{0.01 + 0.12375} = \frac{1}{0.13375} = 7.48 \times$ Why? Master equation. Total time = floor + one slice, and speedup is its reciprocal.

Verify: 7.48× is below 8× (the guess), which is correct — the 1% floor steals the rest. Sanity: if the floor were $0$ , we'd get exactly $1/ (0.99/8) = 8.08$ ? No — with floor $0$ and $p = 1$ we get exactly 8. Good, our answer sits just under the perfect ceiling, as it must.

Forecast: 4-wide hardware — surely at least 2×? Guess.

Name the pieces: $x = f = 0.1$ , $k = n = 4$ . Why? This is ILP now, so $f$ = instruction independence, $n$ = instructions/cycle. See Pipelining-Hazards for why the chain stalls: it's a load-to-use hazard.
Serial part $= 1 - 0.1 = 0.9$ . Why? 90% of instructions must wait — a giant amber floor.
Parallel part shrunk $= \frac{0.1}{4} = 0.025$ . Why? Only 10% overlaps, across 4 slots.
Combine: $S_{I L P} = \frac{1}{0.9 + 0.025} = \frac{1}{0.925} = 1.08 \times$

Verify: 1.08× ≈ almost nothing. The 4-wide machine is wasted because the dependency chain dominates — exactly the lesson: data structure, not hardware width, decides the ceiling. Units check: $S$ is a ratio, dimensionless. ✓

The figure contrasts an array (independent cyan arrows, all fire at once) with a linked list (amber chain, each arrow must wait for the one before). This is why arrays win at both ILP and TLP.

Forecast: what speedup do you expect at each extreme?

Case $x = 0$ . Why this step? This is the floor test — if the formula misbehaves here, it's wrong. $S = \frac{1}{( 1 - 0 ) + \frac{0}{8}} = \frac{1}{1 + 0} = 1 \times$ Nothing parallel ⇒ no speedup. Correct.
Case $x = 1$ . Why? This is the ceiling test. $S = \frac{1}{( 1 - 1 ) + \frac{1}{8}} = \frac{1}{0 + 0.125} = 8 \times$ Everything parallel ⇒ full $N$ × speedup. Correct.

Verify: $x = 0$ gives 1 (no gain) and $x = 1$ gives exactly $k = 8$ (perfect scaling). These bracket every real answer: any real program lives strictly between them, which is why Ex 1 landed at 7.48 (near ceiling) and Ex 2 at 1.08 (near floor). ✓

Forecast: infinite cores — does the speedup blow up to infinity?

Write the formula and push $N$ up. Why? We want the ceiling, so we take the limit as $N \to \infty$ . $S = \frac{1}{( 1 - p ) + \frac{p}{N}}$
Let the shrinking term vanish. Why? $\frac{p}{N} \to 0$ as $N \to \infty$ — dividing a fixed number by an ever-bigger one goes to zero. $S_{m a x} = \frac{1}{( 1 - p ) + 0} = \frac{1}{1 - p}$
Plug $p = 0.95$ : $S_{m a x} = \frac{1}{0.05} = 20 \times$ .

Verify: even with infinite hardware, a 5% serial part caps you at 20×. This is the amber floor made numeric — it's exactly the "floor you can never dig below" from Figure 1. Related trap in Power-Performance-Tradeoffs: adding cores past this point burns power for zero gain.

The curve flattens toward the dashed amber line at $20 \times$ . Notice how quickly it plateaus — most of the benefit is gone by 32 cores. That flattening is the whole reason scheduling and low serial overhead matter more than raw core count.

Forecast: do these add (2.11 + 7.46) or multiply?

Recompute $S_{I L P}$ with $f = 0.7$ , $n = 4$ . Why? Confirm the input before combining. $S_{I L P} = \frac{1}{0.3 + \frac{0.7}{4}} = \frac{1}{0.475} = 2.105 \times$
Recompute $S_{T L P}$ with $p = 0.99$ , $N = 8$ . Why? Same reason. $S_{T L P} = \frac{1}{0.01 + \frac{0.99}{8}} = 7.477 \times$
Multiply, don't add. Why? ILP shrinks each core's time by 2.11×; TLP then shrinks the already-shrunk time by 7.46× more. Sequential shrinks compound. $S_{t o t a l} = 2.105 \times 7.477 = 15.7 \times$

Verify: if we had added we'd get 9.57×, which is wrong — the shrinks are independent multipliers, like two discounts stacked. SMT and superscalar live at the ILP layer; cache coherence governs the TLP layer — different layers, so they multiply. ✓

Forecast: with 6 cores, guess the final time.

Total serial baseline $= 3 + 27 = 30$ s. Why? $x$ is a fraction of the original single-thread time, so we need that total.
Compute $p$ = parallel seconds ÷ total = $27/30 = 0.90$ . Why? By definition $p$ is the fraction of the original time that overlaps.
Apply master formula, $x = p = 0.9$ , $k = N = 6$ . $S = \frac{1}{0.1 + \frac{0.9}{6}} = \frac{1}{0.1 + 0.15} = \frac{1}{0.25} = 4.0 \times$
Convert back to time: new time $= 30/4.0 = 7.5$ s. Why? Speedup = old/new, so new = old/ $S$ .

Verify (units!): new time should equal serial part + parallel part on 6 cores $= 3 + \frac{27}{6} = 3 + 4.5 = 7.5$ s. ✓ Matches exactly, and the units are seconds throughout.

Forecast: high or low $p$ ? Guess before solving.

Start from the master formula and treat $p$ as the unknown. Why? We know $S$ and $N$ ; algebra recovers $p$ . $3 = \frac{1}{( 1 - p ) + \frac{p}{8}}$
Invert both sides. Why? Get rid of the fraction by taking reciprocals. $\frac{1}{3} = (1 - p) + \frac{p}{8}$
Expand the right side. Why? Collect the $p$ terms. $\frac{1}{3} = 1 - p + \frac{p}{8} = 1 - p (1 - \frac{1}{8}) = 1 - \frac{7}{8} p$
Solve for $p$ . $\frac{7}{8} p = 1 - \frac{1}{3} = \frac{2}{3} \Rightarrow p = \frac{8}{7} \cdot \frac{2}{3} = \frac{16}{21} \approx 0.762$

Verify: plug $p = 16/21$ , $N = 8$ back in: $(1 - p) = 5/21$ , $p /8 = 2/21$ , sum $= 7/21 = 1/3$ , reciprocal $= 3$ . ✓ So only 76% was parallel — the other 24% serial capped the gain at 3×.

Forecast: is the student right?

Recall the categories. Why? The whole page rests on keeping ILP, TLP, and DLP separate. See SIMD-Vector-Processing.
- ILP = many independent instructions overlapping.
- TLP = many independent threads.
- DLP (data-level) = one instruction over many data elements (SIMD).
Classify the SIMD add. Why? One vaddps is a single instruction in the pipeline, however many floats it touches.
Count it correctly. A lone SIMD add contributes $n = 1$ to ILP, not 8. The "8" is the SIMD width (DLP), a different axis entirely — see Memory-Level-Parallelism for yet another orthogonal axis.

Verify (numeric): if that SIMD add is the only instruction per cycle, the ILP factor is $n = 1$ , giving $S_{I L P} = \frac{1}{0 + 1/1} = 1 \times$ from ILP alone — the speedup came from DLP, not ILP. The student mislabelled the axis. ✓

Recall Self-test — cover the answers

Which cell has a speedup you can never exceed no matter the hardware? ::: Cell E — the limit is $1/ (1 - x)$ , the serial floor. If ILP gives 2× and TLP gives 5×, combined speedup is? ::: $10 \times$ — they multiply, not add (Cell F). A pure SIMD add contributes what to your ILP count $n$ ? ::: Just $1$ — it's data-level parallelism, not ILP (Cell I). Measured 3× on 8 cores means roughly what parallel fraction? ::: About $0.76$ (Cell H).