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
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(N) = (s + \frac p N) * T(1)}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Speedup S(N)} = \frac {T(1)} {T(N)} = \frac 1 {s + \frac {1-s} N}}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Load Balance LB} = \frac {avg(tcomp)} {max(tcomp)}}