Parallel Performance Analysis: Amdahl's Law
CS 441 Lecture, Dr. Lawlor
Users care about speed. We want the code to run faster, so define:
speedup = old runtime / new runtime
If we normalize the old runtime to be "1", and define the new runtime as a combination of serial and parallel:
new runtime = serial code + parallel code
We can then define:
N: number of CPUs running in parallel
P: fraction of program that runs in parallel
Then assuming perfect speedup on the parallel code:
new runtime = (1-P) + P/N
speedup = 1 / ((1-P) + P/N) = N/((1-P)*N + P)
This is Amdahl's Law, which tells you two things:
- If N is large, P better be very close to 1, or the (1-P) factor will dominate the new runtime.
- While serial code is running, N processors are sitting there waiting, and only one is working.