Foundations — Amdahl's Law and Gustafson's Law

Before you can read a single line of the parent note, you need to earn every symbol it throws at you. Below, each symbol appears in the order it is built on the previous one. We never use a letter before it has a plain meaning and a picture.

1. Work and time — the picture of a job

Imagine a job as a long horizontal bar. The length of the bar is how long the job takes. That length has a name.

We care about two specific times, so we tag $T$ with a little number below it (a subscript).

Why do we need two names? Because "speedup" (coming soon) is a comparison between them. You cannot compare one thing to itself — you need $T_1$ and $T_n$.

2. Processors — what $n$ counts

Why a whole number and not a fraction? You can't have half a processor. But in the formulas we still let $n$ grow without bound to ask "what's the absolute ceiling?" — that's the $n\to \infty$ notation, read "as $n$ goes to infinity."

3. Splitting the bar — the serial fraction $f$

Here is the heart of everything. Take the $T_1$ bar and cut it into two coloured pieces.

Now we measure what proportion of the bar is coral. That proportion is the single most important symbol in the topic.

Because the whole bar is $1$ (i.e. $100\%$) and the coral part is $f$, the mint part must be whatever is left over:

Why write $1-f$ instead of a new letter like $p$? Because they always add to $1$, giving them two independent letters would hide the fact that they're two halves of the same bar. One letter $f$ tells the whole story.

4. Slicing the mint piece — dividing by $n$

When $n$ workers share the parallel (mint) work, each does $\frac{1}{n}$ of it, so it finishes $n$ times sooner.

Why does the serial part refuse to shrink? Because "serial" is defined as work that cannot be split. Dividing it by $n$ would contradict its own definition. This stubborn coral floor is the entire reason Amdahl's Law has a ceiling.

5. Speedup — the ratio $S(n)$

We finally compare the two bars. "How many times faster?" is a ratio.

Why a ratio and not a difference like $T_1-T_n$? A difference is in seconds and depends on the size of the job. A ratio is a pure number — "2.5×" means the same thing whether the job took milliseconds or hours. That portability is why performance is always quoted as speedup.

6. The limit symbol — finding the ceiling

Why do we bother with infinity when no computer has infinite cores? Because it reveals the hard ceiling. If $f=0.1$, no amount of hardware ever beats $10\times$. Knowing the ceiling stops you wasting money on cores that can't help.

7. Reading Gustafson's rearrangement

Gustafson's formula $S(n)=n-f(n-1)$ uses the same symbols but in a new shape. Every piece is already defined:

• $n$ — processors (Section 2),
• $f$ — serial fraction (Section 3),
• $n-1$ — read "one fewer than $n$"; it appears because Gustafson compares the parallel work at scale ($n$ times bigger) against a single worker doing all of it.

Prerequisite map

Each box on the left must be solid before the topic (right side) makes sense. If any left box is fuzzy, re-read its section above.

Related deep material once you're ready: Performance Metrics, Scalability Analysis, Parallel Architectures, Load Balancing, Thread Synchronization, Cache Coherence, and GPU Computing.

Equipment checklist

Test yourself — cover the right side and answer aloud.