Programmieren mit Tasks und parallelen Schleifen

Spekulation, Task-Scheduling

Anzeige

Tasks eignen sich nicht nur für die Parallelisierung rekursiver Algorithmen. Ein weiteres Anwendungsgebiet ist die spekulative Ausführung mehrerer Programmteile. Spekulation bedeutet, dass eine Berechnung durchgeführt wird, bevor feststeht, ob man das Ergebnis tatsächlich benötigt. Was zunächst abwegig klingt, ist in zahlreichen Anwendungen zu finden, wenngleich in unterschiedlicher Form. Ein typisches Beispiel ist die Berechnung von Vorschaubildern in Bildverwaltungsprogrammen oder Dateimanagern. Dabei lassen sich parallel zu den sichtbaren Vorschaubildern die noch nicht sichtbaren berechnen, sodass man letztere beim Scrollen sofort anzeigen kann. Nun sei eine abstraktere, durch folgenden Ausdruck gegebene Form der Spekulation betrachtet:

use(condition() ? f() : g());

Obwohl es auf den ersten Blick unmöglich erscheint, die Funktionen condition, f, g und use parallel auszuführen, lässt sich eine Beschleunigung erreichen, indem beide Pfade der sich hinter dem Konditionaloperator versteckenden Verzweigung spekulativ ausgeführt werden. Sobald das Ergebnis des Aufrufs von condition vorliegt und beide Zweige abgearbeitet sind, wählt man den entsprechenden Wert aus und übergibt ihn der Funktion use. Diese Form der Spekulation ist jedoch nur sinnvoll, wenn die Berechnung der Bedingung nicht trivial ist oder von Benutzereingaben abhängt. Das folgende Codebeispiel zeigt die Implementierung mit TBB.

decltype(f()) x, y;
tbb::task_group group;
group.run([&x] {x = f();});
group.run([&y] {y = g();});
bool cond = condition();
group.wait();
use(cond ? x : y);

Die spekulative Ausführung geht immer mit unnötigen Berechnungen einher, da sie nur die Ergebnisse eines Zweigs tatsächlich verwendet. Der damit verbundene Mehraufwand kann bei einem voll ausgelasteten System sogar zu einer Verlangsamung führen, da Rechenzeit, die sich für andere Aufgaben verwenden ließe, verschwendet wird. Deshalb sollte man vor dem Einsatz von Spekulation Aufwand und Nutzen sorgfältig abwägen. Angenommen, dass die Funktionen condition, f, g und use aus obigem Beispiel vier, fünf, drei beziehungsweise zwei Zeiteinheiten benötigen. Dann beträgt die Ausführungszeit der sequenziellen Variante elf beziehungsweise neun Zeiteinheiten, je nachdem, ob die Bedingung erfüllt ist oder nicht (in beiden Fällen ist die Rechenzeit, also die geleistete Arbeit, gleich der Ausführungszeit). Die spekulative Implementierung hingegen kommt mit sieben Zeiteinheiten aus. Allerdings erhöht sich die Rechenzeit auf 14 Zeiteinheiten.

Auch hier gibt es wieder mehrere Möglichkeiten der Optimierung. Beispielsweise muss man nicht warten, bis beide Pfade durchlaufen wurden. Sobald die Bedingung feststeht und der entsprechende Pfad durchlaufen wurde, kann man mit der Abarbeitung des Programms fortfahren. Die Synchronisation erfolgt also in Abhängigkeit der Bedingung. Außerdem ist es nicht immer sinnvoll, beide Pfade spekulativ auszuführen. Wird ein Pfad mit einer hohen Wahrscheinlichkeit eingeschlagen, bietet es sich an, nur ihn spekulativ auszuführen und den anderen Pfad wie im sequenziellen Fall abzuarbeiten. So erreicht man im Mittel eine gute Beschleunigung und reduziert den Mehraufwand. Ein typisches Anwendungsszenario dieser asymmetrischen Form der Spekulation ist die Behandlung von Sonderfällen.

Für die korrekte Verwendung von Tasks muss man sich darüber im Klaren sein, wie das Laufzeitsystem arbeitet. Letztlich werden Tasks wieder auf Threads abgebildet, zumal die gängigen Betriebssysteme keine direkte Unterstützung für Tasks bieten. Das geschieht durch einen sogenannten Task Scheduler (siehe unten). Im Gegensatz zu Threads sind Tasks jedoch nicht präemptiv, das heißt, ein Task lässt sich nicht von anderen Tasks unterbrechen. Damit spart man sich den Aufwand für Kontextwechsel. Davon ausgenommen ist das Warten auf andere Tasks, zum Beispiel mit wait. In dem Fall verbleiben die zu einem Task gehörenden Daten auf dem Stack und stehen nach Beendigung der Tasks, auf die gewartet wird, wieder zur Verfügung.

Eine Konsequenz der Ununterbrechbarkeit von Tasks ist, dass Synchronisationsoperationen wie Mutexe nur mit Bedacht einzusetzen sind. Versucht ein Task beispielsweise, einen bereits gesperrten Mutex zu sperren, legt das Betriebssystem den ausführenden Thread schlafen. Als Folge davon kann eine Unterbelegung eintreten, da dieser Thread keine anderen Tasks ausführen kann. Dadurch sinkt die Leistung. Zur Lösung des Problems starten manche Task Scheduler, wie der von .NET, in solchen Fällen automatisch zusätzliche Threads. Bei den meisten Implementierungen sollte man jedoch sicherstellen, dass die Teile einer Anwendung, die häufig blockieren, in eigenen Threads ablaufen. Dazu gehören neben Ein- und Ausgabeoperationen solche Teile, die über Nachrichtenaustausch kommunizieren und nur sporadisch aktiv sind.

Task Scheduler erzeugen üblicherweise für jeden Prozessorkern genau einen Thread, der nach Möglichkeit immer auf demselben Kern ausgeführt wird. Jeder Thread verfügt über eine eigene, lokale Warteschlange für ausführbereite Tasks. Alle in einem Thread erzeugten Tasks landen zunächst in der lokalen Warteschlange und werden in der Regel von genau diesem Thread abgearbeitet. Das fördert die Datenlokalität: Tasks, die mit hoher Wahrscheinlichkeit auf dieselben Daten zugreifen, werden auf demselben Prozessorkern ausgeführt. Die lokalen Warteschlangen funktionieren üblicherweise nach dem LIFO-Prinzip (Last In – First Out). Das bedeutet, dass der zuletzt eingereihte Task zuerst bearbeitet wird. Das soll verhindern, dass mit jedem einer Warteschlange entnommenen Task der Cache neu zu laden ist.

Es fehlt nur noch ein Mechanismus, um die Last auf die Prozessorkerne zu verteilen. Hier kommt das sogenannte Work Stealing zum Einsatz [4]. Wenn die Warteschlange eines Threads leer ist, "stiehlt" er einen Task aus der Warteschlange eines anderen Threads. Die Auswahl des "Opfers" erfolgt üblicherweise nach dem Zufallsprinzip, um eine gleichmäßige Auslastung zu erreichen. Das eigentliche Stehlen geht dabei nach dem FIFO-Prinzip (First In – First Out) vonstatten. Es wird der Task entnommen, der am längsten auf seine Ausführung wartet. Zu dem Zweck bietet sich die Verwendung von Double-ended Queues an, für die effiziente, nicht blockierende Implementierungen existieren. Die folgende Abbildung illustriert die Vorgehensweise beim Work Stealing auf einem System mit vier Prozessorkernen.

Anzeige