namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


parallelisieren

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

parallelisieren [2014-05-25 16:24] (aktuell)
Zeile 1: Zeile 1:
 +====== Parallelisieren ======
 +> // The Free Lunch is over. //
 +>> --- Herb Sutter
  
 +Über Jahrzehnte haben Programmierer die Laufzeit-Effizienz von Programmen vernachlässigt.
 +Emulatoren, virtuelle Maschinen, interpretierende Systeme konnten von 
 +schnelleren Prozessoren mit immer mehr Speicher profitieren.
 +Doch schon dabei hatte (nicht nur) ich den Eindruck,
 +dass die Hardware langsamer beschleunigt als die Software langsamer wird.
 +Die Taktraten wachsen nicht mehr, wie 
 +[[http://​www.gotw.ca/​publications/​concurrency-ddj.htm|Sutters Artikel]]
 +vom März 2005 zeigt.
 +Allenfalls die Zahl der Rechenkerne pro Maschine steigt noch ein paar Jahre.
 +
 +Ein Zuwachs an Leistungsfähigkeit ist nicht mehr kostenlos zu haben.
 +[[wpde>​Parallele_Programmierung]] verteilt die Datenverarbeitung ​
 +auf mehrere Rechenkerne,​ Prozessoren bzw. Maschinen.
 +Dazu müssen die Programmquellen verändert werden.
 +Prozessoren und Compiler können nur begrenzt erkennen,
 +welche Teile eines Programms für nebenläufige Abarbeitung geeignet sind.
 +Zur Wahl geeigneter Algorithmen,​ Datenstrukturen und Kommunikationsstrategien ​
 +kommen noch ein paar alte, fast in Vergessenheit geratene Tugenden: ​
 +Programmierdisziplin,​ Messen und gezieltes Optimieren.
 +Nebenbei spielt auch die Wahl der Programmiersprache eine Rolle.
 +Hier werden Ansätze in C++ untersucht.
 +
 +===== Amdahls Gesetz =====
 +{{ :​amdahl.png?​400|Speedup als Funktion der Zahl der Rechenkerne}}
 +
 +Die Geschwindigkeitssteigerung (engl. speedup) S eines parallelisierbaren Programms hängt von der Anzahl n verfügbarer Prozessoren bzw. Kerne ab:
 +\[ 
 +S(n) = \frac{t_{\rm sequentiell}}{t_{\rm parallelisiert}} = \frac{1}{1-p + \frac{p}{n}} < \frac{1}{1-p}.
 +\]
 +Darin ist 0 ≤ p ≤ 1 der Anteil parallelisierter Schritte.
 +In [[http://​de.wikipedia.org/​wiki/​Amdahlsches_Gesetz|Amdahls Gesetz]] (blaue Kurve) wird der Kommunikationsaufwand k(n) ~ O(n) (rote Kurve) zwischen parallelen und seriellen Abschnitten nicht berücksichtigt.
 +In der modifizierten Form (grüne Kurve)
 +\[
 +S(n) = \frac{1}{1-p + k \cdot n + \frac{p}{n}}
 +\]
 +existiert ein ausgeprägtes Optimum für die Prozessorzahl,​ das bestenfalls experimentell bestimmbar ist.
 +
 +
 +===== Ansätze =====
 +Die Rechenarbeit wird auf mehrere Kerne einer Maschine verteilt durch
 +  * ausdrückliches Multithreading (POSIX / Boost / C++11 <​thread>​),​
 +  * implizites Multithreading in [[http://​www.openmp.org/​|OpenMP]],​ [[http://​msdn.microsoft.com/​de-de/​library/​dd492418.aspx|Parallel Pattern Library]] (Microsoft Visual C++ 2010) und [[http://​www.threadingbuildingblocks.org/​|Thread Building Blocks]] (Intel C++),
 +  * Einspannen der Grafikprozessoren in [[http://​www.khronos.org/​opencl/​|OpenCL]] und [[http://​www.nvidia.de/​object/​cuda_what_is_de.html|CUDA]] (General Purpose Programming on Graphics Processing Units = GPGPU). ​
 +Stehen mehrere Maschinen zur Verfügung, kommen
 +  * allgemeine verteilte Systeme (Client/​Server-Anwendungen über Netzwerk-Sockets,​ CORBA, ...) und
 +  * Message Passing Interface ([[http://​www.open-mpi.org/​|Open MPI]]) als Grundlage für Supercomputer-Cluster
 +zum Einsatz.
 +===== Beispiele =====
 +{{ :​mandel.png?​200|}}
 +
 +Um einen Eindruck zu gewinnen, wurde dieselbe Programmieraufgabe (Berechnung eines Apfelmännchens) mit mehreren Techniken umgesetzt; ​
 +die Ausgabe des Rechenergebnisses als Bilddatei (Abb. rechts) erlaubt ein leichtes Erkennen von Fehlern:
 +  * [[parallel:​openMP|OpenMP]]
 +  * [[parallel:​ppl|PPL]]
 +  * [[parallel:​thread|C++11 std::​thread]]
 +  * [[parallel:​openCL|OpenCL]]
 +  * [[parallel:​openMPI|Open MPI]]
 +
 +===== Einschätzung =====
 +Die Tabelle fasst die gemachten Erfahrungen zusammen:
 +
 +|         ​^Technik ^Programmieraufwand ^Compiler ^Einschränkungen,​ Abhängigkeiten ^ erreichte Beschleunigung((2 CPU-Kerne, 2 GPU-Kerne))^
 +^OpenMP ​  ​|Pragmas,​ geteilte Schleifen |minimal, auch seriell |GCC, Visual C++ ≥2005 |OpenMP-Bibliothek | 2,1|
 +^PPL      |Templates, Lambdas, Threadpool |gering |Visual C++ 2010 || 1,9|
 +^OpenCL ​  ​|Rechenkerne in C |hoch |GCC, Visual C++ 2010 |Grafikkarte,​ Treiber, ATI-Stream-Software,​ nicht alle Datentypen nutzbar | 15|
 +^Open MPI |Bibliothek |hoch |GCC, Linux |ssh-Zugriff auf alle beteiligten Maschinen | ---|
 + 
 +OpenMP und MPI weisen die größte Reife auf und können ergänzend genutzt werden, MPI ist auf Rechnerclustern skalierbar.
 +OpenCL ist noch relativ jung und wegen der Abhängigkeit von Fähigkeiten der Grafikkarte und weiterer Software noch wenig portabel, verspricht aber bei vielen Grafikkernen große Geschwindigkeitsgewinne.
 +
 +Weitere Messungen wurde an [[parallel:​Udoo|Udoo Quad]] durchgeführt.
parallelisieren.txt · Zuletzt geändert: 2014-05-25 16:24 (Externe Bearbeitung)