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)

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.

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.

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.

• [x] Visual Studio 2019
• [x] g++10: erfordert Intel TBB und linken mit -ltbb (Anleitung für MinGW)