Aufgabenbasierte Parallelbibliotheken mit gemeinsamem Speicher in Scientific Computing

10

In den letzten Jahren sind mehrere Bibliotheken / Softwareprojekte erschienen, die die eine oder andere Form der datengesteuerten Parallelität für gemeinsam genutzten Speicher für allgemeine Zwecke bieten.

Die Hauptidee ist, dass Programmierer ihre Algorithmen nicht als explizit getunten Code schreiben, sondern als voneinander abhängige Aufgaben implementieren, die dann von einer Allzweck-Middleware auf einem Shared-Memory-Computer dynamisch geplant werden.

Beispiele für solche Bibliotheken sind:

  • QUARK : Ursprünglich für die MAGMA- Bibliothek für parallele lineare Algebra entwickelt, scheint sie auch für eine parallele schnelle Multipolmethode verwendet worden zu sein.

  • Cilk : Ursprünglich ein MIT-basiertes Projekt, die jetzt von Intel unterstützt, implementiert als Sprache / Compiler Erweiterungen C, in der verwendeten Cilkchess Computer Schach - Software und experimentell in FFTW .

  • SMP-Superskalar : Entwickelt im Barcelona Supercomputing Center, ähnlich wie Cilk in vielerlei Hinsicht, basierend auf #pragmaErweiterungen.

  • StarPU : Ähnliche bibliotheksbasierte "Codelets", die für verschiedene Architekturen, einschließlich GPUs, kompiliert und geplant werden können.

  • OpenMP-Tasks: Ab Version 3.0 hat OpenMP "Tasks" eingeführt, die asynchron geplant werden können (siehe Abschnitt 2.7 der Spezifikation).

  • Intels Threading-Bausteine : Verwendet C ++ - Klassen zum Erstellen und Starten asynchroner Aufgaben (siehe Abschnitt 11 des Lernprogramms).

  • OpenCL : Unterstützt aufgabenbasierte Parallelität auf mehreren Kernen.

Obwohl es eine Menge Literatur gibt, die das Innenleben dieser Bibliotheken / Spracherweiterungen und ihre Anwendung auf bestimmte Probleme beschreibt, bin ich nur auf sehr wenige Beispiele gestoßen, die in der Praxis in wissenschaftlichen Computeranwendungen verwendet werden.

Hier ist also die Frage: Kennt jemand wissenschaftliche Computercodes, die eine dieser Bibliotheken / Spracherweiterungen oder ähnliches für die Parallelität von gemeinsamem Speicher verwenden?

Pedro
quelle
Suchen Sie eine aufgabenbasierte Parallelität? Gibt es einen Grund, warum Sie OpenCL und Intel TBB übersprungen haben? Ich muss zugeben, dass ich nicht genau sagen kann, wonach Sie hier suchen.
Aron Ahmadia
1
@AronAhmadia: Ignoranz, hauptsächlich ... :) Ich habe TBB und OpenCL zur Liste hinzugefügt, aber die Frage ist immer noch dieselbe: Wurden diese, dh ihre aufgabenbasierten Komponenten, in einer bedeutenden Software für wissenschaftliche Zwecke verwendet? Computer?
Pedro
Wie denken wir darüber, diese Frage und ihre Antworten in ein Community-Wiki zu verwandeln, anstatt zu versuchen, sie weiter zu erweitern?
Aron Ahmadia
@AronAhmadia: Ich mache mir ein bisschen Sorgen, dass wenn ich das Fragenformat verlasse, dies schnell zu langen Diskussionen über die Vor- und Nachteile der aufgabenbasierten und / oder gemeinsam genutzten Speicherprogrammierung im Allgemeinen ausarten wird. Ich würde es jedoch befürworten, es zu wechseln, nachdem es ein paar weitere Antworten erhalten hat.
Pedro
Der Titel ist nicht angemessen. Bei dieser Frage geht es um Aufgabenparallelität, nicht um Shared Memory.
Jeff

Antworten:

8

deal.II verwendet die Threading-Bausteine ​​in der gesamten Bibliothek und im Großen und Ganzen sind wir ziemlich zufrieden damit. Wir haben uns einige Alternativen angesehen, insbesondere OpenMP, da jeder diese für einfachere Codes zu verwenden scheint, aber festgestellt hat, dass sie fehlen. Insbesondere hat OpenMP den großen Nachteil, dass das Aufgabenmodell es Ihnen nicht ermöglicht, ein Handle für eine gestartete Aufgabe zu erhalten, und folglich ist es schwierig, auf den Status einer Aufgabe zuzugreifen (z. B. auf deren Abschluss zu warten) oder Werte von zurückzugeben Funktionen, die Sie für eine separate Aufgabe ausführen. OpenMP eignet sich in erster Linie für die Parallelisierung der innersten Schleifen. Sie erzielen jedoch eine parallele Effizienz, indem Sie die äußersten , komplexen Schleifen parallelisieren. OpenMP ist nicht das Werkzeug dafür, während die TBB dafür einigermaßen gut geeignet sind.

Wolfgang Bangerth
quelle
Vielen Dank für den Hinweis, ich hatte Deal nicht angeschaut. II! Gibt es eine Veröffentlichung oder Dokumentation, in der die Verwendung des TBB durch deal.II ausführlich beschrieben wird?
Pedro
Keine Veröffentlichung, aber dies kann helfen: dealii.org/developer/doxygen/deal.II/group__threads.html
Wolfgang Bangerth
4

Meiner Meinung nach waren diese Systeme vor allem aus folgenden Gründen relativ erfolglos.

  • Die naive Perspektive der parallelen Berechnung besteht darin, die Berechnung (z. B. Flops) mehr zu parallelisieren als die Speicherlokalität freizulegen und Synchronisationspunkte zu entfernen. Obwohl einige Probleme, wie z. B. Dichtematrix-Algorithmen, immer noch FP-begrenzt sind, tritt dies nur nach sorgfältiger Prüfung des Speichersubsystems auf, und die meisten Rechenkerne (insbesondere in der PDE-Welt) sind speicherempfindlicher. Arbeitswarteschlangen tendieren dazu, die Speicherlokalität gegen ein besseres naives Gleichgewicht von Flops und atomarere Speicheroperationen auszutauschen (aufgrund der Synchronisation durch die Warteschlange).
  • Verlassen Sie sich auf eine Überzerlegung für einen dynamischen Lastausgleich auf Kosten einer starken Skalierbarkeit. Aufgaben haben im Allgemeinen überlappende Datenabhängigkeiten (Geisterwerte). Wenn die Größe des Innenraums kleiner wird, nimmt das Verhältnis von Geist zu Innenraum zu. Selbst wenn dies keine redundante Arbeit impliziert, impliziert dies eine erhöhte Speicherbewegung. Erhebliche Reduzierungen der Speicherbandbreitenanforderungen können durch Ansätze wie das kooperative Prefetch erzielt werden, bei dem mehrere Threads einen L1- oder L2-Cache gemeinsam nutzen, indem sie für ihren Nachbarn Software-Prefetching durchführen (wodurch die Gruppe von Threads implizit ungefähr kohärent bleibt). Dies ist genau das Gegenteil von Überzersetzung.
  • Unvorhersehbare Leistung, hauptsächlich aufgrund der oben genannten Speicherprobleme.
  • Mangel an bibliotheksfreundlichen Komponenten. Dies kann fast so zusammengefasst werden, dass es kein Analogon von a gibt, MPI_Commdas es verschiedenen Bibliotheken ermöglicht, umfangreiche Operationen ohne Kollision auszuführen sowie den Kontext zwischen Bibliotheken zu übergeben und die erforderlichen Attribute wiederherzustellen. Die vom "Kommunikator" bereitgestellte Abstraktion ist wichtig für die Bibliothekszusammensetzung, unabhängig davon, ob gemeinsamer oder verteilter Speicher verwendet wird.
Jed Brown
quelle
Ich verstehe Ihre Antwort vielleicht falsch, aber der erste Punkt ist genau das Gegenteil von dem, was Buttari, Kurzak, Dongarra und andere mit MAGMA gezeigt haben, einer aufgabenbasierten Shared-Memory-Bibliothek für dichte lineare Algebra ... Auch in Ihrem zweiten Punkt Sie beziehen sich auf überlappende Daten, dh Geisterwerte, und das Verhältnis von Oberfläche zu Volumen, aber dies ist ein Überbleibsel von Zerlegungsschemata für Domänen mit verteiltem Speicher. Ich selbst arbeite mit solchen Methoden für partikelbasierte Codes und erhalte eine viel bessere Leistung als MPI-basierte parallele Implementierungen.
Pedro
Die Frage war auf jeden Fall eine andere ... Kennen Sie wissenschaftliche Computersoftwareprojekte, die diese Ansätze verwenden?
Pedro
1. Es gibt eine Handvoll Projekte, die diese Systeme verwenden, aber ich denke nicht, dass der Ansatz als "erfolgreich" angesehen werden kann. 2. Die Abhängigkeiten überlappen sich im gemeinsam genutzten Speicher immer noch. Sehen Sie sich an, wie tcmalloc oder der Linux-Kernel Threads unabhängiger machen, um Engpässe wie die Synchronisation durch Atomics zu vermeiden. Gemeinsamer Adressraum bedeutet nicht, dass Sie so arbeiten sollten, als hätten Sie einen einheitlichen Speicher, oder dass Sie Atomics als kostengünstig betrachten sollten.
Jed Brown
3. Ich weiß nicht, welchen "fairen Vergleich" Sie zitieren wollen, aber PLASMA erhält nur etwa 25% der Spitzen-FPU (z. B. Folie 5 von hpcgarage.org/cscads2012/Luszczek-UTK-PowerTools.pdf ) hochveröffentlichbar schlecht für den gleichen Vorgang im verteilten Speicher, bei dem mindestens 70% des Peaks erwartet werden. Dichte lineare Algebra ist ein FPU-gebundener Fall, den ich speziell als mögliche Ausnahme angeführt habe, aber trotz der enormen Matrixgrößen ist PLASMA offensichtlich weit davon entfernt, FPU-gebunden zu sein.
Jed Brown
Pedro, die meiste Physik hat eine Komponente mit großer Reichweite, daher werden Partikel mit einem Update gekoppelt, das dem oben genannten Effekt von Oberfläche zu Lösungsmittel (PPPM, Wirbelpartikel usw.)
unterliegt