PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] 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)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 4196 times total.

Classification:
AMS MSC68M20 (Computer science :: Computer system organization :: Performance evaluation; queueing; scheduling)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)