Parallelism and performance

Vocabulary

English	Meaning
instruction-level parallelism	instruction-level parallelism
SMT	SMT

Amdahl's ceiling

A program has a serial fraction and a parallelizable fraction $f$. On $p$ processors: $\text{Speedup} = 1/((1-f) + f/p)$ — the serial part never shrinks, and as $p \to \infty$ the speedup ceiling is $1/(1-f)$.
With $f = 0.9$: at most $10\times$; at $p = 8$: $4.71\times$; at $p = 16$: $6.40\times$ — the second eight processors add $1.7\times$ where the first added $4.7\times$. With $f = 0.99$, reaching $50\times$ needs $p = 99$ exactly.

{exercise:uni-cs0606-amdahl}

Practice

With f = 0.9, the speedup ceiling is —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

A render spends 36 s compositing (serial) and 64 s shading (parallel): $f = 0.64$. On 4 processors: $1/(0.36 + 0.16) = 1.92\times$, runtime $52.0$ s. On 8: $2.27\times$, $44.0$ s — the serial tail now dominates, and the next purchase is an algorithm, not a machine.
Report measured speedups only: the baseline is the same program on the same machine with one core active; peak numbers assume $f = 1$, which no program achieves.

{exercise:uni-cs0606-price}

Practice

36 s serial + 64 s parallel on p = 4 gives —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Before cores, the pipeline itself is instruction-level parallelism: the 5-stage machine overlaps five instructions. Hardware threads (SMT) fill pipeline bubbles with another thread's work — the hazard math still applies per thread.
The stack — ILP within a core, threads per core, cores per chip — is one ladder with one discipline: every rung leans on Amdahl.

{exercise:uni-cs0606-ladder}

Practice

The pipeline itself is a form of —

Difficulty 1/5 · 100 coins + a small bonus on first completion today