Parallelizing SIR Epidemic Spread Simulation Using Pthreads, OpenMP, and MPI

Technische Samenvatting: Parallellisatie van een SIR-epidemie-verspreidingssimulatie met behulp van Pthreads, OpenMP en MPI

Probleemstelling
De simulatie van epidemische verspreiding met behulp van het Susceptible–Infected–Recovered (SIR) cellulaire automaatmodel is een computationeel intensieve taak die cruciaal is voor het publieke gezondheidsbeleid en de voorbereiding op pandemieën. In zijn ruimtelijke roosterformaat simuleert het model de ziekteverspreiding over een twee-dimensionale populatie waarbij infectie zich verspreidt naar aangrenzende buren. Simulaties op nationale schaal (bijv. $N=10.000$ die $1 \text{ km}^2$ regio's vertegenwoordigen over $T=365$ tijdstappen) vereisen ongeveer 36 miljard cel-updates, wat zonder high-performance parallel rekenen computationeel onhaalbaar is. De kernuitdaging die wordt aangepakt, is de efficiënte parallellisatie van deze "stencil-berekening", waarbij de staat van elke cel uitsluitend afhangt van zijn directe buren, wat binnen elk tijdstap een "embarrassingly parallel" workload creëert, maar synchronisatie vereist bij de grenzen.

Methodologie
De studie implementeert en vergelijkt drie verschillende parallelle programmeerparadigma's tegenover een sequentiële baseline op een twee-dimensionaal $N \times N$ rooster:

1. Sequentiële Baseline: Een referentie-implementatie met ping-pong buffers (twee $N \times N$ roosters) met een $O(N^2 \cdot T)$ tijdscomplexiteit. De update-regel iterereert door cellen en past probabilistische transities toe op basis van het deel geïnfecteerde buren ($\beta$) en herstelpercentages ($\gamma$).
2. Pthreads (POSIX Threads): Het rooster wordt gedecomposeerd in $P$ horizontale stroken, waarbij elke thread een specifieke set rijen bezit. Synchronisatie wordt beheerd via pthread_barrier_t om te garanderen dat alle threads een tijdstap voltooien voordat de bufferwissel plaatsvindt. De implementatie benadrukt het risico op "false sharing" op de randrijen waar aangrenzende threads naar dezelfde cachelijnen lezen/schrijven, ondanks het gebruik van aparte buffers.
3. OpenMP: Maakt gebruik van een enkele #pragma omp parallel for directive met statische scheduling om de buitenste rij-loop te partitioneren. Deze aanpak vertrouwt op impliciete barriers voor synchronisatie en maakt gebruik van per-thread willekeurige zaadwaarden (rand_r) om data races te voorkomen. Het biedt automatische decompositie met minimale handmatige interventie.
4. MPI (Message Passing Interface): Ontworpen voor gedistribueerd geheugen, waarbij het root-proces het rooster genereert en $N/P$ rijen verspreidt naar worker-processen. Elk proces alloceert "ghost" of "halo" rijen om buurcommunicatie te faciliteren. Een MPI_Sendrecv patroon handelt halo-exchanges af voor elke tijdstap, en MPI_Reduce aggregeert globale statistieken. Deze methode beheert expliciet de communicatie-overhead versus de berekening.

Belangrijkste Bijdragen
Het artikel levert vier primaire bijdragen:

1. Een geverifieerde sequentiële SIR-implementatie die dient als correctheid-referentie.
2. Drie verschillende parallelle implementaties (Pthreads, OpenMP, MPI) die zijn afgestemd op het SIR stencil-probleem.
3. Een systematische prestatieanalyse inclusief strong scaling-metingen voor variërende roostergroottes ($N=500, 1000$) en het aantal processen/threads ($P=1$ tot $8$).
4. Een vergelijkende discussie over bottlenecks, programmeercomplexiteit en de trade-offs tussen shared-memory (Pthreads/OpenMP) en distributed-memory (MPI) modellen.

Experimentele Resultaten
Experimenten werden uitgevoerd op een quad-core machine (Apple M-series/Intel Core i5) met $N=1000$ en $T=100$. De runtime van de sequentiële baseline was 1,576 seconden.

• MPI Prestaties: Bereikte de hoogste versnelling van 6,35× bij $P=8$ processen, met een efficiëntie van 79%. Het vertoonde bijna lineaire schaling voor grote roosters, aangezien het communicatievolume (halo-exchange van ~8 KB per stap) verwaarloosbaar bleef vergeleken met de $O(N^2/P)$ berekening.
• OpenMP Prestaties: Leverde een versnelling van 2,25× bij $P=4$ threads. Hoewel efficiënt, was de schaling matig vanwege de overhead van impliciete barriers aan het einde van elke parallelle loop, die dominant wordt ten opzichte van de berekening bij kleinere probleemomvang.
• Pthreads Prestaties: Bereikte een versnelling van 2,12× bij $P=4$ threads. De schaling werd beperkt door false sharing op de randrijen en de overhead van expliciete barrier-synchronisatie, wat resulteerde in een bijna vlakke schaling naarmate het aantal threads toenam.

Opvallend genoeg vertoonden de Pthreads- en OpenMP-implementaties met $P=1$ runtimes die iets sneller waren dan de sequentiële baseline door compiler-optimalisaties (-O3) die werden toegepast tijdens de parallelle build, hoewel de echte parallelle winsten werden waargenomen bij hogere $P$.

Betekenis en Claims
Het artikel claimt dat de keuze van het parallelle paradigma een significante impact heeft op de prestaties en schaalbaarheid van epidemie-simulaties.

• MPI wordt geïdentificeerd als de superieure aanpak voor grootschalige simulaties die hoge versnelling en de mogelijkheid vereisen om te schalen buiten een enkele node, dankzij de lage communicatie-naar-berekening ratio.
• OpenMP wordt uitgelicht als de meest toegankelijke implementatie, die de eenvoudigste codestructuur biedt met een matige versnelling, geschikt voor single-node shared-memory systemen.
• Pthreads, hoewel het fijne controle biedt, blijkt minder effectief voor dit specifieke stencil-probleem vanwege synchronisatiekosten en cache-coherentieproblemen (false sharing).

De studie concludeert dat hoewel alle drie de modellen de SIR-simulatie succesvol parallelliseren, MPI de meest robuuste schaling biedt voor simulaties op nationaal niveau. De auteur suggereert dat toekomstig werk non-blocking MPI-communicatie moet verkennen om halo-exchanges met berekeningen te overlappen, hybride MPI+OpenMP-benaderingen, en GPU-acceleratie via CUDA.