Instruction-level vs thread-level parallelism: Question bank

This page is a set of conceptual traps for Instruction-level vs thread-level parallelism. No number-crunching here — every item targets a misconception, a definition boundary, or an edge case. Each answer is real reasoning, not a bare yes/no.

Before you start, let's lock in three plain-word anchors so nothing below is ambiguous.

Figure — Instruction-level vs thread-level parallelism

The one formula behind every item on this page

Almost every trap below quotes Amdahl's Law, so let's build it once, in plain words, before using any symbol.

Definition Every symbol used on this page, defined once

Pick a job and split all its work into two buckets by fraction of total work:

parallel fraction = the share of the work that can run in parallel. We write it $p$ when we talk about whole threads splitting a problem (TLP), and $f$ when we talk about independent instructions inside one stream (ILP). Same idea, two names on purpose — the number comes from a different source (algorithm split vs instruction independence), so we keep the letters apart to remember which world we're in.
serial fraction = the leftover $1 - p$ (or $1 - f$ ) that must run step-by-step. This is the un-speedable bucket.
== $N$ == = number of cores/threads we throw at the parallel part (TLP).
== $n$ == = average instructions finished per cycle, i.e. how many independent instructions overlap (ILP). Also called IPC (instructions per cycle).

Now, with $p$ , $f$ , $N$ , $n$ , and IPC all defined and the formula on the table, the traps below are fair game.

True or false — justify

Every answer explains why, not just the verdict.

A SIMD add of 8 floats counts as 8 instructions worth of ILP.

False. SIMD is one instruction in the pipeline that happens to carry many data elements, so it contributes to DLP, not ILP — the pipeline still issues it as a single op.

Doubling the superscalar issue width always doubles real-world ILP speedup.

False. Dependency chains — the serial fraction

(1 - f)

in Amdahl's Law — cap ILP; once wide-issue slots sit idle waiting on results, extra width buys nothing.

TLP and ILP are mutually exclusive — a chip picks one.

False. They stack: each core exploits ILP internally and many cores run threads in parallel, so total speedup is roughly the product of both.

An "embarrassingly parallel" workload is one that's embarrassingly hard to parallelize.

False. It means the opposite — the work splits into fully independent pieces with almost no communication, so TLP scales nearly linearly.

Out-of-order execution changes the program's final result.

False. The hardware only reorders instructions that are independent and commits results in program order, so the observable outcome is identical to sequential execution.

Adding more cores helps a program with a large sequential fraction just as much as a highly parallel one.

False. Amdahl's Law says the serial fraction

(1 - p)

becomes the hard ceiling; a big serial fraction leaves little for extra cores to speed up.

Pipelining is a form of ILP even though it issues only one instruction per cycle.

True. Pipelining overlaps stages of consecutive instructions in flight simultaneously, which is instruction-level overlap even when issue width is one.

A single-core CPU can still exploit thread-level parallelism.

True. Via hardware multithreading / SMT a core interleaves threads to hide stalls — it's TLP without multiple cores, though throughput is limited.

Linked-list traversal is limited mainly by the arithmetic unit, not by memory.

False. It's limited by pointer chasing — each next load must finish before the following load can even start, a memory/dependency chain, not compute.

Spot the error

Each item contains a wrong statement; the reveal names and fixes it.

"We used AVX vectors, so our thread-level parallelism improved."

The error is mislabeling: AVX vectors are SIMD / DLP, not TLP. Vectorizing widens data per instruction but does not add independent threads.

"The loop is inherently serial, so let's rewrite it as a wider superscalar issue to fix it."

You can't fix a dependency chain with wider issue — superscalar only helps independent instructions. The fix is algorithmic: break the chain (e.g., multiple accumulators) or restructure the data.

"IPC of 4 means the CPU always finishes 4 instructions every cycle."

The error confuses peak issue width (the design maximum

n = 4

) with sustained IPC (the long-run average). Real average IPC is far lower because hazards, cache misses, and dependencies leave issue slots empty most cycles — see the lane picture in figure s02's right panel.

"Since matrix multiply parallelizes perfectly, Amdahl's Law doesn't apply."

Amdahl's Law always applies; it just gives a favorable answer when

p \approx 1

. Setup, memory allocation, and the final reduction keep the serial fraction

(1 - p) > 0

"Two threads on one SMT core run twice as fast as one thread."

They share one core's execution units, so combined throughput gains are typically only 10–30%, not 2×. SMT hides latency, it doesn't duplicate hardware.

"Our code has no data hazards, so out-of-order execution is pointless."

Even with no data hazards, out-of-order execution still hides memory latency and control stalls by finding later independent work — its value isn't only about data hazards.

"A masked SIMD add with only 3 of 8 lanes active does one-eighth the useful work but still costs a full vector instruction."

This is correct, not an error — inactive lanes ("masked off") still occupy the instruction's cycle, so partial vectors waste DLP throughput; that's the vector-length edge case shown in figure s01.

"We split the linked list across 8 threads, so we'll get near-8× speedup."

Splitting a linked list needs traversal to find boundaries and causes cache thrashing between threads; combining results adds overhead, so real speedup is small and far below 8×.

Why questions

Deeper "why" reasoning behind the mechanisms.

Why does ILP saturate at only 2–6 IPC in typical code?

Because real programs are chains of dependent instructions and branches; once the few nearby independent instructions are issued, the hardware runs out of ready work — see Pipelining-Hazards.

Why is the same Amdahl's Law formula used for both ILP and TLP?

Both split work into a serial part that can't overlap and a parallel part divided by a parallelism factor (

n

for IPC,

N

for cores); the algebra is identical — the meaning of the fraction differs, which is exactly why we keep the letters

f

and

p

separate (see Amdahls-Law).

Why does TLP scale to hundreds of units while ILP does not?

TLP exploits algorithmic independence between whole threads, which large problems have plenty of; ILP is bounded by the short dependency distances inside one stream.

Why does adding multiple accumulators expose more ILP in a sum-reduction loop?

One accumulator forces every add to wait for the previous add (one serial chain); several partial accumulators create several independent chains the superscalar core can overlap, combined only at the end.

Why is DLP kept as a separate category rather than folded into ILP?

A SIMD instruction is a single instruction, so counting its lanes as ILP would double-count parallelism and confuse hardware analysis; keeping DLP distinct (see SIMD-Vector-Processing) avoids that error.

Why does moving from a linked list to an array unlock both ILP and TLP?

Array indices are known in advance, so loads are independent (ILP) and index ranges split cleanly across threads (TLP); linked lists hide the next address until the current load completes, blocking both.

Why can more cores actually slow down some parallel programs?

Communication, synchronization, and cache-coherence traffic grow with core count (see Cache-Coherence-Protocols); past a point this overhead exceeds the shrinking per-core work, so net speedup falls.

Edge cases

Boundary and degenerate scenarios you must not be surprised by. Each one plugs a limiting value into the Amdahl formula above.

What is the ILP speedup when the parallel fraction

f = 0

(fully dependent code)?

Set

f = 0

S_{I L P} = \frac{1}{( 1 - 0 ) + 0/ n} = \frac{1}{1} = 1 \times

— no overlap is possible no matter how wide

n

is, because every instruction waits on the last.

What is the ILP speedup when

f = 1

(every instruction independent)?

Set

f = 1

S_{I L P} = \frac{1}{0 + 1/ n} = n

— speedup rises linearly with issue width

n

and saturates only at the hardware limit of

n

(real code never reaches

f = 1

, which is why sustained IPC stays low).

What is the TLP speedup as core count

N \to \infty

with serial fraction

(1 - p)

N \to \infty

the term

p / N \to 0

, so

S_{T L P} \to \frac{1}{1 - p}

— the parallel part vanishes but the serial part remains, so infinite cores give finite speedup.

p = 1

(perfectly parallel), what limits TLP speedup?

With

p = 1

the formula gives

S = \frac{1}{0 + 1/ N} = N

, so math alone predicts full

N \times

; in practice only physical resources cap it — core count

N

, memory bandwidth, and power/thermal limits.

What is the ILP speedup when issue width

n = 1

(a scalar, non-superscalar core)?

Set

n = 1

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

regardless of

f

— with one issue slot there is nowhere to overlap, so instruction independence is wasted.

For a single instruction (one-instruction program), how much ILP is available?

None — ILP needs multiple instructions to overlap; with one instruction there is nothing to run alongside it, so IPC is at most 1.

A workload is a stream of totally independent instructions but still gets low speedup — why?

If those independent instructions all miss in cache or contend for one execution port, the bottleneck shifts to memory or ports, not instruction dependency — high

f

alone isn't enough when

n

is throttled by resources.

What happens to SMT benefit when both threads are compute-bound on the same unit?

Almost nothing — SMT wins by filling idle slots left by stalls; if both threads keep the shared unit busy, they simply compete and gain little.

Recall Fast self-check

ILP overlaps ::: many instructions from one stream TLP overlaps ::: many independent instruction streams DLP/SIMD is ::: one instruction over many data elements The hard ceiling in Amdahl's Law comes from ::: the serial fraction $(1 - p)$ Why two letters $f$ and $p$ ? ::: $f$ = instruction independence (ILP), $p$ = algorithmic split (TLP); same formula, different source ILP speedup at $f = 1$ equals ::: the issue width $n$ Pointer chasing hurts because ::: each load must finish before the next address is known