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.