Was sind die Vor- und Nachteile der Parallelisierungsalgorithmen für die Partikelzerlegung und die Domänenzerlegung?

Ich führe Molekulardynamik (MD) -Simulationen mit verschiedenen Softwarepaketen wie Gromacs und DL_POLY durch.

Gromacs unterstützt jetzt sowohl den Partikelzerlegungs- als auch den Domänenzerlegungsalgorithmus . Standardmäßig verwenden Gromacs-Simulationen die Domänenzerlegung, obwohl bis vor kurzem die Partikelzerlegung für viele Jahre die einzige in Gromacs implementierte Methode war. In einem der Gromacs-Artikel (DOI 10.1002 / jcc.20291) geben die Autoren einen Grund für ihre anfängliche Wahl der Partikelzersetzung an:

"Eine frühe Entwurfsentscheidung war die Entscheidung, mit Partikelzerlegung statt Domänenzerlegung zu arbeiten, um die Arbeit auf die Prozessoren zu verteilen. Im letzteren Fall werden räumliche Domänen Prozessoren zugewiesen, wodurch räumliche Nachbarn nur durch lokale Kommunikation schnell gefunden werden können, aber Komplikationen aufgrund Die Domänenzerlegung ist nur dann eine bessere Wahl, wenn die lineare Systemgröße den Wechselwirkungsbereich erheblich überschreitet, was in der Molekulardynamik selten der Fall ist. Bei der Partikelzerlegung berechnet jeder Prozessor die Kräfte und Koordinaten- / Geschwindigkeitsaktualisierungen für einen zugewiesenen Bruchteil der Partikel unter Verwendung einer vorberechneten Nachbarliste, die gleichmäßig auf Prozessoren verteilt ist ergibt sich aus der Paarwechselwirkung zwischen den Partikeln i und j , die für die Geschwindigkeitsaktualisierung beider Partikel i und $F_{ij}$$i$$j$$i$$j$, wird nur einmal berechnet und an andere Prozessoren übermittelt. Jeder Prozessor speichert in seinem lokalen Speicher den vollständigen Koordinatensatz des Systems, anstatt den Speicher auf die benötigten Koordinaten zu beschränken. Dies ist einfacher und spart Kommunikationsaufwand, während der Speicheranspruch selbst für Millionen von Partikeln in der Regel kein einschränkender Faktor ist. Die Nachbarliste hingegen, die das 1000-fache der Partikelanzahl enthalten kann, ist auf die Prozessoren verteilt. Die Kommunikation beschränkt sich im Wesentlichen auf das Senden von Koordinaten und Kräften einmal pro Zeitschritt um den Prozessorring. Diese Auswahl hat sich im Laufe der Zeit als robust erwiesen und lässt sich problemlos auf moderne Prozessor-Cluster anwenden. "

Was bedeuten sie mit "linearer Systemgröße" im Satz "Domänenzerlegung ist nur dann eine bessere Wahl, wenn die lineare Systemgröße den Wechselwirkungsbereich, der in der Molekulardynamik selten vorkommt, erheblich überschreitet"? Aus dem obigen Absatz gehe ich davon aus, dass die Partikelzerlegung den Vorteil hat, dass man sich nicht mit Partikeln befassen muss, die sich über Domänengrenzen hinweg bewegen. Vielmehr muss jeder Prozessor über genügend Speicher verfügen, um die gesamte Systemkonfiguration zu speichern . Die Zersetzung von Partikeln sieht also sehr günstig aus, wohingegen die Zersetzung von Domänen sehr ungünstig ausschaut.

Ich bin mir sicher, dass dies eine sehr komplizierte Frage ist (und wahrscheinlich das Thema vieler Bücher ist), aber im Grunde genommen, wenn die Zerlegung von Partikeln so günstig erscheint, warum sollte jemand die Zerlegung von Domänen verwenden müssen? Ist die Zerlegung von Domänen nur dann günstig, wenn das System sehr groß ist (was es schwierig oder unmöglich macht, die Gesamtkonfiguration in jedem Prozessor zu speichern)? Aufgrund des oben zitierten Abschnitts bin ich mir nicht sicher, warum die Zerlegung von Domänen in letzter Zeit der Standard-Parallelisierungsalgorithmus in Gromacs ist.

Es scheint, dass DL_POLY jetzt (Version 4) auch die Zerlegung von Domänen verwendet. Aus dem Handbuch der Version 4:

Die Aufteilung der Kongurationsdaten auf diese Weise basiert auf der Position der Atome in der Simulationszelle. Eine solche geometrische Zuordnung von Systemdaten ist das Kennzeichen von DD-Algorithmen. Damit diese Strategie effizient funktioniert, muss das Simulierte beachtet werden Das System muss eine einigermaßen einheitliche Dichte haben, damit jedem Prozessor (so weit wie möglich) nahezu der gleiche Anteil an Atomdaten zugewiesen wird Die Methode ist konzeptionell einfach, aber schwierig zu programmieren und eignet sich besonders für Simulationen in großem Maßstab, bei denen die Effizienz am höchsten ist.

...

Bei der DD-Strategie ist der Algorithmus SHAKE (RATTLE) einfacher als bei der Methode Replicated Data von DL_POLY Classic, bei der globale Aktualisierungen der Atompositionen (Zusammenführen und Spleißen) erforderlich sind. "

Dies lässt den Eindruck entstehen, dass die Zerlegung von Domänen gut ist, da sie möglicherweise effizienter ist, auch wenn sie möglicherweise schwieriger zu implementieren ist.

Andererseits verwendete eine frühere Version (DL_POLY Classic) die Parallelisierung replizierter Daten, was ein anderer Name für die Partikelzerlegung zu sein scheint. Aus dem Handbuch dieser Version:

$\textbf{r}_i$$\textbf{v}_i$$\textbf{f}_i$$N$Atome im simulierten System werden auf jedem Verarbeitungsknoten reproduziert. Bei dieser Strategie können die meisten Kräfte, die für die Berechnung und Integration der Bewegungsgleichungen benötigt werden, leicht und gleichmäßig auf die Knoten verteilt und zu einem großen Teil auf jedem Knoten unabhängig voneinander verarbeitet werden. Die Methode ist relativ einfach zu programmieren und relativ effizient. Darüber hinaus kann es „zusammengeklappt“ werden, um sehr einfach auf einem einzelnen Prozessor ausgeführt zu werden. Die Strategie kann im Speicher teuer sein und einen hohen Kommunikationsaufwand verursachen. Insgesamt hat sie sich jedoch in einer Vielzahl von Anwendungen als erfolgreich erwiesen.

Dieser Absatz scheint im Allgemeinen mit dem ersten Absatz dieser Frage übereinzustimmen, mit der Ausnahme, dass er besagt, dass die Zerlegung replizierter Daten / Partikel einen "hohen Kommunikationsaufwand" hat. Der Absatz aus dem Gromacs-Papier scheint das Gegenteil zu sagen: Die Zersetzung von Partikeln ist vorzuziehen, da sie einen geringeren Kommunikationsaufwand als die Zersetzung von Domänen hat.

Hast du irgendwelche Gedanken?

Die Zerlegung von Partikeln und Domänen ist direkt mit den beiden Hauptmethoden zur Beschleunigung von Kraftberechnungen für Systeme mit begrenzten Wechselwirkungen verbunden - Verlet-Nachbarlisten und Zellverknüpfungslisten. Wenn Sie näher auf Details eingehen möchten, gibt es ein hübsches Buch von Allen und Tildesley mit dem Titel Computer Simulation of Liquids , das von vielen als "Bibel" der Molekulardynamik- und Monte-Carlo-Studien angesehen wird. Dann gibt es die Numerische Simulation in der Molekulardynamik von Griebel, Knapek und Zumbusch, die die verschiedenen Techniken für die parallele Implementierung von MD vertieft.

$O(N^2)$$O(N)$

$O(N)$$O(N)$ $N$es skaliert besser. Daher das Argument der linearen Größe. Die Methode zur Zerlegung von Domänen ist eine einfache Erweiterung der Methode für verknüpfte Listen von Zellen - Zellen werden auf verschiedene CPUs aufgeteilt.

Das Problem bei der Zerlegung von Domänen besteht darin, dass sie kommunizieren muss, wenn sich Partikel von einer Zelle in eine andere bewegen, für die eine andere CPU sorgt. Dies könnte bei höheren Simulationstemperaturen problematisch werden, bei denen Partikel dazu neigen, sich weiter als bis zu ihrer Gleichgewichtsposition zu entfernen, oder wenn Partikel strömen. Außerdem müssen Informationen aus Zellen an der Domänengrenze bei jeder Iteration an die Nachbardomäne (n) übertragen werden. Dies alles ist jedoch lokal synchrone Kommunikation und kann sehr effizient durchgeführt werden.

Die replizierten Daten sind der einfachste Ansatz, aber leider müssen bei jedem Schritt alle Positions- und Geschwindigkeitsinformationen global synchronisiert werden. Dies lässt sich nicht gut skalieren, und bei sehr großen Systemen entspricht die globale Speicherkapazität der Größe der Datenstruktur und der Anzahl der verwendeten CPUs, während eines der Ziele der parallelen Verarbeitung die Verteilung von Daten ist, sodass jede CPU weniger Speicherplatz hat als die globale Datenmenge.

Zusammenfassend gibt es keine "Einheitsgröße" -Methode, die für alle zu simulierenden Systeme geeignet ist. Meist lässt sich aus der Systemgeometrie die beste Parallelisierungsstrategie ableiten und der für diesen Fall geeignete MD-Code auswählen - schließlich implementieren alle mehr oder weniger die gleichen zugrunde liegenden Kraftfelder und Integratoren.

Mit "Die Zerlegung von Domänen ist nur dann eine bessere Wahl, wenn die lineare Systemgröße den Wechselwirkungsbereich erheblich überschreitet, was in der Molekulardynamik selten der Fall ist" meinen die Autoren dieses (sehr alten) GROMACS-Papiers, wenn die räumliche Größe der Nachbarliste gleich ist in der Größenordnung von 1 nm, und die Simulationszelle ist nur einige Nanometer groß, dann ist der Aufwand für die Durchführung der Domänenzerlegung zu hoch. Möglicherweise akzeptieren Sie auch eine Gesamtinformationsverteilung bei der Zerlegung von Partikeln und müssen für die Zerlegung von Domänen keine Zeit für die gesamte Buchhaltung aufwenden.

Das Problem bei der Partikelzerlegung bei der Implementierung von GROMACS bestand darin, dass die jedem Prozessor zugewiesenen Partikel mit der Zeit durch den Raum diffundieren. Da die Verantwortung für die Berechnung jeder Interaktion durch ihren anfänglichen Ort festgelegt war, erhöhte die Diffusion allmählich das Volumen des gesamten Speicherplatzes, den jeder Prozessor wissen musste, um seine Nachbarliste zu erstellen, selbst wenn die von der Nachbarliste beschriebene Gesamtberechnung konstant war. In der Praxis würden Sie die Simulation regelmäßig neu starten, um die Daten und den Kommunikationsort zurückzusetzen.

Ihre Annahme, dass "Partikelzersetzung den Vorteil hat, dass man sich nicht mit Partikeln befassen muss, die sich über Domänengrenzen hinweg bewegen", gilt nicht, wenn die Diffusion über die Zeitskala der Simulation signifikant ist.

Die Zerlegung von Domänen bewältigt dieses Problem, indem die Verantwortung für die Interaktion zusammen mit der Diffusion migriert wird, wodurch die Datenlokalität auf jedem Prozessor verbessert und das Kommunikationsvolumen minimiert wird.

Haftungsausschluss: Ich helfe bei der Entwicklung von GROMACS und werde wahrscheinlich nächste Woche die Implementierung der Partikelzerlegung herausreißen ;-)

Ich möchte die Antwort von Hristo Iliev ergänzen. Während in seinem Beitrag vor allem die Komplexität von Rechnern angesprochen wird , ist bei der Parallelisierung die Komplexität der Kommunikation mindestens ebenso wichtig - und dies ist der Hauptgrund für die Zerlegung von Domänen.

Moderne Parallelmaschinen haben normalerweise eine Art Torustopologie. Dies bedeutet, dass jede CPU eine Anzahl "benachbarter" CPUs hat, mit denen sie sehr schnell kommunizieren kann. Die Kommunikation mit einer CPU, die kein Nachbar ist, ist teurer. Daher ist es immer günstig, einen Algorithmus zu haben, der nur mit benachbarten CPUs kommunizieren muss.

$P$$\mathcal{O}(P^2)$

$P$$\mathcal{O}(P)$

$\mathcal{O}(P)$

Beachten Sie jedoch, dass ungleichmäßige Systeme nicht so häufig sind, wie es sich anhört. Sie treten nur auf, wenn entweder etwas im Vakuum simuliert wird oder wenn ein implizites Lösungsmittel verwendet wird. Die Dichte von Kristallen und Flüssigkeiten ist nahe genug, um eine Zersetzung der Domänen durchzuführen.