© Leonid Shcheglov, 123RF.com

Intels Bibliothek Threading Building Blocks hilft dem C++-Programmierer, die Rechenarbeit parallel auf die vielen Prozessoren oder Kerne moderner Computer zu verteilen. Dabei ersetzt das elegante Task-Konzept die leidige Verwaltung von Threads.

Die Threading Building Blocks (TBB) von Intel helfen bereits seit 2006 bei der Programmierung für Multicore- und SMP-Systeme. Die Bibliothek enthält eine Sammlung verschiedener Mechanismen zum Schreiben paralleler Programme in der Programmiersprache C++. Die TBB orientieren sich in vielen Konzepten an der Standard Template Library (STL). Sie sind inzwischen in Version 3.0 und auch als GPLv2-lizenzierte Ausgabe erhältlich, die funktional identisch zur kommerziellen Version ist [1]. Als Plattformen unterstützt die Bibliothek Linux, Windows und Mac OS X.

Die aktuelle TBB-Version 3.0 berücksichtigt die Erfahrungen der vergangenen Jahre, orientiert sich insbesondere am kommenden C++0x-Standard [2] und unterstützt beispielsweise die dort eingeführten Lambda-Funktionen. Dieser Artikel stellt die Neuerungen seit dem Linux-Magazin-Beitrag zu Version 1 [3] vor und vertieft einige der Konzepte, die dem Entwickler dabei helfen, skalierbaren Code für Mehrprozessor- und Mehrkern-Computer zu schreiben.

Abstraktion

Die zugrunde liegende Philosophie der Bibliothek ist es, dem Programmierer eine abstraktere Schnittstelle als beispielsweise die Pthreads von Linux bereitzustellen und ihn von sehr Betriebssystem-naher Programmierung zu befreien. Die Template-Funktionen zum Parallelisieren von Schleifen hat Intel um »parallel_invoke()« erweitert, das im Unterschied zu den Varianten von »parallel_for()« auch verschiedene Funktionen parallel ausführt, nicht immer nur dieselbe.

Wenn parallele Threads sich gegenseitig ihren Cache zerstören, obwohl sie auf unterschiedlichen Daten arbeiten, bezeichnet man das als False Sharing. Mit Hilfe von Allokatoren-Klassen zur Cache-sensitiven Reservierung des Hauptspeichers lässt sich dieses Phänomen vermeiden. Die Containerklassen der STL sind nicht gegen einen gleichzeitigen Zugriff paralleler Threads geschützt. Die TBB führen daher Containerklassen für Vektoren, Hashtabellen und Warteschlangen ein, die Thread-safe sind. Deren Umfang ist stark gewachsen und umfasst jetzt auch »concurrent_unordered_map« und »concurrent_bounded_queue« . Der Programmierer muss aber bei der Verwendung im Kleingedruckten lesen, was Thread-safe im Einzelfall bedeutet.

Zum Synchronisieren von parallel arbeitenden Threads stellen die TBB beim Zugriff auf gemeinsame Objekte eine Reihe von Mutex-Klassen zur Verfügung. Für einige Anwendungen sind atomare Operationen wie Compare and Swap, bei der Operationen zum Vergleichen und Vertauschen unteilbar ausgeführt werden, wesentlicher schneller.

Tausende Tasks

Insbesondere das Task-Konzept der TBB bietet im Gegensatz zu Threads eine einfache Möglichkeit, ein Programm skalierbar zu machen – unabhängig von der tatsächlichen Anzahl physikalischer Rechenkerne. Eine Task ist eine parallele Aufgabe, die den Vorteil hat, dass sie sich im Gegensatz zu den Threads des Betriebssystems effizient erzeugen und löschen lässt. So sind sehr viele Tasks – Tausende bis Hunderttausende – in der eigenen Anwendung einsetzbar. Dieser Artikel zeigt am Beispiel eines Sudoku-Lösers, wie das geht.

Des Weiteren sind einige Klassen für eine einfache Zeitmessung, beispielsweise »tick_count« , jetzt Bestandteil der TBB. Darüber hinaus ermöglicht es die aktuelle Version, Thread-lokalen Speicher zu verwenden.

Parallele Schleifen

Schleifen sind einfach zu parallelisieren, wenn die einzelnen Ausführungen des Schleifenrumpfes voneinander unabhängig sind und die Berechnungen nicht aufeinander aufbauen. Das ist zwar nicht immer, aber oft genug der Fall. Das parallele Äquivalent zur C-Schleife ist »parallel_for« . Hierbei handelt es sich um ein Funktionstemplate, das als

template<typename Range, typename Body>
void parallel_for(const Range& range, const Body& body [, partitioner]);

deklariert ist und drei Parameter besitzt: den Wertebereich »range« , den eigentlichen Schleifenrumpf »body« und optional einen Partitionierer »partitioner« . Der Wertebereich definiert das halboffene Intervall »[a,…,b)« , das die Schleife durchläuft. Für jeden Wert wird der Schleifenrumpf einmal ausgeführt. Dies entspricht einer sequenziellen Schleife der Anweisung »for(i=a;i<b;i++)« .

Die TBB bieten mehrere Wertebereich-Klassen an. Die Anweisung

blocked_range::blocked_range(Value begin,Value end,size_type grainsize=1);

deklariert den Konstruktor der »blocked_range« -Klasse für den eindimensionalen Fall. Da allerdings insbesondere bei sehr wenigen Befehlen im Rumpf der Verwaltungsaufwand zu groß gegenüber dem Parallelitätsgewinn ist, unterteilt der Partitionierer den gesamten Wertebereich rekursiv in einzelne Teilintervalle (Extremfall: ein Element pro Teilintervall). Die Granularität »grainsize« beschreibt die minimal mögliche Größe eines Teilintervalls. Zusätzlich besitzt die »blocked_range« -Klasse noch die zwei Methoden »begin()« und »end()« , die die rechte und die linke Grenze des Wertebereichs liefern. Der Schleifenrumpf »Body« ist ein Funktionsobjekt oder Funktor, das einen Kopierkonstruktor, einen Destruktor und den »()« -Operator benötigt.

Der Partitionierer erzeugt für jedes Teilintervall ein »Body« -Objekt, anschließend kommt der »()« -Operator zur parallelen Ausführung. In einer sequenziellen Schleife wird dann für jedes Element des Intervalls »range« der eigentliche Schleifenrumpf implementiert.

Beispiel: Initialisierung eines Feldes

Das folgende Beispiel verdeutlicht die Anwendung einer parallelen For-Schleife. Es initialisiert ein Feld von Zahlen so, dass das i-te Element den Wert i erhält. Die »ArrayInitializer« -Klasse in Listing 1 enthält als Attribut den Zeiger auf den Anfang des Feldes, der dem Konstruktor übergeben wird. Der »()« -Operator besteht aus einer sequenziellen »while« -Schleife, die mit Hilfe eines Iterators alle Elemente des Teilintervalls durchläuft und ein Feldelement nach dem anderen initialisiert. Auf einen expliziten Kopierkonstruktor und Destruktor verzichtet dieses sehr einfache Beispiel.

01 class ArrayInitializer {
02     int* array;
03 public:
04     ArrayInitializer(int* a):array(a){}
05     void operator()(const blocked_range<unsigned int>& range) const {
06         blocked_range<unsigned int>::const_iterator it=range.begin();
07                 while (it!=range.end()) {
08                 array[it]=it;
09                 it++;
10             }
11         }
12 };

Auch wenn viele parallele Rechenkerne auf dasselbe Feld gleichzeitig zugreifen, muss der Zugriff nicht geschützt werden, weil die TBB dafür Sorge tragen, dass die Teilintervalle sich nicht überlappen. Die folgenden Codezeilen initialisieren parallel ein Feld in der Größe von »size« Elementen:

int* arr=new int[size];
ArrayInitializer init(arr);
parallel_for(blocked_range<unsigned int>(0,size,grain),init);

Der Parameter »grain« gibt die Grenze an, bis zu der der Partitionierer die Intervalle rekursiv unterteilt – die tatsächliche Untergrenze legen die TBB bei »grain/2« fest. Standardmäßig übernimmt der »auto_partitioner« die Aufteilung des Wertebereichs, sofern der Programmierer nicht einen anderen in der parallelen Schleife angibt.

Der automatische Partitionierer sieht sich das Laufzeitverhalten an und unterteilt nur dann, wenn ein Rechenkern Gefahr läuft, untätig zu werden. Das führt zu einer minimalen Anzahl von Partitionen. Beispielsweise erzeugt der Partitionierer bei zwei Rechenkernen zwei gleich große Intervalle, welche die TBB dann parallel initialisieren. Ist dieses Verhalten nicht erwünscht, kann stattdessen der »simple_partitioner« zum Einsatz kommen, der den gesamten Wertebereich stumpf in (fast) gleich große Teilintervalle unterteilt, wobei der Parameter »grain« die obere Grenze angibt.

Der Partitionierer ist als Parameter beim Aufruf der Schleife anzugeben:

simple_partitioner sp;
parallel_for(blocked_range<unsigned int>(0,size,grain),init,sp);

Neben dem »simple_partitioner« existiert noch der »affinity_partitioner« , dessen Einsatz sinnvoll ist, wenn die Daten komplett in den Cache passen und die Schleife mehrfach durchlaufen wird. Dieser Partitionierer merkt sich, wie der Wertebereich im vorherigen Durchlauf unterteilt war, um so auszunutzen, dass sich die Daten noch im Cache des entsprechenden Rechenkerns befinden.

Partitionierung

Viele Aufgabenstellungen sind mit einer parallelen Schleife effizient zu lösen. Dies trifft besonders dann zu, wenn die Daten linear oder mehrdimensional angeordnet sind und somit eine Partitionierung der Daten offensichtlich ist. Andererseits gibt es eine Reihe von Problemen, bei denen eine Baum- oder allgemeiner eine Graphenstruktur nach möglichen Lösungen zu durchsuchen ist. Ein Beispiel hierfür ist ein Schachprogramm, das eine Vielzahl von Spielstellungen untersucht und bewertet.

In der parallelen Programmierung eignen sich Threads für die Bewältigung solcher Aufgabenstellungen. Allerdings ist die Thread-Programmierung fehleranfällig, weshalb die TBB mit der Einführung des Task-Konzepts eine neue Möglichkeit zur Handhabung paralleler Kontrollflüsse anbieten. Ein weiterer Vorteil ist, dass wenig oder gar kein Wissen über die verwendete Hardware notwendig ist.

Arbeiten mit Tasks

Eine Task ist eine Abstraktion außerhalb des Betriebssystems und lässt sich als logischer Thread verstehen. Abbildung 1 skizziert die Schichtenaufteilung von Task, Thread und physikalischen Rechenkernen. Es werden hierbei m Tasks auf n Threads abgebildet. Ein Thread ist eins zu eins einem Rechenkern zugeordnet. Um eine gute Skalierung zu erreichen, unterstellen die TBB, dass m sehr viel größer als n ist. Während Threads Elemente des zugrunde liegenden Betriebssystems sind, die beim Scheduling einen aufwändigen Kontextwechsel notwendig machen, arbeiten Tasks komplett im Benutzermodus.

Abbildung 1: Abstraktionsebenen bei der Arbeit mit den TBB: Eine Gruppe von Tasks bildet sich auf einen Thread des Betriebssystems und auf einen Rechenkern der Hardware ab.

Das Verhalten einer Task ähnelt dem eines Thread, allerdings gelten einige Unterschiede:

• Nicht-Unterbrechbarkeit: Die Ausführung einer Task lässt sich nicht unterbrechen. Ausnahmen sind das Starten einer Kind-Task sowie der Zugriff auf gemeinsam genutzte und geschützte Ressourcen aus der Task heraus.
• Unfaires Scheduling: Ein Thread bearbeitet eine Task bis zum Ende des definierten Kontrollflusses ohne Unterbrechung. Es findet kein Scheduling anderer Tasks statt (Ausnahme: Starten einer Kind-Task).
• Task-Stealing: Falls ein Thread keine Task mehr zur Ausführung vorliegen hat, besteht die Möglichkeit, dass dieser noch nicht bearbeitete Tasks von einem anderem Thread übernimmt und ausführt (“stiehlt”).

Durch das unfaire Scheduling fällt der sonst übliche Verwaltungsaufwand sehr gering aus: Ein Thread führt eine Task so lange aus, bis diese beendet ist. Hier gibt es allerdings eine Nebenwirkung, die im ungünstigen Fall gegen eine Verwendung des Task-Konzepts spricht: Wenn eine Task blockiert, weil sie etwa auf ein Semaphor wartet, wird der ausführende Thread suspendiert. Ein Scheduling wartender Tasks findet nicht statt.

Da es genauso viele Threads wie Rechenkerne gibt, folgt aus der Suspendierung eines Thread, dass sich ein Kern im Leerlauf befindet, wodurch der Parallelitätsgewinn abnimmt. Das Task-Konzept sollte man also nicht einsetzen, wenn das Programm sehr viele blockierende Synchronisationsmittel verwendet. Dies ist ohnehin ein schlechtes Zeichen für den Einsatz von Parallelisierung.

Durch Vererbung von der virtuellen Oberklasse »task« aus der TBB-Bibliothek realisiert der Programmierer eine eigene Task-Klasse. Die Klasse muss zusätzlich zum Konstruktor die Methode »execute()« implementieren, die den Kontrollfluss einer Task enthält (Listing 2).

01 class MyTask : public task {
02 public:
03     MyTask(Parameter) {...}
04     task* execute() {...}
05 };

Abbildung 2 zeigt die baumartige Struktur bei der Erzeugung von Task-Objekten. Es gibt eine ausgezeichnete Wurzel-Task, während alle anderen Tasks vom Typ Kinder-Task sind. Das Erzeugen einer Task erfolgt durch spezielle, überladene »new« -Operatoren der TBB-Bibliothek. Folgender Code erzeugt eine Wurzel-Task:

Abbildung 2: Die Wurzel-Task W bekommt Kinder, die wieder Kinder-Tasks haben können.

MyTask* root = new (allocate_root())MyTask(Parameter);

So entsteht eine Kind-Task:

MyTask* child = new (allocate_child())MyTask(Parameter);

Der »new« -Operator legt die Objekte im Speicher an, führt sie aber noch nicht aus. In vielen Fällen sind mehrere Kinder-Objekte zu erzeugen. Hierzu bietet die TBB eine »task_list« -Klasse an, in der die Methode »push_back()« beliebig viele Tasks anhängt.

Eine Menge von Tasks startet gemeinsam durch:

set_ref_count(count+1);
spawn_and_wait_for_all(list);

Zuvor muss der Entwickler mit »set_ref_count()« einen internen Referenzzähler setzen, um später festzustellen, wie viele Tasks sich zurückmelden müssen (wobei die TBB die wartende Eltern-Task mitzählen). Im Beispiel gibt »count« die Anzahl der Elemente von »list« an.

Der »spawn_and_wait_for_all()« -Aufruf suspendiert die aufrufende Task so lange, bis alle gestarteten Kinder-Tasks die Ausführung der jeweiligen »execute()« -Methode beendet haben. Jedoch ist danach kein Zugriff mehr auf die Kinder-Tasks möglich, weil TBB nach Ende von »execute« den Destruktor der Kinder aufruft. Um Daten der Kind-Task an die Eltern-Task zurückzugeben, muss man entweder globalen Speicher oder (besser) lokalen Speicher der Eltern-Task verwenden.

Paralleler Sudoku-Löser

Als Beispielanwendung für diesen Ansatz, der dem Entwurfsmuster Fork-Join entspricht, soll ein parallelisierter Sudoku-Löser dienen. Die vollständigen Code-Listings finden sich unter [4]. Sudoku ist ein mathematisches Rätselspiel, das oft in Tageszeitungen zu finden ist. Das Spielfeld besteht aus 81 Feldern, die in neun Zeilen und neun Spalten quadratisch angeordnet sind. Diese Felder gliedern sich noch einmal quadratisch in neun Blöcke mit jeweils drei mal drei Feldern. Die Aufgabe besteht darin, die 81 Felder mit Zahlen von 1 bis 9 so zu belegen, dass pro Zeile, pro Spalte und pro Block keine Zahl doppelt vorkommt. In Abbildung 3 ist ein einfaches Sudoku dargestellt, bei dem 50 Felder bereits vorbelegt sind.

Abbildung 3: Beim Sudoku müssen alle Felder mit Zahlen von 1 bis 9 belegt werden. Eine Ziffer darf in Reihe, Spalte und Block nur einmal vorkommen.

Die »Sudoku« -Klasse (Listing 3) besteht daher aus einem 9-mal-9-Feld mit Zahlen zwischen 0 und 9, wobei die 0 bedeutet, dass das entsprechende Feld noch nicht belegt ist. Die Methode »nextfree()« liefert das nächste freie Feld zurück – beziehungsweise »false« , wenn alle Felder belegt sind und das Sudoku-Rätsel damit gelöst ist. Die Methode durchsucht zeilenweise die 81 Felder, bis sie ein leeres findet. Die Methode »check()« überprüft, ob eine Zahl (»number« ) für ein freies Feld möglich ist. Hierzu prüft sie in Zeile, Spalte und Block, ob die Zahl bereits vergeben wurde.

01 const char EMPTY = 0;
02 const int LENGTH = 9;
03 const int SQUARE = LENGTH * LENGTH;
04
05 class Sudoku {
06 public:
07     Sudoku() { memset(square,EMPTY,SQUARE); }
08
09     bool check(int x, int y, char number) const;
10     bool nextfree(int& x, int& y);
11
12     char at(int x, int y) const { return square[y*LENGTH+x]; }
13     char& at(int x,int y) { return square[y*LENGTH+x]; }
14
15     void print();
16     void read(const char* fname);
17     void write(const char* fname);
18
19 private:
20
21     char square[SQUARE];
22
23 };
24
25 bool Sudoku::check(int x, int y, char number) const {
26     bool retvalue=true;
27     int i=0,bi=3*(x/3),bj=3*(y/3);
28     while (i<LENGTH && retvalue==true) {
29         if (at(x,i)==number || at(i,y)==number || at(bi+i%3,bj+i/3)==number)
30             retvalue=false;
31         i++;
32     }
33     return retvalue;
34 }
35
36 bool Sudoku::nextfree(int& x, int& y) {
37     bool retvalue=true;
38     int i=0;
39     while (i<SQUARE && square[i]!=EMPTY)
40         i++;
41     if (i!=SQUARE) {
42         y=i/LENGTH;
43         x=i%LENGTH;
44     } else
45         retvalue=false;
46     return retvalue;
47 }

Die »SudokuTask« (Listing 4) ist eine Spezialisierung der TBB-Task-Klasse und übernimmt die Aufgabe, ein unvollständiges Sudoku-Rätsel mit einer weiteren Zahl zu vervollständigen, um dann rekursiv neue Kinder-Tasks auszuführen. Der Konstruktor erhält zwei Parameter, zum einen das »Sudoku« -Objekt und zum anderen einen Zähler für die Anzahl der erzeugten Kinder-Tasks.

01 #include "tbb/task.h"
02 using namespace tbb;
03
04 #include "sudoku.h"
05
06 class SudokuTask : public task {
07 public:
08     SudokuTask(Sudoku* p,unsigned long* sub):puzzle(p),subtasks(sub) {};
09     ~SudokuTask() { delete puzzle; }
10
11     task* execute();
12 private:
13     Sudoku* puzzle;
14     unsigned long* subtasks;
15
16 };
17
18 task* SudokuTask::execute() {
19     int x=-1,y=-1;
20     *subtasks=0;
21
22     if (puzzle->nextfree(x,y)==true) {
23         unsigned long childtasks[LENGTH]={0};
24         int count=0;
25         task_list list;
26
27         for(int i=1;i<=LENGTH;i++) {
28             if (puzzle->check(x,y,i)==true) {
29                 Sudoku* childpuzzle=new Sudoku(*puzzle);
30                 childpuzzle->at(x,y)=i;
31                 list.push_back(*new(allocate_child())SudokuTask(childpuzzle,childtasks+count));
32                 count++;
33             }
34         }
35         if (count>0) {
36             set_ref_count(count+1);
37             spawn_and_wait_for_all(list);
38             for(int i=0;i<LENGTH;i++)
39                 *subtasks+=childtasks[i];
40                 *subtasks+=count;
41         }
42     } else {
43         cout << "Solution found." << endl;
44         puzzle->print();
45     }
46
47     return NULL;
48 }

Sehr wichtig ist hierbei, dass der Programmierer den zweiten Parameter als Zeiger übergibt. Da die TBB-Bibliothek nach Ende der »execute« -Methode die Task automatisch löscht, ist es allerdings unmöglich, Ergebnisse der Kind- an die Eltern-Task zu übergeben. Daher erhält die Kind-Task einen Zeiger auf eine Speicherstelle, in die das Ergebnis einzutragen ist. Da die Eltern-Task während der Ausführung der Kinder pausiert, ist sichergestellt, dass kein anderer auf diese Speicherstelle zugreift.

Wie arbeitet nun die »execute()« -Methode? Der Aufruf »nextfree()« liefert das nächste freie Feld zurück. Anschließend testet eine Schleife für alle Zahlen zwischen 1 und 9, ob diese als Kandidat für das Feld in Frage kommen. Für jeden ermittelten Kandidaten erzeugt das Programm eine neue Kind-Task und speichert diese in einer Liste. Der Aufruf »spawn_and_wait_for_all()« startet die Kinder-Tasks und pausiert die aufrufende Eltern-Task. Wenn alle Kinder sich zurückgemeldet haben, werden die Ergebnisse eingesammelt.

Listing 5 enthält das Hauptprogramm. Die Wurzel-Task erzeugt rekursiv sehr viele Kinder-Tasks. Den Rest erledigt die TBB-Bibliothek und verteilt diese Task-Objekte auf die einzelnen Threads. Der Entwickler ist vom Programmieren mit Threads und tückischen Problemen wie etwa Deadlocks befreit.

01 #include <iostream>
02 #include <cstdlib>
03 using namespace std;
04
05 #include "tbb/task_scheduler_init.h"
06 #include "tbb/tick_count.h"
07 using namespace tbb;
08
09 #include "sudoku.h"
10 #include "SudokuTask.h"
11
12 int main(int argc, char* argv[]) {
13     cout << "Sudoku Solver Using Intel's Threading Building Blocks." << endl;
14
15     task_scheduler_init init(argc==3 ? atoi(argv[2]) : task_scheduler_init::default_num_threads());
16
17     Sudoku* puzzle=new Sudoku;
18     puzzle->read(argv[1]);
19     puzzle->print();
20
21     unsigned long subtasks=0;
22     SudokuTask* root=new(task::allocate_root())SudokuTask(puzzle,&subtasks);
23
24     tick_count t0=tick_count::now();
25     task::spawn_root_and_wait(*root);
26     tick_count t1=tick_count::now();
27
28     cout << "Found " << subtasks << " tasks to be evaluated." << endl;
29     cout << "Searching time was " << (t1-t0).seconds() << "." << endl;
30
31     return 0;
32 }

Abbildung 4 zeigt die Skalierung des parallelen Lösers auf einer Hexacore-CPU für ein Sudoku. Je mehr Cores zum Einsatz kommen, umso schneller ist das Sudoku gelöst. Die lineare Kurve zeigt die maximal mögliche Beschleunigung. Bei sechs Kernen ist die tatsächlich messbare aber wegen des steigenden Verwaltungsaufwands nur knapp fünffach.

Abbildung 4: Theoretisch steigt die Performance linear mit der Zahl der Kerne, doch in der Praxis fordert der Verwaltungsaufwand seinen Teil.

Parallele Datenstrukturen

Die TBB versprechen eine Reihe von Containerklassen, die im Gegensatz zur STL verbindlich Thread-safe sind. Allerdings ist das nicht ganz korrekt: Um beurteilen zu können, ob eine Klasse gegen einen gleichzeitigen Zugriff mehrerer Threads geschützt ist, muss man jede einzelne Methode der Klasse betrachten. Dabei wird deutlich, dass die Containerklassen der TBB nur Thread-sicher in Hinblick auf bestimmte Methoden sind. Beispielsweise sollte der Aufruf des Konstruktors oder Destruktors immer nur durch einen einzigen Thread erfolgen.

Der »concurrent_vector« verhält sich Thread-safe, wenn ein neues Element mit »push_back()« angehängt wird. Paralleler Zugriff mit dem »[]« -Operator auf ein Element im Vektor ist möglich, aber nicht Thread-safe, das ist Sache des Entwicklers. Elemente lassen sich aus der Datenstruktur im Gegensatz zum STL-Pendant nicht einmal mehr entfernen.

Einzig der Container »concurrent_hash_map« bietet die Möglichkeit, den gleichzeitigen Zugriff auf ein einzelnes Element zu verhindern. Hierzu gibt es Accessor-Objekte, also intelligente Zeiger auf ein Element in der Hashtabelle. Solange ein Zeiger existiert, dürfen andere Threads nicht auf das referenzierte Element zugreifen und werden suspendiert.

Das Beispiel in Listing 6 zeigt die parallele Berechnung des Histogramms eines Grauwertbildes. Die Methode »insert()« fügt ein neues Element in die Hashtabelle ein, wenn dieses noch nicht existiert. Gleichzeitig wird ein Zugriffselement »a« initialisiert, das exklusiven Schreibzugriff ermöglicht. Hierdurch ist es möglich, den Zähler für die Anzahl der gefundenen Punkte eines Farbwerts Thread-safe um 1 zu erhöhen.

01 struct ColorHashCompare {
02     static size_t hash(const unsigned char& c) {
03         return c;
04     }
05     static bool equal(const unsigned char& a, const unsigned char& b) {
06         return a==b;
07     }
08 };
09 typedef concurrent_hash_map<unsigned char,unsigned long,ColorHashCompare>
10 ConcurrentColorMap;
11 class ColorHistogram {
12     ConcurrentColorMap& map;
13 public:
14     ColorHistogram(ConcurrentColorMap& m):map(m) {}
15     void operator()(const blocked_range<unsigned char*> range) const {
16         for(unsigned char* p=range.begin();p<range.end();p++) {
17             ConcurrentColorMap::accessor a;
18             map.insert(a,*p);
19             a->second+=1;
20         }
21     }
22 };

Die Berechnung der Farbverteilung erfolgt dann mit einer parallelen Schleife:

ConcurrentColorMap table;
ColorHistogram histogram(table);
parallel_for(blocked_range<unsigned char*>(picture,picture+length*width),histogram);

Die Variable »picture« ist ein Zeiger auf den ersten Bildpunkt, die Variablen »length« und »width« geben Länge und Breite des Bildes an. Aber hier gilt auch, dass durch das Einfügen von Elementen mögliche Iteratoren auf die Tabelle ungültig werden. Bei der Verwendung paralleler Datenstrukturen ist es unbedingt nötig, die Dokumentation der TBB im Detail zu studieren, sonst sind sporadische, nicht reproduzierbare Fehler, die sich aus dem Zugriff paralleler Threads ergeben, schon programmiert.

Die Containerklassen der TBB sind sehr effizient, da sie die Verwendung von globalen Sperren wie Mutexen minimieren oder sogar vermeiden. Dies erreichen die TBB durch den Einsatz atomarer Operationen. Selbst unscheinbare Funktionen wie »i++« führt der Prozessor normalerweise nicht atomar (unteilbar) aus. Das hat zur Folge, dass, wenn zwei Threads parallel die Variable »i« inkrementieren, der Wert anschließend nicht um 2, sondern unglücklicherweise nur um 1 größer ist. Aber auch hier bieten die TBB dem Entwickler Unterstützung an:

atomic<int> i;
i=40;

Zuweisungen und das Erhöhen des Wertes von »i« sind jetzt atomar. Zwei Threads können somit »i++« aufrufen, das Ergebnis wird anschließend 42 sein. Die Ausführung atomarer Funktionen benötigt aber wesentlich mehr Rechenzeit als die der Standardvarianten.

Die TBB machen parallele Programmierung einfacher, besonders wenn parallele Schleifen und Task-Objekte zum Einsatz kommen. Die umständliche Thread-Programmierung entfällt. Allerdings ist mit dem Einsatz des Task-Konzepts auch ein Verlust an Performance verbunden. Insbesondere bei sehr vielen (Millionen oder Milliarden) kurzlebigen Objekten kommt es dazu, dass die Bibliothek länger mit dem Anlegen und Löschen der Objekte beschäftigt ist.

Ausblick

Der Hersteller Intel entwickelt die TBB weiter. In einer Community Preview (Version 3, Update 5 der TBB) lassen sich neue parallele Datenstrukturen wie Graphen und prioritätsgesteuerte Warteschlangen bereits ausprobieren. Das Buch von James Reinders zu den TBB [5] ist schon ein paar Jahre alt, für den Einstieg in die Thematik aber gut geeignet. Die aktuellen Entwicklungen lassen sich am besten in Intels Onlineforum zum Thema [6] verfolgen (Abbildung 5).

Abbildung 5: Neues aus der TBB-Entwicklung, beispielsweise Preview-Versionen, gibt es im Intel-Forum.