Speed-up limits: Amdahl's and Gustafson's laws
Speed-up is the time on one processor divided by the time on p processors. Amdahl's law (1967) says that if a fraction P of a program's work can be parallelized and the rest must run serially, the best possible speed-up on p processors is 1 / ((1 − P) + P / p). As p grows, P / p vanishes and the speed-up approaches 1 / (1 − P). A program that is 90 percent parallel can never run more than 10 times faster, however many processors you add.
Python
def amdahl(parallel_fraction, processors):
return 1 / ((1 - parallel_fraction) + parallel_fraction / processors)
def gustafson(parallel_fraction, processors):
return (1 - parallel_fraction) + parallel_fraction * processors
for processors in (1, 2, 8, 64, 1024):
print(processors, round(amdahl(0.9, processors), 2), round(gustafson(0.9, processors), 1))
print(round(1 / (1 - 0.9), 1))