3.4.2 Effizienz

Parallele Effizienz :  
Hier sei nur die Formel für die klassische (parallele) Effizienz angegeben, die skalierte Effizienz berechnet sich analog.

$$\boxed{ E_{P,par}\;=\; \frac{S_P}{P} }$$ (3.3)

Eine Effizienz von 100% wäre ideal, d.h. die Verwendung von $P$ Prozessoren beschleunigt die Programmabarbeitung auf das $P$-fache. Die parallele Effizienz für den Scaleup läßt sich explizit angeben :

$$E_{C,par} \;=\; \frac{S_C(P)}{P} \;=\; \frac{s_1+P(1-s_1)}{P}\;=\; 1-s_1+\frac{s_1}{P} > 1- s_1$$

$\Longrightarrow$ Ganz leicht sinkende Effizienz bei wachsender Prozessorzahl.
$\Longrightarrow$ Effizienz jedoch mindestens so hoch wie paralleler Anteil im Programm.

$\Longrightarrow$ Vorlesung hat doch einen Sinn.


Numerische Effizienz :  
Setzt den schnellsten seriellen Algorithmus mit dem schnellsten parallelen Algorithmus (ausgeführt auf einem Prozessor) ins Verhältnis.

$$\boxed{ E_{num}\;=\; \frac{t_{parallel}}{t_{seriell}} }$$ (3.4)

Somit ergibt sich die (skalierte) Effizienz eines parallelen Algorithmus

$$\boxed{ E\;=\; E_{par} \cdot E_{num} }$$ (3.5)

Obige Scaled Speedup- und Effizienzaussagen sind sehr optimistisch.

Aber :

In Formel (3.4) ist stillschweigend eine Gleichverteilung der Gesamtaufgabe auf alle Prozessoren vorausgesetzt. Dies ist in der Praxis a priori oder im Laufe der Rechnung oft nicht der Fall. Gleichzeitig wird in Formel (3.4) keinerlei Verlust durch die Kommunikation während der Programmabarbeitung berücksichtigt.
$\Longrightarrow$ Praktische Effizienz liegt unter der theoretischen.



Loadbalancing :  
Versuch der gleichmäßigen Auslastung der Prozessoren.

Möglichkeiten dem idealen Loadbalancing nahezukommen :

• Statisches Loadbalancing [a priori]:
  • Aufteilung der Netze, Daten nach Abzählung ist zu ineffektiv und nutzt keinerlei, wie auch immer geartete, Nachbarschaftsbeziehungen aus.
  • Aufteilung der Daten nach gewissen Bisektionstechniken (z.B. Koordinatenbisektion, rekursive spektrale Bisektion, Kerningham-Lin-Algorithmus [TK96].
    $\longrightarrow$ Je besser die Datenverteilung (auch in Bezug auf die Kommunikation), desto mehr Aufwand muß bei den einzelnen Bisektionstechniken betrieben werden.
    $\longrightarrow$ Besonders geeignet für Optimierungsprobleme, Verteilung der Grobnetzes in Mehrgitteralgorithmen.
• Dynamisches Loadbalancing [Umverteilung während der Rechnung] [Bas96] :
  • Hoher Aufwand für Lastverteilung (Heuristische Vorgehensweise notwendig).
  • Bei hoch adaptiven Verfahren notwendig.
• Neue parallele Betriebssysteme ??