3.1 Einige Begriffe

Skalierbarkeit :  
Einfache Anpassung eines Programmes an eine real verfügbare Anzahl von Prozessoren.

Skalierbarkeit wird mittlerweile höher bewertet als höchste Effizienz (d.h. Gewinn an Rechenzeit durch Parallelisierung) auf einer speziellen Architektur.

Granularität :  
Größe der Programmabschnitte, welche ohne Kommunikation mit anderen Prozessoren ausführbar sind.

Feinkörniger Algorithmus : $\longrightarrow$ Systolische Felder [SIMD]

Bsp.: $\omega$-Jacobi-Iteration 

Laplace-Problem, mit dem 5-Punkte-Differenzenstern diskretisiert.

Hier treten keinerlei Datenabhängigkeiten innerhalb einer Iteration auf.
$\Longrightarrow$ Gut parallelisierbar (und vektorisierbar).

Bsp.: $\omega$-Gauß-Seidel-Iteration (vorwärts) 

Laplace-Problem, mit dem 5-Punkte-Differenzenstern diskretisiert.

$$\widehat{c} \makebox[0pt]{}_{i,j} \;:=\; c_{i,j} + \left({ ... ...-1} + 4 c_{i,j} - c_{i+1,j} - c_{i,j+1} \right] }\right) / 4$$

 

Abbildung 3.1: Gauß-Seidel im systolischen Feld

Die Werte $\widehat{c} \makebox[0pt]{}_{i-1,j}$ und $\widehat{c} \makebox[0pt]{}_{i,j-1}$ müssen berechnet sein, bevor $\widehat{c} \makebox[0pt]{}_{i,j}$ berechnet werden kann.

• Berechnung als Wellenfront {1,2,3,4-ter Schritt}.
  
  
• $m\times n$ systolisches Feld
  $\longrightarrow$ ($m+n-1$) Zeitschritte für eine Iteration nötig.
  $\longrightarrow$ mehrere Iterationen kompensieren diesen Overhead beim Startup.

1. Iteration :
Zeitgewinn : $\frac{t_{parallel}}{t_{seriell}} \,=\, \frac{m+n-1}{mn} \,\approx\, \frac{m+n}{mn} \,\ge\, \frac{2\sqrt{mn}}{mn} \,=\, \frac{2}{\sqrt{mn}}$
Ideal wäre aber ein Verhältnis $\frac{1}{P} \,=\, \frac{1}{mn}$ !

2. Iteration :

• Nach Initialisierung benötigt eine Iteration nur noch einen Zeitschritt.
• $k$-te (letzte) Iteration benötigt gleiche Zeit wie Initialisierung
  
  $$\begin{eqnarray*}\frac{t_{parallel}}{t_{seriell}} &=& \frac{2(m+n-1)+k-2}{k\cdo... ... \,\stackrel{k\mapsto \infty}{\longrightarrow}\, \frac{1}{mn} \end{eqnarray*}$$
  
  

Asymptotisch, d.h. bei vielen Iterationen wird der bestmögliche Zeitgewinn durch die Parallelisierung erzielt.

Grobkörniger Algorithmus : $\longrightarrow$ Mehrprozessorrechner [MIMD]
z.B. Blockvarianten von $\omega$-Jacobi- bzw. Gauß-Seidel-Iteration

Bemerkung : Heutzutage ist der Zeitbedarf für eine Kommunikation zwischen den Knoten/Prozessoren deutlich höher als für lokalen Speicherzugriff bzw. arithmetische Operationen. Daher sind grobkörnige Algorithmen für die Parallelisierung gefragt.

Funktionale Parallelität :  
Aufspaltung eines Algorithmus in funktional unterschiedliche, parallel abarbeitbare Teilschritte.

Bsp.: $E \,=\, (d \ast e \ast f + g + c) \ast b + a +h$

• seriell (von links nach rechts) 7 Zeitschritte
• parallel 2 Prozessoren 5 Zeitschritte
  
  
  
    

  Abbildung 3.2: Funktionale Parallelität

  
  
  

Aufgabe :

Teilen Sie obige Berechnungsvorschrift auf 3 Prozessoren auf. Nutzen Sie Umformungsregeln. (Ergebnis: 4 Zeitschritte)

• Im parallelen Fall können in Summe mehr arithmetische Operationen auftreten, trotzdem ist die parallele Variante (theoretisch) schneller.
• Funktionale Parallelität ist nur bedingt skalierbar. In obigem Beispiel ergeben mehr als 3 Prozessoren keine weitere Zeitersparnis.

Datenparallelität :  
Gleiche Programmabschnitte werden parallel über verschiedenen Datensegmenten ausgeführt.

• Voraussetzung: Einfache Aufteilung der Daten in Segmente (High Performance Fortran).
• (relativ) leicht skalierbar. Probleme treten bei komplexen Datenzusammenhängen auf, z.B. bei indirekter Adressierung (FEM).

Bsp.: Block-$\omega$-Jacobi 

• Aufteilung der Vektoren und (Block-)Matrizen.
• Mehrere Möglichkeiten der Datenaufteilung (siehe Abschnitt 5)

Spezialfall : Geometrische Parallelität.

Die Aufspaltung der Daten in Teilmengen entsprechend geometrischer Überlegungen über der räumlichen Anordnung der Objekte (Teilchen, Diskretisierungspunkte etc.), bzw. Ausnutzung von Nachbarschaftsbeziehungen bei Diskretisierungsmethoden wie FEM, FDM, FVM.