A Parallel-in-Time Combination Method for Parabolic Problems

1. Probleemstelling

Het artikel behandelt de numerieke benadering van parabolische partiële differentiaalvergelijkingen (PDE's) in hoge ruimtelijke dimensies ($d$), specifiek tot $d=6$. Deze vergelijkingen komen voor in diverse gebieden, waaronder statistische mechanica, chemische kinetiek (Chemical Master Equation), neurowetenschappen en financiële wiskunde (Fokker-Planck-vergelijkingen).

Belangrijkste Uitdagingen:

• Vervlochtenheid van Dimensies (Curse of Dimensionality): Standaard discretisaties op uniforme roosters vereisen $O(2^{dL})$ vrijheidsgraden, waardoor ze computationeel onuitvoerbaar worden voor $d > 3$.
• Sequentiële Tijdstappen: Traditionele methoden (zoals de Rothe-methode) lossen elliptische deelvragen sequentieel in de tijd op. Dit beperkt parallelisatie tot de ruimtelijke dimensies alleen, wat leidt tot lange looptijden bij hoge nauwkeurigheidsvereisten.
• Schaalbaarheid: Bestaande parallelle oplossers schalen vaak niet efficiënt op moderne exascale-systemen omdat ze geen gebruik maken van parallelisme in de tijdsdimensie of de specifieke lastverdelingsproblemen van hoge-dimensionale dunne roosters niet aanpakken.

2. Methodologie

De auteurs stellen een drie-niveau geneste parallelisatiestrategie voor die drie verschillende numerieke technieken combineert:

A. Ruimtelijke Discretisatie: Sparse Grid Combination Method

Om de vervlochtenheid van dimensies te overwinnen, vervangen de auteurs uniforme roosters door een Sparse Grid Combination Method.

• Mechanisme: In plaats van één massaal probleem op een uniform rooster op te lossen, decomponeert de methode het probleem in een set onafhankelijke deelvragen op anisotrope roosters ($\Omega_l$).
• Combinatie: De uiteindelijke oplossing wordt verkregen door een lineaire combinatie van deze deeloplossingen met afwisselende tekens (inclusie-exclusie principe).
• Voordeel: De kosten schalen als $O(L^{d-1} 2^L)$ in plaats van $O(2^{dL})$, wat effectief oplossingen toestaat voor dimensies tot $d=6$.
• Parallelisme Niveau 1: Alle deelvragen op verschillende anisotrope roosters kunnen volledig parallel worden opgelost.

B. Tijdsparallelisatie: Multigrid Reduction-in-Time (MGRIT)

Om de sequentiële afhankelijkheid van tijdstappen te doorbreken, maken de auteurs gebruik van MGRIT (geïmplementeerd via de XBraid-bibliotheek).

• Mechanisme: MGRIT gebruikt een multigrid-aanpak in het tijdsdomein, waarbij het tijdsrooster wordt vergruisd en "F-relaxatie" (fijnrooster-propagatie) en "C-relaxatie" (grofrooster-correctie) worden gebruikt om het tijdstap-probleem parallel op te lossen.
• Integratie: MGRIT wordt toegepast op elk deelvraag van de combinatiemethode individueel. Dit zorgt voor fijnmazige controle over tijdstappen voor elk deelvraag.
• Parallelisme Niveau 2: Tijdstappen binnen elk deelvraag worden parallel opgelost over meerdere processen.

C. Oplosser voor Deelvragen: Domeindecompositie (DD)

Voor de lineaire systemen die in elk deelvraag bij elke tijdstap ontstaan, wordt een Domeindecompositiemethode gebaseerd op Ruimtevullende Curven (Hilbert-curve) gebruikt.

• Mechanisme: Het ruimtelijke domein van elk anisotroop subrooster wordt gepartitioneerd in overlappende subdomeinen met behulp van een Hilbert-curve. Een tweeniveau-preconditioner (Additief of Gebalanceerd) wordt geconstrueerd met behulp van deze subdomeinen en een grofroosterprobleem.
• Parallelisme Niveau 3: De oplossing van het lineaire systeem voor een enkel deelvraag wordt via domeindecompositie verdeeld over processen.

Het Resultante Algorithmus (CTMGRIT$_{loc}$):
De voorgestelde methode, CTMGRIT$_{loc}$, voert de volgende lus uit:

1. Recombinatiestappen: Het tijdsinterval wordt verdeeld in $s$ recombinatiestappen.
2. Parallelle Deelvragen: Voor elk recombinatie-interval worden alle sparse grid-deelvragen gelijktijdig opgelost.
3. Parallelle Tijd: Binnen elk deelvraag lost MGRIT de tijdsontwikkeling parallel op.
4. Parallelle Ruimte: Binnen elke MGRIT-stap wordt het ruimtelijke elliptische probleem parallel opgelost via Domeindecompositie.
5. Combinatie: Oplossingen worden geprojecteerd, gecombineerd en gerecombineerd aan het einde van elk interval.

3. Belangrijkste Bijdragen

• Drie-Niveau Geneste Parallelisme: Het artikel presenteert een oplosser die gelijktijdig parallelisme in ruimte (deelvragen), tijd (MGRIT) en subdomein (DD) benut. Dit maakt efficiënt gebruik van duizenden kernen mogelijk.
• Omgaan met Hoge Dimensies: Door sparse grids te combineren met parallel-in-time, lost de methode succesvol parabolische problemen op in tot 6 ruimtelijke dimensies, een regime waar traditionele methoden falen.
• Flexibele Wachtrij voor Deelvragen: In tegenstelling tot globale MGRIT-benaderingen, maakt het toepassen van MGRIT op individuele deelvragen onafhankelijke tijdstappen per deelvraag mogelijk en het gebruik van job-schedulers (bijv. SLURM) om onafhankelijke compute-taken te beheren, wat de resourcebenutting op heterogene clusters verbetert.
• Communicatiepatronen: De auteurs analyseren communicatiekosten en merken op dat hoewel combinatiestappen globale communicatie vereisen, het zware werk (MGRIT en DD) grotendeels lokaal is voor deelvragen of subdomeinen, wat knelpunten minimaliseert.

4. Numerieke Resultaten

De methode is getest op een high-performance cluster (Yuma, 45 nodes, 2880 kernen) met drie testcases:

1. Warmtevergelijking (Dimensies 2–6):

   • Toonde optimale zwakke schaalbaarheid en bijna-optimale sterke schaalbaarheid.
   • Het iteratieaantal voor MGRIT bleef stabiel, ongeacht dimensie of roosterniveau.
   • Looptijden werden gedomineerd door de ruimtelijke solver, die zijn uitstekende schaalbaarheid erfde.

2. Chemical Master Equation (Genetische Toggle Switch):

   • 2D en 3D Bistabiele/Tristabiele Systemen: De methode loste de evolutie van de waarschijnlijkheidsdichtheidsfunctie (PDF) op.
   • Vergelijking met SSA: In vergelijking met het Stochastic Simulation Algorithm (SSA/Gillespie) produceerde CTMGRIT gladde PDF's zonder de statistische ruis (sprongen) die inherent is aan deeltjesgebaseerde methoden. Hoewel SSA sneller was voor een vast aantal trajecten, biedt de deterministische aard van CTMGRIT hogere nauwkeurigheid voor stationaire verdelingen zonder dat enorme bemonstering nodig is.

3. Stochastische Differentiaalvergelijkingen (Fokker-Planck):

   • 2D Lineaire Oscillator & 4D Lineair Systeem:
   • CTMGRIT$_{loc}$ presteerde aanzienlijk beter dan zowel sequentiële tijdstappen op volledige roosters als naïef MGRIT op volledige roosters.
   • Het behaalde de laagste fout en snellste looptijd onder de geteste schema's, wat aantoont dat de combinatie van sparse grids en parallel-in-time superieur is aan het opschalen van volledige roostermethoden.

5. Betekenis

Dit werk vertegenwoordigt een aanzienlijke vooruitgang in High-Performance Computing (HPC) voor PDE's:

• Klaar voor Exascale: De architectuur is perfect geschikt voor moderne exascale-systemen, waarbij gebruik wordt gemaakt van enorme aantallen kernen zonder geblokkeerd te worden door sequentiële tijdstappen of de vervlochtenheid van dimensies.
• Brug tussen Deterministisch en Stochastisch: Het biedt een deterministisch alternatief voor stochastische simulatie voor de evolutie van waarschijnlijkheidsdichtheden in hoge dimensies, en levert gladde oplossingen waar Monte Carlo-methode worstelen met convergentie.
• Schaalbaarheid: Het bewijst dat "embarrassingly parallel" ruimtelijke deelvragen effectief kunnen worden gekoppeld aan parallel-in-time-oplossers om problemen op te lossen die eerder als onoplosbaar werden beschouwd in dimensies $d > 3$.

Concluderend stelt het artikel een robuust raamwerk vast voor het oplossen van hoge-dimensionale parabolische problemen door synergistisch sparse grid-discretisatie, parallel-in-time-integratie en domeindecompositie te combineren, waarbij uitstekende snelheidsverhoging en schaalvergrotings eigenschappen worden bereikt.