|
|
|
|
proof of Amdahl's Law
|
(Proof)
|
|
|
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}}$
|
"proof of Amdahl's Law" is owned by lieven.
|
|
(view preamble | get metadata)
Cross-references: speedup, running, parallelizable, units, operations, algorithm
This is version 2 of proof of Amdahl's Law, born on 2002-11-26, modified 2005-03-12.
Object id is 3622, canonical name is ProofOfAmdahlsLaw.
Accessed 3978 times total.
Classification:
| AMS MSC: | 68M20 (Computer science :: Computer system organization :: Performance evaluation; queueing; scheduling) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|