Über unsMediaKontaktImpressum
Rainer Grimm 21. März 2017

C++17 und C++20: Gleichzeitigkeit in modernem C++

Welche Abstraktionen für unsere  Rechenkerne werden wir Zukunft mit C++ erhalten? © Informatik Aktuell
© Informatik Aktuell

Eine, wenn nicht die Herausforderung für eine moderne Programmiersprache ist es, die Power, die in jedem modernen Rechner steckt, auf sichere Weise herauszukitzeln. Das ist mit bisherigen Multithreading-Abstraktionen für den sterblichen Programmierer nicht möglich. Daher bietet C++17 und vor allem C++20 deutlich bessere Abstraktionen an, die die bisherigen Abstraktionen atomare Variablen, Threads, Bedingungsvariablen oder Mutexe und Locks auf die Stufe einer Assemblersprache für Gleichzeitigkeit degradieren. Doch welche Abstraktionen werden wir in naher Zukunft erhalten und auf welche Abstraktionen können wir in ferner Zukunft hoffen? Genau diese Fragen werde ich in zwei Artikeln verfolgen.

Bevor es aber um diese Frage geht, steht ein kleiner Umweg an. Es gilt, die Begriffe Gleichzeitigkeit (engl. Concurrency), Parallelisierung und Multithreading zu klären: Gleichzeitigkeit ist der Oberbegriff, der Parallelisierung mit einschließt. Gleichzeitigkeit bedeutet, dass mehrere Aufgaben sich zeitlich überschneiden. Das bedeutet aber nicht, dass diese Aufgaben zum selben Zeitpunkt ausgeführt werden. Diese Eigenschaft zeichnet die Parallelisierung aus, bei der mehrere Aufgaben zeitgleich ausgeführt werden. Multithreading ist ein Implementierungdetail. Genausogut kann das Programm gleichzeitig auf mehreren Prozessen ausgeführt werden. In diesem Fall sprechen wir natürlich von Multiprocessing.

Jetzt kann es losgehen. Zuerst gilt es, das große Bild im Auge zu behalten.

Gleichzeitigkeit in C++

Abb.1: Timeline von C++. © Rainer Grimm
Abb.1: Timeline von C++. © Rainer Grimm

Der Zeitstrahl besitzt eine starke Tendenz nach rechts, denn mit der parallelen Standard Template Library (STL) in C++17 und insbesondere atomaren Smart Pointern, den std::future-Erweiterungen, Latches und Barrier, Coroutinen, Transactional Memory und Task-Blöcken in C++20 wird C++ um viele neue Konzepte erweitert, die alle Inhalt dieses und des nächsten Artikels sein werden.

Dieser Artikel wird die Parallelisierung zum Fokus haben. Genauer ausgedrückt, geht es um die Parallele Algorithmen der STL und die Task-Blöcke zum parallelen Ausführen von Aufgaben.

C++17: Parallele Algorithmen der STL

Abb.2: Parallelisierung in C++. © Rainer Grimm
Abb.2: Parallelisierung in C++. © Rainer Grimm

Die Idee ist schnell skizziert. Die Standard Template Library enthält gut 100 Algorithmen für das Suchen, Zählen und Manipulieren von Bereichen und deren Elemente. Mit C++17 wurden 69 der Algorithmen überladen und 8 neue Algorithmen hinzugefügt. Diese überladenen und neuen Algorithmen können mit einer sogenannte Execution Policy aufgerufen werden. Mit dieser Execution Policy lässt sich spezifizieren, ob der Algorithmus sequentiell, parallel oder parallel und vektorisiert ausgeführt wird. Vektorisierung bezeichnet die SIMD-Erweiterung (Single Instruction, Multiple Data) [1] des Befehlssatzes moderner Prozessoren, die eine Operation parallel auf mehreren Daten ausführen können. Welche überladene Version eines Algorithmus ausgewählt wird, steuert der Anwender über das sogenannte Policy Tag.

Ein einfaches Beispiel soll die Strategie der Algorithmen verdeutlichen.

vector<int> v = ...

// standard sequential sort
std::sort(v.begin(), v.end());                             (1)

// sequential execution
std::sort(std::parallel::seq, v.begin(), v.end());         (2)

// permitting parallel execution
std::sort(std::parallel::par, v.begin(), v.end());         (3)

// permitting parallel and vectorized execution
std::sort(std::parallel::par_unseq, v.begin(), v.end());   (4)

Schön ist an dem kleinen Beispiel zu sehen, dass die klassische Variante von std::sort (1) mit C++17 immer noch zu Verfügung steht. Dagegen lässt sich jetzt mit C++17 explizit die sequentielle (2), die parallele (3) oder auch die parallele und vektorisierende Variante (4) von std::sort anfordern.

Zwei Besonderheiten gilt es aber im Kopf zu behalten: Zum einen muss ein mit der Exection Policy std::parallel::par_unseq versehener Algorithmus nicht parallel und vektorisiert ausgeführt werden. Zum anderen ist der Anwender für die richtige Anwendung des Algorithmus verantwortlich.

Ob ein Algorithmus parallel und vektorisierend (std::parallel::par_unseq) ausgeführt werden kann, hängt von vielen Faktoren ab. Unter anderem davon, ob die CPU und das Betriebssystem SIMD-Anweisungen unterstützen. Natürlich ist es auch eine Frage des Compilers und Optimierungslevels, mit dem der Code übersetzt wird. Bereits der kleine Codeschnipsel bringt mithilfe des online Compiler Explorer [2] diese interessanten Fakten ans Licht.

Zuerst der kleine Codeschnipsel:

const int SIZE= 8;

int vec[]={1,2,3,4,5,6,7,8};
int res[]={0,};

int main(){
  for (int i= 0; i < SIZE; ++i){
    res[i]= vec[i]+5;           (1)
  }
}
Abb.3: Assembleranweisungen ohne Optimierung. © Rainer Grimm
Abb.3: Assembleranweisungen ohne Optimierung. © Rainer Grimm

res[i]= vec[i]+5 ist die entscheidende Zeile des Programms. Wird das Programm ohne Optimierung mit einem clang 3.6-Compiler übersetzt, erzeugt dieser für (1) die Assembler Anweisungen in Abb.3.

Auch ohne tiefe Assembler-Kenntnisse ist klar: Hier findet alles sequentiell statt. Das ändert sich aber, wenn der clang 3.6 mit maximaler Optimierung (-O3) zum Einsatz kommt. Jetzt finden die Operationen auf mehreren Elementen gleichzeitig statt. Abb.4 zeigt die resultierenden Assembler-Anweisungen.

Abb.4: Assembleranweisungen mit Optimierung. © Rainer Grimm
Abb.4: Assembleranweisungen mit Optimierung. © Rainer Grimm

Sowohl die move-Operationen (movdqa) als auch die add-Operationen (paddd) arbeiten auf den besonderen Registern xmm0 und xmm1. Beide Register sind sogenannte SSE-Register und 128 Bits groß. SSE steht für Streaming SIMD Externsions [3].

Der Anwender ist für die richtige Anwendung der Algorithmen verantwortlich. Was heißt das? Die Algorithmen schützen nicht automatisch vor kritischen Wettläufen [4] (data races) oder Verklemmungen (deadlocks). Beispiel gefällig?

int numComp= 0;                                                          (1)
std::vector<int> vec={1,3,8,9,10};
std::sort(std::parallel::vec, vec.begin(), vec.end(),
         [&numComp](int fir, int sec){ numComp++; return fir < sec; });  (2)

Das kleine Programmbeispiel enthält bereits einen kritischen Wettlauf um die Variable numComp. numComp (1) soll die Anzahl der Operationen zählen. Das heißt insbesondere, in der Lambda-Funktion (2) wird auf numComp lesend und schreibend zugegriffen. Damit besitzt der Code undefiniertes Verhalten. Um ein wohldefiniertes Programm zu erhalten, muss der Zugriff auf numComp atomar sein.

Die Exection Policy legt fest, ob ein Algorithmus sequentiell std::parallel::seq, parallel std::parallel::par oder parallel und vektorisierend std::parallel::unseq ausgeführt. Diese Entscheidung kann im Sourcode (statisch) oder zur Laufzeit (dynamisch) getroffen werden. Warum ist das notwendig? Die Erzeugung eines Threads ist eine teure Operation. Daher macht es keinen Sinn, einen Container mit wenigen Elementen mit einer parallelen oder parallel und vektorisierenden Strategie zu sortieren. In diesem Fall frisst der Verwaltungsaufwand den Vorteil der Parallelisierung mehr als auf. Noch drastischer können die Nebenwirkungen sein, wenn ein Teile-und-Herrsche-Algorithmus (divide and conquer algorithm) [5] zum Einsatz kommt. Ein klassisches Beispiel für einen Teile-und-Herrsche-Algorithmus ist der Quicksort-Algorithmus in Listing 1.

C++ - Listing 1: Der parallelisierte Quicksort Algorithmus

Jeder std::partition-Aufruf in Zeile 5 und 7 findet parallel statt. Hier ist die Gefahr natürlich groß, dass die Anzahl der gestarteten Threads deutlich zu groß für das System wird. Umso besser, dass es in C++17 auch eine dynamische Execution Policy gibt. Listing 2 stellt die ressourcenschonende Alternative vor.

C++ - Listing 2: Der parallelisierte Quicksort-Algorithmus mit dynamischer Execution Policy in C++17

Abb.5: Die parallelen und parallel und vektorisierenden Algorithmen der STL. © Rainer Grimm
Abb.5: Die parallelen und parallel und vektorisierenden Algorithmen der STL. © Rainer Grimm

In Zeile 12 und 13 kommt die dynamische Execution Policy zu Einsatz. Per Default wird Quicksort parallel ausgeführt (Zeile 9). Falls aber die Länge des zu sortierenden Bereichs kleiner als eine vorgegebene Schwelle threshold (Zeile 1) ist, wird Quicksort sequentiell ausgeführt (Zeile 10).

69 der Algorithmen unterstützen eine parallel oder parallele und vektorisierende Execution Policy. In Abb.5 sind die Kandidaten.

Das ist noch nicht alles. Dazu gibt es acht neue Algorithmen (Listing 3).

C++ - Listing 3: Die acht neuen Algorithmen

Besonders interessant ist std::parallel::transform_reduce. Warum? Die aus Haskell bekannte Funktion map entspricht der Funktion std::transform in C++. Wenn das kein Wink mit dem Zaunpfahl ist. Denn wird in dem Name std::parallel::transform_reduce transform durch map ersetzt, so heißt der Algorithmus std::parallel::map_reduce. MapReduce [6] ist das weltweit eingesetzte, parallele Framework, das in seiner ersten Phase jeden Wert auf einen neuen Wert abbildet und in seiner zweiten Phase diese neuen Werte auf das Ergebnis reduziert.

Dieser zweistufige Algorithmus lässt sich jetzt direkt in C++17 anwenden. So bildet in Listing 4 die Transform-Phase jedes Wort auf seine Länge ab und summiert die Reduce-Phase die Länge aller Wörter auf. Als Startwert kommt die 0 zum Einsatz.

C++ - Listing 4: MapReduce in C++17

Das Ergebnis ist die Summe aller Wörter eines Vektors. Parallel geht es weiter mit C++20.

Task-Blöcke mit C++

Abb.6: Das Fork-Join-Paradima. © Rainer Grimm
Abb.6: Das Fork-Join-Paradima. © Rainer Grimm

Task-Blöcke setzen das beliebte Fork-Join-Paradigma für die parallele Ausführung von Aufgaben um. Der Name Fork-Join lässt sich in einer Graphik (Abb.6) einfach erklären.

Wie funktioniert das Ganze? Der Erzeuger-Thread ruft define_task_block oder define_task_block_restore_thread auf. Dadurch steht ein Task-Block zur Verfügung, der neue Tasks erzeugen oder auf diese warten kann. Am Ende des Task-Blocks findet die Synchronisation statt. Das Erzeugen der neuen Tasks ist die Fork-Phase, die Synchronisation der Tasks die Join-Phase des Fork-Join-Prozesses. Zugegeben, die Idee des Paradigma ist überzeugend einfach. Wie schaut das Ganze im Code aus? Listing 5 stellt vor, wie sich mit dem Paradigma eine Baumstruktur rekursiv prozessieren lässt.

C++ - Listing 5: Rekursive Prozessierung einer Baumstruktur

traverse in Listing 5 ist eine Funktions-Template, das auf jedem Knoten des Baumes node mit zwei Kindern die Funktion f (Zeile 2) aufruft. Das Schlüsselwort define_task_block definiert den Task-Block. In diesem kann der Task-Block tb neue Tasks starten. Genau das findet für den linken und rechten Zweig des Baumes in Zeile 6 und 7 statt. Zeile 9 stellt das Ende des Task-Blocks dar und ist damit der Synchronisationspunkt.

Das war schon der grobe Überblick. Jetzt folgen ein paar Details zu den Task-Blöcken. Der feine Unterschied zwischen define_task_block und define_task_block_restore_thread ist, dass bei define_task_block_restore_thread der Erzeuger-Thread des Task-Blocks auch nach dem Ende des Task-Blocks wieder der Thread ist, der die weiteren Anweisungen ausführt. Dies lässt sich am einfachsten an einem Codesbeispiel in Listing 6 aufzeigen.

C++ - Listing 6: define_task_block versus define_task_block_restore_thread

Task-Blöcke sichern zu, dass der Erzeuger-Thread des äußersten Task-Block (Zeile 2 - 14) nach dem Beenden des Tasks-Blocks auch wieder zum Zuge kommt. Das heißt, der Thread der die Anweisung in Zeile 2 ausführt, führt auch die Anweisungen in Zeile 15 und 16 wieder aus. Diese Zusicherung gilt aber nicht für alle verschachtelten Task-Blöcke. Daher führt der Erzeuger-Thread des Task-Blocks in Zeile 6 - 8 nicht automatisch die Zeilen 9 und 10 aus.

Ist diese Anforderungen notwendig, muss die Funktion define_task_block_restore_thread (Zeile 4) verwendet werden. Nun gilt, der Thread, der die Anweisung in Zeile 4 ausgeführt hat, führt auch die Anweisungen in Zeile 12 und 13 aus.

Ein Task-Block tb besitzt ein sehr eingeschränktes Interface. Er kann nicht explizit erzeugt werden. Dazu sind die zwei bereits verwendeten Funktionen define_task_block oder define_task_block_restore_thread notwendig. Der Task-Block tb ist in seinem Bereich sofort aktiv und kann daher eine neue Aufgabe durch tb.run starten oder warten (tb.wait), bis die Aufgabe fertig ist. Listing 7 zeigt die Methoden des Task-Blocks tb in der Anwendung.

C++ - Listing 7: Methoden eines Task-Blocks

In Zeile 2 wird eine neue Aufgabe gestartet, die die Daten x1 und x2 benötigt. Hingegen werden in Zeile 4 die Daten von x3 und x4 prozessiert. Im Falle, dass x2 == x3 ist, gilt es, diese vor dem gemeinsamen Zugriff zu schützen. Daher wartet in diesem Fall der ausführende Thread, bis die Aufgabe in Zeile 2 fertig ist.

Der Scheduler ist verantwortlich dafür, welcher Thread zum Zuge kommt. Genau das liegt bei Task-Blocks nicht mehr in der Verantwortung des Programmierers. Damit sind Threads genau auf die Rolle reduziert, die sie einnehmen sollten: ein Implementierungsdetail. Für das Scheduling gibt es zwei Strategien für die durch den Task-Block tb mittels tb.run gestartete Aufgaben. Dabei bezeichnet Parent den Erzeuger-Thread und Child den Thread, in der die Aufgabe ausgeführt wird.

  • Child stealing: Der Scheduler klaut die Aufgabe und führt sie aus.
  • Parent stealing: Der Erzeuger-Thread führt die Aufgabe selbst aus. Der Scheduler schnappt sich in diesem Fall aber den Parent.

Der zukünftige Standard erlaubt nach dem jetzigen Stand der Dinge [7] beide Strategien.

Wie geht's weiter?

Nachdem dieser Artikel sich rund um die Parallelisierung in naher und ferner Zukunft gedreht hat, wird der Fokus im nächsten Artikel "Gleichzeitigkeit in C++17 und C++20" weiter: Atomare Smart Pointer, die Future Erweiterungen, Latches und Barriers, Couroutinen und Transaktiona Memory werden für die notwendige Spannung sorgen.

nach Oben
Autor

Rainer Grimm

Rainer Grimm ist Trainer und Coach für C++ und Python. Seine Bücher "C++11 für Programmierer", "C++", "C++ Standardbibliothek" und "The C++ Standard Library" sind bei O'Reilly und Leanpub erschienen.
>> Weiterlesen
Bücher des Autors:

botMessage_toctoc_comments_929