View source for Amdahl's Law

Amdahl's law characterizes the speedup of a parallel program. It assumes perfect [[Load_Balancing|load balance]], meaning that all threads / processes do the exact same amount of work and therefore all finish simultaneously.

__TOC__

== Formula ==

s: serial part of the application

p: parallel part of the application

N: number of processors

: <math>T(N) = (s + \frac p N) * T(1)</math>

: <math>\text{Speedup S(N)} = \frac {T(1)} {T(N)} = \frac 1 {s + \frac {1-s} N}</math>

: <math>\text{Efficiency E(N)} = \frac {S(N)} N = \frac {\frac 1 {s + \frac {1-s} N}} N = \frac 1 {s(N-1)+1}</math>


Amdahl's law is based on perfect load balance. Generally, load balance is defined as follows with tcomp being the time a processor spent with actual work.

: <math>\text{Load Balance LB} = \frac {avg(tcomp)} {max(tcomp)}</math>