Amdahl’s law gives the best speedup you can expect when you run a program on several processors. Some parts of a task can be split among processors, but others, such as reading input or combining results, must run in sequence. The serial part sets a ceiling on the speedup, whatever the number of processors. The law is used to decide whether it is worth buying more cores or better to improve the code.
How the calculation works
With a parallel fraction p and n processors:
- Speedup = 1 ÷ ((1 − p) + p ÷ n)
- Maximum speedup = 1 ÷ (1 − p)
- Efficiency = speedup ÷ n
- Processors for a target speedup S = p ÷ (1 ÷ S − (1 − p)), if the target is below the maximum
Example
If 90% of a program can run in parallel, 8 processors give a speedup of 1 ÷ (0.1 + 0.1125) = 4.71, an efficiency of 58.8%. The maximum speedup is 10×, however many processors are added. To reach a 5× speedup, you need 9 processors.
Diminishing returns
With a 90% parallel part, going from 8 to 16 processors raises the speedup only from 4.7 to 6.4, and 1,000 processors give 9.9. The last 1% of serial work costs more than all the others combined. This is why optimizing the serial part is often more profitable than adding hardware.
Limits of the model
Amdahl’s law assumes a fixed problem size. Many tasks get larger when more processors are available, and in that case the parallel part grows, which is the idea behind Gustafson’s law. Real programs also face overheads, so measure speedup on your own workload and use the law as an upper bound for planning.
When to optimize instead
Before adding processors, profile the program to find the serial parts: loading data, locks, single-threaded libraries and final merging. Reducing the serial share from 10% to 5% lifts the ceiling from 10× to 20×, a gain that no amount of extra hardware could match on the original code.