Wie ist der Stand der Technik bei parallelen ODE-Methoden?

39

Ich suche derzeit nach parallelen Methoden für die ODE-Integration. Es gibt eine Menge neuer und alter Literatur, die eine Vielzahl von Ansätzen beschreibt, aber ich habe in letzter Zeit keine Umfragen oder Übersichtsartikel gefunden, die das Thema allgemein beschreiben.

Es gibt das Buch von Burrage [1], aber es ist fast 20 Jahre alt und deckt daher nicht viele der moderneren Ideen wie den Parareal-Algorithmus ab.

[1] K. Burrage, parallele und sequentielle Methoden für gewöhnliche Differentialgleichungen, Clarendon Press, Oxford, 1995

Florian Brucker
quelle

Antworten:

35

Mir sind keine aktuellen Übersichtsartikel bekannt, aber ich bin aktiv an der Entwicklung des PFASST-Algorithmus beteiligt, sodass ich einige Gedanken austauschen kann.

Es gibt drei große Klassen zeitparalleler Techniken, die mir bekannt sind:

  • methodenübergreifend können parallel unabhängige Stufen von RK- oder Extrapolationsintegratoren ausgewertet werden; siehe auch RIDC (revisionist integral deferred correction algorithm)
  • über das Problem - Wellenformrelaxation
  • im Zeitbereich - Parareal; PITA (Parallel in Time Algorithmus); und PFASST (paralleles Vollnäherungsschema in Raum und Zeit).

Methoden, die methodenübergreifend parallelisiert werden, arbeiten normalerweise sehr spezifikationsnah, skalieren jedoch nicht über eine Handvoll (Zeit-) Prozessoren hinaus. In der Regel sind sie relativ einfach zu implementieren als andere Methoden und eignen sich gut, wenn Sie ein paar zusätzliche Kerne haben und nach vorhersehbaren und bescheidenen Beschleunigungen suchen.

Methoden, die über den Zeitbereich parallelisieren, umfassen Parareal, PITA, PFASST. Diese Verfahren sind alle iterativ und bestehen aus billigen (aber ungenauen) "groben" Vermehrern und teuren (aber genauen) "feinen" Vermehrern. Sie erzielen eine parallele Effizienz, indem sie den Feinpropagator iterativ parallel auswerten, um eine serielle Lösung zu verbessern, die unter Verwendung des Grobpropagators erhalten wird.

EE<1/KK

Mit all diesen Methoden können viele Spiele gespielt werden, um sie zu beschleunigen. Die Leistung dieser domänenübergreifenden Techniken scheint davon abzuhängen, welches Problem Sie lösen und welche Techniken zur Beschleunigung der Grobbearbeitung verfügbar sind Propagator (vergröberte Gitter, vergröberte Operatoren, vergröberte Physik usw.).

Einige Referenzen (siehe auch Referenzen in den Papieren):

Ich habe zwei Implementierungen von PFASST geschrieben, die im Internet verfügbar sind: PyPFASST und libpfasst .

Matthew Emmett
quelle
1
Ich lerne gerade Parareal. Und ich denke, es ist eine große Hilfe für mich.
eccstartup
Dies ist eine großartige Übersicht. Es sollte jedoch ausdrücklich erwähnt werden, dass ODEs häufig nach einer räumlichen Diskretisierung von PDEs gelöst werden. Daher kann die methodenübergreifende Parallelität eine hohe Skalierbarkeit für Tausende von Kernen ergeben, wenn Ihre räumliche Domäne groß genug ist. Dies liegt daran, dass die überwiegende Mehrheit der Rechenzeiten beispielsweise für die Berechnung der RHS-Bewertungen der RK-Stufe verwendet wird.
NoseKnowsAll
15

Obwohl dieser Beitrag jetzt zwei Jahre alt ist, möchte ich mich kurz über ihn informieren, falls jemand darüber stolpert:

Martin Gander hat kürzlich einen schönen Übersichtsartikel geschrieben, der eine historische Perspektive auf das Gebiet bietet und viele verschiedene PINT-Methoden behandelt: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

Es gibt jetzt auch eine Community-Website, die sehr viele Referenzen auflistet und verschiedene Methoden beschreibt: http://www.parallel-in-time.org/

Eine Diskussion des Parareal-Parallel-in-Time-Algorithmus finden Sie hier: https://en.wikipedia.org/wiki/Parareal

Daniel
quelle
1
Ein wenig überrascht, dass Gander nicht über den MGRIT-Ansatz von Falgout et al. Spricht, zumal er von netter Software (XBraid) unterstützt zu werden scheint, aber ich weiß, dass die MGRIT-Papiere erst kürzlich erschienen sind.
Geoff Oxberry
1
Hallo Geoff, ich bin mir ziemlich sicher, dass Martin Gander das Paper geschrieben hat, bevor die MGRIT-Papiere veröffentlicht wurden - während das Review-Paper 2015 erscheinen wird, ist der Preprint meiner Meinung nach bereits Ende 2013 online gegangen.
Daniel
1
Auf den ersten Blick sieht es so aus, als würde in diesem Review "Parallelität über die Methode" weggelassen - zum Beispiel wird Extrapolation nie erwähnt.
David Ketcheson
4

u0u(t)=exp(λt)u0, Reλ>0.

Hui Zhang
quelle
Wie gesagt, ich habe bereits viele Artikel zu den einzelnen Themen gefunden. Was mir fehlt, ist ein allgemeiner Überblick über die Ansätze.
Florian Brucker
1
FWIW, der PFASST-Algorithmus zeigt eine sehr gute Konvergenz (wird bald veröffentlicht) für Hamilton-Systeme, selbst für viele (Hunderte) Zeitprozessoren. Allerdings hängt eine nennenswerte Beschleunigung (wieder) davon ab, dass die Grobpropagatoren viel billiger sind als die Feinpropagatoren. Eine Multipolexpansion oder ein anderer multiphysikalischer Ansatz scheint erforderlich zu sein, um eine gute Beschleunigung für Partikelsysteme zu erzielen.
Matthew Emmett