A computation may contain many tasks that can run at once, but some steps depend on earlier ones. The critical path is the longest chain of steps that must run one after another. Adding helpers can speed up independent work, but it cannot shorten this chain. section 1.5
A sequential bottleneck
If 10% of a program must run sequentially, that portion limits the total speedup: even infinitely many cores cannot make the program more than 10× faster. The sequential work forms the bottleneck on the critical path. 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 predicted speedups as core counts rise under Amdahl’s fixed-problem assumption and Gustafson’s growing-problem assumption. section 1.5

