From Task 'til Dawn – Tasks versus Threads

Inhaltsverzeichnis

Eine zentrale Fragestellung bei der Entwicklung paralleler Software ist, ob man direkt mit Threads programmieren sollte oder nicht doch lieber Tasks verwenden möchte. Auch wenn Tasks am Ende von Threads ausgeführt werden, so unterscheiden sich die Programmiermodelle deutlich. Die Autoren verwenden für die folgenden Beispiele OpenMP als parallele Sprache für C/C++, jedoch gelten ihre Feststellungen auch für andere Task-Programmiermodelle.

Eine kurze Einführung in OpenMP-Tasks

OpenMP ist eine Sprache, die eine Wirtssprache (C, C++ oder Fortran) mittels Pragmas in C/C++ oder Direktiven in Fortran um parallele Konstrukte erweitert. Durch diese Konstrukte teilt ein Programmierer dem Compiler mit, wie aus dem Originalprogramm eine parallele Variante erzeugt werden soll.

Abbildung 1 zeigt die parallele Berechnung der Fibonacci-Zahlen mit OpenMP-Tasks. Diese Vorgehensweise stellt keineswegs die beste Implementierung für dieses Problem dar. Dennoch hat sich dieses Beispiel als eine Art "Hello World" für die Task-basierte Programmierung etabliert.

Die Grundidee des Beispiels fußt auf der Beobachtung, dass man die beiden rekursiven Aufrufe innerhalb der fib-Funktion parallel ausführen kann. Genau das wird auf der rechten Seite mit den beiden Pragmas (#pragma omp task) erreicht. Der mit geschweiften Klammern umschlossene Code wird vom Compiler so eingepackt, dass er in einem anderen Thread ausgeführt werden kann. Mittels des taskwait-Pragmas kann auf die beiden Kind-Tasks gewartet werden, sodass am Ende die korrekten Werte in x und y aufsummiert werden können.

Der Aufruf der fib-Funktion auf der linken Seite mutet etwas seltsam an. Es ist vielleicht noch einsichtig, dass #pragma omp parallel eine parallele Ausführung startet. Dennoch wird sofort die Ausführung auf einen einzelnen Thread eingeschränkt (#pragma omp single). Der Grund hierfür ist, dass die Rekursion mit nur einem fib-Aufruf beginnt. Würde man nun ohne das single-Konstrukt arbeiten, so würden alle gestarteten Threads parallel fib(45) ausrechnen, was wenig zielführend ist. Mit #pragma omp single wird genau das verhindert.

Eine Frage der Granularität

Wann sind Tasks dem Programmieren mit Threads vorzuziehen? Um diese Frage zu beantworten, ist zunächst die Frage nach dem Overhead von Tasks im Vergleich zu Threads zu beantworten.

Ein Task ist eine Art Datenstruktur, die, ähnlich einer Closure (manchmal auch Funktionsabschluss genannt) in funktionalen Sprachen, ein Stück Code inklusive der zur Ausführung benötigten Daten speichert. Beim Erzeugen eines Tasks sind daher die benötigten Daten zu kopieren oder zumindest per Zeiger erreichbar zu hinterlegen. Hinzukommen dann je nach Implementierung und Task-Modell weitere Daten zur Verwaltung. Sobald die Datenvorbereitung abgeschlossen ist, kann der neu erzeugte Tasks in eine Warteschlange eingefügt werden. Die Warteschlange muss gegen parallelen Zugriff gesichert werden, da alle ausführenden Threads sie lesen und hineinschreiben. Die hierfür nötigen Sperroperationen kosten ebenfalls etwas Zeit.

Man kann sich nun überlegen, welche Ausführungszeit ein Task haben muss, damit dieser Overhead nicht allzu sehr ins Gewicht fällt. Für OpenMP liegt dieser Punkt bei rund 100.000 Taktzyklen, die ein Task rechnen muss, damit der Overhead noch tolerierbar klein bleibt. Bei Intel Threading Building Blocks liegt dieser Wert bei ungefähr 50.000 Zyklen.

Bei normalen Threads stellt sich die gleiche Frage. Einen Thread über das Betriebssystem zu erzeugen ist kostspielig. Die Erzeugung eines Threads kann leicht mehrere Millisekunden in Anspruch nehmen. Das bedeutet, dass der Overhead der Erzeugung nur dann kompensiert werden kann, wenn ein Thread Millionen von Instruktionen abarbeitet.

Tasks sind im Vergleich zu Threads also deutlich leichtgewichtiger und eignen sich daher besser für die Verteilung kleinerer Arbeitspakete. Aufgrund des Konzepts der Warteschlange, können Tasks auch modular verwendet werden. Eine Komponente, die Tasks erzeugt, lässt sich einfach mit einer anderen Komponente verbinden, die ihrerseits ebenfalls Tasks erzeugt. Die jeweilige Komponente fügt die erzeugten Tasks in die Warteschlange ein, wo sie sich automatisch mischen – und ausgeführt werden. Ähnliches mit Threads zu implementieren, ohne das System mit zu vielen Threads zu überlasten, ist zwar möglich, erfordert aber einen höheren Planungs- und Implementierungsaufwand.

Threads bleiben das Mittel der Wahl, wenn es um schwergewichtige Aufgaben geht. Typisches Beispiel sind Web- oder Applikationsserver, die Anfragen von Clients entgegennehmen und eventuell nach Datenbankanfragen ein Ergebnis zurücksenden. Gleiches gilt für Datenbankserver, die ankommende Anfragen parallel mit Threads bearbeiten und die Ergebnisse an den anfragenden Client liefern.

Andere klassische Domänen sind die Verteilung von Aufgaben in Applikationen, bei denen typischerweise ein Thread für die Bereitstellung der graphischen Oberfläche abgestellt wird und weitere Threads andere nebenläufige Aufgaben übernehmen.