Ist diskontinuierliches Galerkin wirklich parallelisierbarer als kontinuierliches Galerkin?

9

Ich habe immer gehört, dass eine einfache Parallelisierung einer der Vorteile von DG-Methoden war, aber ich verstehe nicht wirklich, warum einer dieser Gründe nicht auch für kontinuierliches Galerkin gilt.

Truman Ellis
quelle
1
Ich glaube nicht, aber es könnte die Frage verbessern, wenn Sie einige dieser vermeintlichen Gründe verlinken oder beschreiben.
Bill Barth

Antworten:

9

Ein Grund, warum DG-Methoden als parallele Methode möglicherweise mehr Aufmerksamkeit erhalten, besteht darin, dass leicht ersichtlich ist, dass die Methode für ein Element von Natur aus lokal ist. Die Kopplung bei DG-Methoden ist schwach, da sie nur durch benachbarte Kanten (oder Flächen in 3d) auftritt. Bei Dreiecken oder Quads kommuniziert DG also höchstens mit drei oder vier Prozessoren. Während CG-Methoden Elementecken enthalten, wird die Wertigkeit der Ecke eines Elements wichtig. Abhängig vom verwendeten Netzgenerator kann diese Wertigkeit acht Prozessoren (möglicherweise höher) betragen. Daher können die Kosten für die Zusammenstellung der Zeitableitung für CG-Methoden als "höher" angesehen werden. Dies ist insbesondere bei Spektralverfahren von Bedeutung, bei denen das zu übermittelnde Informationsvolumen sehr groß sein kann (und das Ausblenden der Latenz schwieriger werden kann, wenn die Größe jeder Partition abnimmt).

Diese zusätzlichen Kosten für CG für die Zusammenstellung der Zeitableitung könnten jedoch durch eine andere Lastausgleichsstrategie ausgeglichen werden. Verschiedene Netzpartitionierungsstrategien (ich bin mit METIS am vertrautesten) ermöglichen es dem Benutzer, die Last durch verschiedene Metriken auszugleichen, z. B. sicherzustellen, dass jede Partition ungefähr die gleiche Anzahl von Elementen aufweist, oder den Umfang der Kommunikation zwischen Partitionen zu begrenzen. Ich glaube, ein Grund dafür, dass das Kolloquisium von DG leicht parallelisierbar ist, ist, dass eine naive Aufteilung des Problems in gleiche Teile eine sehr effiziente parallele Implementierung ergeben kann, die in bestimmten Fällen aufgrund von Cache-Effekten sogar eine superlineare Beschleunigung darstellt (siehe zum Beispiel Baggag et al . oder et Altmann. al.). Während CG möglicherweise eine cleverere Partitionierungsmethode erfordert. So kann es sein, dass eine Änderung der räumlichen Diskretisierungen von DG zu CG beispielsweise erfordert, dass auch überlegt wird, wie das Netz in Teilprobleme unterteilt wird.

Andrew Winters
quelle
8

Aufgrund meiner langjährigen Erfahrung mit dem Schreiben von FEM-Software glaube ich, dass die Aussage, dass DG-Schemata besser für die Parallelisierung geeignet sind als CG-Schemata, apokryphisch ist. Es wird häufig in Einführungen von DG-Papieren als Rechtfertigung für DG-Methoden verwendet, aber ich habe nie gesehen, dass es mit einer Referenz belegt ist, die die Frage tatsächlich untersucht hat. Es ähnelt jedem NSF-Vorschlag zu einem zahlentheoretischen Projekt, bei dem "Kryptographie" als ein Bereich mit größerer Wirkung bezeichnet wird, eine Aussage, die in dieser Allgemeinheit auch niemals begründet wird.

Tatsächlich glaube ich, dass DG-Schemata mit Ausnahme von expliziten Zeitschrittschemata und möglicherweise Problemen, bei denen Sie eine Massenmatrix invertieren müssen, nicht besser oder schlechter sind als CG-Schemata, wenn man die damit verbundenen Kommunikationskosten untersucht. Ich meine dies im praktischen Sinne: Sicher, man muss möglicherweise weniger Daten kommunizieren, aber ich würde mir vorstellen, dass der Unterschied in der Wanduhrzeit für alle anderen Betriebsprogramme, die mit diesen Daten arbeiten, vernachlässigbar ist.

Natürlich würde ich mich freuen, wenn sich jemand der Herausforderung stellen würde, mir das Gegenteil zu beweisen!

Wolfgang Bangerth
quelle
5

Genau wie bei den meisten allgemeinen Aussagen zu numerischen Schemata hängt die Antwort von den genauen Umständen ab, die Sie betrachten. Erstens zahlen sich die Vorteile der GD in Bezug auf die Parallelisierung vor allem bei expliziten Zeitintegrationsschemata aus

  • Die zelllokale Massenmatrix von DG-Schemata (damit Sie die Umkehrung der Massenmatrix nicht global anwenden müssen)
  • Ein günstiges Verhältnis von CPU-lokaler Arbeit (Volumenintegrale) zu kommunikationsbezogener Arbeit (Kantenintegrale), insbesondere für höhere Aufträge

Während diese Aussagen für generische DG-Diskretisierungen gelten, erfordern echte HPC-Anwendungen (z. B. mit mehreren tausend Prozessoren) einige weitere Anstrengungen hinsichtlich der Parallelisierungsstrategie, um eine gute Skalierung aufrechtzuerhalten. Dieses Papier zeigt zum Beispiel, wie man eine nahezu perfekte Skalierung bis zu einer Zelle pro Prozessor erreichen kann . Dies ist sicherlich etwas, das Sie von einer kontinuierlichen FEM nicht erwarten können, aber wie bereits erwähnt, sind implizite Schemata völlig anders.

Bigge
quelle
1

Beim Zusammenstellen einer Steifheitsmatrix müssen die in einem Element in kontinuierlicher (Knoten-) FEM gespeicherten Daten an alle ihre Knotennachbarn übermittelt werden. Im Gegensatz dazu verlangt DGFEM, dass die Elementdaten an alle seine Gesichtsnachbarn übermittelt werden. In 1D sind Knoten- und Gesichtsnachbarn identisch, aber in 3D kann der Unterschied ziemlich groß sein: Für ein reguläres hexaedrisches Netz gibt es 26 Knotennachbarn, aber nur 6 Gesichtsnachbarn. Bei unregelmäßigen Netzen mit vielen hochvalenten Eckpunkten verschlechtert sich die Situation für CG, während sie für DG gleich bleibt.

gokturk
quelle
Stimmt, aber ist das, was Sie sagen, von praktischer Bedeutung? Mit anderen Worten, wenn Sie die Zeit für die Kommunikation dieser Elemente in einem realen FEM-Programm messen und mit der Zeit vergleichen würden, die für die Berechnung der Matrixeinträge erforderlich ist, wäre das wichtig?
Wolfgang Bangerth
1

DG für hyperbolische PDE kann als Ersatz für Schemata mit endlichem Volumen verwendet werden. Im endlichen Volumen wie in der endlichen Differenz erhöht sich Ihre Schablone, wenn Sie die Reihenfolge des Schemas erhöhen. Dies erschwert die Parallelisierung, da Sie für jede Schemareihenfolge unterschiedliche Schablonen haben. An Partitionsgrenzen müssen Sie sicherstellen, dass alle erforderlichen Zellen aus der benachbarten Partition für die bestimmte Reihenfolge des Schemas verfügbar sind. Bei DG kommuniziert jede Zelle unabhängig von der Reihenfolge des Schemas nur mit ihren Gesichtsnachbarn. Im Vergleich zwischen endlichem Volumen / Differenz und DG kann man also sagen, dass die DG leichter zu parallelisieren ist.

cfdlab
quelle