Czy nieciągły Galerkin jest naprawdę bardziej zrównoleglalny niż ciągły Galerkin?

Zawsze słyszałem, że łatwa równoległość była jedną z zalet metod DG, ale tak naprawdę nie rozumiem, dlaczego którykolwiek z tych powodów nie dotyczy również ciągłego Galerkina.

Jednym z powodów, dla których metody DG mogą otrzymać większą uwagę jako metoda równoległa, jest to, że łatwo można zauważyć, że metoda ta jest z natury lokalna dla elementu. Sprzężenie w metodach DG jest słabe, ponieważ występuje tylko przez sąsiednie krawędzie (lub ściany w 3D). Tak więc w przypadku trójkątów lub quadów DG komunikuje się odpowiednio z trzema lub czterema procesorami. Podczas gdy metody CG będą obejmować narożniki elementu, w ten sposób wartościowość narożnika elementu staje się ważna. W zależności od zastosowanego generatora siatki, ta wartościowość może wynosić osiem procesorów (być może wyższa). Zatem koszt złożenia pochodnej czasu można uznać za „wyższy” dla metod CG. Jest to szczególnie ważne w przypadku metod spektralnych, w których objętość przekazywanej informacji może być dość duża (a ukrywanie opóźnień może stać się trudniejsze, ponieważ zmniejsza się rozmiar każdej partycji).

Ale ten dodatkowy koszt montażu przez CG jego pochodnej czasu może zostać zrekompensowany przez inną strategię równoważenia obciążenia. Różne strategie partycjonowania siatki (jestem najbardziej zaznajomiony z METIS) pozwalają użytkownikowi zrównoważyć obciążenie za pomocą różnych metryk, np. Upewnienie się, że każdy partitiom ma w przybliżeniu taką samą liczbę elementów lub ograniczenie komunikacji między partycjami. Wydaje mi się, że powodem, dla którego DG łatwo jest zrównoleglać, jest to, że naiwny podział problemu na równe części może zapewnić bardzo wydajną równoległą implementację, nawet w niektórych przypadkach prezentując superliniowe przyspieszenie z powodu efektów pamięci podręcznej (patrz na przykład Baggag i in. . lub Altmann i. in.). Podczas gdy CG może wymagać bardziej sprytnej metody partycjonowania. Może się zdarzyć, że zmiana dyskretyzacji przestrzennych z DG na CG, powiedzmy, wymagałaby również ponownego przemyślenia, jak podzielić siatkę na podproblemy.

Po wielu latach pisania oprogramowania MES uważam, że stwierdzenie, że schematy DG lepiej nadają się do paralelizacji niż schematy CG, jest apokryficzne. Jest często wykorzystywany we wstępach do dokumentów DG jako uzasadnienie metod DG, ale nigdy nie widziałem tego uzasadnionego odniesieniem, które faktycznie badało to pytanie. Jest podobny do każdej propozycji NSF dotyczącej projektu teorii liczb odnoszącej się do „kryptografii” jako obszaru o szerszym wpływie, stwierdzenia, że ​​w tej ogólności również nigdy nie ma uzasadnienia.

W rzeczywistości uważam, że z jednym wyjątkiem wyraźnych schematów krokowych i, być może, problemów, w których trzeba odwrócić macierz mas, schematy DG nie są lepsze ani gorsze niż schematy CG, jeśli zbadano by koszty komunikacji związane z którymkolwiek z nich. Mam na myśli to w sensie praktycznym: pewnie może być konieczne przesłanie mniejszej ilości danych, ale wyobrażam sobie, że różnica w czasie pracy zegara ściennego byłaby nieistotna dla wszystkich innych programów operacyjnych, które wykonują te dane.

Oczywiście byłbym zachwycony, gdyby ktoś podjął wyzwanie, by udowodnić, że się mylę!

Tak jak w przypadku większości ogólnych stwierdzeń dotyczących schematów numerycznych, odpowiedź zależy od dokładnych okoliczności, na które patrzysz. Przede wszystkim korzyści DG w zakresie paralelizacji opłaciły się głównie w przypadku wyraźnych systemów integracji czasowej z powodu

• Lokalna macierz masy macierzy schematów DG (więc nie trzeba globalnie stosować odwrotności macierzy masy)
• Korzystny stosunek pracy lokalnej CPU (całki woluminów) do pracy związanej z komunikacją (całki brzegowe), szczególnie przy wyższych zamówieniach

Chociaż te stwierdzenia dotyczą ogólnych dyskretyzacji DG, rzeczywiste aplikacje HPC (powiedzmy, wykorzystujące kilka tysięcy procesorów) wymagają nieco więcej wysiłku w zakresie strategii równoległości w celu utrzymania dobrego skalowania. W tym artykule pokazano na przykład, w jaki sposób można osiągnąć niemal idealne skalowanie do jednej komórki na procesor . Jest to z pewnością coś, czego nie można oczekiwać od ciągłego MES, ale jak wspomniano wcześniej, ukryte schematy są zupełnie inne.

Podczas montażu macierzy sztywności dane przechowywane w elemencie w ciągłym (węzłowym) MES muszą być przekazywane wszystkim jego węzłowym sąsiadom. W przeciwieństwie do tego, DGFEM wymaga, aby dane elementu były przekazywane wszystkim sąsiednim twarzom. W 1D sąsiedzi węzłowi i twarzowi są identyczni, ale w 3D różnica może być dość duża: w przypadku regularnej siatki sześciościennej istnieje 26 węzłów węzłowych, ale tylko 6 sąsiadów twarzy. W przypadku nieregularnych siatek z wieloma wierzchołkami o wysokiej wartościowości sytuacja jest gorsza dla CG, podczas gdy pozostaje taka sama dla DG.

DG dla hiperbolicznego PDE może być stosowany jako zamiennik schematów skończonej objętości. W skończonej objętości jak w skończonej różnicy, kiedy zwiększasz kolejność schematu, twój szablon wzrasta. Utrudnia to równoległość, ponieważ dla każdego zamówienia schematu masz inny szablon. Na granicach partycji należy upewnić się, że wszystkie wymagane komórki z partycji sąsiedniej dla określonej kolejności schematu są dostępne. Ale w DG, bez względu na kolejność schematu, każda komórka komunikuje się tylko z sąsiadami twarzy. Tak więc w porównaniu między skończoną objętością / różnicą a DG, można powiedzieć, że DG łatwiej jest zrównoleglić.