Amdahl's Law

In one sentence: Amdahl’s law tells you how much faster a whole program gets when you speed up only part of its work, and why the part you leave alone caps the gain.

$S = \frac{1}{(1 - p) + \frac{p}{s}}$

Read it out loud: “S equals one divided by the quantity one minus p, plus p divided by s.”

What each symbol means

Symbol	Meaning
$S$	The overall speedup: how many times faster the whole job runs. A value of 1 means no change and a value of 2 means twice as fast.
$p$	The fraction of the work that can be sped up, from 0 to 1. For example $p = 0.9$ means 90% of the job.
$s$	The speedup of that part alone. With 8 cores on a perfectly split job, $s = 8$ .
$1 - p$	The fraction of the work that stays the same, the part that cannot be sped up.
$\frac{p}{s}$	The time the sped-up part now takes, as a fraction of the original total time.

What the formula is doing

Imagine a program whose total running time is 1 unit. A fraction $p$ of that time is work that can be split across several processors. The rest, $1 - p$ , must run one step after another and cannot be split.

Without any speedup the program takes $p + (1 - p) = 1$ unit. With the speedup, the splittable part takes $\frac{p}{s}$ of the original time, and the part that cannot be split still takes $1 - p$ . The new total time is $(1 - p) + \frac{p}{s}$ .

Speedup is the old time divided by the new time. The old time is 1, so the speedup is $S = \frac{1}{(1 - p) + \frac{p}{s}}$ . That is the formula.

The shape explains a hard limit. As $s$ grows, $\frac{p}{s}$ shrinks toward 0, but the $1 - p$ part never shrinks. So the speedup can never be bigger than $\frac{1}{1 - p}$ , however many processors you add.

An everyday picture

Think of cooking a holiday dinner. Chopping the vegetables can be shared among four helpers, which speeds that part up a lot. The oven still needs its one hour, and no helper can make it bake faster. The dinner cannot be ready sooner than the oven allows, however many people chop.

Worked example: A program that is 90% parallel on 8 cores

A program spends 90% of its time on work that can be split across cores, so $p = 0.9$ . That part runs $s = 8$ times faster on 8 cores. The other 10% is serial and stays the same.

Serial part: $1 - p = 1 - 0.9 = 0.1$ of the original time.
Parallel part on 8 cores: $\frac{p}{s} = \frac{0.9}{8} = 0.1125$ of the original time.
New total time: $0.1 + 0.1125 = 0.2125$ , compared with 1 before.
Speedup on 8 cores: $S = \frac{1}{0.2125} \approx 4.71$ .
Limit with unlimited cores: the parallel part takes almost no time, so the total time is close to $0.1$ and $S = \frac{1}{0.1} = 10$ .

Answer: On 8 cores the program runs about 4.71 times faster, not 8 times faster. Even with unlimited cores it can never get more than 10 times faster, because the 10% serial part still takes its full time.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Assuming 8 cores give 8 times the speed. Only the parallel part gets faster, so the total speedup is always smaller than the number of cores.
Entering $p$ as a percentage, such as 90, instead of a fraction, such as 0.9. The formula needs $p$ between 0 and 1.
Forgetting the serial part. The $1 - p$ term is what limits the speedup, and it is easy to leave out of the calculation.
Reading the law as saying parallel work is useless. It says the gain is limited by the serial fraction. More cores still help, but each extra core helps a little less.

Where you will meet it

Deciding how many CPU cores or threads a program should use, and when adding more stops helping.
Planning parallel jobs on supercomputers and GPUs, to judge whether a program is worth rewriting for parallel hardware.
Performance tuning, where engineers measure a program and speed up the part that takes the most time first.
Comparing multicore chip designs, where it shows how much a serial part limits the benefit of extra cores.

Questions people ask

Does Amdahl's law mean parallel computing is pointless?

No. It means the serial part sets a ceiling. When $p$ is small, the gain is small, and when $p$ is close to 1, many cores pay off well. The law tells you where the ceiling is, so you know which part to work on.

What is a serial part?

Work that must be done in order, where each step needs the result of the step before it, such as a calculation that builds on the previous answer.

Is the speedup ever equal to the number of cores?

Only when the whole job can be split perfectly, which is rare. For any job with a serial part, the speedup is smaller than the number of cores.

Little's Law: Little’s law says the number of things inside a system equals how fast they arrive, multiplied by how long each one stays.
Binary Search Steps: Binary search finds an item in a sorted list by checking the middle and throwing away half, and this formula counts how many checks that takes at most.