namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:parallel_algorithms

Parallele Algorithmen

Ausführungsrichtlinien

Viele der Algorithmen der Standardbibliothek in <algorithm>, z.B.

std::sort(begin(v), end(v));

lassen sich parallelisieren (seit C++17), indem vor den weiteren Parametern ein in <execution> definierter Hinweis (genaueres hier)

seq nacheinander
par parallel
par_unseq parallel und/oder vektorisiert (SIMD o.ä.)
unseq vektorisiert (seit C++20)

auf die Ausführungsweise angegeben wird:

std::sort(std::execution::par, begin(v), end(v));

Die in <numeric> aufgeführten Algorithmen accumulate(), innerproduct(), adjacent_difference() und partial_sum() haben parallelisierbare Pendants [transform_]reduce(), [transform_][in|ex]clusive_scan() bekommen.

Einige Algorithmen sind inhärent sequentiell: [copy|move]_backward(), shuffle(), sample(), partition_point(), [lower|upper]_bound(), binary_search(), equal_range(), [make|push|pop]_heap(), [is|next|prev]_permutation(), iota() und daher nicht in paralleler Form zu haben.

Bei so elementaren Aufrufen wie max(x,y) oder swap(x,y) ist Parallelisieren nicht möglich.

Wettrennen und Verklemmungen

Der Aufrufer muss sicherstellen, dass bei der nicht garantierten Aufrufreihenfolge weder data races noch deadlocks eintreten. Auch die Nutzung von Synchronisationsmitteln erfordert Fachkenntnis. Durch die nicht garantierte Reihenfolge können bei nicht assoziativen Vorgängen wie Gleitkommazahloperationen auch andere Ergebnisse entstehen.

Kosten und Nutzen

Amdahls Gesetz besagt, dass ein Algorithmus nie vollständig parallelisiert werden kann. Sequentielle Anteile und Kommunikations- und Synchronisationsaufwand stehen dem entgegen, ebenso der Aufwand zum Starten und Beenden von nebenläufigen Threads. Lese- und Schreibgeschwindigkeit der zu verarbeitenden Datenmengen in den Hauptspeicher sind ebenso begrenzende Faktoren. Nur durch Messung ist entscheidbar, ob Parallelisierung nutzt oder eher schadet.

Verfügbare Implementierungen

kennen/parallel_algorithms.txt · Zuletzt geändert: 2021-07-31 12:31 von rrichter