namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:parallel_algorithms

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.


kennen:parallel_algorithms [2021-07-31 12:31] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 +====== Parallele Algorithmen ======
 +
 +===== Ausführungsrichtlinien =====
 +
 +Viele der Algorithmen der Standardbibliothek in [[.:include:algorithm]], z.B.
 +
 +<code cpp>
 +std::sort(begin(v), end(v));
 +</code>
 +lassen sich parallelisieren (seit C++17), indem vor den weiteren Parametern ein in [[.:include::execution]] definierter Hinweis ([[https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t|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:
 +
 +<code cpp>
 +std::sort(std::execution::par, begin(v), end(v));
 +</code>
 +Die in [[.:include: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 
 +[[http://ithare.com/using-parallel-algorithm-without-a-clue-90x-performance-loss-instead-of-8x-gain/|Fachkenntnis]]. 
 +Durch die nicht garantierte Reihenfolge können bei nicht assoziativen Vorgängen wie Gleitkommazahloperationen auch andere Ergebnisse entstehen.
 +
 +===== Kosten und Nutzen =====
 +
 +[[wpde>Amdahlsches_Gesetz|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] g++10: erfordert Intel TBB und linken mit ''-ltbb'' ([[https://stackoverflow.com/questions/43116560/setting-up-intel-tbb-with-nuwen|Anleitung für MinGW]]) 
 +
 +
  
kennen/parallel_algorithms.txt · Zuletzt geändert: 2021-07-31 12:31 von 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki