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: