proof of Amdahl’s Law

Suppose an algorithm 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 $\frac{(1-f)n}{N}$ time units and the remaining $fn$ non parallelizable operations will take $fn$ time units for a total running time of $fn+\frac{(1-f)n}{N}$ time units. So the speedup $S$ is $\frac{n}{fn+\frac{(1-f)n}{N}}=\frac{1}{f+\frac{1-f}{N}}$.

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