💻 computer science

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

本文评估了 Pthreads、OpenMP 和 MPI 在对二维网格上的计算密集型 SIR 流行病模拟进行并行化处理方面的性能，证明了与由于同步和内存争用开销导致的 OpenMP 和 Pthreads 所观察到的中等且有限的扩展性相比，MPI 在处理大型网格时实现了更优越的加速比和近乎线性的扩展性。

原作者： amna atiq

发布于 2026-09-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： amna atiq

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一座广袤无垠、肉眼不可见的城市，数以百万计微小的市民生活在其中的网格中，每人占据一个方格。在这座城市里，疾病并非通过空气或水传播，而是通过接触邻居来传播。如果一个健康的人接触到了生病的人，他可能会染上疾病。如果他们生病了，他们最终可能会康复并获得免疫力。科学家使用计算机模型来模拟这种传播过程，帮助公共卫生官员了解疾病如何在真实人群中移动。挑战在于，这些模拟工作的计算量极其庞大。为了获得全国性疫情的清晰图景，计算机必须在数百天内，日复一日地更新网格中每个人的状态。在标准计算机上逐一执行这些步骤可能耗时过长，从而失去其实用价值。

这正是研究人员阿姆娜·阿提克（Amna Atiq）的研究领域。她致力于解决如何利用并行计算的力量来提高这些模拟运行速度的问题。她没有让一个处理器承担所有的重任，而是探索了如何将工作分配给许多处理器同时进行，就像一个庞大的工人团队将一幅巨大的壁画分成若干部分，以便每个人都能同时绘制属于自己的部分。她的研究专注于一种被称为 SIR 模型（追踪易感者、感染者和康复者这三类人群）的特定模型。其目标是观察哪种拆分工作的方法对计算机而言最为高效。

阿提克测试了三种不同的组织工人团队的方法。第一种被称为 Pthreads 的方法，将网格划分为水平条带，并将每个条带分配给单个计算机内的不同执行线程。第二种方法称为 OpenMP，它使用一套更简单的指令，自动将网格的行分配给可用的处理器。第三种方法是 MPI，它是为分布式系统设计的，在这些系统中，多个计算机或处理器通过相互发送消息来进行通信，通过传递它们所分配的网格部分的边缘信息，以确保感染能在整个地图上正确传播。

模拟结果揭示了每种方法在表现上的明显差异。当研究人员在代表一千乘以一千人的网格上运行一百个时间步长的模拟时，标准的单线程方法大约耗时 1.58 秒完成。在四核机器上使用 Pthreads 方法后，时间有所下降，但加速效果有限。工人们花费了太多时间在彼此完成各自的部分之前进行等待，以便交换工作，而且他们偶尔会干扰彼此的内存空间，从而导致速度变慢。OpenMP 方法的表现略好，在 0.7 秒内完成了任务，但当增加更多处理器时，它也遇到了瓶颈，这主要是由于每天结束时同步工人所花费的时间造成的。

最成功的方法是 MPI 方法。通过将网格视为一系列独立的碎片，并且仅在边界处进行通信，这种方法表现出了卓越的可扩展性。当研究人员将处理器数量增加到八个时，模拟运行的速度比原始单线程版本快了六倍多。这是因为在处理器之间发送消息所花费的时间，与计算每个区域内人员健康状态所需的时间相比非常小。虽然其他方法在处理单台机器上的众多工人协调问题时显得吃力，但这种消息传递法让工人能够专注于自己的任务，仅在分享其领地边缘的必要信息时进行短暂停顿。

这项研究还强调了选择方法时所涉及的权衡。消息传递法需要最复杂的代码和精心的规划，以确保网格碎片被正确地发送和接收而不会发生卡顿。自动分配法是最容易编写的，但提供的速度提升也最小。基于线程的方法则处于中间位置，但受到与计算机内存组织相关的技术问题的困扰。最终，研究表明，对于大规模流行病模拟，使用消息传递将工作拆分到多个处理器上，可以提供最显著的速度优势，使科学家能够在比旧方法快得多的时间内运行复杂的模型。这种效率对于应对未来的疫情至关重要，因为在模拟中，每一秒钟的节省都可能转化为更好的准备和应对策略。

技术摘要：使用 Pthreads、OpenMP 和 MPI 实现 SIR 流行病传播模拟的并行化

问题陈述
使用易感-感染-康复（SIR）细胞自动机模型进行流行病传播模拟是一项计算密集型任务，对于公共卫生政策制定和流行病预防至关重要。在其空间网格形式下，该模型模拟疾病在二维人口中的传播，其中感染会扩散到相邻的邻居。国家级规模的模拟（例如， $N=10,000$ 代表覆盖 $1 \text{ km}^2$ 区域，时间步长 $T=365$ ）大约需要 360 亿次单元更新，这使得在没有高性能并行计算的情况下，计算在实际上是不可行的。本文解决的核心挑战是高效并行化这种“模板计算”（stencil computation），在这种计算中，每个单元的状态仅取决于其直接相邻的邻居，这在每个时间步内创造了一个高度可并行的工作负载，但需要在边界处进行同步。

方法论
本研究实现并对比了三种不同的并行编程范式与一个二维 $N \times N$ 网格的串行基准模型：

串行基准（Sequential Baseline）： 一个使用乒乓缓冲区（两个 $N \times N$ 网格）的参考实现，具有 $O(N^2 \cdot T)$ 的时间复杂度。更新规则通过遍历单元，根据感染邻居的比例（ $\beta$ ）和康复率（ $\gamma$ ）应用概率转换。
Pthreads（POSIX 线程）： 将网格分解为 $P$ 个水平条带，每个线程拥有特定的行集。通过 pthread_barrier_t 进行同步，以确保所有线程在缓冲区交换前完成一个时间步。该实现强调了边界行存在“伪共享”（false sharing）的风险，尽管使用了独立的缓冲区，但在这些行上相邻线程仍会读写相同的缓存行。
OpenMP： 利用单个 #pragma omp parallel for 指令配合静态调度来划分外层行循环。这种方法依赖于隐式屏障进行同步，并采用每线程随机数种子（rand_r）来防止数据竞争。它提供了自动化的分解，且人工干预极少。
MPI（消息传递接口）： 专为分布式内存设计，根进程生成网格并将 $N/P$ 行分发给工作进程。每个进程分配“幽灵”行或“光晕”（halo）行，以促进邻居间的通信。使用 MPI_Sendrecv 模式在每个时间步之前处理光晕交换，并使用 MPI_Reduce 聚合全局统计数据。该方法显式地管理了通信开销与计算之间的权衡。

主要贡献
本文提供了四个主要贡献：

一个经过验证的串行 SIR 实现，作为正确性参考。
三种针对 SIR 模板问题定制的截然不同的并行实现（Pthreads、OpenMP、MPI）。
系统的性能分析，包括针对不同网格大小（ $N=500, 1000$ ）和进程/线程数（ $P=1$ 到 $8$）的强扩展性测量。
关于瓶颈、编程复杂性以及共享内存模型（Pthreads/OpenMP）与分布式内存模型（MPI）之间权衡的比较性讨论。

实验结果
实验在配备四核处理器（Apple M 系列/Intel Core i5）的机器上进行，设置 $N=1000$ 且 $T=100$ 。串行基准运行时间为 1.576 秒。

MPI 性能： 在 $P=8$ 个进程时实现了最高的 6.35× 加速，效率为 79%。由于通信量（每步约 8 KB 的光晕交换）相对于 $O(N^2/P)$ 的计算量而言微不足道，它展示了近乎线性的扩展性。
OpenMP 性能： 在 $P=4$ 个线程时实现了 2.25× 加速。虽然效率较高，但由于每个并行循环结束时的隐式屏块开销，其扩展性较为适中；当问题规模较小时，该开销相对于计算量变得显著。
Pthreads 性能： 在 $P=4$ 个线程时实现了 2.12× 加速。由于边界行的伪共享问题和显式屏障同步的开销，其扩展性受到限制，随着线程数增加，扩展性趋于平缓。

值得注意的是，由于在并行构建过程中应用了编译器优化（-O3）， $P=1$ 时的 Pthreads 和 OpenMP 实现运行时间略快于串行基准，但真正的并行增益是在较高的 $P$ 值下观察到的。

意义与主张
论文声称，并行范式的选择会显著影响流行病模拟的性能和可扩展性。

MPI 被确定为大规模模拟（需要高加速比和超越单节点扩展能力）的优选方案，这归功于其较低的通信/计算比。
OpenMP 被强调为最易实现的方案，提供最简单的代码结构和中等的加速比，适用于单节点共享内存系统。
Pthreads 虽然提供了细粒度的控制，但由于同步成本和缓存一致性问题（伪共享），被证明对于这种特定的模板问题效果较差。

研究结论认为，虽然这三种模型都成功地实现了 SIR 模拟的并行化，但 MPI 为国家级规模的模拟提供了最稳健的扩展性。作者建议未来的工作应探索非阻塞 MPI 通信以实现光晕交换与计算的重叠、混合 MPI+OpenMP 方法，以及通过 CUDA 进行 GPU 加速。

技术摘要：使用 Pthreads、OpenMP 和 MPI 实现 SIR 流行病传播模拟的并行化

类似论文