# 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 |