Part 4 of 7 · 2 min read
Amdahl's law
In plain words: Few programs can be split completely. Reading the input, combining the results and the setup often run in one thread. If a fraction p of the work can be spread over n processors and the rest, 1 − p, must run serially, then the run time, with the one-processor time as 1, is
(1 − p) + p / n
and the speed-up is the inverse of that:
speed-up = 1 / ((1 − p) + p / n)
This is Amdahl's law. As n grows without limit, the term p / n goes to 0, and the speed-up approaches 1 / (1 − p). The serial part alone sets the ceiling.
The table was computed from the formula (not measured):
Parallel fraction p |
n = 2 | n = 4 | n = 8 | n = 16 | n = 64 | Ceiling |
|---|---|---|---|---|---|---|
| 0.50 | 1.33 | 1.60 | 1.78 | 1.88 | 1.97 | 2.0 |
| 0.90 | 1.82 | 3.08 | 4.71 | 6.40 | 8.77 | 10.0 |
| 0.95 | 1.90 | 3.48 | 5.93 | 9.14 | 15.42 | 20.0 |
A program that is 90 per cent parallel can never go beyond 10 times faster, however many processors it has, and with 16 processors it reaches only 6.4. A program with half its work serial is stuck below 2.
A test checks the formula on the two-processor machine. The program spends 25 per cent of its work in a serial part, so p is 0.75, and splits the rest over n threads. The law predicts 1 / (0.25 + 0.75 / 2) = 1 / 0.625 = 1.6 for two threads. Two runs measured:
1 thread : 1.16 s, speed-up 1.00
2 threads: 0.73 s, speed-up 1.60
2 threads: 0.76 s, speed-up 1.52
The first run gave exactly 1.60, and the second gave 1.52, a little lower because of timing noise. The law holds as a good estimate.
The law has a message for design: finding and shrinking the serial part is worth more than adding processors. Doubling the cores of a program with a 25 per cent serial part cannot give more than 4 times speed in any case.
Amdahl's law
Amdahl's law states that if a fraction p of a program's work can be run in parallel on n processors and the remaining fraction 1 − p must run serially, the greatest speed-up is 1 / ((1 − p) + p / n), which can never exceed 1 / (1 − p).
Example: if 90 per cent of a program is parallel, its speed-up is at most 10, no matter how many processors it has.
Check yourself:
1. Compute the speed-up for p = 0.8 and n = 4.
2. What is the ceiling for p = 0.8?
3. Why does the law say the serial part matters more than the number of processors?