3.4.1 Speedup and Scaleup

Speedup :
Let

$t_1$ - system time of process A on one processor
$t_P$ - system time of process A on $P$ processors

$$\boxed{ S_P \;=\; \frac{t_1}{t_P} }$$ (3.1)

A Speedup of $P$ is desirable, i.e., $P$ processes are $P$ times faster than one.

The size $N_{ges}$ of the problem which have to be solved remains constant.

$$N_{ges} = \text{const.}\;\;\;\Longrightarrow\;\;\; N_i \sim \frac{1}{P}\;\;\forall i=\overline{1,P} \makebox[0pt]{}\enspace,$$


i.e., the more processors to be used, the less the individual processor has to do.

Ex.: Speedup-Worker

$P=1$ worker digs a pit of $1 m^3$ [$N_{ges}$] in $t_1 = 1h$ . How long [$t_P$] does it take $P=1000$ workers to perform the same work ?
$\longrightarrow$ The workers obstruct themselves mutually, a too high organization overhead is necessary.
$\Longrightarrow$ very little speedup.

Remark : The above theorem was said as a remark by Gene Amdahl in 1967
Interpretation of AMDAHL's Theorem (very old advertisement of IBM)

1% sequential part in algorithm $\Longrightarrow$ $S_{{\infty},max} = 100$

$P$	10	100	1000	10000
$S_P$	9	50	91	99

The use of more than 100 processors appears senseless, i.e., that the wages of 1000 workers are 10 times higher than the wages of 100 workers but the work did not even double itself.
$\Longrightarrow$ Discouraging
$\Longrightarrow$ End of lecture ?


Is AMDAHL's Theorem suitable for us ?

• Certain algorithms achieve even a speedup higher than $P$ on smaller processor numbers ($<20$) ! This is caused by a more intensive use of cache memory on the processors if the size of the local problem is getting smaller.
• AMDAHL's Theorem does not take into account any time for communication so that the real behavior of the speedup is even worse, see Fig. 3.16.
  

  Figure 3.16: Several Speedups

  

Consequence: The attainable speedup depends on the problem size.

Ex.: If each worker digs a pit of $1 m^3$ , then 1000 workers reach nearly a 1000 times higher performance during that hour. They all work on one huge project.

A scaling of the problem size with the number of processors is a way out to overcome AMDAHL's Theorem.

Scaleup :
Which increase in problem size is obtained on the parallel computer in comparison to the sequential case with comparable computing time.

Scaled Speedup :
Under the assumption that the parallel part of the algorithm is optimal with respect to the problem size (i.e.  ${\mathcal O}$($N$)) and introducing the notations
$s_1 + p_1$ - system time on a parallel computer
$s_1 + P\cdot p_1$ - system time on a sequential computer
we can define

$$\boxed{ S_C(P) \;=\; \frac{s_1 + P\cdot p_1}{s_1 + p_1} \stackrel{s_1+p_1=1}{=} s_1 + P(1-s_1) }$$

Interpretation : 1% sequential part $\Longrightarrow$ $S_C(P) \approx P$
because the serial part decreases with the problem size.
This theoretical forecast is confirmed in practice.

Remarks on Speedup/Scaleup

• (Scaled) Speedup may not be the only criteria for the usefulness of an algorithm, e.g., on can see in Fig. 3.17 that
  $S_P$(Gaußelimination) $>$ $S_P$ (pcg=preconditioned cg)
  BUT $t$(Gaußelimination) $»$ $t$(pcg) !!
• If one compares algorithms implemented on different parallel machines also the costs of that machine should be taken into account, e.g., cents per unknown variable.

Figure 3.17: system times for Gauß, cg, pcg [Dr. Pester, Chemnitz]