7.2 Parallele Ausführung

Wir besprechen zunächst die Implementierung der zwei Varianten des con-Sprachkonstrukts.

con S1; ...; Sn end
bzw.
con i=1 to n do S(i) end

Die Schleifenvariante von con wird wie schon angedeutet durch die `parallel for'-Direktive implementiert.

   //omp parallel for
      for (int i=0; i < n; i++) {
          S(i);
      }
Wobei `S(i)' die Implementierung des Statements S(i) darstellt. Die OpenMP-Direktiven wirken jeweils auf das nächste Statement oder (bei Java) auf den nächsten in geschweifte Klammern `{...}' eingeschlossenen Block. Für FORTRAN gibt es ein `omp end parallel', um das Ende des parallelen Blocks anzuzeigen.

Die Semantik entspricht in etwa der der con-Schleife. `parallel for' terminiert, nachdem alle `S(i)' terminiert sind. Allerdings kann dieses Verhalten durch den Zusatz `nowait' zur Direktive abgestellt werden. Dann muss man sich auf anderen Wegen von der Terminierung überzeugen.

Für die Sichtbarkeit von Variablen gelten zunächst die Regeln der con-Schleife. Variablen, die außerhalb (vor) der Direktive deklariert sind, sind auch innerhalb von `parallel for' wie globale Variablen sichtbar. Das heißt, der Zugriff darauf muss gegebenenfalls synchronisiert werden. Es gibt eine Reihe von Zusätzen (so genannte Klauseln) zur Direktive, mit denen sich für einzelne (oder alle) Variablen andere Sichtbarkeitsbereiche einstellen lassen.

Ein Unterschied zur con-Schleife besteht in der Art, wie die einzelnen Statements auf Prozessoren oder Threads aufgeteilt werden. Bei `con i=1 to n do' bezeichnet n die Anzahl der parallelen Tasks die verwendet werden sollen. Bei `parallel for' bezeichnet `n' die Anzahl der Schleifendurchgänge unabhängig von der Anzahl der zu erzeugenden Threads. Der Grad der Parallelisierung wird durch die Anzahl der CPUs bzw. genauer durch die Anzahl der eingestellten Threads in der `jomp.threads'-Property bestimmt. Bei der Ausführung des Java-Programms kann zum Beispiel mit `-Djomp.threads=4', der Grad der Parallelität auf 4 eingestellt werden.

Aufgabe 37   Die Multiplikation von Matrizen (siehe Seiten [*] und [*]) lässt sich mit OpenMP sehr leicht parallelisieren. Es ist nur die äußere Schleife mit der `parallel for'-Direktive zu versehen.
   public void parmult(double[][] C, 
                       double[][] A, 
                       double[][] B) {
   //omp parallel for
      for (int i=0; i < A.length; i++) {
          for (int j=0; j < B[0].length; j++) {
              double c = 0.0;
              for (int k=0; k < B.length; k++) {
                  c += A[i][k] * B[k][j];
              }
              C[i][j] = c;
          }
      }
   }
Im Vergleich mit dem durch Threads parallelisierten Programm 3.1 auf Seite [*] brauchen wir keine Klasse, die das `Runnable'-Interface implementiert und die die inneren zwei for-Schleifen enthält. Auch müssen wir nicht selbst die Threads erzeugen, starten und auf deren Beendigung warten.

Die einfache Variante von con wird etwas aufwendiger durch die `parallel sections'-Direktive implementiert.

   //omp parallel sections
      {
   //omp section
          S1;
   ...
   //omp section
          Sn;
      }
Wobei S1, ..., Sn die Implementierung der Statements S1, ..., Sn darstellen. Die OpenMP-Direktive wirkt hier auf den nächsten in geschweifte Klammern `{...}' eingeschlossenen Block. Die section-Direktiven dienen zur Trennung der einzelnen parallel auszuführenden Programmteile.

Bezüglich der Sichtbarkeit von Variablen und der Aufteilung der Programmteile auf Prozessoren bzw. Threads gelten die Aussagen wie für die `parallel for'-Direktive.

7.2.1 Sichtbarkeit von Variablen

Die Sichtbarkeit von Variablen in den `parallel'-Direktiven kann durch folgende Zusatzklauseln bestimmt werden.

shared:
Entspricht der Voreinstellung, bei der die entsprechenden Variablen in allen Threads sichtbar und änderbar sind.
private:
Damit werden die entsprechenden Variablen in allen Threads verschieden und lokal, sie sind uninitialisiert und ihre Werte sind nach der Beendigung von `parallel' verloren.
firstprivate:
Wie bei `private', nur werden die Variablen mit dem Wert, den sie vor `parallel' haben, initialisiert.
lastprivate:
Wie bei `private', nur wird der eine Wert der letzten Iteration, den diese verschiedenen Variablen haben, nach dem Ende von `parallel' in die globale Variable übernommen.
threadprivate:
Hierbei sind die entsprechenden Variablen in allen Threads verschieden, aber global, die Variablen sind initialisiert, aber ihre Werte sind nach der Beendigung von `parallel' nicht mehr erreichbar. Diese Klausel ist bei Jomp derzeit nicht implementiert.
In den Büchern [LB00,Lea00a] gibt es Kapitel über Thread-Specific Data (TSD) und wie damit `threadprivate' zu realisieren ist. In Java 2.0 bzw. JDK 1.2 wurde die Klasse java.lang.ThreadLocal hinzugefügt, die genau dieses leistet.

Diese Klauseln können in beliebiger Reihenfolge und Anzahl zu den anderen Direktiven hinzugefügt werden. Zur Illustration betrachten wir folgendes Beispiel:

   int a, b, c, d, e;
   a = 1; b = 1; c = 1; d = 1; e = 1;
   (0)
   //omp parallel ...
   //omp firstprivate(a) firstprivate(c)
   //omp lastprivate(b)  lastprivate(c)
   //omp private(d)
      {
         (1) ... (2)
      }
   (3)
An der Stelle (0) sind alle Variablen deklariert und mit 1 initialisiert. Ohne die OpenMP-Direktiven sind alle Variablen an den Stellen (1), (2) und (3) sichtbar und änderbar (falls sie nicht durch weitere Deklarationen zwischen (1) und (2) verdeckt werden).

An der Stelle (1) gilt Folgendes: e ist wie in Java sichtbar, änderbar und hat den Wert 1 und ist in allen Threads die gleiche Variable. a ist sichtbar, änderbar hat den Wert 1 und ist in allen Threads eine verschiedene Variable. b ist sichtbar, änderbar, der Wert ist undefiniert und sie ist in allen Threads eine verschiedene Variable. c ist sichtbar, änderbar hat den Wert 1 und ist in allen Threads eine verschiedene Variable. d ist sichtbar, änderbar, der Wert ist undefiniert und sie ist in allen Threads eine verschiedene Variable.

Bei dem Übergang von der Stelle (2) zur Stelle (3) gilt Folgendes: Die Werte der Variablen a, c und d gehen verloren. Der Wert, den die Variablen b und c in der letzten Iteration haben wird in die jeweiligen globalen Variablen übernommen. Die Variable e hat bei (3) den gleichen Wert wie bei (2).

7.2.2 Lastverteilung

Die Aufteilung der Schleifenanweisung auf Threads kann durch eine Reihe von Parametern der `schedule'-Klauseln kontrolliert werden.

   //omp parallel for
   //omp schedule(static)
   oder  schedule(dynamic)
   oder  schedule(guided)
      for (int i = 0; i < n; i++ ) {
          ...
      }
Die Voreinstellung `static' bewirkt, dass gleich große Teile (chunks) der Schleife auf die Threads aufgeteilt werden. Mit der Einstellung `dynamic' wird ein Arbeitsstapel (siehe Workpile in Abschnitt 6.3, Seite [*]) angelegt, aus der die Threads sich neue Aufgaben holen, wenn sie mit der vorhergehenden fertig sind. Dies eignet sich vor allem, wenn die einzelnen Schleifeniterationen verschieden lang dauern. Bei der Einstellung `guided' wird wie bei `dynamic' eine Workqueue angelegt, aus der sich die Threads bedienen. Die Größe der Aufgaben variiert aber von einem größeren Anfangswert bis zu einem vorgegebenen minimalen Endwert.

Aufgaben

Aufgabe 38   Implementieren Sie das nicht atomare Programm aus Abschnitt 2.2.1.
x=0; y=0;
con z= x + y; x=1; y=2 end;

Wir geben im Folgenden eine Lösung in Java OpenMP an. Die reine Java-Lösung finden Sie im Abschnitt 3.1 auf Seite [*].

Das Jomp-Programm sehen Sie in dem weiter unten folgenden Programmlisting. Die Variablen x, y und z werden global deklariert. Die drei Statements z = x + y, x = 1, und y = 2 werden in den parallel sections abgearbeitet.

Diese Methoden werden nun nicht wie in reinem Java erforderlich in Runnable-Klassen implementiert, sondern in einer `parallel sections'-Direktive aufgerufen. Die Aufrufe werden durch `section'-Direktiven als parallel ausführbar markiert. Damit auch die Verzögerungsmethode innerhalb der Sektion ausgeführt wird, sind beide Teile in geschweifte Klammern eingeschlossen. Die Variablen x, y, z sind als globale Variable in den einzelnen Abschnitten sichtbar (wegen dem Default shared).

   public class ExConJomp {
     private boolean done = true;
   
     void setDone() { done = true; }
   
     boolean isDone() { return done; }
   
     public static void main(String[] args) {
       new ExConJomp().work(
           new PrintWriter(System.out,true));
     }
   
     void work(PrintWriter out) {
       // define global (shared) variables
       int x, y, z;

       done = false;
       // repeats the simulation
       while (!done) {
         // initialize the variables
         x = 0; y = 0; z = 0;

   //omp parallel sections
         {
   //omp section
           { doSomeWork(2); z = x + y; }
   //omp section
           { doSomeWork(2); x = x + 1; }
   //omp section
           { doSomeWork(2); y = y + 2; }
         }
         // prints the result
         out.println("x="+x+", y="+y+", z="+z);
       }
     }
   }

Zur Kompilierung des Programms verwenden wir ein (GNU-)Makefile, das die erforderlichen Einstellungen des Jomp-Compilers und des Java CLASSPATH vornimmt. Das Makefile finden Sie auf der Website zum Buch. Mit diesem Makefile genügt es

   >make ExConJomp
einzugeben, um die Übersetzung von Jomp nach Java, danach zu den class-Dateien und schießlich zur Ausführung anzustoßen.

Ein Jomp-Programm muss sich in einer Datei befinden, die die Endung jomp hat. Die Übersetzung von Jomp nach Java geschieht (durch das Makefile) wie folgt:

   /usr/lib/jdk1.3/bin/java \
       -cp /home/kredel/java/lib/jomp1.0b.jar \
       jomp.compiler.Jomp ExConJomp

   Jomp Version 1.0.beta.
   Compiling class ExConJomp....
   Parallel Sections Directive Encountered
Der Jomp-Compiler (jomp.compiler.Jomp) analysiert die Datei und stellt die `parallel sections'-Direktive fest. Die Ausgabe wird in eine Datei mit der Endung java und dem Klassennamen als Anfang geschrieben. Diese Datei wird dann wie gewohnt mit dem Java-Compiler in Bytecode übersetzt.
   /usr/lib/jdk1.3/bin/javac \
       -classpath /home/kredel/java/lib/jomp1.0b.jar \
       ExConJomp.java
Falls keine Fehler aufgetreten sind, wird das Programm mit dem Java-Interpreter sogleich ausgeführt.
   /usr/lib/jdk1.3/bin/java \
       -classpath /home/kredel/java/lib/jomp1.0b.jar:. \
       -Djomp.threads=2 ExConJomp

Das Makefile kennt einen Parameter `np=x', mit dem die Anzahl `x' der gewünschten Threads an die Jomp-Property jomp.threads weitergegeben wird.

   >make ExConJomp np=8
Die Voreinstellung sind 2 Threads. In diesem Beispiel werden 8 Threads gestartet.

Ein Beispiel für die Ausgabe der Terminalversion des Programms für drei Threads könnte wie folgt aussehen:

   >make ExConJomp np=3
   x=1, y=2, z=2
   x=1, y=2, z=3
   x=1, y=2, z=0
   x=1, y=2, z=3
   x=1, y=2, z=2
   x=1, y=2, z=1
   x=1, y=2, z=3
   x=1, y=2, z=2
   x=1, y=2, z=2
   x=1, y=2, z=3
   ...
Die Ausgabe ähnelt der aus dem früheren Beispiel. z = 2 in der ersten Zeile zeigt, dass zuerst die Zuweisung an y ausgeführt wurde, dann die Summe x + y berechnet wurde und schließlich die Zuweisung an x erfolgte. Die Ausgabe z = 3 in der zweiten Zeile besagt, dass die Summe x + y nach den Zuweisungen an die Variablen berechnet wurde. z = 0 in der dritten Zeile zeigt, dass die Summe x + y vor den Zuweisungen an x und y berechnet wurde. Aus z = 1 in der sechsten Zeile ist zu entnehmen, dass zuerst die Zuweisung an x ausgeführt wurde, dann die Summe x + y berechnet wurde und schließlich die Zuweisung an y erfolgte.


Heinz Kredel
2002-04-05