7.3 Atomare Bereiche

Da wir in OpenMP auch gemeinsame Variablen haben, müssen wir, wie in der vorhergehenden Aufgabe gesehen, den Zugriff darauf koordinieren. Da wir uns in Java befinden, könnten wir direkt auf die Java synchronized-Konstrukte zurückgreifen. OpenMP bietet aber selbst einige Direktiven die Vergleichbares leisten.

Diese OpenMP-Direktiven sind `critical' und `atomic'. Entgegen dem Namen, entspricht `critical' dem synchronized bzw. dem atomic. Die Direktive `atomic' ist in Jomp nicht implementiert und soll in etwa synchronized auf der Ebene von Maschineninstruktionen realisieren.

atomic S1; ...; Sn end
wird daher ganz direkt mit OpenMP als
   //omp critical
       {
         S1; ...; Sn;  
       }
implementiert. Wobei wie üblich S1, ..., Sn die Implementierung des Statements S1, ..., Sn darstellt. Die Direktive bewirkt, dass immer nur maximal ein Thread von allen Threads der entsprechenden `parallel'-Direktive die Statements S1; ...; Sn ausführen kann.

Benötigt man mehrere verschiedene kritische Abschnitte, so kann man der Direktive einen Namen mitgeben.

   //omp critical SectionName
       {
         S1; ...; Sn;  
       }
Unter Java entspricht dem ziemlich genau ein
   synchronized ( Object(`SectionName') ) 
       {
         S1; ...; Sn;  
       }
wobei aus `SectionName' ein eindeutiges Objekt gebildet werden muss.

Aufgaben

Aufgabe 39   Implementieren Sie das atomare Programm aus Abschnitt 2.2.1 mit Jomp.
x=0; y=0;
con atomic z = x + y; end; atomic x = 1; y = 2 end end

Wir besprechen dafür einen Lösungsvorschlag in Jomp. Die Variablen x, y und z werden wie oben global deklariert. Die drei Statements z = x + y, x = 1, und y = 2 werden jetzt in nur zwei parallel sections abgearbeitet. Die Gruppierung zu atomaren Statements erfolgt mit der `critical'-Direktive innerhalb von `parallel' in zwei `sections'.

   public class ExAtomJomp {
     private boolean done = true;

     void setDone() { done = true; }
   
     boolean isDone() { return done; }
   
     public static void main(String[] args) {
       new ExAtomJomp().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
   //omp critical
           { doSomeWork(1); z = x + y; }
   //omp section
   //omp critical
           { x = x + 1; doSomeWork(3); 
             y = y + 2; }
         }
         // prints the result
         out.println("x="+x+", y="+y+", z="+z);
       }
     }
   }

Die Ausgabe der Terminalversion könnte wie folgt aussehen:

   >make ExAtomJomp np=2
   x=1, y=2, z=0
   x=1, y=2, z=0
   x=1, y=2, z=0
   x=1, y=2, z=0
   x=1, y=2, z=0
   x=1, y=2, z=0
   ...
Jetzt kommen im Vergleich zur vorhergehenden Aufgabe nur noch der Wert z = 0 vor. Im Grunde müsste auch der Wert z = 3 vorkommen können. Die Ausgabe z = 0 zeigt, dass zuerst die Summe x + y berechnet wurde und dann die Zuweisungen an die Variablen ausgeführt wurden.

Aufgabe 40   Summieren Sie die m Elemente eines Feldes A[ ] mit t parallel arbeitenden Funktionen, wobei t >= 3. Benutzen Sie eine globale Variable s_{global}, die am Ende die Summe enthalten soll. Das heißt, implementieren Sie das Programm in Abbildung 7.1. Benutzen Sie Java OpenMP mit kritischen Abschnitten zur Parallelisierung.

Eine entsprechende Aufgabe für Distributed Memory Computer finden Sie in Aufgabe 22 auf Seite [*] und für reines Java in Aufgabe 7 auf Seite [*]. Eine zweite elegantere Lösung mit Jomp lernen Sie im nächsten Abschnitt kennen.

Abbildung 7.1: Vektorsumme mit Jomp
\framebox{
\begin{minipage}[]{10.0cm}
\begin{minipage}[t]{5.0cm}
\begin{tabbing}...
...m global}} + s_{{\rm l}}$\ {\bf end};
\end{tabbing}\end{minipage}\end{minipage}}

Wir besprechen hier eine Musterlösung. Der Programmteil S(i) wird mit Hilfe der `parallel'-Direktive parallel ausgeführt. In dem parallelen Abschnitt wird in einer Schleife eine lokale Summe über einen entsprechenden Bereich des Arrays gebildet. Anschließend wird mit sum += s die lokale Summe auf die globale Summe innerhalb der `critical'-Direktive aufaddiert.

Im Hauptprogramm wird zunächst das Array vec initialisiert (mit Bildung einer Kontrollsumme ans). Wir sparen uns hier die Berechnung der Arbeitsbereiche, die wir in der Aufgabe 7 bestimmt haben, durch einen kleinen Trick. Wir teilen die Arbeit an dem Vektor nicht in nebeneinander liegende Abschnitte auf, sondern wir greifen modulo der Anzahl der Threads auf die Array-Elemente zu, wobei wir mit dem Element mit der Thread-Nummer beginnen. Die Anzahl der Threads erhalten wir mit der Methode OMP.getNumThreads() und die Nummer des jeweiligen Threads mit der Methode OMP.getThreadNum(). Die Variable myid, die die Nummer des Threads enthält, muss mit private(myid) als verschieden in allen Threads deklariert werden.

In diesem Beispiel wird die for-Schleife nicht von OpenMP parallelisiert. Der gesamte Block, in dem die for-Schleife enthalten ist, wird zwar mehrfach parallel ausgeführt, aber es liegt in unserer Verantwortung, die Schleifenindizes richtig aufzusetzen. Die Parallelisierung der for-Schleife würde uns hier nicht viel nützen, da wir noch keine Möglichkeit kennen, die Werte der lokalen Summation innerhalb der Schleife in das globale Programm zu übernehmen. Dies machen wir im nächsten Abschnitt mit Hilfe der Reduktionen.

   import jomp.runtime.*;
   
   public class ExVecOmp {
     public static void main(String[] args) {
       new ExVecOmp().work(
           new PrintWriter(System.out,true));
     }
   
     void work(PrintWriter out) {
       int counts = 2000000;
       // initialize data
       long ans = 0;
       long vec[] = new long[counts];
       for (int i=0; i<counts; i++) { 
           vec[i] = i; ans += i; 
       }
       /* summation variable */
       long sum = 0;

       int myid = 1;
   //omp parallel private(myid) 
       {
          int num_threads = OMP.getNumThreads();
          myid = OMP.getThreadNum();
          System.out.println("running " + myid );
          long s = 0;
          for (int i=myid; i<counts; i+=num_threads) {
              s += vec[i];
          }
   //omp critical
          {
             sum += s;
          }
        } 
   // end parallel
       out.println("results ");
       out.println("s = "+sum+", s'="+ans);
     }
   }

Die Ausgabe könnte etwa wie folgt lauten:

   >make ExVecOmp np=8
   running 0
   running 6
   running 3
   running 7
   running 4
   running 5
   running 2
   running 1
   results 
   s = 1999999000000, s'=1999999000000
Die ersten Anzeigen von `running' zeigen, dass die Arbeitsschritte in der Reihenfolge 0, 6, 3, 7 bis 1 begonnen wurden. Das Ergebnis s ist wie erwartet gleich s'.


Heinz Kredel
2002-04-05