Enter the fraction of a program that can run in parallel and the number of processors (cores) to see how much faster the whole program gets under Amdahl's law. A log-log chart compares this fixed-size limit with Gustafson's view, in which the problem grows with the number of processors.
The thin dashed line is ideal linear speedup (N times), the blue line is Amdahl's law and the green line is Gustafson's law. Both axes are logarithmic. Overheads from communication, synchronization and load imbalance are not included, so real speedups are usually lower.
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
Take the run time on one processor as 1 and let p be the fraction that can be parallelized. With N processors the parallel part shrinks to p/N, but the serial part (1 − p) stays the same, so the speedup is S = 1/((1 − p) + p/N). However large N becomes, the serial part never disappears, so the speedup is capped at 1/(1 − p). With the defaults of p = 95% and N = 16, S ≈ 9.14 and the limit is 20. Just 5% of serial work decides how fast the program can ever run.
Parallel efficiency, E = S/N, shows how much useful work each processor does. With the defaults it is 9.14 ÷ 16 ≈ 57.1%, so over 40% of the processing capacity is effectively idle. On the chart the blue line follows the dashed ideal line at small N, then bends away and flattens toward the limit. Keeping p = 95% and raising N to 64 gives S ≈ 15.4 and an efficiency of only about 24%. The point where efficiency starts to drop quickly is a practical guide to how many processors are worth their cost.
Amdahl's law assumes a fixed problem size while processors are added, which is called strong scaling. Gustafson's law instead grows the problem with the processor count and solves it in the same time, which is called weak scaling, giving S = (1 − p) + p·N. When a simulation grid is refined, for example, only the parallel work grows, so the speedup rises almost in proportion to N. Note that p here is the fraction of time measured on the N-processor run, which is not the same definition as the p in Amdahl's law.
Real programs add thread start-up, data communication, waiting at locks and barriers, and load imbalance, so actual speedups fall below Amdahl's prediction. Reducing the serial part is often more effective than adding cores, so the usual practice is to profile first and then parallelize the hot spots. On GPUs, data transfers to and from the host and kernel launches act as serial parts too. In chip design, combining a few high-performance cores with many small cores is a way to speed up both the serial and the parallel parts of a workload.
Practice performance questions
Answer: B. 1.6×
The new time is the unchanged 50% (0.5) plus the accelerated 50% (0.5 ÷ 4 = 0.125), totaling 0.625. The speedup is 1 ÷ 0.625 = 1.6×. No matter how much the improved part is accelerated, the other 50% remains, so the overall speedup can never exceed 2×. Large overall gains require finding and improving the parts that take most of the time.
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.
Answer: A. When adding processors, also enlarging the problem increases the parallel fraction, yielding large speedups
Amdahl's law considers adding processors to a fixed-size problem, so the serial part caps the speedup. Gustafson's law instead assumes that with more processors one solves a larger problem in the same time. Enlarging the problem, for example with a finer simulation grid, grows the parallel part and shrinks the serial fraction, giving gains nearly proportional to processor count.
Answer: A. 75%
Parallel efficiency is speedup divided by core count and indicates how effectively the cores are used. 6 ÷ 8 = 75%, three quarters of the ideal 8×. The remaining 25% is lost to synchronization waits, load imbalance, communication and contention for memory bandwidth. Efficiency tends to fall as cores are added, so the core count is chosen by how well efficiency holds up.
Under Amdahl's law the limit is 1/(1 − 0.9) = 10 times. Even with 16 processors the speedup is only 1/(0.1 + 0.9/16) = 6.4, an efficiency of 40%. Unless the remaining 10% of serial work is reduced, the speedup can never exceed 10.
No. Amdahl's law covers strong scaling with a fixed problem size, while Gustafson's law covers weak scaling, where the problem grows with the number of processors. Which view applies depends on whether you want to solve the same problem faster or a bigger problem in the same time.
Yes. When adding processors shrinks each processor's share of the data enough to fit in its cache, memory accesses get faster and superlinear speedup can appear. Amdahl's law does not model such effects.
Amdahl's law Gustafson's law Speedup Parallel efficiency Strong scaling Weak scaling