# 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 ProofOfAmdahlsLaw 2013-03-22 13:10:36 2013-03-22 13:10:36 lieven (1075) lieven (1075) 5 lieven (1075) Proof msc 68M20