AmdahlsLaw 2001-12-22 05:45:22 2006-10-24 10:33:44 Theorem parallel computation \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{xypic} 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. % dummy change