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.
pde
parallel-computing
time-integration
David Ketcheson
quelle
quelle
Antworten:
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
quelle
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.
quelle
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 .
quelle
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.
quelle
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.
quelle