# Amdahl’s Law

Amdahl’s Law reveals the maximum speedup that can be expected from parallel algorithms given the proportion of parts that must be computed sequentially. It gives the speedup $S$ as

$$S\le \frac{1}{f+(1-f)/N}$$ |

Where $f$ is the fraction of the problem that must be computed sequentially and $N$ is the number of processors.

Note that as $f$ approaches zero, $S$ nears $N$, which we’d expect from a perfectly parallelizable algorithm^{}.

Title | Amdahl’s Law |
---|---|

Canonical name | AmdahlsLaw |

Date of creation | 2013-03-22 12:04:15 |

Last modified on | 2013-03-22 12:04:15 |

Owner | alozano (2414) |

Last modified by | alozano (2414) |

Numerical id | 17 |

Author | alozano (2414) |

Entry type | Theorem |

Classification | msc 68M20 |