Speedup measures how many times faster a parallel computation finishes than its sequential version: divide sequential execution time by parallel execution time. section 1.4
Imagine doubling 1,000 array values. A sequential loop handles them one at a time; a parallel version assigns one thread to each value. The ideal suggests one step instead of 1,000, but real speedup is lower: threads run in groups, and setup, scheduling, memory latency, and data movement take time. section 1.4
Sequential work limits the gain. If 10% of a program must run sequentially, Amdahl’s Law caps speedup at 10×, even with infinitely many processors. With eight processors, it predicts 4.7×. Gustafson’s Law assumes the problem grows with the processor count and predicts 7.3× for eight processors. The difference is whether the problem size stays fixed or grows. 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 speedup as processor counts rise under fixed-size and growing-problem assumptions. section 1.5


