Amdahl's Law

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

Formula

s: serial part of the application

p: parallel part of the application

N: number of processors

$T(N)=(s+{\frac {p}{N}})*T(1)$

${\text{Speedup S(N)}}={\frac {T(1)}{T(N)}}={\frac {1}{s+{\frac {1-s}{N}}}}$

${\text{Efficiency E(N)}}={\frac {S(N)}{N}}={\frac {\frac {1}{s+{\frac {1-s}{N}}}}{N}}={\frac {1}{s(N-1)+1}}$

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.

${\text{Load Balance LB}}={\frac {avg(tcomp)}{max(tcomp)}}$