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

According to Amdahl's law, the speedup can never become infintely large. If that were possible, a program with 100 processes or threads would be 100x faster than the serial execution. However, the speedup is limited by the serial part of the program, whose time remains constant. Another important aspect is that the more threads or processor the program is run with, the more overhead will be introduced by managing threads etc.

In the formulas below, T(N) describes the runtime of a program with N threads / processes.

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)}}$