Parallele Programmierung und C ++

Muster:

• Produzieren / Verbraucher

  • Ein Thread erzeugt Daten
  • Ein Thread verbraucht die Daten

• Schleifenparallelität

  • Wenn Sie zeigen können, dass jede Schleife unabhängig ist Jede Iteration kann in einem separaten Thread
  durchgeführt werden

• Faden neu zeichnen

  • Andere Threads funktionieren und aktualisieren Datenstrukturen, aber ein Thread zeichnet den Bildschirm neu.

• Hauptereignis-Thread

  • Mehrere Threads können Ereignisse generieren
  • Ein Thread muss die Ereignisse verarbeiten (da die Reihenfolge wichtig ist)
  • Sollte versuchen, den Event Thread / Re-Draw Thread zu trennen Dies verhindert, dass die Benutzeroberfläche eingefroren wird Es kann jedoch zu übermäßigen Wiederholungen kommen, wenn sie nicht sorgfältig durchgeführt werden.

• Arbeitsgruppe

  • Eine Gruppe von Threads wartet auf Jobs auf einer Warteschlange.
  • Thread extrahiert ein Arbeitselement aus der Warteschlange (wartet, wenn keines verfügbar ist).
    Thread arbeitet an einem Arbeitselement, bis es fertig ist Sobald der Thread fertig ist, kehrt er zur Warteschlange zurück.

Zuerst müssen Sie zwischen Shared-Memory-Computing und Shared-Nothing-Computing wählen. Shared Memory ist einfacher, skaliert aber nicht so gut - Sie werden Shared-Nothing verwenden, wenn Sie entweder

a) haben einen Cluster, anstatt ein Multiprozessorsystem oder

b) wenn Sie viele CPUs haben (sagen wir & gt; 60) und einen hohen Grad an ungleichförmigem Speicher

Für Shared-Memory ist die übliche Lösung, Threads zu verwenden; Sie sind als Konzept einfach zu verstehen und in der API einfach zu verwenden (aber schwer zu debuggen).

Für shared-nothing verwenden Sie eine Art von Messaging. Im Hochleistungsrechnen ist MPI als Messaging-Middleware etabliert.

Sie müssen dann auch eine Architektur für die parallelen Aktivitäten entwerfen. Der häufigste Ansatz (wieder, weil es leicht zu verstehen ist) ist das Farmer-Worker-Pattern (auch bekannt als Master-Slave).

Parallele Ausführungsmuster

Strukturierte parallele Programmierung mit deterministischen Mustern ist ein High-Level-Ansatz, der hauptsächlich auf einer Sammlung von wiederkehrenden parallelen Ausführungsmustern basiert, oft als algorithmische Skelette oder parallele Konstrukte bezeichnet, die die Programmbeschreibung abstrahieren und Low-Level-Multithreading-Details und viele Komplexitäten verbergen in der Parallelität von den Programmierern inhärent.

Diese wiederverwendbaren Muster automatisieren viele parallele Paradigma-bezogene Routinen wie Synchronisation, Kommunikation, Datenpartitionierung oder Aufgabenplanung und behandeln sie intern. Dieser High-Level-Ansatz versucht das traditionelle Low-Level-Thread-Lock-Modell mit mehr Abstraktion und einer einfacheren Möglichkeit, Parallelität und Fokus-Produktivität und Programmierbarkeit statt Leistung zu erzielen.

Es gibt viele gebräuchliche Muster wie: Map-Reduce, Fork-Join, Pipeline oder Parallel Loop ...

Papiere

"Strukturierte parallele Programmierung mit deterministischen Mustern" ist ein Papier, das diese Muster diskutiert. Sie können auch "MHPM: Mehrskaliges hybrides Programmiermodell: Eine flexible Parallelisierungsmethodik" sehen, die eine C ++ - Implementierung dieses Ansatzes namens XPU beschreibt.

Bibliothek

XPU ist eine aufgabenbasierte C ++ - Bibliothek, die aus einer Reihe wiederverwendbarer Ausführungsmuster besteht. Es ermöglicht die Darstellung mehrerer Arten von Parallelität auf mehreren Granularitätsebenen innerhalb eines einzigen homogenen Programmiermodells. Es ist einfach zu bedienen und veranschaulicht die Interesse am Verwenden von Mustern, um parallele Programme zu entwerfen.

Zum Beispiel erlaubt es Ausdruck von:

1. Task-Parallelitätsmuster:

   Einfache oder hierarchische Fork / Join Ausführungsmuster mit einigen Funktionen wie  als automatische Erkennung und Schutz von gemeinsamen Daten.

2. Datenparallelitätsmuster:

   Paralleles Schleifenmuster mit skalierbarer Datenpartitionierung.

3. Temporales Parallelitätsmuster:

   Pipeline-Ausführungsmuster.

Sie haben die Grundlagen, die Parallelität zu Teilen eines Programms herstellen. C ++ 17 bekommt viele von ihnen (zB parallele Versionen von foreach, sort, find und friends, map_reduce, map, reduce, prefix_sum ...) siehe C ++ - Erweiterungen für die Parallelität

Dann haben Sie die Gegenstände wie Fortsetzungen. Denken Sie std :: future , aber mit fortfahren. Es gibt nur wenige Möglichkeiten, diese zu implementieren ( boost hat jetzt einen guten, da die erste keine nächste (...) oder dann (...) Methode hat, aber der große Vorteil ist, dass man nicht darauf warten muss, um die nächste Aufgabe zu erledigen

Die fehlende Synchronisation zwischen den nachfolgenden Tasks ist wichtig, da die Kommunikation zwischen Tasks / threads / ... parallele Programme verlangsamt.

Also mit dieser aufgabenbasierten Parallelität ist das wirklich nett. Mit einem Aufgabenplaner übergeben Sie Aufgaben einfach und gehen weg. Sie können Methoden haben, wie ein Semaphor, um zurück zu kommunizieren, aber das ist nicht obligatorisch. Sowohl Intel-Thread-Bausteine ​​ als auch Die Microsoft Parallel Pattern Library verfügt über entsprechende Funktionen.

Danach haben wir das fork / join-Muster. Es bedeutet nicht, N Threads für jede Aufgabe zu erstellen. Nur dass Sie diese N, idealerweise unabhängige, Dinge zu tun haben (fork) und wenn sie fertig sind, haben Sie irgendwo einen Synchronisationspunkt (Join).

Von oben können Sie beginnen, das Muster zu sehen, dass dies ein Flussdiagramm ist. Zukunft ist (A & gt; B & gt; & gt; C & gt; & gt; D) und Gabelverbindung ist (A | B | C | D). Damit können Sie sie zu einem Graph kombinieren. (A1 & gt; & gt; A2 | B1 & gt; & gt; B2 & gt; & gt; B3 | C1 | D1 & gt; & gt; & gt; (E1 & gt; & gt; E2 | F1)) wobei A1 & gt; & gt; A2 bedeutet, daß A1 A2 und A vorausgehen muß | B bedeutet, dass A und B gleichzeitig ausgeführt werden können. Die langsamen Teile sind am Ende der Graphen / Untergraphen, wo sich die Dinge treffen.

Ziel ist es, unabhängige Teile des Systems zu finden, die nicht kommunizieren müssen. Die parallelen Algorithmen sind, wie oben erwähnt, in fast allen Fällen langsamer als ihre sequentiellen Gegenstücke, bis die Arbeitslast hoch genug wird oder die Größe groß genug wird (unter der Annahme, dass die Kommunikation nicht zu geschwätzig ist). Zum Beispiel Sortieren. Auf einem 4-Kern-Computer erhalten Sie etwa 2,5-fache Leistung, da die Zusammenführung gesprächig ist und viel Synchronisation erfordert und nicht alle Kerne nach der ersten Zusammenführungsrunde funktioniert. Auf einer GPU mit einem N, das sehr groß ist, kann man eine weniger effiziente Sortierung verwenden, wie Bitonic, und es ist sehr schnell, weil man viele Arbeiter hat, die durch die Arbeit arbeiten, und jeder ruhig sein eigenes Ding macht.

Einige Tricks, um die Kommunikation zu reduzieren, umfassen die Verwendung eines Arrays für Ergebnisse, so dass jede Aufgabe nicht versucht, ein Objekt zu sperren, um einen Wert zu verschieben. Oft kann die Reduzierung dieser Ergebnisse sehr schnell erfolgen.

Aber bei allen Arten von Parallelität kommt die Langsamkeit aus der Kommunikation. Reduziere es.