zurück zum Artikel

Parallele Algorithmen der STL mit dem GCC-Compiler

Rainer Grimm

Der GCC-Compiler unterstützt nun mein liebstes C++17-Feature: die parallelen Algorithmen der Standard Template Library (STL).

Der GCC-Compiler unterstützt nun mein liebstes C++17-Feature: die parallelen Algorithmen der Standard Template Library (STL). Das habe ich vor ein paar Tagen bemerkt und ich freue mich, einen Beitrag darüber schreiben zu können und meine Begeisterung zu teilen.

Parallele Algorithmen der STL mit dem GCC

Im Gegensatz zum GCC- und Clang-Compiler unterstützt der Microsoft-Compiler die parallelen Algorithmen seit ihren Anfängen. Das ändert sich nun mit GCC 9. Ab dieser Compiler-Version lassen sich die parallelen Algorithmen verwenden. Bevor ich in meinem nächsten Artikel Performanzzahlen präsentiere, möchte ich über die parallelen Algorithmen der STL berichten und die dafür nötigen Informationen teilen.

Die Standard Template Library besitzt mehr als 100 Algorithmen zum Suchen, Zählen und Manipulieren von Bereichen und deren Elementen. Mit C++17 erhalten 69 von ihnen neue Überladungen, und neue Algorithmen kommen hinzu. Die überladenen und neuen Algorithmen können mit einer sogenannten Execution Policy aufgerufen werden. Mit einer Execution Policy lässt sich festlegen, ob der Algorithmus sequentiell, parallel oder parallel mit Vektorisierung laufen soll. Um die Execution Policy zu verwenden, braucht es den Header <execution>.

Der C++17-Standard definiert drei Execution Policies:

Das entsprechende Policy-Tag gibt an, ob ein Programm sequentiell, parallel oder parallel mit Vektorisierung ausgeführt werden soll.

Das Verwenden der Execution Policies std::execution::par oder std::execution::par_unseq erlaubt es, den Algorithmus parallel oder parallel und vektorisiert auszuführen. Diese Policy ist aber nur ein Hinweis, den der Compiler nicht umsetzen muss.

Der folgende Codeschnipsel wendet alle Execution Policies an.

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

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

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

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

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

Wie das Beispiel zeigt, lässt sich jederzeit auch weiterhin die klassische Variante von std::sort (4) verwenden. Außerdem lässt sich in C++17 explizit angeben, ob die sequentielle (2), parallele (3) oder die parallele und vektorisierte (4) Version zum Einsatz kommen soll.

Ob ein Algorithmus parallel und vektorisiert ausgeführt wird, hängt von vielen Faktoren ab; zum Beispiel davon, ob die CPU und das Betriebssystem SIMD-Instruktionen unterstützen. Außerdem hängt es vom Compiler und der Optimierungsstufe ab, die für die Übersetzung des Codes verwendet wurde.

Das folgende Beispiel zeigt eine einfache Schleife zum Füllen eines Vektors:

const int SIZE = 8;

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

int main( {
for (int i = 0; i < SIZE; ++i) {
res[i] = vec[i]+5;
}
}

Der Ausdruck res[i] = vec[i] + 5 ist hier die entscheidende Zeile. Dank des Compiler Explorers können wir uns die von clang 3.6 generierten Assembleranweisungen genauer ansehen.

Hier sind die Assembleranweisungen. Jede Addition wird sequentiell durchgeführt.

Parallele Algorithmen der STL mit dem GCC-Compiler

Durch Verwenden der höchsten Optimierungsstufe -O3 kommen spezielle Register wie xmm0 zum Einsatz, die 128 Bit oder 4 int's aufnehmen können. Dieses spezielle Register bedeutet, dass die Addition parallel auf vier Elemente des Vektors erfolgt.

Parallele Algorithmen der STL mit dem GCC-Compiler

Das Überladen eines Algorithmus ohne Execution Policy und das Überladen eines Algorithmus mit einer sequenziellen Execution Policy std::execution::seq unterscheiden sich in einem Aspekt: Exceptions.

Wenn eine Exception während der Verwendung eines Algorithmus mit einer Execution Policy auftritt, wird std::terminate [2] aufgerufen. std::terminate ruft den installierten std::terminate_handler [3] auf. Die Konsequenz ist, dass standardmäßig std::abort [4] aufgerufen wird, was zu einem anormalen Programmabbruch führt. Die Behandlung von Exceptions ist der Unterschied zwischen dem Aufruf eines Algorithmus ohne Execution Policy und einem Algorithmus mit einer sequenziellen std::execution::seq Execution Policy. Der Aufruf des Algorithmus ohne Execution Policy propagiert die Exception. Dadurch lässt sich die Exception abfangen.

Mit C++17 erhielten 69 der STL-Algorithmen neue Überladungen, und neue Algorithmen wurden hinzugefügt.

Hier sind die 69 Algorithmen mit parallelisierten Versionen.

Parallele Algorithmen der STL mit dem GCC-Compiler

Die neuen Algorithmen in C++17, die für die parallele Ausführung konzipiert sind, befinden sich im std Namensraum und benötigen die Headerdatei <numeric>.

Ein Callable ist eine Entität, die sich aufrufen lässt. Prominente Beispiele für Callables sind Funktion, Funktionsobjekte oder Lambda-Ausdrücke.

Zugegebenermaßen ist diese Beschreibung nicht leicht zu verdauen, aber wer std::accumulate und std::partial_sum bereits kennt, dem sollten die reduce- und scan-Varianten vertraut sein. std::reduce ist das parallele Pendant zu std::accumulate und scan das parallele Pendant zu partial_sum. Die parallele Ausführung ist der Grund dafür, dass std::reduce einen assoziativen und kommutativen Callable benötigt. Die entsprechende Aussage gilt für die scan-Varianten im Gegensatz zu den partial_sum-Varianten. Wer die vollständigen Details nachlesen möchte, sollte cppreferenc.com/algorithm [5] besuchen.

Warum brauchen wir std::reduce für die parallele Ausführung, wenn wir doch bereits std::accumulate besitzen? Der Grund ist einfach: std::accumulate verarbeitet seine Elemente in einer Reihenfolge, die nicht parallelisiert werden kann.

Während std::accumulate seine Elemente von links nach rechts abarbeitet, wendet std::reduce keine definierte Reihenfolge an. Lass mich mit einem kleinen Codeschnipsel beginnen, der std::accumulate und std::reduce verwendet. Der Callable ist die Lambda-Funktion [](int a, int b){ return a * b; }.

std::vector<int> v{1, 2, 3, 4};

std::accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a * b; });
std::reduce(std::execution::par, v.begin(), v.end(), 1 , [](int a, int b){ return a * b; });

Die beiden folgenden Diagramme zeigen die unterschiedlichen Verarbeitungsstrategien von std::accumulate und std::reduce.

Parallele Algorithmen der STL mit dem GCC-Compiler
Parallele Algorithmen der STL mit dem GCC-Compiler

Die Assoziativität des Callables erlaubt es dem std::reduce Algorithmus, den Reduktionsschritt auf beliebige benachbarte Paare von Elementen zu anzuwenden. Dank der Kommutativität können die Zwischenergebnisse in beliebiger Reihenfolge berechnet werden.

Wie eingangs versprochen, wird mein nächster Beitrag die parallelen Algorithmen der STL verwenden und liefert Performanzzahlen für den Microsoft- und den GCC-Compiler.

Parallele Algorithmen der STL mit dem GCC-Compiler

In den nächsten Monaten biete ich die folgenden Seminare an. Falls es die Covid-19 Situation zulässt, werde ich die Seminare nach Rücksprache als Präsenzseminare durchführen.

( [11])


URL dieses Artikels:
https://www.heise.de/-6140991

Links in diesem Artikel:
[1] https://en.wikipedia.org/wiki/SIMD
[2] https://en.cppreference.com/w/cpp/error/terminate
[3] https://en.cppreference.com/w/cpp/error/terminate_handler
[4] https://en.cppreference.com/w/cpp/utility/program/abort
[5] https://en.cppreference.com/w/cpp/algorithm
[6] https://www.modernescpp.de/index.php/c/2-c/32-c-20
[7] https://www.modernescpp.de/index.php/c/2-c/33-embedded-programmierung-mit-modernem-c20210421085111
[8] https://www.modernescpp.de/index.php/c/2-c/34-clean-code-best-practices-fuer-modernes-c
[9] https://www.modernescpp.de/index.php/c/2-c/35-concurrency-mit-modernem-c
[10] https://www.modernescpp.de/index.php/c/2-c/36-design-pattern-und-architekturpattern-mit-c
[11] mailto:rainer@grimm-jaud.de