Przykłady obliczeń PDE z wykorzystaniem równoległości w przestrzeni i czasie

14

W numerycznym rozwiązaniu początkowych wartości granicznych PDE bardzo często stosuje się równoległość w przestrzeni . O wiele rzadziej stosuje się jakąś formę paralelizmu w dyskretyzacji czasu , a paralelizm ten jest zwykle znacznie bardziej ograniczony. Jestem świadomy rosnącej liczby kodów i opublikowanych prac wykazujących równoległość czasową, ale żaden z nich nie obejmuje równoległości przestrzennej.

Czy istnieją przykłady implementacji, które obejmują równoległość zarówno w przestrzeni, jak i czasie? Interesują mnie zarówno publikacje, jak i dostępne kody.

David Ketcheson
źródło
Właśnie znalazłem ten przedruk, łączący Parareal z dekompozycją domen przestrzennych dla nieściśliwego Naviera-Stokesa na procesorach 2048: icsweb.inf.unisi.ch/preprints/preprints/file201203.pdf
David Ketcheson

Odpowiedzi:

8

The PFASST (Parallel Full Schemat Zbliżanie w czasie i przestrzeni) oraz PEPC (Całkiem Sprawne Coulomba równoległe) algorytmy zostały niedawno używane razem, aby osiągnąć równoległość w czasie i przestrzeni.

PFASST wykonuje paralelizm czasowy, PEPC wykonuje paralelizm kosmiczny. Wyniki tego zostały niedawno zaprezentowane w konferencji DD21 , a my przygotowaliśmy zgłoszenie do SC12 opisujące połączenie PFASST + PEPC.

Wykazano, że „mały” problem składający się z 4 milionów cząstek (PEPC jest równoległym solwerem N-ciała) pozwala na skalowanie do 8192 rdzeni na JUGENE przy użyciu tylko PEPC (tj. Tylko równolegle w przestrzeni). Poza tym koszty komunikacji stały się znaczne, a wydajność równoległa zaczęła się obniżać. Dodanie PFASST pozwala na uruchomienie tego problemu o stałej wielkości na 262 144 rdzeniach (tzn. Wypełniliśmy JUGENE) przy użyciu 32 procesorów „czasowych” (z których każdy składa się z 8192 „przestrzennych” rdzeni).

Chociaż wydajność równoległa algorytmów równoległych czasowo nie jest 100%, byliśmy w stanie uzyskać przyspieszenie około 6,5x przy użyciu 32 procesorów PFASST z tą konfiguracją PFASST + PEPC.

Oto link do przedruku: masywny czasoprzestrzenny solver N-body

Matthew Emmett
źródło
To brzmi całkiem nieźle, zaktualizuj link do wersji roboczej, kiedy będziesz gotowy.
Aron Ahmadia
Świetnie, właśnie tego szukałem. A tak przy okazji, fajna robota.
David Ketcheson
Dzięki! Postaram się wkrótce opublikować link. BTW, z powodzeniem wykorzystałem również PETSc DA do dystrybucji domeny przestrzennej solvera płytkiej wody wewnątrz PyPFASST.
Matthew Emmett
1
@AronAhmadia, dodano link do przedruku!
Matthew Emmett
4

Istnieją również metody czasoprzestrzenne DG i ciągłe metody Galerkina. Po wybraniu kwadratury DG czasoprzestrzenna z siatką strukturalną w kierunku czasu jest równoważna niejawnej metodzie Runge-Kutty. Metoda DG czasoprzestrzenna pozwala jednak na różne rozmiary kroków w różnych częściach domeny, co jest trudne do analizy pod kątem niejawnych metod RK. W tym kontekście można również zastosować metody wielosiatkowe czasoprzestrzenne.

Jed Brown
źródło
Nie rozumiem, jak to jest równoległe w czasie. Czy możesz wskazać przykład lub wyjaśnić więcej?
David Ketcheson
Gdy powiększysz domenę, możesz rozłożyć się na więcej domen o danym rozmiarze. Metody czasoprzestrzenne dodają wymiar czasowy do dziedziny, zwiększając w ten sposób równoległość. Zauważ, że robienie kilku powiązanych rzeczy na raz ma ogromne zalety obliczeniowe, więc w celu uzyskania maksymalnej wydajności przy płytach czasowych o niewielkich rozmiarach nadal możesz rozkładać się tylko w przestrzeni i lokalnie wektoryzować w wymiarze czasu.
Jed Brown
2

Po rozważeniu równoległości czasoprzestrzeni poddomena jest czasoprzestrzenią na wielu poziomach czasu. Metoda zwana relaksacją kształtu fali wykorzystuje subdomeny czasoprzestrzenne, ale równolegle tylko w przestrzeni (bez podziału w wymiarze czasowym). Tak więc kartezjański podział na przestrzeń i podział na czas daje rodzaj równoległości czasoprzestrzennej. Artykuł o takiej kartezjańskiej metodzie można znaleźć tutaj . Jak wspomniał Jed Brown w swojej odpowiedzi, metoda czasoprzestrzenna zapewnia nie tylko bardziej elastyczny paralelizm, ale także adaptację do dyskretyzacji. W drugim temacie możesz wyszukiwać prace Schwab w Google, zobacz także ich projekt . Prace wykorzystujące równoległość i adaptację można obejrzeć na stronie głównej R. Haynesa .

Hui Zhang
źródło
1

Przyjrzyj się algorytmowi Parareal i związanej z nim pracy, takiej jak odroczona korekcja spektralna (prosta wyszukiwarka Google pokazuje całkiem sporo materiału). Podstawową ideą jest użycie zgrubnej „siatki” w czasie i zrobienie kroku z grubsza, ale następnie cofnięcie się i wykonanie poprawek w dokładniejszej skali czasowej. Wydaje się, że jest stosowany głównie w symulacjach płynów, ale jestem w obszarze elektromagnetyki, więc nie mogę tak naprawdę nic więcej na ten temat powiedzieć. Jedyny powód, jaki o tym wiem, to to, że uczestniczyłem w seminarium na temat podejścia do odroczonej korekty i wydawało się bardzo interesujące, że jakakolwiek paralelizacja może być wykonana na czas.

Victor Liu
źródło
Znam je, ale czy możesz wskazać przypadek, w którym są one stosowane w połączeniu z równoległością przestrzenną?
David Ketcheson
Dla jasności, odroczone lub wady schematy korekty same w sobie nie mają nic wspólnego ze schematami Parareal i / lub równoległymi w czasie.
Matthew Emmett
1

Metoda wielokrotnego fotografowania stosowana w optymalnej kontroli została zaprojektowana w taki sposób, aby pod-problemy w każdym interwale fotografowania mogły być rozwiązywane równolegle. Nie znam artykułów, które łączą to z równoległością przestrzenną (nie ma zbyt wielu optymalnych problemów sterowania, które zostały rozwiązane w przeszłości, gdzie równanie jest zależnym od czasu PDE przestrzennym), ale byłoby oczywiste, jak zrobić równoległość w zarówno przestrzeń, jak i czas.

Wolfgang Bangerth
źródło