proof of Amdahl’s Law

Suppose an algorithmMathworldPlanetmath needs n operations to compute the result. With 1 processor, the algorithm will take n time units. With N processors, the (1-f)n parallelizable operations will take (1-f)nN time units and the remaining fn non parallelizable operations will take fn time units for a total running time of fn+(1-f)nN time units. So the speedup S is nfn+(1-f)nN=1f+1-fN.

Title proof of Amdahl’s Law
Canonical name ProofOfAmdahlsLaw
Date of creation 2013-03-22 13:10:36
Last modified on 2013-03-22 13:10:36
Owner lieven (1075)
Last modified by lieven (1075)
Numerical id 5
Author lieven (1075)
Entry type Proof
Classification msc 68M20