Instruction-level vs thread-level parallelism: Visual walkthrough

The parent note handed you two formulas that look almost identical — but before we even write them, notice they are stuffed with symbols: an $f$ , an $n$ , a $p$ , an $N$ . This page refuses to use a single one of those until we have drawn it. So we start with a blank chalkboard and a bar of chalk, and we earn each letter.

By the end you will see exactly why "make one core do more per cycle" (ILP) and "throw more cores at it" (TLP) collapse into the same shape of equation.

We are extending the parent Instruction-level vs thread-level parallelism discussion, and the root of both formulas is Amdahl's Law.

Step 1 — What is "work"? Draw the bar of instructions

WHAT. Before we can speed anything up, we need a picture of the thing we are speeding up. Let a program be a bar whose length is the total amount of work. We will call the number of little pieces of work $I$ — think " $I$ instructions", one grain of chalk per instruction.

WHY. Speedup is always a ratio of two times: how long the job takes before vs. after. To measure a time we must first measure an amount of work. A bar of length $I$ is the simplest honest picture of "how much there is to do."

PICTURE. The bar below is one program. Every tick is one unit of work. Right now nothing is parallel yet — we are just naming the raw material.

Figure — Instruction-level vs thread-level parallelism

At this stage, if we did everything one piece at a time, the time is just

$T_{original} = I \cdot (time per piece)$

We will measure time in units of "one piece", so we can simply write $T_{original} = I$ . Every symbol so far is earned: $I$ is a count you can literally see as bar length.

Step 2 — Split the bar: the part that MUST wait, and the part that CAN spread

WHAT. Colour the bar in two shades. One shade is work that is stuck being sequential — piece 2 cannot start until piece 1 finishes. The other shade is work whose pieces are independent — they don't need each other's answers.

WHY. This is the only honest way to talk about parallelism. Parallelism helps exactly the independent pieces and helps the stuck pieces not at all. So we must separate them before we can do arithmetic. This single split is the seed of both formulas.

PICTURE. The pink chunk is the stuck (serial) part. The blue chunk is the free (parallelizable) part.

We name the fraction that is free with a single letter. In the ILP world we call it $f$ ; in the TLP world we call it $p$ . They mean the same kind of thing — "what fraction can spread out" — but the reason a piece is stuck differs (we return to that in Step 6).

So the blue length is $f \cdot I$ and the pink length is $(1 - f) \cdot I$ . Check the picture: blue + pink $= f \cdot I + (1 - f) \cdot I = I$ . Nothing lost.

Step 3 — What does "spreading" actually do to time? Introduce the width $n$ (or $N$ )

WHAT. We now let the blue (free) part run several pieces side by side. The number of pieces we can run at the same instant is the width. In ILP that width is $n$ , the instructions finished per cycle (from superscalar issue). In TLP that width is $N$ , the number of cores.

WHY. Running $n$ pieces at once means the blue part finishes in $1/ n$ of the time it used to. This is the whole payoff of parallelism, and we need a symbol for "how wide can we go." Different question, different letter — but same geometric move: squash the blue bar horizontally by the width.

PICTURE. Watch only the blue part: its length $f \cdot I$ gets folded into $n$ stacked lanes, so its time shrinks to $\frac{f \cdot I}{n}$ . The pink part is untouched — it has no lanes to fold into.

Step 4 — Add up the new time

WHAT. The new total time is just pink time + squashed-blue time.

WHY. The two coloured segments run one after the other on the timeline: first the whole pink (serial) segment, and only then the blue (parallel) segment. So their durations simply add. The only "overlap" anywhere is inside the blue segment — the $n$ free pieces run side by side, which is exactly what shrank its length to $\frac{f I}{n}$ in Step 3. Pink and blue never overlap each other. There is no third piece; Step 2 proved blue + pink is the whole bar.

PICTURE. Two segments laid end to end: the full pink $(1 - f) I$ , then the shrunken blue $\frac{f I}{n}$ .

T_{I L P} = pink: serial work, full length (1 - f) \cdot I + blue: parallel work, squashed by width n \frac{f \cdot I}{n}

Read each term where it sits:

$(1 - f) \cdot I$ — the pink fraction $(1 - f)$ times the total pieces $I$ : the part that could not be helped.
$\frac{f \cdot I}{n}$ — the blue fraction $f$ times $I$ (the free pieces), divided by the width $n$ (the lanes).

This is the exact result the parent note lists as its step 4. We have now built it from a coloured bar.

Step 5 — Form the speedup ratio (the punchline)

WHAT. Speedup is old time ÷ new time. Divide Step 1's $T_{original} = I$ by Step 4's $T_{I L P}$ .

WHY. "How many times faster?" is literally the old duration measured in units of the new duration. That ratio is what everyone quotes as the speedup.

PICTURE. Two bars stacked: the long original bar over the shorter new bar. The speedup is how many new-bars fit inside one old-bar.

S_{I L P} = \frac{T _{original}}{T _{I L P}} = \frac{I}{( 1 - f ) I + \frac{f I}{n}}

Now the magic cancellation. Every term has a factor of $I$ — because we asked a ratio, the absolute amount of work does not matter. Divide top and bottom by $I$ :

S_{I L P} = \frac{1}{( 1 - f ) + \frac{f}{n}}

The $1$ on top is the old time in $I$ -units.
$(1 - f)$ is the leftover pink time (never shrinks).
$\frac{f}{n}$ is the blue time after $n$ -way squashing.

Swap letters $f \to p$ , $n \to N$ and you have the twin

S_{T L P} = \frac{1}{( 1 - p ) + \frac{p}{N}}

with zero extra work — the derivation never cared why a piece was free. That is why the two formulas are twins. Both are Amdahl's Law.

Step 6 — Same skeleton, different bones: why $f$ and $p$ are NOT the same number

WHAT. The formulas are identical, but the value you plug in comes from different physics. We show what makes a piece "pink" in each world.

WHY. If you forget this you will predict the wrong speedup even with the right formula. The parent's linked-list example (ILP $\approx 1.08 \times$ , TLP $\approx 3.33 \times$ for the same list) is exactly this gap.

PICTURE. Left board: ILP pinkness comes from instruction dependencies — a load-to-use chain, a branch, a pipeline hazard. Right board: TLP pinkness comes from algorithm structure — initialization, the final reduction, thread spawn/join.

Step 7 — The degenerate cases: pin down the corners

WHAT. Test the formula at its extremes so no reader ever meets a surprise.

WHY. A law you trust must give sane answers at the edges. Contract rule: cover every case.

PICTURE. The speedup curve $S$ vs width, drawn for a few values of "free", showing where each flattens.

free $= 0$ (all pink): $S = \frac{1}{1 + 0} = 1$ . No speedup, whatever the width. Matches intuition: a fully serial chain cannot be helped.
free $= 1$ (all blue): $S = \frac{1}{0 + 1/ width} = width$ . Perfect linear scaling — the embarrassingly parallel image strips in the parent note.
width $\to \infty$ : $S \to \frac{1}{1 - free}$ . The famous ceiling: even infinite cores can't beat this. With $p = 0.99$ the ceiling is $1/0.01 = 100 \times$ , full stop.
width $= 1$ : $S = \frac{1}{( 1 - free ) + free} = 1$ . One lane is no lanes — sanity check passes.

The one-picture summary

Everything above, compressed: one work bar, split pink/blue, blue squashed by the width, ratio taken, $I$ cancels, ceiling revealed.

Recall Feynman retelling — say it like you'd tell a friend

Imagine a job as a strip of paper. Colour it: the pink bit is work that has to be done in order (each step waits on the last), the blue bit is work whose pieces don't care about each other. Now let helpers grab blue pieces — with $n$ helpers the blue strip finishes $n$ times faster, but the pink strip never speeds up, because you can't do step 2 before step 1. Lay the shortened strip end to end: pink (full) then blue-over- $n$ — the two colours run one after the other, and the only side-by-side action is within the blue part. Ask "how many times faster?" — that's the old length over the new length. When you divide, the total amount of work cancels out (a ratio doesn't care how big the job is), leaving $S = 1/ ((1 - free) + free / width)$ . ILP and TLP plug into this same box — ILP's "free" is instructions the core finds independent, TLP's "free" is chunks the programmer split off. And no matter how many helpers you throw in, you can never beat $1/ (1 - free)$ , because the pink part is still sitting there.

Recall Quick self-test

With all work parallel and 8 lanes, what is the speedup? ::: $S = 1/ (0 + 1/8) = 8 \times$ (perfect linear). With 90% parallel and infinite lanes, what is the ceiling? ::: $1/ (1 - 0.9) = 10 \times$ . Why does the total instruction count $I$ vanish from the final formula? ::: Because speedup is a ratio of two times; $I$ factors out of both and cancels. Same list, why is TLP speedup bigger than ILP here? ::: The "free" fraction is measured differently — instruction dependencies cripple $f$ while the algorithm still allows some thread-level split, so $p > f$ .