liveBook · Manning

Gustafson's law

As explained in Grokking GPU Programming

Gustafson’s Law models scalable speedup by allowing the problem size to grow as more processors are added.

Adding processors cannot shorten steps that depend on earlier results. Gustafson’s law estimates speedup under a different assumption: as processors are added, the problem can grow too, giving them more parallel work. section 1.5

The estimate is S(p) = p − f(p − 1), where p is the processor count and f is the fraction of the parallel run that must remain sequential. Unlike Amdahl’s law, Gustafson’s law assumes the problem grows with the processors. section 1.5

Eight processors and 10% sequential work

With f = 0.1 and p = 8, Gustafson’s law predicts 7.3× speedup. Amdahl’s law predicts 4.7× because it holds the problem size fixed. A larger image or batch can give the parallel portion more work as more GPU cores are added. 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 how the two laws predict speedup at different processor counts when 10% of the work is sequential. section 1.5

How Grokking GPU Programming covers it

How deep it goes
Defines a speedup formula and works through a 10%-sequential, eight-processor estimate.
Examples
Compares predicted speedups for 2, 4, 8, and infinitely many processors with 10% sequential work.
What you can do after
Evaluate potential speedup as processor counts and problem size grow.
How it connects
Contrasts Amdahl’s law and links scalable workloads to GPU image processing and larger batches.

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.