Theory
...states that, given P cores, the speed up for that number of cores is S(P)
\[S(P) = \frac{t_{total}(1)}{t_{total}(P)} = \frac{t_{serial} + t_{parallel}}{t_{serial}+\frac{t_{parallel}}{P}}\]
with \(t_{total}\) the total runtime, \(t_{serial}\) the time needed to run the serial part of the code and \(t_{parallel}\) the time needed to run the parallel part of the code.
Under this formulation, the maximum speedup, as \(P\rightarrow\infty\) is
\[S_{max} = \frac{t_{total}}{t_{serial}} = 1 + \frac{t_{parallel}}{t_{serial}}\]
Applying the law
- the output of monitor for 1 CPU contains the total runtime i.e. \(t_{serial}+t_{parallel}(1)\)
- log statements have been added to the source code such that the parallel runtime \(t_{parallel}(P)\) is recorded for P CPU’s
Thus, you obtain the predicted speed up \(S_p(P)\) and the observed speedup \(S_o(P)\)
\[S_p (P) = \frac{t_{serial} + t_{parallel}(1)}{t_{serial} + \frac{t_{parallel}(1)}{P}} \qquad S_o(P) = \frac{t_{serial} + t_{parallel}(1)}{t_{serial} + t_{parallel}(P)}\]
From these, one can derive the efficiency for P cores as
\[E_p(P)=\frac{S_p(P)}{P} \qquad\qquad\qquad E_o(P)=\frac{S_o(P)}{P}\]
External resources
Wikipedia
Reevaluating Amdahl’s Law and Gustafson’s Law