Seite 3: Ein Spiel zum Schluss

Inhaltsverzeichnis

Dass die bisher diskutierten Muster Task-paralleler Programme tatsächlich auf viele Problemstellungen anwendbar sind, soll ein Task-paralleler Sudoku-Löser demonstrieren. Ein einfacher Algorithmus, der alle möglichen Kombinationen probiert und damit alle Lösungen findet, lautet wie folgt:

1. Gehe zeilen- und dann spaltenweise zum nächsten nicht ausgefüllten Feld.
2. Für alle Zahlen i im Bereich 1 bis N: sofern i in der Zeile und Spalte noch nicht vorkommt, fahre mit Punkt (1) fort.

Dieser Algorithmus ist aus zwei Gründen für eine klassische Parallelisierung mit Threads schwierig: Zum Ersten gibt es keine lange Schleife, die partitioniert und auf Threads verteilt werden kann, und zum Zweiten ist die Rekursion problematisch. Somit bieten sich Tasks an, da sie sich problemlos ineinander schachteln lassen.

Die Parallelisierung mit Tasks setzt in Schritt 2 an: Für jede Kandidatin i, also jede Zahl, die nach aktuellem Lösungsstand des Sudokus an der aktuellen Position stehen könnte, wird ein Task erzeugt. Dieser führt dann den Algorithmus auf einer eigenen Kopie des Spielfelds mit Schritt 1 fort. Um eine parallele Ausführung zu ermöglichen, wird in OpenMP eine umschließende Parallele Region benötigt. Und wiederum ist ein Single-Konstrukt notwendig: der Algorithmus muss sequentiell beginnen und das erste nicht ausgefüllte Feld finden; erst ab dort wird Parallelität ausnutzbar.

Es ist leicht vorstellbar, dass eine große Menge von Tasks erzeugt wird. Wie oben argumentiert, ist die absolute Anzahl von Tasks aber kein Problem. Jedoch nimmt auch hier die Arbeit je Task mit dem Fortschritt der Lösung des Spielfeldes ab. Ab einem gewissen Punkt verdirbt der Aufwand der Task-Ausführung dann den Spaß.

Konkrete Zahlen sollen das verdeutlichen. Bei der Ausführung auf einem Spielfeld der Größe 16x16 wurden über 10 Millionen Tasks erzeugt. Auf einem System mit 16 physischen Kernen benötigte das Programm mit einem Thread circa 6 Sekunden zur Ausführung. Das bedeutet, dass auf einen Task im Mittel nur etwas über 4 Mikrosekunden Laufzeit entfallen. Betrachtet man dann aber die "inclusive time" eines Tasks auf verschiedenen Rekursionstiefen wird der Unterschied deutlich: Auf Ebene 6 lag die Zeit bei 0,16 Sekunden, auf Ebene 82 nur noch auf 2,2 Mikrosekunden. Die absolute Beschleunigung durch die parallele Ausführung auf allen 16 Kernen resultierte in einem enttäuschenden Ergebnis von nur 3,6.

Der Einbau einer Abbruchbedingung ist in diesem Fall nicht ganz einfach, da einem generellen Löser die Struktur des Spielfelds nicht bekannt ist. Der Abbruch soll ja erst erfolgen, wenn genügend Tasks erzeugt wurden. Deren Anzahl hängt wiederum von der Menge der bearbeiteten freien Felder ab. Dazu dient ein OpenMP if-Konstrukt, durch das die nachfolgenden Tasks direkt (ohne Mehraufwand) ausgeführt werden, sobald mit der Zeilenposition die Hälfte des Spielfelds überschritten ist.

Der Unterschied ist enorm. Zunächst wird bereits die Ausführung mit nur einem Thread um circa 15 Prozent schneller. Auch wenn dies zunächst überrascht, liegt der Grund in der verringerten Anzahl von Tasks. Im vorgestellten Algorithmus wird für jeden Task eine Kopie des Spielfelds angelegt, so dass der Task darauf unabhängig von allen anderen Tasks weiterarbeiten kann. Das Kopieren eines kleinen Arrays (16 x 16 Elemente) ist zwar nur ein geringer Aufwand, bei der genannten Zahl von Tasks wird die Reduktion aber bereits sichtbar. Und wie verhält sich schließlich die parallele Ausführung? Mit der genannten Abbruchbedingung wird für das obige Beispiel eine lineare Beschleunigung erreicht, also ein Faktor von knapp 16 bei Verwendung aller 16 Rechenkerne.