7.4 Reduktionen

Wie in der letzten Aufgabe schon angesprochen, steht man immer wieder vor folgendem Problem:

int result = 0;
con i=1 to n do computeResult(i) end
collectResult
In parallelen Threads wird ein partielles Ergebnis berechnet, das dann zu einem globalen Ergebnis zusammengefasst, verdichtet oder reduziert werden soll.

Zur Lösung wurde ein Sprachkonstrukt `reduction( op: var )' entwickelt. In OpenMP ist dies eine Compiler-Direktive und zum Beispiel in MPI (siehe Kapitel 8) ein Methodenaufruf. Dieses Sprachkonstrukt behandelt die Variable `var' wie die Variable result von oben. Die Operation `op' legt dabei fest, mit welcher Operation die lokalen Ergebnisse zum globalen Ergebnis reduziert werden sollen. In der Regel sind für `op' die Operationen `+, *, max, min, and, or' vorgesehen und implementiert.

Im Prinzip entspricht die Reduktion

   reduction( +: var )
      {
         computeResult();
      }
folgendem Pseudocode, der Java-Sichtbarkeitsregeln folgt.
   { int temp; 
     {
         int var = 0;      // var ist nicht mehr var
         computeResult();
         temp = var;
     }
     atomic var += temp; end;
   }
Das heißt computeResult() wird ersetzt durch einen Programmteil, der zunächst die globale Variable maskiert (mit int var = 0), dann die gewünschte Berechnung durchführt und zum Schluss das lokale Ergebnis in einem atomaren Bereich zu dem globalen Ergebnis hinzuaddiert.

Werden mehrere Variablen in der `reduction'-Direktive angegeben, dann wird die Reduktion für jede dieser Variablen durchgeführt. Mit mehreren `reduction'-Direktiven können mehrere verschiedene Operationen zur Reduktion ausgewählt werden. Benötigt man zusätzliche lokale Hilfsvariablen, so kann man diese durch `private'-Klauseln bereitstellen.

Aufgaben

Aufgabe 41   Summieren Sie die m Elemente eines Arrays 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 auf Seite [*]. Benutzen Sie Java OpenMP mit Reduktion zur Parallelisierung.

Zur Vorstellung dieser Lösung mit Jomp ist fast nichts mehr zu sagen. Die gesamte Arbeit der Parallelisierung und der Reduktion des Ergebnisses wird jetzt von einer Zeile OpenMP `parallel for reduction(+:sum)' erledigt.

   import jomp.runtime.*;
   
   public class ExVecOmpRed {
     public static void main(String[] args) {
       new ExVecOmpRed().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;

   //omp parallel for reduction(+:sum)
       for (int i=0; i<counts; i++) {
           sum += vec[i];
       }
       out.println("results ");
       out.println("s = "+sum+", s'="+ans);
     }
   }

Die Ausgabe könnte etwa folgendermaßen aussehen:

   make ExVecOmpRed np=8
   results 
   s = 1999999000000, s'=1999999000000
Das Ergebnis s ist wie erwartet gleich s'. Weitere Ausgaben macht das Programm nicht.

Aufgabe 42   Berechnen Sie $\pi$ mit OpenMP in Java. Benutzen Sie dabei die Näherungsformel

\begin{displaymath}
\frac{\pi}{4} =
\arctan(1) =
\int_{0}^{1} \frac{1}{1+x^2} dx \cong
h \sum_{i=1}^{n} \frac{1}{1+( (i-0.5) h )^2 }
\end{displaymath}

für große n, wobei h = 1/n. Die Summation kann mit einer for-Schleife durchgeführt werden, die sich mit Jomp parallelisieren lässt. Entwickeln Sie eine Version, bei der der Wert der Summation in einer globalen Variablen steht, auf die atomar zugegriffen werden muss. Entwickeln Sie eine zweite Variante, die eine Reduktion der Summationsvariablen benutzt.

Zusammenfassung

Wir haben in diesem Kapitel die wichtigsten Konzepte von Java OpenMP besprochen. Wir haben gesehen, wie mit einer Zeile OpenMP der ganze Mechanismus der Thread-Verwaltung erledigt werden kann. Atomare Bereiche verwendet man ähnlich wie in Java. Für das immer wiederkehrende Problem, aus lokalen Ergebnissen globale Antworten zu erzeugen haben wir die OpenMP reduction-Direktiven kennen gelernt. Das Jomp-Paket kann als reine Java Lösung zusammen mit praktisch allen Java-Paketen die Nutzung von Threads erleichtern.

Weiterführende Literatur über das (FORTRAN) API von OpenMP findet sich in dem Buch [CMD$^+$00] oder auf der Website der OpenMP-Organisation [Ope98]. Unter anderem haben wir die OpenMP-Barrieren nicht besprochen, die in bestimmten Situationen anstelle von await verwendet werden können.


Heinz Kredel
2002-04-05