Anwendung paralleler Iterationsverfahren auf Gitter

Bei der Simulation physikalischer Vorgänge ist es häufig notwendig, die auftretenden Differentialgleichungen numerisch zu lösen. Dazu wird eine Diskretisierung des betrachteten Problems durchgeführt, auf der dann die Differentialgleichungen durch einfache Näherungen ersetzt werden. Dies führt häufig zu sehr regelmäßigen Gleichungssystemen, die dann mit geeigneten Iterationsverfahren gelöst werden. Zum Beispiel führt die Bestimmung des Temperaturverlaufs in einem Wasserbad mit vorgegebenen Randwerten zu einer Diskretisierung mit 2-dimensionaler Gitterstruktur.

Vorgabe für Temperaturverlauf im Wasserbad

Die Temperatur u_ij wird mit Hilfe der vier Nachbartemperaturen modifiziert:

Zur Synchronisation des Datenaustausches wird eine Partitionierung des 2D-Gitters in schwarze und weiße Prozessoren durchgeführt (Schachbrettfärbung).

Schachbrettfärbung eines 6 × 6 Prozessorgitters

Der parallele Algorithmus lautet dann:

REPEAT
     FOR ALL 0 $\leq$ i,j $\leq$ n - 1 DO IN PARALLEL
         P_ij : IF weisser Prozessor
             THEN
                 empfange vier schwarze Nachbarwerte;
                 update u_ij ;
                 sende u_ij an vier schwarze Nachbarn;
                 warte;
             ELSE
                 sende u_ij an vier weisse Nachbarn;
                 warte;
                 empfange vier weisse Nachbarwerte;
                 update u_ij ;
             END

UNTIL fertig