6.1 Amdahl's Law

Amdahl's Law

Amdahl’s Law is a principle in computer architecture that defines the potential speedup $S$ in the execution of a task when only a certain proportion of the task can be parallelized. Formally,
$S=\frac{1}{(1-P)+\frac{P}{N}},$
where $N$ is the factor by which the parallelized part is sped up, and $P\in [0,1]$ is the proportion of the total task runtime that can be parallelized.

Intuition

Consider the two parts of the denominator:

• $1-P$ represents the proportion of the total task runtime that cannot be parallelized.
• $\frac{P}{N}$ represents the proportion of total task runtime of $P$ when parallelized.
  Together, $(1-P)+\frac{P}{N}$ represent the proportion of time that the whole task when parallelized as a fraction of the not parallelized task time. As such, its inverse represents the speedup when compared to the original speed.

Therefore, in order to speed up your code, you must know which parts of your code make the program slower.

Properties

(Constraint) $S\le \frac{1}{1-P}$

As $N\to \infty$, $S\to \frac{1}{1-P}$, such that ${\lim }_{N\to \infty }S=\frac{1}{1-P}$.

Examples

Example