English
Menu

Amdahl's Law vs Gustafson's Law: Key Differences

Both laws estimate how much faster a program gets when you add processors, but they rest on different assumptions. Amdahl's law fixes the problem size and asks how fast the same work can be finished, so the part that cannot be parallelized sets the upper limit on speedup. Gustafson's law fixes the run time and solves a larger problem as processors are added, so speedup grows nearly in proportion to the number of processors. The two do not contradict each other; they answer different questions.

AspectAmdahl's lawGustafson's law
What is fixedProblem size (total amount of work)Run time (amount of work per processor)
QuestionHow much faster can the same problem be solved?How much larger a problem can be solved in the same time?
Formula (N is the number of processors)S = 1 / ((1 − p) + p / N)S = s + (1 − s) × N = N − s × (N − 1)
How the fraction is measuredp is the fraction of time taken by the parallelizable part when run on one processors is the fraction of time taken by the serial part when run in parallel on N processors
As N increasesLevels off at 1 / (1 − p)Keeps growing nearly in proportion to N
Worked exampleWith p = 0.95, about 17× at N = 100; even with infinite N, the limit is 20×With s = 0.05, about 95× at N = 100
Corresponding scalingStrong scalingWeak scaling
OutlookPessimistic. A small serial part sets the upper limitOptimistic. Parallelism pays off if the problem is made larger
Examples where it appliesWhen you want to process a fixed-size input quickly: processing a single image, interactive responses, etc.Simulations with finer grids, or when you want to process larger data or models in the same time
Not included in eitherCommunication and synchronization overhead, load imbalance, insufficient memory bandwidthCommunication and synchronization overhead, load imbalance, insufficient memory bandwidth

Figures are typical orders of magnitude and vary by process generation and product.

When to use which

Amdahl's law
When the problem size is fixed and you want to shorten the response time. Use it to estimate the limit of parallelization and decide whether to reduce the serial part.
Gustafson's law
When the problem can grow along with the number of processors. Use it to estimate the value of solving finer and larger problems in large-scale simulations and data processing.
Reporting results
When reporting parallel performance, state clearly whether it was measured with strong or weak scaling. Under different conditions, the speedup of the same program can differ greatly.

FAQ

Don't the two laws contradict each other?

No. Amdahl's law fixes the problem size and Gustafson's law fixes the run time, so they answer different questions. The serial fraction is also measured differently: by the time on one processor in Amdahl's law and by the time on N processors in Gustafson's law, so you cannot plug the same number into both and compare.

If 90% can be parallelized, why is the maximum only 10×?

Because the remaining 10% does not get shorter no matter how many processors you add. Even as the time of the parallel part approaches zero, the total time cannot drop below 10% of the original, so the speedup levels off at 1 / 0.1 = 10×.

Why is the actual speedup smaller than these laws predict?

Neither law includes communication and synchronization between processors, load imbalance, or insufficient shared memory bandwidth. These effects grow as processors are added, and parallel efficiency drops.

Which law should I apply to my program?

If the input size is fixed and you want results sooner, use Amdahl's law. If you want to handle finer grids or larger data as processors are added, use Gustafson's law. The same program can fall under either law depending on how it is used.

Check your understanding

If 90% of a program can be parallelized, what is the theoretical maximum speedup when it runs on an unlimited number of processors?

  1. A10 times
  2. B90 times
  3. CInfinite
Show answer and explanation

Answer: A. 10 times

Amdahl's law gives speedup as 1/((1 − p) + p/N) for parallel fraction p and N processors. With p = 0.9 the limit as N grows is 1/0.1 = 10×, and even N = 10 yields only about 5.3×. Even a small serial portion caps the speedup, so reducing it is crucial. Gustafson's law takes the complementary view of scaling the problem size to grow the parallel part.

Which lesson about how to approach performance improvement follows best from Amdahl's law?

  1. APrioritize speeding up the parts that take most of the time (the common case)
  2. BSpeed up rarely executed parts first
  3. CSpeeding up any part has the same effect on the whole
Show answer and explanation

Answer: A. Prioritize speeding up the parts that take most of the time (the common case)

Making a part that uses 1% of the time infinitely fast speeds up the whole by only about 1%. Doubling the speed of a part that uses 80% yields about 1.7× overall. So the basic approach is to find where time is spent, for example with a profiler, and improve that first. "Make the common case fast" is a principle used again and again in computer design.

  1. What idea does Gustafson's law express?
  2. What is the difference between strong scaling and weak scaling in evaluating parallel computing?
  3. How is speedup, which expresses a performance improvement, calculated?

Practice Performance Analysis questions

Key terms explained

Amdahl's law
The law that when only part of a program is parallelized, overall speedup is limited by the part that cannot be. For example, parallelizing 90% gives at most a 10x speedup.
Gustafson's law
The observation that when processors are added and the problem is enlarged, the parallel fraction grows, giving gains nearly proportional to processor count.
Strong scaling
Parallel performance evaluation that fixes problem size and measures how much time drops as processors are added.
Weak scaling
Parallel performance evaluation that fixes problem size per processor while growing the total and checks whether time stays constant.
Parallel efficiency
Parallel speedup divided by the number of processors, indicating how effectively the cores are used.

Related comparisons