liveBook · Manning

Amdahl’s Law

As explained in Grokking GPU Programming

Amdahl’s Law models the maximum speedup obtainable when the problem size is fixed and a fraction of the work remains sequential.

Adding processors can speed up work that runs in parallel, but not the part that must run sequentially. Amdahl’s Law estimates the speedup ceiling when the problem size stays fixed: S(p) = 1 / (f + (1 − f) / p), where f is the sequential fraction and p is the processor count. As p grows, the sequential part becomes the bottleneck. section 1.5

A 10% sequential bottleneck

If 10% of a program must run sequentially, even infinitely many processors cannot make it more than 10 times faster. With 8 processors, the predicted speedup is about 4.7×. Gustafson’s Law gives a different picture when the problem grows with the processor count. section 1.5

Table 1.1 Speedup with 10% sequential code. Amdahl’s Law assumes a fixed problem, so extra cores give diminishing returns and stall at 10×. Gustafson’s Law assumes the problem grows with the cores, so speedup keeps climbing.
Cores
Amdahl speedup
Gustafson speedup
2
1.8×
1.9×
4
3.1×
3.7×
8
4.7×
7.3×
∞
10× (hard ceiling)
keeps growing

Compare Amdahl and Gustafson speedups as processor counts increase. section 1.5

How Grokking GPU Programming covers it

How deep it goes
Defines the speedup formula and works through numerical limits without deriving the formula.
Examples
Uses a program with 10% sequential work to compare speedups across processor counts.
What you can do after
Evaluate whether parallelization is worthwhile by estimating speedup from the sequential fraction and processor count.
How it connects
Connects sequential dependencies and the critical path with Gustafson’s Law.

Also explained in

Compare how 4 books explain Amdahl’s Law →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.