Jakie są zalety i wady algorytmów równoległego rozkładu cząstek i dekompozycji domen?

Prowadzę symulacje dynamiki molekularnej (MD) przy użyciu kilku pakietów oprogramowania, takich jak Gromacs i DL_POLY.

Gromacs obsługuje teraz zarówno algorytmy dekompozycji cząstek, jak i dekompozycji domen. Domyślnie symulacje Gromacs wykorzystują rozkład domen, chociaż przez wiele lat, do niedawna, rozkład cząstek był jedyną metodą zaimplementowaną w Gromacs. W jednym z artykułów Gromacsa (DOI 10.1002 / jcc.20291) autorzy podają powód swojego wstępnego wyboru rozkładu cząstek:

„Wczesną decyzją projektową był wybór raczej pracy z rozkładem cząstek niż z rozkładem domen w celu rozdzielenia pracy między procesorami. W tym drugim przypadku domeny przestrzenne są przypisywane do procesorów, co umożliwia szybkie znajdowanie sąsiadów przestrzennych tylko przez lokalną komunikację, ale z powodu komplikacji cząstki poruszające się ponad granicami przestrzennymi są znaczne. Rozkład domen jest lepszym wyborem tylko wtedy, gdy rozmiar układu liniowego znacznie przekracza zakres interakcji, co rzadko ma miejsce w przypadku dynamiki molekularnej. Dzięki rozkładowi cząstek każdy procesor oblicza siły i aktualizuje współrzędne / prędkości dla przypisanej frakcji cząstek, przy użyciu wstępnie obliczonej listy sąsiadów równomiernie rozmieszczonej w procesorach$F_{ij}$ powstające z interakcji pary między cząstkami i, która jest potrzebna do aktualizacji prędkości obu cząsteki j i $i$$j$$i$$j$, jest obliczany tylko raz i przekazywany innym procesorom. Każdy procesor zachowuje w swojej lokalnej pamięci pełny zestaw współrzędnych systemu, a nie ogranicza pamięci do potrzebnych współrzędnych. Jest to prostsze i pozwala zaoszczędzić koszty komunikacji, podczas gdy twierdzenie o pamięci zwykle nie jest wcale czynnikiem ograniczającym, nawet dla milionów cząstek. Z drugiej strony lista sąsiadów, która może zawierać do 1000 razy więcej cząstek, jest rozłożona na procesory. Komunikacja ogranicza się zasadniczo do wysyłania współrzędnych i sił raz na krok wokół pierścienia procesora. Wybory te okazały się z czasem solidne i można je łatwo zastosować w nowoczesnych klastrach procesorów ”.

Co rozumieją przez „rozmiar systemu liniowego” w zdaniu „Dekompozycja domen jest lepszym wyborem tylko wtedy, gdy rozmiar systemu liniowego znacznie przekracza zakres interakcji, co rzadko zdarza się w dynamice molekularnej”? Z powyższego akapitu rozumiem, że rozkład cząstek ma tę zaletę, że nie trzeba zajmować się cząstkami poruszającymi się przez granice domen; raczej wystarczy mieć wystarczającą ilość pamięci dla każdego procesora, aby zapisać całkowitą konfigurację systemu. Tak więc rozkład cząstek wygląda bardzo korzystnie, podczas gdy rozkład domen wygląda bardzo niekorzystnie.

Jestem pewien, że jest to bardzo skomplikowane pytanie (i prawdopodobnie temat wielu książek), ale w gruncie rzeczy, jeśli rozkład cząstek wydaje się tak korzystny, dlaczego ktoś miałby używać rozkładu domen? Czy dekompozycja domeny jest po prostu korzystna, jeśli rozmiar systemu jest bardzo duży (utrudniając lub uniemożliwiając zapisanie całkowitej konfiguracji w każdym procesorze)? Na podstawie cytowanego akapitu powyżej nie jestem pewien, dlaczego dekompozycja domen jest teraz, niedawno, domyślnym algorytmem paralelizacji w Gromacs.

Wygląda na to, że DL_POLY teraz (wersja 4) również korzysta z dekompozycji domen. Z podręcznika wersji 4:

„Podział danych konguracyjnych w ten sposób opiera się na lokalizacji atomów w komórce symulacyjnej, taki geometryczny przydział danych systemowych jest cechą charakterystyczną algorytmów DD. Należy pamiętać, że aby strategia działała skutecznie, symulowano system musi posiadać odpowiednio jednorodną gęstość, aby każdy procesor miał przydzieloną prawie równą część danych atomu (w jak największym stopniu). Dzięki temu podejściu obliczanie sił i całkowanie równań ruchu są dzielone (rozsądnie) równo między procesory i w dużym stopniu można go obliczyć niezależnie dla każdego procesora. Metoda jest koncepcyjnie prosta, ale trudna do zaprogramowania i szczególnie nadaje się do symulacji na dużą skalę, w których wydajność jest najwyższa.

...

W przypadku strategii DD algorytm SHAKE (RATTLE) jest prostszy niż w przypadku metody replikowanych danych DL_POLY Classic), gdzie wymagane są globalne aktualizacje pozycji atomów (scalanie i splicing). ”

To sprawia, że ​​brzmi to tak, jakby dekompozycja domeny była dobra, ponieważ może być bardziej wydajna, chociaż być może trudniejsza do wdrożenia.

Z drugiej strony poprzednia wersja (DL_POLY Classic) stosowała równoległą replikację danych, która wydaje się być inną nazwą rozkładu cząstek. Z podręcznika tej wersji:

Strategia danych replikowanych (RD) jest jednym z kilku sposobów osiągnięcia równoległości w MD. Jego nazwa pochodzi od replikacji danych konfiguracyjnych na każdym węźle komputera równoległego (tj. Tablic definiujących współrzędne atomowe , prędkości i wymusza , dla wszystkiev i f i$\textbf{r}_i$$\textbf{v}_i$$\textbf{f}_i$$N$atomy w układzie symulowanym są odtwarzane na każdym węźle przetwarzającym). W tej strategii większość obliczeń sił i całkowanie równań ruchu można łatwo i równo podzielić między węzłami i w dużym stopniu przetwarzać niezależnie w każdym węźle. Metoda jest stosunkowo prosta do zaprogramowania i jest dość wydajna. Co więcej, można go bardzo łatwo „zwinąć”, aby działać na jednym procesorze. Jednak strategia może być kosztowna pod względem pamięci i mieć duże koszty ogólne komunikacji, ale ogólnie okazała się skuteczna w szerokim zakresie zastosowań.

Ten akapit wydaje się zasadniczo zgodny z pierwszym akapitem tego pytania, z tym wyjątkiem, że mówi, że powielony rozkład danych / cząstek ma „wysokie koszty ogólne komunikacji”. Akapit z artykułu Gromacsa wydaje się mówić przeciwnie - ten rozkład cząstek jest lepszy, ponieważ ma mniejszy narzut komunikacyjny niż rozkład domen.

Czy masz jakieś przemyślenia?

Dekompozycja cząstek i domen jest bezpośrednio połączona z dwiema głównymi metodami przyspieszenia obliczeń siły dla systemów z oddziaływaniami o ograniczonym zakresie - listami sąsiadów Verleta i listami powiązanymi z komórkami. Jeśli chcesz wniknąć w szczegóły, istnieje całkiem niezła książka Allena i Tildesleya, zatytułowana Komputerowa symulacja cieczy , uważana przez wielu za „biblię” badań nad dynamiką molekularną i Monte Carlo. Następnie jest Symulacja numeryczna w dynamice molekularnej Griebla, Knapka i Zumbuscha, która zagłębia się w różne techniki równoległej implementacji MD.

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

$O(N)$$O(N)$ $N$skaluje się lepiej. Stąd argument wielkości liniowej. Metoda dekompozycji domen jest prostym rozszerzeniem metody list połączonych z komórkami - komórki są dzielone między różne procesory.

Problem z dekompozycją domen polega na tym, że musi się komunikować, gdy cząsteczki przemieszczają się z jednej komórki do drugiej, którą zajmuje się inny procesor. Może to stać się problematyczne w wyższych temperaturach symulacji, w których cząstki mają tendencję do odsuwania się dalej niż ich położenie równowagi lub gdy występuje przepływ cząstek. Również informacje z komórek na granicy domeny muszą być przekazywane przy każdej iteracji do sąsiednich domen. Ale wszystko to jest lokalnie synchroniczną komunikacją i można to zrobić bardzo skutecznie.

Replikowane dane są najłatwiejszym podejściem, ale niestety wymagają, aby na każdym etapie wszystkie informacje o pozycji i prędkości były synchronizowane globalnie. To naprawdę nie skaluje się dobrze, a dla bardzo dużego systemu globalną ilością pamięci jest rozmiar struktury danych pomnożony przez liczbę używanych procesorów, podczas gdy jednym z celów przetwarzania równoległego jest dystrybucja danych, tak aby każdy procesor mieścił mniej niż globalna ilość danych.

Podsumowując, nie istnieje metoda „jeden rozmiar dla wszystkich”, odpowiednia dla wszystkich symulowanych systemów. W większości przypadków najlepszą strategię paralelizacji można wywnioskować z geometrii systemu i wybrać odpowiedni kod MD - wszystkie implementują mniej więcej te same podstawowe pola sił i integratory.

„Rozkład domen jest lepszym wyborem tylko wtedy, gdy rozmiar układu liniowego znacznie przekracza zakres interakcji, co rzadko zdarza się w dynamice molekularnej”, autorzy tego (bardzo starego) artykułu GROMACS oznaczają, że jeśli rozmiar przestrzenny listy sąsiadów wynosi rzędu 1 nm, a komórka symulacyjna ma tylko kilka nanometrów, wówczas narzut spowodowany rozkładem domen jest zbyt wysoki. Równie dobrze możesz zaakceptować całościową dystrybucję informacji przy rozkładzie cząstek i nie musisz poświęcać czasu na całą księgowość dotyczącą rozkładu domen.

Problem z rozkładem cząstek w miarę wdrażania GROMACS polegał na tym, że z czasem cząstki przypisane do każdego procesora dyfundują w przestrzeni. Ponieważ odpowiedzialność za obliczanie każdej interakcji ustalono na podstawie ich początkowej lokalizacji, rozproszenie stopniowo zwiększało objętość całkowitej przestrzeni, którą każdy procesor musiał znać, aby zbudować swoją listę sąsiadów, nawet jeśli całkowite obliczenia opisane przez listę sąsiadów były stałe. W praktyce okresowo uruchamiasz ponownie symulację, aby zresetować dane i lokalizację komunikacji.

Twoje przypuszczenie, że „rozkład cząstek ma tę zaletę, że nie ma do czynienia z cząstkami poruszającymi się przez granice domen” nie ma zastosowania, jeśli dyfuzja jest znacząca w skali czasowej symulacji.

Dekompozycja domen radzi sobie z tym „z góry”, migrując odpowiedzialność za interakcję wraz z rozpowszechnianiem, poprawiając w ten sposób lokalizację danych na każdym procesorze i minimalizując objętość komunikacji.

Oświadczenie: Pomagam opracować GROMACS i prawdopodobnie wyrwę implementację rozkładu cząstek w przyszłym tygodniu ;-)

Chciałbym dodać do odpowiedzi Hristo Ilieva. Podczas gdy jego post mówi głównie o złożoności obliczeniowej , jeśli chodzi o równoległość, złożoność komunikacji jest co najmniej tak samo ważna - i że jest to główny powód dekompozycji domen.

Nowoczesne równoległe maszyny mają zwykle pewną topologię torusa. Oznacza to, że każdy procesor ma kilka „sąsiadujących” procesorów, z którymi może komunikować się bardzo szybko. Komunikacja z procesorem, który nie jest sąsiadem, jest bardziej kosztowna. Dlatego zawsze korzystne jest posiadanie algorytmu, który musi komunikować się tylko z sąsiednimi procesorami.

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

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

$\mathcal{O}(P)$

Należy jednak pamiętać, że niejednorodne systemy nie są tak powszechne, jak może się wydawać, występują tylko podczas symulacji czegoś w próżni lub przy użyciu ukrytego rozpuszczalnika. Gęstość kryształów i cieczy jest wystarczająco bliska, aby uruchomić rozkład domen.