3.4.3 Kommunikationsaufwand

Die in den beiden vorangegangenen Abschnitten dargestellten Speedup- und Effizienzbetrachtungen vernachlässigen die zur Datenkommunikation benötigte Zeit.

Sei

$t_{\mathrm{Startup}}$ - Startupzeit (Latency)
$t_{\mathrm{Word}}\;\;$ - Zeit für die Übertragung eines Wortes (Bandweite)


so ergibt sich die Zeit für eine Kommunikation mit $N$ Byte Information :

$$\boxed{ t_k \;=\; t_{\mathrm{Startup}} + N\cdot t_{\mathrm{Word}} }$$ (3.6)

Nach Formel (3.8) und praktischer Erfahrung ist das Senden einer langen Nachricht besser als das Senden mehrerer, entsprechend kurzer, Nachrichten.
Betriebssystem oder Hardware teilen große Datenpakete in kleinere auf. Die konkrete Größe hängt vom Hersteller ab ($>\,1kByte$).

 

Tabelle 3.1: Vergleich Latency und Bandbreite

Maschine/OS	Latency	Bandbreite
Xplorer/Parix	100 $\mu$s	(gemessen) 1.3 MB/sec
		(peak) 8.8 MB/sec
T9000	10 $\mu$s	(progn.) 80 MB/sec
Intel iPsc/860	82.5 $\mu$s	2.5 MB/sec
Convex SPP-1	0.2 $\mu$s	16.0 MB/sec
nCube2		71.0 MB/sec
Cray TT3D	6 $\mu$s	120.0 MB/sec
IntelParagon		200.0 MB/sec
Origin2000		(real) 680.0 MB/sec

 

Die erreichte Bisektionsbandweite einer Origin2000 wächst linear bis zu zu 10 GB/sec auf 32 Prozessoren, verbleibt bei diesem Wert auf 64 Prozessoren und verdoppelt sich bei 128 Prozessoren. Es gibt Algorithmen die nicht unbedingt parallelisierungswürdig sind, obwohl sie so aussehen. Bsp.: FFT-feinkörnig 

Berechnung der FFT-Koeffizienten $e^{2\pi i \frac{k}{N}}$ $k=\overline{0,N-1} \makebox[0pt]{}$

Sei $t_x$ die Zeit zur Berechnung eines Koeffizienten, dann ist
seriell : $t_{\mathrm{seriell}} \;=\; N\cdot t_x$ für einen Vektor der Länge $N$.
parallel :

a) Lokal einen Teilvektor der Länge  $\frac{N}{P}$ ausrechnen $\frac{N}{P}\cdot t_x$ .
b) Datenaustausch (alle benötigen das Ergebnis)
${\mathcal O}(N)\cdot t_{\mathrm{Word}} + \underbrace{{\mathcal O}(\log{P})}_{\mbox{\tiny bester Fall}}\cdot t_{\mathrm{Startup}}$

$t_{\mathrm{par}} \;=\; \frac{N}{P}\cdot t_x + {\mathcal O}(N)\cdot t_{\mathrm{Word}} + {\mathcal O}(\log{P})\cdot t_{\mathrm{Startup}}$



Frage : Wann ist $t_{\mathrm{seriell}} > t_{\mathrm{par}}$ ?
$\longrightarrow$ Nur wenn $t_x$ groß genug ist, d.h. bei kleinen $t_x$ lohnt sich die auch bei sehr guter Latency und Bandbreite die Parallelisierung nicht.
$\longrightarrow$ Verhältnis $\frac{\mbox{{\scriptsize Arithmetik}}}{\mbox{{\scriptsize Kommunikation}}}$ sollte möglichst groß sein.
$\longrightarrow$ Grobkörnige Algorithmen bevorzugen (siehe Abschnitt (6.4)).