Performance Measures

Speedup and Efficiency

Let $T_0$ be the execution time of the serial version of a problem and $T_p$ the execution time of the parallel version of the same problem to run on $p$ processors. The speedup $S_p$, algorithmic speedup $\bar{S}_p$ and efficiency $E_p$ are then given by

$$S_p={T_0 \over T_p}, \quad \bar{S}_p={T_1 \over T_p} \quad E_p={S_p \over p}$$

Since the parallelisation of a problem normally involves a certain overhead for synchronisation and/or communication, the efficiency is usually below 100

Amdahl's Law

If a fraction $s$ of the serial problem is inherently sequential and can not be parallelised, the highest possible speedup is limited by Amdahl's law.

$$S_p \leq {T_0 \over T^{ser}+{T^{par} \over p}} = {1 \over s+{1-s \over p}} \leq {1 \over s}$$

$$\mbox{with} \quad T_0=T^{ser}+T^{par}, \quad T^{ser}=s T_0, \quad T^{par}=(1-s) T_0$$