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 seit C++17 parallelisieren, indem vor den weiteren Parametern ein in <execution> definierter Hinweis

seq nacheinander
par parallel
par_unseq parallel oder vektorisiert (SIMD o.ä.)

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

  • [x] Visual Studio 2019
  • [x] MinGW g++10 HEAD: kein Zeitunterschied zwischen par und seq, beide langsamer als ohne Richtlinie – bug or QOI issue?
  • [-] Clang
kennen/parallel_algorithms.txt · Zuletzt geändert: 2020-01-03 19:26 von rrichter