Speed-up limits: Amdahl's and Gustafson's laws

The concept

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.

Amdahl's law assumes the problem size is fixed. Gustafson's law (1988) observes that when people get more processors they usually solve bigger problems, so the serial part stays about the same while the parallel part grows. Scaled speed-up is then (1 − P) + P × p, which keeps growing nearly linearly with p. The two laws are not contradictory: they answer different questions, how fast a fixed job can finish versus how large a job can be solved in fixed time.

The program tabulates both for P = 0.9. Amdahl's curve flattens out near 10. Gustafson's scaled speed-up rises almost in step with the processor count. Both are idealized models: they ignore communication cost, load imbalance, memory limits, and synchronization overhead, all of which reduce real speed-up further.

Code example

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))

1 1.0 1.0
2 1.82 1.9
8 4.71 7.3
64 8.77 57.7
1024 9.91 921.7
10.0

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

1 1.0 1.0
2 1.82 1.9
8 4.71 7.3
64 8.77 57.7
1024 9.91 921.7

1 1.0 1.0
2 1.82 1.9
8 4.71 7.3
64 8.77 57.7
1024 9.91 921.7
10.0

Behind the scenes

Cost and common mistakes

Evaluating either formula is O(1) arithmetic.

• Amdahl's law gives an upper bound. Overheads such as communication and synchronization make real speed-up smaller.
• Do not compare the two laws as if one were wrong. They model fixed-size and scaled workloads respectively.
• The parallel fraction is measured in time of the original serial program, not in lines of code.

Try it yourself

What is the maximum Amdahl speed-up when 95 percent of the work is parallel?

Further reading

• Amdahl (1967): Validity of the single processor approach to achieving large scale computing capabilities (external)
• Gustafson (1988): Reevaluating Amdahl's Law (external)
• Introduction to Parallel Computing (LLNL) (external)