3.4.1 Speedup und Scaleup

Speedup :  
Sei

$t_1$ - Ausführungszeit des Algorithmus A auf einem Prozessor
$t_P$ - Ausführungszeit des Algorithmus A auf $P$ Prozessoren

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

Wünschenswert ist ein Speedup von $P$, d.h. $P$ Prozessoren sind $P$-mal schneller als ein einzelner.

Die Größe des zu lösenden Problems $N_{ges}$ bleibt konstant.

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


d.h. je mehr Prozessoren verwendet werden, desto weniger hat der einzelne Prozessor zu tun.

Bsp.: Speedup-Arbeiter 

$P = 1$ Arbeiter hebt in $t_1 = 1h$ eine Grube von $1\,m^3$ [$N_{ges}$] aus. Wie lange [$t_P$] benötigen $P=1000$ Arbeiter um dieselbe Arbeit zu verrichten ?
$\longrightarrow$ Die Arbeiter behindern sich gegenseitig, ein zu hoher Organisationsaufwand [Overhead] ist notwendig.
$\Longrightarrow$ sehr geringer Speedup.

    Bemerkung : Obiger Satz geht auf eine Bemerkung von Gene Amdahl im Jahre 1967 zurück
Interpretation des AMDAHLschen Gesetzes (sehr alte Reklame von IBM)

1% serieller Anteil im Algorithmus $\Longrightarrow$ $S_{{\infty},max} = 100$

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

Mehr als 100 Prozessoren erscheinen sinnlos (d.h. daß von 100 auf 1000 Arbeiter zwar der 10-fache Lohn bei nicht einmal verdoppelter Leistung gezahlt wird).
$\Longrightarrow$ Entmutigend
$\Longrightarrow$ Vorlesungsende ?


Ist das AMDAHLsche Gesetz für uns relevant ?

• Bei kleineren Prozessorzahlen ($<20$) ist bei bestimmten Algorithmen sogar ein Speedup $>P$ erreichbar ! Dies kann z.B. durch das verbesserte Cacheverhalten der Prozessoren mit kleiner werdender Teilproblemgröße oder durch die Ordnung des arithmetischen Aufwands des lokalen Algorithmus mit weniger Daten auftreten.
• Da das AMDAHLsche Gesetz keine Kommunikationszeiten berücksichtigt, sieht das reale Verhalten des Speedup noch schlechter aus, siehe Abbildung 3.16.
  
  
    

  Abbildung 3.16: Realer Speedup

  
  
  

Folgerung : Der erreichbare Speedup hängt von der Problemgröße ab.

zu Bsp.: Wenn jeder Arbeiter eine Grube von $1\,m^3$ aushebt, so schaffen 1000 Arbeiter in einer Stunde fast die 1000-fache Leistung da sie sinnvoll eingesetzt sind.

Ein Skalierung der Problemgröße mit der Prozessoranzahl führt uns aus dem Dilemma des AMDAHLsche Gesetzes.

Scaleup :  
Welcher Zuwachs an Problemgröße wird auf dem Parallelrechner im Vergleich zum sequentiellen Fall bei vergleichbarer Rechenzeit erzielt.

Scaled Speedup :  
Unter der Annahme, daß der parallele Teil des Algorithmus optimal bzgl. der Problemgröße ist (d.h.  ${\mathcal O}$($N$)) gilt mit den Vereinbarungen
$s_1 + p_1$ - Ausführungszeit auf dem Parallelrechner
$s_1 + P\cdot p_1$ - Ausführungszeit auf dem seriellen Rechner

$$\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) }$$ (3.2)

Interpretation : 1% serieller Anteil $\Longrightarrow$ $S_C(P) \approx P$
da der serielle Anteil mit der Problemgröße abnimmt.
Diese theoretische Voraussage wird in der Praxis bestätigt.

Bemerkungen zum Speedup/Scaleup

• (Scaled) Speedup darf nicht einziges Bewertungskriterium sein, z.B. ist in Abbildung 3.17 ersichtlich, daß
  $S_P$(Gauß Elimination) $>$ $S_P$ (pcg=vorkonditionierter cg)
  ABER $t$(Gauß Elimination) $>>$ $t$(pcg) !!
• Fairerweise müßten bei der Bewertung auch die Kosten der Rechner in Betracht gezogen werden, z.B. die Kosten pro berechnete Unbekannte.

  

Abbildung 3.17: Rechenzeitvergleich Gauß, cg, pcg [Dr. Pester, Chemnitz]