Amdahl’s Law
Amdahl’s Law reveals the maximum speedup that can be expected from parallel algorithms given the proportion of parts that must be computed sequentially. It gives the speedup as
Where is the fraction of the problem that must be computed sequentially and is the number of processors.
Note that as approaches zero, nears , which we’d expect from a perfectly parallelizable algorithm.