Seite 3: Benutzerdefinierte Reduktion

Inhaltsverzeichnis

Reduzierstück

Wenn alle Threads eines OpenMP-Teams kooperativ an einem globalen Ergebnis erarbeiten, ist häufig eine Reduktionsoperation beteiligt. Bei einer Reduktion in OpenMP erhält jeder Thread eine private Kopie einer Variablen und sammelt dort sein lokales Zwischenergebnis. Kurz vor dem Ende der parallelen Ausführung werden alle Teilergebnisse der Threads eingesammelt und ins Gesamtergebnis reduziert. Vor OpenMP 4.0 ließen sich solche Reduktionen nur auf primitiven Datentypen (z.B. int oder float) und vordefinierten Operationen (bspw. Addition, Minimum/Maximum) berechnen. Für alles andere musste ein Programmierer in seine Trickkiste greifen und die Reduktion selbst implementieren. Abgesehen vom Aufwand musste er sich überlegen, welcher parallele Reduktionsalgorithmus zum Einsatz kommen sollte; je nach Thread-Anzahl sind lineare oder binäre Reduktionsalgorithmen besser geeignet. Es muss nicht extra erwähnt werden, dass die Wahl des korrekten Algorithmus dem Programmierer überlassen ist.

OpenMP 4.0 löst dieses lang währende Problem durch Einführung benutzerdefinierter Reduktionen. Für beliebige Datentypen und nahezu beliebige Arten von Reduktionsoperationen lässt sich damit ohne allzu viel Schreibarbeit die Menge an vordefinierten Reduktionsoperationen von OpenMP erweitern. Das folgende Codebeispiel nutzt das bei der Implementierung eines parallelen Algorithmus zur Bestimmung eines minimalen Rechtecks, das eine Punktwolke vollständig enthält ("Bounding Box").

#include <algorithm>

#pragma omp declare reduction(minp : Point2D : \  
    omp_out.setX(std::min(omp_in.getX(), omp_out.getX())),
        omp_out.setY(std::min(omp_in.getY(), omp_out.getY())) )
    initializer(omp_priv = Point2D(MAX_X, MAX_Y))
#pragma omp declare reduction(maxp : Point2D : \  
    omp_out.setX(std::max(omp_in.getX(), omp_out.getX())),
        omp_out.setY(std::max(omp_in.getY(), omp_out.getY())) )
    initializer(omp_priv = Point2D(MIN_Y, MAX_X))

Rectangle bounding_box(std::vector<Point2D> points) {
  Point2D lb(MAX_X, MAX_Y);
  Point2D ub(MIN_X, MIN_Y);
#pragma omp parallel for reduction(minp:lb) reduction(maxp:ub)
  for (std::vector<Point2D>::iterator it = points.begin(); 
       it != points.end(); 
       it++) {
    Point2D &p = *it; 
    lb.setX(std::min(lb.getX(), p.getX()));
    lb.setY(std::min(lb.getY(), p.getY()));
    ub.setX(std::max(ub.getX(), p.getX()));
    ub.setY(std::max(ub.getY(), p.getY()));
  }
  return Rectangle(lb, ub);
}

Hier kommt das declare reduction-Pragma ins Spiel. Es definiert für einen Datentyp und eine Berechnungsvorschrift einen symbolischen Namen, der sich wiederum in einer reduction-Klausel verwenden lässt. Innerhalb der runden Klammern wird zunächst der Name der Reduktion festgelegt. Dieser darf ein normaler Bezeichner sein und auch existierende Reduktionsoperationen für neue Datentypen überladen. Durch einen Doppelpunkt getrennt folgt der Datentyp, auf den sich der Name beziehen soll. Ein weiterer Doppelpunkt trennt den Ausdruck zur Reduktion ab. Dieser beschreibt, wie sich zwei lokale Ergebnisse von zwei Threads in ein neues Zwischenergebnis reduzieren lassen. Durch schrittweise Anwendung dieses Ausdrucks auf die Zwischenergebnisse der Threads erhält der Programmierer so irgendwann das Endergebnis der Reduktion.

Das Beispiel nutzt eine C++-Klasse Point2D zur Speicherung eines Punkts mit x- und y-Koordinate inklusive passender get- und set-Methoden. Der Algorithmus selbst iteriert über alle Punkte ein einen Vektorund berechnet für jeden Punkt das Minimum beziehungsweise Maximum zur Bestimmung der jeweiligen Ecken des Rechtecks. Zur Parallelisierung kommt ein parallel for-Konstrukt zum Einsatz, das die Iteratorenschleife auf die Threads im Team verteilt. Damit kann jeder Thread zunächst das umgebende Rechteck für seine lokale Punktwolke bestimmen. Es fehlt jetzt noch die Reduktion aller umgebenden Rechtecke.

Als Reduktionsausdruck darf jeder beliebige Ausdruck der Basissprache auftreten. Die speziellen Variablen omp in und omp out verweisen im Ausdruck auf die beiden Eingabewerte und den Ausgabewert bei der Anwendung des Reduktionsausdrucks. Bei der Initialisierung der privaten Kopien für jeden Thread ist ein neutrales Element anzugeben. Dieses hängt vom Datentyp ab und wird mit initializer bei der Deklaration einer Reduktion angegeben. Die Variable omp priv steht hierbei für die private Kopie eines Threads und lässt sich durch einen beliebigen Ausdruck initialisieren. Das Beispiel ruft den Konstruktor der Punkt-Klasse auf, um ein lokales Minimum beziehungsweise Maximum zu erzeugen.