Beispiele für PDE-Berechnungen, bei denen sowohl räumlich als auch zeitlich Parallelität verwendet wird

14

In der numerischen Lösung von anfänglichen Randwert-PDEs ist es sehr verbreitet, Parallelität im Raum zu verwenden . Es ist weitaus seltener, eine Form von Parallelität in der Zeitdiskretisierung anzuwenden , und diese Parallelität ist normalerweise viel begrenzter. Mir ist eine zunehmende Anzahl von Codes und veröffentlichten Arbeiten bekannt, die zeitliche Parallelität demonstrieren, aber keine von ihnen beinhaltet räumliche Parallelität.

Gibt es Beispiele für Implementierungen, die sowohl räumliche als auch zeitliche Parallelität beinhalten? Ich interessiere mich sowohl für Veröffentlichungen als auch für verfügbare Codes.

David Ketcheson
quelle
Ich habe gerade diesen Preprint gefunden, der Parareal mit räumlicher Domänenzerlegung
David Ketcheson

Antworten:

8

In letzter Zeit wurden die Algorithmen PFASST (Parallel Full Approximation Scheme in Space and Time) und PEPC (Pretty Efficient Parallel Coulomb) zusammen verwendet, um eine räumliche und zeitliche Parallelität zu erreichen.

PFASST übernimmt die Zeitparallelität, PEPC die Raumparallelität. Die Ergebnisse wurden kürzlich auf der DD21- Konferenz vorgestellt, und wir haben eine Einreichung für SC12 vorbereitet , die die Kombination von PFASST + PEPC beschreibt.

Es wurde gezeigt, dass ein "kleines" Problem, das aus 4 Millionen Partikeln besteht (PEPC ist ein paralleler N-Körper-Löser), unter Verwendung von nur PEPC (dh nur parallel im Raum) gut auf 8192 Kerne auf JUGENE skaliert werden kann . Darüber hinaus wurden die Kommunikationskosten erheblich und die parallele Effizienz begann sich zu verschlechtern. Durch Hinzufügen von PFASST kann dieses Problem mit 262.144 Kernen (dh wir haben JUGENE aufgefüllt) unter Verwendung von 32 "Zeit" -Prozessoren (von denen jeder aus 8192 "räumlichen" Kernen besteht) ausgeführt werden.

Obwohl die parallele Effizienz von zeitparallelen Algorithmen nicht 100% beträgt, konnten wir mit 32 PFASST-Prozessoren mit dieser PFASST + PEPC-Konfiguration eine Geschwindigkeitssteigerung von ca. 6,5x erzielen.

Hier ist ein Link zu einem Preprint: Ein massiv raumzeitparalleler N-Body-Solver

Matthew Emmett
quelle
Matt, das klingt ziemlich ordentlich, bitte aktualisieren Sie mit einem Link zum Entwurf, wenn Sie fertig sind.
Aron Ahmadia
Genial, genau das, wonach ich gesucht habe. Übrigens, gute Arbeit.
David Ketcheson
Vielen Dank! Ich werde versuchen, bald einen Link zu posten. Übrigens habe ich auch einen PETSc DA erfolgreich verwendet, um die räumliche Domäne eines Flachwasserlösers innerhalb von PyPFASST zu verteilen.
Matthew Emmett
1
@AronAhmadia, Link zum Preprint hinzugefügt!
Matthew Emmett
4

Es gibt auch Raum-Zeit-DG- und kontinuierliche Galerkin-Methoden. Nach der Wahl der Quadratur entspricht die Raum-Zeit-DG mit einem strukturierten Gitter in Zeitrichtung einer impliziten Runge-Kutta-Methode. Die Raum-Zeit-DG-Methode ermöglicht jedoch unterschiedliche Schrittgrößen in verschiedenen Teilen der Domäne, ein Fall, der für implizite RK-Methoden schwer zu analysieren ist. In diesem Zusammenhang können auch Raum-Zeit-Multigrid-Methoden angewendet werden.

Jed Brown
quelle
Ich verstehe nicht, wie das zeitlich parallel ist. Können Sie ein Beispiel nennen oder mehr erklären?
David Ketcheson
Wenn Sie die Domäne vergrößern, können Sie sie in mehrere Domänen einer bestimmten Größe aufteilen. Raum-Zeit-Methoden erweitern die Domäne um die Zeitdimension und erhöhen so die Parallelität. Beachten Sie, dass das gleichzeitige Ausführen mehrerer verwandter Aufgaben enorme Rechenvorteile mit sich bringt. Wenn Sie also eine maximale Leistung mit bescheidenen Zeitblöcken erzielen, können Sie möglicherweise nur räumlich zerlegen und lokal in der Zeitdimension vektorisieren.
Jed Brown
2

Wenn Sie Raum-Zeit-Parallelen betrachten, ist die Unterdomäne Raum-Zeit über mehrere Zeitebenen. Eine Methode namens Wellenformrelaxation nutzt Raum-Zeit-Subdomänen, parallelisiert jedoch nur im Raum (keine Partition in der Zeitdimension). Ein Kartesier aus Raumpartition und Zeitpartition ergibt also eine Art Raum-Zeit-Parallelität. Über eine solche kartesische Methode können Sie sich hier informieren . Wie Jed Brown in seiner Antwort erwähnte, bietet die Raum-Zeit-Methode nicht nur flexiblere Parallelen, sondern auch Anpassungsmöglichkeiten für die Diskretisierung. Zum letzteren Thema können Sie Werke von Schwab googeln, siehe auch deren Projekt . Auf der Homepage von R. Haynes können Sie nachlesen, welche Arbeiten sowohl Parallelität als auch Adaptivität ausnutzen .

Hui Zhang
quelle
1

Werfen Sie einen Blick auf den Parareal-Algorithmus und die damit verbundene Arbeit wie die spektral verzögerte Korrektur (eine einfache Google-Suche liefert ziemlich viel Material). Die Grundidee besteht darin, ein grobes "Netz" in der Zeit zu verwenden und eine grobe Zeitabstufung vorzunehmen, aber dann darauf zurückzukommen und Korrekturen auf einer feineren Zeitskala durchzuführen. Es scheint hauptsächlich in Fluidsimulationen verwendet zu werden, aber ich bin auf dem Gebiet der Elektromagnetik, daher kann ich nicht wirklich viel mehr dazu sagen. Der einzige Grund, warum ich davon weiß, ist, dass ich an einem Seminar über den Ansatz der verzögerten Korrektur teilgenommen habe und es sehr interessant erschien, dass jede Art von Parallelisierung rechtzeitig durchgeführt werden kann.

Victor Liu
quelle
Ich weiß von denen, aber können Sie auf einen Fall hinweisen, in dem sie in Verbindung mit räumlicher Parallelität verwendet werden?
David Ketcheson
Um klar zu sein, haben zurückgestellte oder Fehlerkorrekturschemata für sich genommen nichts mit Parareal- und / oder zeitparallelen Schemata zu tun.
Matthew Emmett
1

Die Mehrfachaufnahmemethode, die bei der optimalen Steuerung verwendet wird, ist so ausgelegt, dass die Unterprobleme in jedem Aufnahmeintervall parallel gelöst werden können. Ich kenne keine Papiere, die dies mit räumlicher Parallelität verbinden (es gibt nicht so viele optimale Steuerungsprobleme, die in der Vergangenheit gelöst wurden, als die Gleichung eine zeitabhängige räumliche PDE ist), aber es wäre offensichtlich, wie Parallelität hergestellt werden kann Raum und Zeit.

Wolfgang Bangerth
quelle