How to use the amdahl's law speedup calculator
- Choose what to find: the speedup, the parallel share from a measured speedup, or the cores needed for a target speedup.
- For the speedup, enter the parallel share of the work in percent and the number of processors.
- For the other two, enter the measured or wanted speedup together with the processors or the share.
- Read the speedup, the efficiency, the best speedup that is possible with unlimited processors, the Gustafson estimate and a table for more processors.
Formula
Amdahl speedup S = 1 / ((1 - p) + p / n), with p the parallel share and n the processors
Best possible speedup = 1 / (1 - p), as n grows without limit
Efficiency = S / n
Gustafson speedup = n - (1 - p) x (n - 1), when the problem grows with the machine
Amdahl's law holds the problem size fixed and shows that the serial part limits the gain. Gustafson's law lets the problem grow with the machine and gives a more hopeful figure.
A program that is 90 percent parallel on 8 processors
The serial share is 0.1 and the parallel share on 8 processors is 0.9 / 8 = 0.1125, so the run time is 0.2125 of the original. The speedup is 1 / 0.2125 = 4.7059 and the efficiency is 4.7059 / 8 = 58.82 percent.
No number of processors can beat 1 / 0.1 = 10. If the problem grows with the machine, the Gustafson speedup is 8 - 0.1 x 7 = 7.3. A program that is 99 percent parallel on 64 processors reaches about 39.26. A measured speedup of 6 on 16 processors points to a parallel share of 88.89 percent, and a speedup of 5 at 90 percent needs 9 processors.
Why the serial part matters
Even a small serial part dominates once there are many processors. With 5 percent serial work, 100 processors give a speedup of about 17 and 1,000 give about 20, with a ceiling of 20. The table on the page shows how the gain flattens out as you add processors, and how the efficiency drops.
Real programs also pay for communication, waiting and load imbalance, which Amdahl's law does not include. The measured speedup is usually lower than the prediction. The CPU scheduling simulator shows how a scheduler shares processors among jobs.
Finding the parallel share
If you can time a program on one processor and on many, the page works back to the parallel share that explains the speedup. That share is an effective figure, which includes losses, and it is a good way to compare versions of a program. For more on how the memory system limits speed, see the cache replacement policy simulator and the sorting algorithm operation counter.
Assumptions and limits
- The work is split into a part that is fully serial and a part that scales perfectly across processors.
- The problem size stays fixed in Amdahl's law and grows with the machine in Gustafson's law.
- The parallel share is a fraction of the single processor run time, entered as a percent.
- Costs of communication and imbalance are not modeled.
Frequently asked questions
What is Amdahl's law?
It says the speedup from adding processors is limited by the part of the work that cannot be run in parallel. The serial share sets a ceiling of one over that share.
How is Gustafson's law different?
It assumes you use extra processors to solve a larger problem in the same time. Then the serial part is a smaller share of the total, and the speedup is closer to linear.
How many cores do I need?
Choose cores needed and enter the share and the target. The page tells you if the target is above the ceiling, in which case no number of cores will reach it.
What is efficiency?
It is the speedup divided by the number of processors. It falls as you add processors, because each added one helps less.