Seite 2: Tasks

Sag's mit Tasks

Die eingangs skizzierte Entwicklung hin zu immer mehr Kernen führt dazu, dass die Verteilung von Arbeit auf eine zunehmend größer werdende Zahl von Threads mit Worksharing-Konstrukten nicht immer praktikabel ist. Dazu kommt, dass offensichtlich nicht alle zu parallelisierenden Algorithmen aus Schleifen oder ähnlich einfachen Konstrukten bestehen. Man denke etwa an rekursive Algorithmen oder allgemein Irregularität, zum Beispiel Algorithmen auf Graphen. Um dem zu begegnen, haben in den letzten Jahren zunehmend mehr Programmiermodelle die Unterstützung von Tasks aufgenommen, wie auch 2008 OpenMP 3.0.

Man kann sich einen OpenMP Task als ein leichtgewichtiges Paket aus Code und Datenumgebung vorstellen. Dabei wird ein Task durch ein entsprechendes Konstrukt markiert, nämlich #pragma omp task, wobei der nachfolgende strukturierte Block den Code definiert und die bekannten Klauseln die Datenumgebung mit shared und private-Variablen festlegen. Die Abbildung von Tasks zur Ausführung auf Threads unterliegt der ausschließlichen Kontrolle der OpenMP-Laufzeitumgebung. Erreicht der Programmfluss ein task-Konstrukt, gibt es für die Laufzeitumgebung im Prinzip zwei Optionen:

1. die direkte Ausführung des Tasks oder
2. die Auslagerung des Tasks auf eine Warteschlange zur späteren Abarbeitung. In diesem Fall wird die Programmausführung direkt hinter dem Task fortgesetzt.

Das Listing zeigt die Task-Parallelisierung eines einfachen Sudoku-Lösers, der alle gültigen Ergebnisse findet. Der Algorithmus arbeitet dabei wie folgt:

1. Finde ein leeres Feld.
2. Füge eine Nummer ein.
3. Prüfe das Sudoku.
4. Falls ungültig: Füge die nächste Nummer ein.
5. Falls gültig: Gehe zum nächsten Feld und starte erneut.

Zur Task-Parallelisierung wird eine parallele Region benötigt, um ein Team von Threads aufzuspannen. Allerdings soll zunächst nur ein Thread den Algorithmus zum Lösen aufrufen, daher das single-Konstrukt. Das Durchprobieren einer Zahl (Schritt 4) ist jeweils als ein unabhängiger Task implementiert, somit entsteht die Parallelität in diesem Algorithmus. Am Ende wird auf alle Tasks gewartet, um mit den gefundenen Lösungen arbeiten zu können.

Das Listing zeigt übrigens auch, dass die Kombination von C++-Klassen und OpenMP-Parallelisierung nicht wirklich ein Problem darstellen muss. Die Variable sudoku ist eine vom Typ Zeiger auf die Klasse CSudokuBoard, und die Festlegung als firstprivate bedeutet, dass für jeden Task eine Kopie des Zeigers angelegt wird, im Task selbst wird dann die Klasse über den Copy-Konstruktor instanziiert.

In OpenMP lassen sich alle Threads eines Teams dazu nutzen, Tasks abzuarbeiten. Insbesondere wenn Threads an einer Barriere oder einem sonstigen Synchronisationskonstrukt warten, können sie die Warteschlange auf zu bearbeitenden Tasks hin untersuchen und diese gegebenenfalls zur Ausführung bringen. Das Task-Modell von OpenMP erlaubt dabei, dass ein unterbeschäftigter Thread unbearbeitete Tasks von anderen Threads "stiehlt", um eine bessere Lastbalancierung zu erzielen.

Nach einem barrier-Konstrukt, das alle Threads im Team erreichen müssen, ist die Erledigung aller Tasks garantiert. Für feingranularere Synchronisation gibt es das taskwait-Konstrukt, das den Thread/Task, der es erreicht, auf alle direkt von ihm erzeugten Tasks warten lässt, nicht aber noch auf weitere von diesen erzeugte Tasks. Alle Tasks, die im Kontext eines taskgroup-Konstrukt erstellt werden, gehören zu einer logischen Gruppe und sind an ein implizites taskwait-Konstrukt am Ende der taskgroup gebunden.

Lieber nicht bis zum Ende

Hin und wieder kommt es auch in der besten Applikation vor, dass eine Berechnung abgebrochen werden soll. Mögliche Gründe gibt es viele. Ein typischer ist, dass ein Fehler aufgetreten ist und die Fortführung der Berechnung keinen Sinn mehr ergibt. Ein weiterer könnte sein, dass man die Berechnung abbrechen möchte, weil das Ergebnis feststeht (z. B. in numerischen Verfahren oder in Suchalgorithmen). Bislang konnte man das in OpenMP nur schwer und auch nicht für alle Konstrukte gleichermaßen umsetzen. Gerade ein Worksharing-Konstrukt ließ sich nicht stoppen, sobald dessen parallele Ausführung einmal begonnen hatte. Die einzige Möglichkeit bestand darin, mit einer if-Anweisung die Schleife bis zum Ende ohne sinnvollen Code weiterlaufen zu lassen. Abgesehen von einer gewissen Unsauberkeit hat dieses Verfahren auch den Nachteil, dass es Energie und Zeit kostet, bis die Schleife ihr natürliches Ende erreicht hat.

OpenMP 4.0 löst das Problem, indem es Direktiven zum Abbruch paralleler Berechnungen einführt. Die Grundidee hierbei ist es, mit dem cancel-Konstrukt den Abbruch einer parallelen Region anzufordern. Der anfordernde Thread beendet die Ausführung sofort und benachrichtigt andere Threads über den Abbruch. Diese prüfen an sogenannten "Cancellation Points", ob die Ausführung abgebrochen werden soll und beenden das abzubrechende Konstrukt, falls dem so ist.

Das cancel-Konstrukt unterstützt den Abbruch paralleler Regionen (parallel-Klausel) und relevanter Worksharing-Konstrukte (Klauseln sections, for bzw. do) sowie von Task-Gruppen (taskgroup-Klausel). Cancellation Points werden nicht verwunderlich durch das cancellation point-Konstrukt eingeführt. Weiterhin definiert OpenMP 4.0 Barrieren und cancel-Konstrukte als Cancellation Points. Etwaige Ressourcen werden vom OpenMP-Laufzeitsystem nicht freigegeben. Programmierer sind daher selbst verantwortlich dafür, dass zum Beispiel vor einem Abbruch Dateien geschlossen worden sind oder Sperren und allokierter Speicher freigegeben wurden.

Der Sudoku-Löser aus dem Listing zeigt, wie sich ein Task-paralleler Algorithmus abbrechen lässt, sobald ein Task eine Sudoku-Lösung gefunden hat. Nach dem Finden einer vermeintlich neuen gültigen Sudoku-Lösung, überprüft der Task, ob nicht doch bereits ein anderer Task ebenfalls eine Lösung gefunden hat. Ist das nicht der Fall, wird die gefundene Lösung gespeichert und ein Abbruch der Berechnung herbeigeführt. Das critical-Konstrukt verhindert, dass zwei Tasks gleichzeitig eine Lösung speichern und einen Abbruch herbeiführen wollen. Der Code liefert somit nicht das "erste" gelöste Sudoku, sondern nur ein mögliches aus der Gesamtheit aller gültigen Lösungen.

Das Beispiel nutzt die Eigenschaft des OpenMP-Taskmodells explizit aus. Beim Abbruch einer Gruppe von Tasks, dürfen die Tasks, die bereits mit der Ausführung begonnen haben, diese beenden. Nur wenn sie einen Cancellation Point enthalten, müssen sie mit der Ausführung vorzeitig stoppen. Alle anderen Tasks, die noch in der Warteschlange stehen und auf Ausführung warten, werden als beendet betrachtet und einfach aus der Warteschlange entfernt. Damit wird klar, warum jeder Task im Beispiel-Code immer prüfen muss, ob eine bereits Lösung gefunden wurde. Sollte der Task nämlich mit der Ausführung begonnen haben, könnte er eine weitere gültige Lösung berechnen und versuchen, diese abzuspeichern.

#pragma omp cancel construct-type-clause[[,] if-clause] new-line
#pragma omp cancellation point construct-type-clause new-line

!$omp cancel construct-type-clause[[,] if-clause] new-line
!$omp cancellation point construct-type-clause new-line

Si, Si, Senior SIMD

Bis zur Version 3.1 hat OpenMP das Thema SIMD komplett ignoriert und sich nur mit Multithreading beschäftigt. Programmierer, die die SIMD-Einheiten einer modernen CPU nutzen wollten, waren auf das Wohlwollen ihres Compilers angewiesen. War der automatische Vektorisierer "schlau" genug zu erkennen, dass sich die SIMD-Einheit nutzen ließ, und hat der Programmierer entsprechende SIMD-Instruktionen ins Programm einbauen können, konnte er wahrlich glücklich sein. Konnte der Vektorisierer nichts ausrichten, war man auf die Nutzung Compiler-spezifischer Pragmas und Direktiven angewiesen, die meist nicht zwischen Compilern portabel waren. Weiterhin musste der Programmierer darauf vertrauen, dass das Zusammenspiel zwischen Vektorisierung und Multithreading klappte und weder die Effizienz noch die Korrektheit litten. Die Erfahrung zeigt allerdings immer wieder, dass es hier Probleme gab und noch heute gibt.

Dank OpenMP 4.0 wird sich das Bild ändern. Die neue Spezifikation definiert OpenMP-Konstrukte, die einem Programmierer die Compiler-übergreifende, portable Beschreibung von SIMD-Programmteilen erlauben. Hauptbestandteil der neuen Konstrukte ist das simd-Konstrukt zur Vektorisierung von Schleifen. Eine damit markierte Schleife wird vom OpenMP-Compiler auf SIMD-Instruktionen übersetzt; die Schleife wird weiterhin sequenziell von einem einzelnen Thread ausgeführt. Möchte man auch eine (Thread-)Parallelisierung der Schleife erreichen, stehen die Worksharing-Konstrukte for simd und parallel for simd zur Verfügung.

Die Syntax des neuen Konstrukts ist eng an die der existierenden Worksharing-Konstrukte angelehnt und unterstützt nahezu die gleichen Klauseln (z. B. private, reduction und collapse). Hinzu kommen spezielle Klauseln, die den Compilern helfen sollen, SIMD-Code zu erzeugen. Die safelen-Klausel gibt an, wie groß die maximale Vektorlänge in der Schleife sein darf. Sie wird besonders wichtig, wenn die Schleife Datenabhängigkeiten über Iterationsgrenzen hinweg enthält und nicht beliebig vektorisierbar ist. Eine weitere wichtige Klausel ist linear, die eine lineare Abhängigkeit einer Variablen vom Schleifenzähler ausdrückt. Die aligned-Klausel hilft dem Compiler bei der Optimierung der SIMD-Instruktionen; bei passend ausgerichteten Daten lassen sich effizientere Lade- und Speicherinstruktionen nutzen.

Bei der Vektorisierung verursachen Schleifen mit Funktionsaufrufen wie im folgenden Beispiel fast immer Probleme. Existiert keine vektorisierte Version der Funktion (min, distance), vermeidet der Compiler die Vektorisierung. Für viele mathematische Funktionen aus der Standardbibliothek liefert ein Compiler in der Regel Vektorversionen mit (z. B. für sqrt). Bei selbst definierten Funktionen ist wieder der Programmierer gefragt, dem Compiler zu erklären, wie sich der Code einer Funktion vektorisieren lässt.

#pragma omp declare simd aligned (a, b) notinbranch
float min(float a, float b) {
    return a < b ? a : b;
}

#pragma omp declare simd aligned(x) uniform(y) notinbranch
float distance(float x, float y) {
    return (x - y) * (x - y);
}

void distance update (float a, float b, float y, int vlen) {
    float *ptr = b;
#pragma omp parallel for simd safelen (16) linear(ptr:1) aligned(a,b,y)
    for (int i=0; i<vlen; i++) {
        y[i] = min(sqrt (distance (a[i], 1.0)), ptr);
        ptr += 1;
    }
}

Hier weisen die declare simd-Konstrukte den Compiler an, die Funktionen zu vektorisieren, indem die Argumente von skalaren Werten in SIMD-Vektorregister umgewandelt werden. Die uniform-Klausel unterbindet das für bestimmte Funktionsargumente, wenn nötig. Weiterhin lassen sich mit aligned
wieder die Datenausrichtung vorschreiben und mit linear lineare Abhängigkeiten zum Schleifenzähler ausdrücken. Die notinbranch-Klausel erlaubt weitergehende Compiler-Optimierungen, falls die vektorisierten Funktionen immer (dann stünde da inbranch) beziehungsweise niemals innerhalb des Rumpfes einer if-Anweisung ausgeführt werden.