💻 computer science

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

This paper evaluates the performance of Pthreads, OpenMP, and MPI in parallelizing a computationally intensive SIR epidemic simulation on a 2D grid, demonstrating that MPI achieves superior speedup and near-linear scaling for large grids compared to the moderate and limited scaling observed in OpenMP and Pthreads due to synchronization and memory contention overheads.

Original authors: amna atiq

Published 2026-09-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: amna atiq

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, invisible city where millions of tiny citizens live in a grid, each occupying a single square. In this city, a sickness spreads not through air or water, but by touching a neighbor. If a healthy person touches someone who is sick, they might catch the illness. If they are sick, they might eventually recover and become immune. Scientists use computer models to simulate this kind of spread, helping public health officials understand how a disease might move through a real population. The challenge is that these simulations are incredibly heavy work. To get a clear picture of a national outbreak, the computer must update the status of every single person in the grid, day after day, for hundreds of days. Doing this one step at a time on a standard computer can take far too long to be useful in an emergency.

This is where the work of researcher Amna Atiq comes in. She tackled the problem of how to make these simulations run faster by using the power of parallel computing. Instead of asking one processor to do all the heavy lifting, she explored ways to split the work among many processors at once, much like a large team of workers dividing a massive mural into sections so everyone can paint their part simultaneously. Her study focused on a specific type of model known as the SIR model, which tracks three groups: those who are susceptible to the disease, those who are infected, and those who have recovered. The goal was to see which method of splitting the work was the most efficient for a computer to handle.

Atiq tested three different approaches to organizing this team of workers. The first method, known as Pthreads, divides the grid into horizontal strips, assigning each strip to a different thread of execution within a single computer. The second method, called OpenMP, uses a simpler set of instructions to automatically divide the rows of the grid among available processors. The third approach, MPI, is designed for distributed systems where multiple computers or processors communicate by sending messages to one another, passing the edges of their assigned grid sections back and forth to ensure the infection spreads correctly across the whole map.

The results of the simulation revealed clear differences in how well each method performed. When the researchers ran the simulation on a grid representing one thousand by one thousand people over one hundred time steps, the standard single-threaded approach took about 1.58 seconds to complete. Using the Pthreads method on a four-core machine, the time dropped, but the speedup was limited. The workers spent too much time waiting for each other to finish their sections before they could swap their work, and they occasionally interfered with each other's memory space, slowing things down. The OpenMP method performed slightly better, finishing the task in under 0.7 seconds, but it too hit a wall when more processors were added, largely due to the time spent synchronizing the workers at the end of each day.

The most successful approach was the MPI method. By treating the grid as a collection of separate pieces that communicated only at their boundaries, this method scaled remarkably well. When the researchers increased the number of processors to eight, the simulation ran more than six times faster than the original single-threaded version. This happened because the time spent sending messages between processors was very small compared to the time spent calculating the health status of the people within each section. While the other methods struggled with the overhead of coordinating many workers on a single machine, the message-passing approach kept the workers focused on their own tasks, only pausing briefly to share the necessary information about the edges of their territories.

The study also highlighted the trade-offs involved in choosing a method. The message-passing approach required the most complex code and careful planning to ensure the pieces of the grid were sent and received correctly without getting stuck. The automatic division method was the easiest to write but offered the least improvement in speed. The thread-based method sat in the middle but suffered from technical issues related to how the computer's memory is organized. Ultimately, the research showed that for large-scale epidemic simulations, splitting the work across multiple processors using message passing provides the most significant speed advantage, allowing scientists to run complex models in a fraction of the time required by older methods. This efficiency is crucial for preparing for future outbreaks, where every second of simulation time can translate into better preparation and response strategies.

Technical Summary: Parallelizing SIR Epidemic Spread Simulation Using Pthreads, OpenMP, and MPI

Problem Statement
The simulation of epidemic spread using the Susceptible–Infected–Recovered (SIR) cellular automaton model is a computationally intensive task critical for public health policy and pandemic preparedness. In its spatial grid form, the model simulates disease propagation across a two-dimensional population where infection spreads to adjacent neighbors. National-scale simulations (e.g., $N=10,000$ representing $1 \text{ km}^2$ regions over $T=365$ timesteps) require approximately 36 billion cell updates, rendering them computationally infeasible without high-performance parallel computing. The core challenge addressed is the efficient parallelization of this "stencil computation," where each cell's state depends solely on its immediate neighbors, creating an embarrassingly parallel workload within each timestep but requiring synchronization at boundaries.

Methodology
The study implements and compares three distinct parallel programming paradigms against a sequential baseline on a two-dimensional $N \times N$ grid:

Sequential Baseline: A reference implementation using ping-pong buffers (two $N \times N$ grids) with $O(N^2 \cdot T)$ time complexity. The update rule iterates through cells, applying probabilistic transitions based on the fraction of infected neighbors ( $\beta$ ) and recovery rates ( $\gamma$ ).
Pthreads (POSIX Threads): The grid is decomposed into $P$ horizontal strips, with each thread owning a specific set of rows. Synchronization is managed via pthread_barrier_t to ensure all threads complete a timestep before the buffer swap. The implementation highlights the risk of "false sharing" on boundary rows where adjacent threads read/write to the same cache lines, despite using separate buffers.
OpenMP: Utilizes a single #pragma omp parallel for directive with static scheduling to partition the outer row loop. This approach relies on implicit barriers for synchronization and employs per-thread random number seeds (rand_r) to prevent data races. It offers automatic decomposition with minimal manual intervention.
MPI (Message Passing Interface): Designed for distributed memory, the root process generates the grid and scatters $N/P$ rows to worker processes. Each process allocates "ghost" or "halo" rows to facilitate neighbor communication. A MPI_Sendrecv pattern handles halo exchanges before each timestep, and MPI_Reduce aggregates global statistics. This method explicitly manages communication overhead versus computation.

Key Contributions
The paper provides four primary contributions:

A verified sequential SIR implementation serving as a correctness reference.
Three distinct parallel implementations (Pthreads, OpenMP, MPI) tailored to the SIR stencil problem.
A systematic performance analysis including strong scaling measurements for varying grid sizes ( $N=500, 1000$ ) and process/thread counts ( $P=1$ to $8$).
A comparative discussion on bottlenecks, programming complexity, and the trade-offs between shared-memory (Pthreads/OpenMP) and distributed-memory (MPI) models.

Experimental Results
Experiments were conducted on a quad-core machine (Apple M-series/Intel Core i5) with $N=1000$ and $T=100$ . The sequential baseline runtime was 1.576 seconds.

MPI Performance: Achieved the highest speedup of 6.35× at $P=8$ processes, with an efficiency of 79%. It demonstrated near-linear scaling for large grids, as the communication volume (halo exchange of ~8 KB per step) remained negligible compared to the $O(N^2/P)$ computation.
OpenMP Performance: Delivered a speedup of 2.25× at $P=4$ threads. While efficient, scaling was moderate due to the overhead of implicit barriers at the end of each parallel loop, which becomes dominant relative to computation for smaller problem sizes.
Pthreads Performance: Achieved a speedup of 2.12× at $P=4$ threads. Scaling was limited by false sharing on boundary rows and the overhead of explicit barrier synchronization, resulting in near-flat scaling as thread count increased.

Notably, the Pthreads and OpenMP implementations with $P=1$ showed runtimes slightly faster than the sequential baseline due to compiler optimizations (-O3) applied during the parallel build, though the true parallel gains were observed at higher $P$ .

Significance and Claims
The paper claims that the choice of parallel paradigm significantly impacts performance and scalability for epidemic simulations.

MPI is identified as the superior approach for large-scale simulations requiring high speedup and the ability to scale beyond a single node, owing to its low communication-to-computation ratio.
OpenMP is highlighted as the most accessible implementation, offering the simplest code structure with moderate speedup, suitable for single-node shared-memory systems.
Pthreads, while offering fine-grained control, is shown to be less effective for this specific stencil problem due to synchronization costs and cache coherence issues (false sharing).

The study concludes that while all three models successfully parallelize the SIR simulation, MPI provides the most robust scaling for national-level simulations. The author suggests future work should explore non-blocking MPI communication to overlap halo exchanges with computation, hybrid MPI+OpenMP approaches, and GPU acceleration via CUDA.

Technical Summary: Parallelizing SIR Epidemic Spread Simulation Using Pthreads, OpenMP, and MPI

More like this