Jaki jest stan techniki w równoległych metodach ODE?

39

Obecnie szukam równoległych metod integracji ODE. Istnieje wiele nowej i starej literatury opisującej szeroki wachlarz podejść, ale nie znalazłem żadnych ostatnich badań ani artykułów przeglądowych opisujących ogólnie ten temat.

Jest książka Burrage [1], ale ma ona prawie 20 lat i dlatego nie obejmuje wielu bardziej nowoczesnych pomysłów, takich jak algorytm pomocniczy.

[1] K. Burrage, równoległe i sekwencyjne metody dla równań różniczkowych zwyczajnych, Clarendon Press, Oxford, 1995

parallel-computing ode numerical-analysis

— Florian Brucker
źródło

35

Nie znam żadnych ostatnich artykułów przeglądowych, ale jestem aktywnie zaangażowany w rozwój algorytmu PFASST, więc mogę podzielić się przemyśleniami.

Istnieją trzy szerokie klasy technik równoległych w czasie, o których wiem:

w całej metodzie - niezależne etapy RK lub integratorów ekstrapolacji mogą być oceniane równolegle; patrz także RIDC (rewizjonistyczny zintegrowany algorytm odroczonej korekty)
przez problem - relaksacja kształtu fali
w dziedzinie czasu - Parareal; PITA (algorytm równoległy w czasie); i PFASST (równoległy pełny schemat aproksymacji w przestrzeni i czasie).

Metody równoległe w całej metodzie zwykle działają bardzo blisko specyfikacji, ale nie skalują się poza garść procesorów (czasowych). Zazwyczaj są one stosunkowo łatwiejsze do wdrożenia niż inne metody i są dobre, jeśli masz kilka dodatkowych rdzeni i szukasz przewidywalnych i skromnych przyspieszeń.

Metody równoległe w dziedzinie czasu obejmują Parareal, PITA, PFASST. Wszystkie te metody są iteracyjne i składają się z niedrogich (ale niedokładnych) „grubych” propagatorów i drogich (ale dokładnych) „drobnych” propagatorów. Osiągają wydajność równoległą poprzez iteracyjną ocenę równoległego drobnego propagatora w celu ulepszenia rozwiązania szeregowego uzyskanego przy użyciu grubego propagatora.

$E$ $E < 1/K$ $K$

Wiele gier można odtwarzać przy użyciu wszystkich tych metod, aby spróbować je przyspieszyć, i wydaje się, że wydajność tych technik w całej domenie zależy od tego, jaki problem rozwiązujesz i jakie techniki są dostępne, aby przyspieszyć zgrubienie propagator (zgrubne siatki, zgrubne operatory, zgrubna fizyka itp.).

Niektóre referencje (patrz także referencje wymienione w artykułach):

W tym artykule pokazano, w jaki sposób można sparaliżować różne metody: Teoretyczne porównanie jawnych metod Runge-Kutty wyższego rzędu, ekstrapolacji i metod odroczonej korekty ; Ketcheson i Waheed.
W tym artykule pokazano także przyjemny sposób równoległego łączenia metod i przedstawiono algorytm RIDC: Równoległe integratory wysokiego rzędu ; Christlieb, MacDonald, Ong.
W artykule przedstawiono algorytm PITA: niejawna metoda czasowo-równoległa przyspieszająca rozwiązanie problemów nieliniowej dynamiki strukturalnej ; Cortial i Farhat.
Na Parareal jest wiele artykułów (tylko Google it).
Oto artykuł na temat metody Nievergelt: Minimalne podejście komunikacyjne do całkowania w czasie równoległym ; Szczekacz.
W pracy przedstawiono PFASST: W kierunku wydajnej metody równoległej w czasie dla równań różniczkowych cząstkowych ; Emmett i stronnik;
W tym artykule opisano zgrabne zastosowanie PFASST: masywnie czasoprzestrzennego solwera N-ciała ; Speck, Ruprecht, Krause, Emmett, Minion, Windel, Gibbon.

Napisałem dwie implementacje PFASST, które są dostępne w sieci: PyPFASST i libpfasst .

— Matthew Emmett
źródło

1

Obecnie uczę się parareal. I myślę, że to mi bardzo pomaga.

— eccstartup

To świetny przegląd. Należy jednak wyraźnie wspomnieć, że ODE często rozwiązuje się po przestrzennej dyskretyzacji PDE. Dlatego równoległość w całej metodzie może zapewnić wielką skalowalność tysiącom rdzeni, jeśli domena przestrzenna jest wystarczająco duża. Wynika to z faktu, że zdecydowana większość czasów obliczeniowych przechodzi na obliczenia, na przykład, oceny RHS na etapie RK.

— NoseKnowsAll

15

Chociaż ten post ma teraz dwa lata, na wypadek, gdyby ktoś się na nim natknął, dam krótką aktualizację:

Martin Gander napisał ostatnio fajny artykuł przeglądowy, który przedstawia historyczną perspektywę w tej dziedzinie i omawia wiele różnych metod PINT: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

Jest teraz także strona społeczności, która zawiera bardzo wiele referencji i zawiera opisy różnych metod: http://www.parallel-in-time.org/

Omówienie algorytmu Parareal równolegle w czasie można znaleźć tutaj: https://en.wikipedia.org/wiki/Parareal

— Daniel
źródło

1

Trochę zaskoczony, że Gander nie mówi o podejściu MGRIT autorstwa Falgouta i wsp., Zwłaszcza, że wygląda na to, że wspiera je ładne oprogramowanie (XBraid), ale wiem, że dokumenty MGRIT pojawiły się dopiero niedawno.

— Geoff Oxberry

1

Cześć Geoff, jestem całkiem pewien, że Martin Gander napisał artykuł przed opublikowaniem artykułów MGRIT - podczas gdy artykuł recenzowany ukaże się w 2015 roku, myślę, że preprint ukazał się już pod koniec 2013 roku.

— Daniel

1

Na pierwszy rzut oka wygląda na to, że w tym przeglądzie pominięto „równoległe stosowanie metody” - na przykład nigdy nie wspomniano o ekstrapolacji.

— David Ketcheson

4

$u_0$ $u(t)=\exp(-\lambda t)u_0,$ $\mathrm{Re}\,\lambda>0.$

— Hui Zhang
źródło

Jak już powiedziałem, znalazłem już wiele artykułów na poszczególne tematy. Brakuje mi ogólnego przeglądu podejść.

— Florian Brucker,

1

FWIW, algorytm PFASST wykazuje bardzo dobrą zbieżność (wkrótce zostanie opublikowana) dla systemów Hamiltonian nawet dla wielu (setek) procesorów czasu. Powiedziawszy to, uzyskanie znacznego przyspieszenia zależy (po raz kolejny) od uczynienia grubszych propagatorów znacznie tańszymi niż drobny propagator - rozszerzenie wieloliniowe lub inne podejście wielofizyczne wydaje się konieczne, aby uzyskać dobre przyspieszenie dla układów cząstek.

— Matthew Emmett,