Programmieren mit Tasks und parallelen Schleifen

Architektur/Methoden  –  13 Kommentare

Spätestens seitdem jeder Softwareentwickler einen Multicore-Rechner auf dem Schreibtisch oder Schoß hat, sind Threads fester Bestandteil vieler Anwendungen. Die Parallelisierung mit ihnen ist jedoch ein mühsames Unterfangen. Gesucht sind Alternativen und deren Umsetzung in den gängigen Programmiersprachen.

Man muss viel Zeit investieren, um ein Programm mit Threads so zu parallelisieren, dass es die verfügbare Rechenleistung effizient ausnutzt. Ein Grund dafür ist, dass das Erzeugen und Verwalten von Threads einen nicht unerheblichen Aufwand verursacht. Hinzu kommt, dass bei einem Thread-Wechsel der aktuelle Kontext (Prozessorregister etc.) zu sichern und der des auszuführenden Threads wiederherzustellen ist. Sind wesentlich mehr Threads rechenbereit als Prozessorkerne vorhanden, kommt es zur Überbelegung des Systems, die zu Leistungseinbußen führen kann.

"Multicore-Software" – das Buch

Der Artikel ist ein für heise Developer aufbereiteter Auszug aus dem im dpunkt.verlag erschienenen Buch "Multicore-Software", das sich auf rund 370 Seiten mit den Grundlagen, der Architektur sowie der Implementierung paralleler Software in C/C++, Java und C# auseinandersetzt.

Um das Potenzial von Multicore-Prozessoren ausschöpfen zu können, ist es wünschenswert, Parallelität auf einer feineren Ebene nutzen zu können. Zu dem Zweck bieten zeitgemäße Programmiersprachen und Bibliotheken zunehmend Programmiermodelle mit Tasks an. Diese erlauben es, ein Problem in kleine Teilaufgaben zu zerlegen und parallel auszuführen. Das Erzeugen eines Tasks ist vergleichsweise einfach und geht viel schneller vonstatten als das eines Threads. Deshalb sind Tasks auch gut für die Implementierung datenparalleler Algorithmen geeignet. Ein weiterer Vorteil ist die bessere Skalierbarkeit: Die meisten mit Tasks parallelisierten Programme lassen sich ohne Anpassungen auf Prozessoren mit unterschiedlich vielen Kernen effizient ausführen, sofern die Anzahl der Tasks groß genug ist.

Management by Delegation

Ein Task ist durch eine parallel zum Aufrufer ausführbare Einsprungsfunktion definiert. In der Regel lassen sich ihr ein oder mehrere Argumente übergeben. Darüber hinaus bieten Tasks spezielle Mechanismen zur Synchronisation an, die je nach Implementierung variieren. So kann man gezielt auf einzelne Tasks warten, auf die von einem "Eltern-Task" erzeugten "Kinder" oder auf eine explizit angegebene Liste beziehungsweise Gruppe von Tasks. Bei manchen Implementierungen hat man sogar die Wahl zwischen mehreren Möglichkeiten. Begonnen sei mit C++ und den Threading Building Blocks (TBB), einer von Intel entwickelten Bibliothek für die parallele Programmierung. Um beispielsweise eine Funktion f parallel zum aktuellen Programmstück auszuführen, legt man eine Task-Gruppe an und ruft anschließend deren run-Methode mit dem auszuführenden Task als Argument auf (mit den seit C++11 verfügbaren Lambda-Funktionen [1] geht das auf kompakte Weise). Die Synchronisation geschieht mit wait:

tbb::task_group group;
group.run([] {f();});
...
group.wait();

In Java verwendet man am besten den in der Version 7 hinzugekommenen ForkJoinPool. Da Java 7 jedoch keine Lambda-Funktionen unterstützt, ist zunächst eine Klasse vom Typ RecursiveAction beziehungsweise RecursiveTask<V> – letztere für Tasks, die ein Ergebnis zurückliefern – zu implementieren:

class MyTask extends RecursiveAction {
// ... Konstruktor
void compute() {
f()
}
}

Nach dem Erzeugen eines neuen ForkJoinPool lässt sich der Task folgendermaßen starten:

static final ForkJoinPool fjPool = new ForkJoinPool();
// ...
MyTask t = new MyTask();
fjPool.invoke(t);

Die Methode invoke wartet implizit auf das Ende des Tasks. Ist das nicht gewünscht, muss man den Task mit execute starten. Tasks, die aus dem Kontext eines laufenden Tasks gestartet werden sollen, stößt man mit invoke beziehungsweise fork (wartet nicht) der Klasse ForkJoinTask an. Das Warten auf mit fork gestartete Tasks erfolgt mit join. Daher der Name des Pools.

In C# sieht das aufgeräumter aus, insbesondere ist der Pool nicht explizit zu erzeugen:

Task t = new Task(f);
t.Start();
// ...
t.Wait();

Mit der alternativen Factory-Methode aus Task.Factory und Lambda-Funktionen ist das C#-Beispiel dem TBB-Beispiel sehr ähnlich:

Task t = Task.Factory.StartNew(() => f());
// ...
t.Wait();

Es ist deutlich zu erkennen, dass die zugrunde liegenden Konzepte überall die gleichen sind. Die Umsetzungen unterscheiden sich vor allem im Komfort der Benutzung sowie im Verhalten des Laufzeitsystems.

Wie bei Threads ist bei der parallelen Ausführung mehrerer Tasks Vorsicht geboten, da Zugriffe auf gemeinsame Variablen oder Ein-/Ausgabeoperationen zu unvorhergesehenen Fehlern führen können. Deshalb sollten Tasks keine Daten modifizieren, auf die parallel andere Tasks oder Threads zugreifen.

Teile und herrsche

Eine nützliche Eigenschaft von Tasks ist die Möglichkeit der verschachtelten Parallelität. Das bedeutet, dass sich innerhalb eines Tasks weitere Tasks erzeugen lassen. Auf diese Weise lassen sich rekursive Algorithmen nach dem "Teile und herrsche"-Prinzip oder das Durchlaufen baumartiger Datenstrukturen einfach parallelisieren. Ein typisches Beispiel ist der Quicksort-Algorithmus, der das zu sortierende Feld anhand eines Pivot-Elements zunächst in zwei Teile partitioniert. In einem zweiten Schritt werden die beiden Teile dann rekursiv sortiert. Die so entstehenden Teilbäume lassen sich parallel ausführen, indem für jeden Aufruf ein neuer Task erzeugt wird. Der folgende Quellcode zeigt die Vorgehensweise mit TBB (auf die Darstellung der Funktion partition haben die Autoren der Übersichtlichkeit halber verzichtet).

template <typename RAI> // RandomAccessIterator
void quicksort(const RAI begin, const RAI end) {
if(size_t(end-begin) > 1) { // Abbruch, falls nur noch ein Element
const RAI pivot = partition(begin, end); // Partitionierung
tbb::task_group group;
group.run([=] {quicksort(begin, pivot);});
group.run([=] {quicksort(pivot+1, end);});
group.wait();
}
}

Beim Ausführen des Algorithmus auf einem Multicore-Rechner stellt man schnell fest, dass er langsamer als die sequenzielle Variante ist. Der Grund dafür ist, dass sehr viele Tasks erzeugt werden, die einen erheblichen Mehraufwand verursachen. Zur Lösung des Problems muss man die Anzahl der erzeugten Tasks reduzieren. Dazu bricht man die Rekursion ab, wenn die Teilfelder eine bestimmte Größe erreicht haben, und sortiert sie sequenziell. Ihre Größe bezeichnet man als Körnung (engl. grain size) und ist so zu wählen, dass alle Prozessorkerne gut ausgelastet sind. Dabei sollte man eine Reserve einplanen, um Leerlaufzeiten zu vermeiden, die entstehen können, wenn die Tasks unterschiedliche Laufzeiten haben. Bei Quicksort kann es je nach Wahl des Pivot-Elements nämlich passieren, dass die Teile unterschiedlich groß sind und das Sortieren der Teilfelder somit unterschiedlich viel Zeit in Anspruch nimmt.

Eine weitere Optimierung ist, den zweiten Aufruf von quicksort direkt im aktuellen Task auszuführen, wodurch nicht für beide Aufrufe jeweils ein neuer Task zu erzeugen ist. Außerdem genügt es, nur einmal am Ende mit wait zu synchronisieren. Ein Aufruf von wait bei jedem Rekursionsschritt ist nur notwendig, wenn die Tasks Ergebnisse zurückliefern, die weiterzuverarbeiten sind. Die optimierte Fassung des Beispiels ist in dem nächsten Codestück zu sehen.

template <typename RAI> // RandomAccessIterator
void quicksort_recursive(const RAI begin, const RAI end,
const size_t grainsize, tbb::task_group& group) {
if(size_t(end-begin) > grainsize) {
const RAI pivot = partition(begin, end);
group.run([=, &group] {quicksort_recursive(begin,
pivot, grainsize, group);});
quicksort_recursive(pivot+1, end, grainsize, group);
}
else
std::sort(begin, end); // sequenziell sortieren
}

template <typename RAI>
void quicksort(const RAI begin, const RAI end) {
const size_t grainsize = size_t(end-begin) /
(NUMBER_OF_CORES * C); // z.B. C = 2
tbb::task_group group;
quicksort_recursive(begin, end, grainsize, group);
group.wait(); // auf das Ende aller Tasks warten
}

Weiterführende Informationen zu parallelen Sortierverfahren sind in den Schriften von Cormen, Leiserson, Rivest und Stein [2] sowie von Miller und Boxer [3] zu finden.

Spekulation, Task-Scheduling

Auf Verdacht

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.

Warten bremst

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.

Stehlen erlaubt

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.

Datenparallelität

Häppchenweise

Tasks erlauben es, unterschiedliche Funktionen parallel auszuführen. Eine andere Quelle der Parallelität ist die Ausführung einer Funktion auf einer Menge gleichartiger Daten durch Schleifen. Parallele Schleifen folgen dem SIMD-Prinzip (Single Instruction, Multiple Data) und bilden die Grundlage für die Verarbeitung regulärer Datenstrukturen wie Felder. Ein Paradebeispiel dafür sind Algorithmen aus der Bildverarbeitung, bei denen sich alle Pixel eines Bilds im Prinzip parallel verarbeiten lassen.

Sofern zwischen den Iterationen einer Schleife keine Abhängigkeiten bestehen, könnte man für jede Iteration einen Task erzeugen, der den Schleifenrumpf ausführt. In der Praxis ist das jedoch ineffizient, wenn das Feld groß ist und eine Iteration nur wenig Zeit in Anspruch nimmt. Wesentlicher effizienter ist es, wie beim Quicksort-Beispiel, die Datenstruktur in Blöcke zu unterteilen und diese jeweils sequenziell zu verarbeiten. Das bedeutet, statt für jede Iteration nur für jeden Block einen eigenen Task zu erzeugen. Glücklicherweise muss man sich um die Partitionierung in der Regel nicht kümmern; die meisten Sprachen und Bibliotheken bieten fertige Konstrukte für parallele Schleifen an. In TBB gibt es das Funktions-Template parallel_for, das neben dem Iterationsbereich den Schleifenrumpf in Form einer Lambda-Funktion oder eines Funktionsobjekts entgegennimmt. Damit lässt sich zum Beispiel das Inkrementieren der Elemente eines Vektors leicht bewerkstelligen:

std::vector<int> v;
// ... Initialisierung
tbb::parallel_for(size_t(0), v.size(), [&v]
(size_t i) {vv[i]++;});

Optional kann man parallel_for eine Schrittweite übergeben. Für komplexere Schleifen, insbesondere für solche über mehrdimensionalen Bereichen, stellt TBB Varianten von parallel_for zur Verfügung, die es erlauben, auf die Partitionierung Einfluss zu nehmen. Zudem gibt es mit parallel_do ein Funktions-Template, das es erlaubt, der zu verarbeitenden Sequenz dynamisch weitere Elemente hinzuzufügen.

Java 7 bietet noch keine direkte Unterstützung für Datenparallelität. Der Grund dafür ist vor allem, dass Lambda-Funktionen noch nicht Teil der Sprache sind. Datenparallele Operationen lassen sich damit wesentlich besser handhaben, was die Implementierungen in .NET und TBB zeigen. Es sind allerdings parallele Array-Operationen in Planung.

Parallele Schleifen in C# sehen wiederum ähnlich zu denen in TBB aus:

int[] v; 
// ... Initialisierung
Parallel.For(0, v.Length, i => {v[i]++;});

Die zweite Form von parallelen Schleifen in C# dient der parallelen Verarbeitung von Aufzählungen (IEnumerable) mit Parallel.ForEach. Die obige Schleife würde damit wie folgt aussehen:

Parallel.ForEach(Enumerable.Range(0, v.Length), i 
=> {v[i]++;});

Ein Vorteil von Parallel.ForEach ist, dass die Daten zu Beginn der Verarbeitung nicht vollständig vorliegen müssen. Eine Datenstruktur mit IEnumerable-Schnittstelle lässt sich zum Beispiel durch einen Thread füllen und durch einen anderen Thread abarbeiten. Daher ist auch die Partitionierungsstrategie anders als bei Parallel.For. Es wird zunächst mit kleinen Blöcken begonnen, um schnell möglichst vielen Kernen Arbeit zu verschaffen. Dann wird die Blockgröße sukzessive erhöht. Bei Parallel.ForEach lassen sich zudem eigene oder vorgefertigte Strategien für die Partitionierung des Iterationsbereichs angeben.

Eine Falle, die man beim Umgang mit parallelen Schleifen tunlichst meiden sollte, betrifft die Initialisierung der Datenstrukturen. Bei Rechnern mit verteiltem, gemeinsamem Speicher, sogenannten NUMA-Systemen (Non-Uniform Memory Access), steht zum Zeitpunkt der Allokation eines Speicherbereichs die Abbildung der virtuellen auf die physikalischen Speicherseiten in der Regel noch nicht fest. Bei den meisten Betriebssystemen kommt hierfür die Strategie des First-touch Placement zum Einsatz, bei der eine Seite im Speicher des Prozessors landet, der als Erster darauf zugreift. Auf diese Weise soll eine Verteilung der Speicherbereiche unter Beibehaltung einer möglichst hohen Datenlokalität erreicht werden. Initialisiert man nun eine große Datenstruktur sequenziell, landen die Speicherseiten mit hoher Wahrscheinlichkeit in nur einem physikalischen Speicher, der bei späteren parallelen Zugriffen einen Flaschenhals bildet. Deshalb sollte die Initialisierung parallel erfolgen.

Auch Schleifen mit Datenabhängigkeiten zwischen den Iterationen lassen sich in vielen Fällen parallelisieren. Eine häufig anzutreffende Abhängigkeit ist die Akkumulation von Werten in einer gemeinsamen Variable. Solche Berechnungen bezeichnet man als Reduktionen oder Aggregationen. Betrachtet sei zunächst die sequenzielle Berechnung der Summe der Elemente eines Vektors in C++:

std::vector<double> v;
// ... Initialisierung
double sum = 0;
for(double x : v)
sum += x;

Ein naheliegender Ansatz für die Parallelisierung dieser Schleife ist, die Zugriffe auf sum zu synchronisieren, sodass sie sich mit parallel_for oder vergleichbaren Funktionen ausführen lässt. Dieser Ansatz ist jedoch alles andere als optimal, da Zugriffe auf gemeinsame Variablen zwangsläufig ein Nadelöhr sind. Eine signifikante Beschleunigung ist deshalb nicht zu erwarten. Wesentlich besser ist es, blockweise Teilsummen zu berechnen und diese dann aufzuaddieren.

TBB bietet für Reduktionen das Funktions-Template parallel_reduce an, das nicht auf die Addition von Werten beschränkt, sondern universell einsetzbar ist. Deshalb erfordert die Summenberechnung etwas Schreibarbeit (siehe auch das folgende Beispiel). Als ersten Parameter übergibt man parallel_reduce den zu reduzierenden Bereich in Form eines Objekts vom Typ blocked_range. Darauf folgt der Wert 0.0, der als Startwert für die Summenberechnung verwendet wird. Der dritte Parameter ist eine Lambda-Funktion, die für einen gegebenen Block die Teilsumme berechnet. Als letzten Parameter übergibt man ebenfalls eine Lambda-Funktion, die für jeweils zwei Blöcke die Teilsummen aufaddiert. Auf die gleiche Weise kann man Produkte, Minima, Maxima etc. berechnen. Einzige Voraussetzung ist, dass die zugrunde liegende Operation assoziativ im mathematischen Sinne ist. Aufgrund von Rundungsfehlern bei Gleitkommazahlen ist das Ergebnis einer parallelen Reduktion jedoch nicht unbedingt identisch mit dem eines sequenziellen Algorithmus.

double SumVectorElements(const std::vector<double>& v) {
return tbb::parallel_reduce(
// zu reduzierender Bereich
tbb::blocked_range<size_t>(size_t(0), v.size()),
// Startwert (neutrales Element der Addition)
0.0,
// Berechnung der Teilsumme eines Blocks
[&v] (const tbb::blocked_range<size_t>& range, double x) -> double {
for(size_t i = range.begin(); i != range.end(); i++)
x += v[i];
return x;
},
// Aufaddieren der Teilsummen zweier Blöcke
[] (double x, double y) {return x + y;});
}

Sowohl Parallel.For als auch Parallel.ForEach in C# unterstützen Thread-lokalen Speicher für Zwischenergebnisse, was die parallele Aggregation vereinfacht. Das folgende Listing zeigt die Summenberechnung mit der generischen Variante von Parallel.For. Der angegebene Typ (double) ist der Typ der Thread-lokalen Daten. Es folgen der Iterationsbereich und eine Funktion, die die Thread-lokalen Daten initialisiert. Das nächste Argument ist eine Funktion, die die eigentliche Arbeit verrichtet. Sie bekommt von der Parallel.For-Implementierung eine Thread-lokale Variable übergeben, in der sie die jeweilige Teilsumme speichert. Eine Synchronisation ist nicht erforderlich, da per Definition nur ein Thread die Variable verwendet. Das letzte Argument umfasst den Aggregationsschritt, den am Schluss jeder beteiligte Thread ausführt. Erst hier wird durch Einsatz einer Sperre die Gesamtsumme gebildet. Da das aber nur einmal pro Thread und nicht einmal pro Task passiert, ist der Aufwand für die Synchronisation vernachlässigbar.

static double SumArrayElements(double[] a) {
double sum = 0;
object sumLock = new object();
Parallel.For<double>(
0, // von (inklusive)
a.Length, // bis (exklusive)
() => 0, // Initialisierung der Thread-lokalen Teilsummen
// Schleifenrumpf für die Berechnung der Teilsummen:
(i, loopState, threadLocalSum) => {
return threadLocalSum + a[i];
},
// Aggregationsfunktion für die Berechnung der Gesamtsumme:
partialSum => {
lock (sumLock) sum += partialSum;
}
);
return sum;
}

Die Implementierung leidet jedoch an der geringen Anzahl der im Schleifenrumpf ausgeführten Befehle. Allein dass in jeder Iteration ein Funktionsaufruf stattfindet, kostet viel Zeit. Dem lässt sich durch das Verwenden eines Partitioners entgegenwirken. Das nächste Beispiel zeigt das Endergebnis im "Vollausbau". Anstelle des Iterationsbereichs übergibt man einen Partitioner, und im Schleifenrumpf verarbeitet man mit einer sequenziellen for-Schleife jeweils einen ganzen Block.

static double SumArrayElementsPartitioner(double[] a) {
double sum = 0;
object sumLock = new object();
Parallel.ForEach<Tuple<int, int>, double>(
Partitioner.Create(0, a.Length),
() => 0,
(range, loopState, threadLocalSum) => {
double rangeSum = 0;
for (int i = range.Item1; i < range.Item2; i++) {
rangeSum += a[i];
}
return threadLocalSum + rangeSum;
},
partialSum => {
lock (sumLock) sum += partialSum;
}
);
return sum;
}

Fazit

Konstrukte für die Nutzung von Task- und Datenparallelität sind die Grundbausteine zahlreicher Anwendungen und gehören zum Handwerkszeug eines jeden Softwareentwicklers, der sich die Leistung moderner Prozessoren zunutze machen möchte. Zusammen mit einer auf Multicore-Systeme optimierten Implementierung des darunter liegenden Laufzeitsystems bilden diese Konstrukte ein mächtiges Programmiermodell für parallele Systeme.

In der Literatur findet sich eine Vielzahl weiterer über den Artikel hinausgehender Entwurfsmuster und Techniken, etwa Futures, die die Entwicklung paralleler Software vereinfachen [5]. Dazu gehören auch für den parallelen Zugriff optimierte Datenstrukturen. (ane)

Urs Gleim
leitet bei der Corporate Technology der Siemens AG ein Team mit den Arbeitsschwerpunkten Softwarearchitekturen und Programmiermodelle zur Parallelisierung industrieller Anwendungen.

Dr. Tobias Schüle
ist ebenfalls Mitarbeiter bei Siemens Corporate Technology. Sein Hauptinteresse gilt neben parallelen Programmiermodellen der Architektur und Implementierung von Software für Multicore-Systeme.

Literatur
  1. International Organization for Standardization; Information Technology – Programming Languages – C++ (ISO/IEC 14882:2011), 2011
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein; Introduction to Algorithms; MIT Press 2009 (3. Aufl.)
  3. Russ Miller, Laurence Boxer; Algorithms Sequential & Parallel; A Unified Approach; Charles River Media, 2005
  4. Robert D. Blumofe, Charles E. Leiserson; Scheduling Multithreaded Computations by Work Stealing; Symposium on Foundations of Computer Science (FOCS); IEEE, 1994, S. 356 ff.
  5. Urs Gleim, Tobias Schüle; Multicore-Software; dpunkt.verlag 2012