Amdahl’s law and scaling

In short: Amdahl’s law says: the non-parallelisable part of a program limits the overall gain from more processors. If 10 % is serial, the speed-up is at most 10×, no matter how many cores you have.

In more detail: With parallel fraction p and n processors, speed-up = 1 / ((1 − p) + p/n). For n → ∞ this gives 1/(1 − p). The law explains why 64 cores are rarely 64 times faster.

In Depth

• Example: p = 0.9, n = 8 → 1 / (0.1 + 0.1125) ≈ 4.7.
• Gustafson: With growing problem size the parallel share grows, scaling stays worthwhile.
• Overhead: Synchronisation, communication and locks worsen scaling further.
• Find the bottleneck: Measure first (profiling), then improve the largest serial part.
• Kinds of scaling: Vertical (stronger machine) and horizontal (more machines).
• Universal scalability law: Also accounts for coherence costs.

See also: Memory hierarchy and cache lines, Little’s law and capacity planning