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



