CSE Roadmap

Core tier · about 4 hours · 7 parts

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?