HW2-1 导读 — 粒子模拟并行化（OpenMP 共享内存）

与课程的关系

Lecture 4 · OpenMP

↓

并行区域、归约、原子操作

Lecture 5 · 局部性

↓

空间划分、邻居列表

Lecture · 同步

↓

Locks、Atomics、内存屏障

Lecture · 性能分析

↓

TAU / HPCToolkit

任务概述

并行化一个玩具粒子模拟：粒子间存在斥力，当距离小于 cutoff 时相互作用。起始代码是 O(n²) 暴力扫描，你需要先优化到 O(n)，再并行化到 T/p。

串行目标 O(n)
通过空间划分（Cell list / Neighbor list）避免全粒子对扫描

并行目标 T/p
p 个处理器下理想线性加速，关注负载均衡

可修改文件
只能修改 serial.cpp 和 openmp.cpp

报告要求
log-log 图、加速比图、时间分解、同步描述

代码组件一览

文件	角色	可以修改？	课程关联
serial.cpp	串行实现，先优化到 O(n)	✅ 是	Lec 5
openmp.cpp	OpenMP 并行实现	✅ 是	Lec 4
common.h / common.cpp	数据结构、I/O、验证	❌ 否	—
Makefile	编译配置	⚠️ 谨慎	工具链

串行优化路线：O(n²) → O(n)

空间划分 (Spatial Decomposition)

把模拟空间划分为边长 ≥ cutoff 的 cell。每个粒子只需与相邻 3×3（2D）或 3×3×3（3D）个 cell 内的粒子交互。

Cell 边长 ≥ cutoff，确保只需检查邻居 cell
构建 Cell List：每个 cell 维护其中的粒子索引
每步模拟前重建 Cell List（粒子位置变化）

邻居列表 (Neighbor List / Verlet List)

进一步优化：为每个粒子维护一个"邻居列表"，只在粒子移动超过阈值时重建。

Skin distance = cutoff + δ，避免频繁重建
跟踪每个粒子的位移，超过 δ/2 时触发重建
这是从 O(n²) 到 O(n) 的关键

⚠️ 常见坑：Cell List 本身已经是 O(n)，但实现时要注意边界 cell 的处理（周期性边界条件 PBC）。

OpenMP 并行化路线

并行化力计算

使用 #pragma omp parallel for 并行化外层粒子循环。注意力计算的对称性：f_ij = -f_ji。

使用 reduction(+:force) 或原子操作
考虑每个线程私有 force 数组再归约
注意 false sharing：避免相邻线程写同一 Cache Line

处理写冲突 (Write Conflicts)

当两个线程同时更新同一粒子的力时，需要同步机制。

#pragma omp atomic — 简单但慢
Coloring（图着色）— 避免冲突，更复杂
私有数组 + 归约 — 内存换性能

负载均衡

粒子分布不均会导致某些线程空闲。使用 schedule(dynamic) 或 schedule(guided)。

对比 static vs dynamic vs guided
chunk size 对性能的影响
用 TAU/HPCToolkit 查看负载分布

OpenMP 同步原语速查

原语	用途	开销
#pragma omp parallel for	并行化 for 循环	低（线程池复用）
#pragma omp atomic	原子读-改-写操作	中（硬件级）
#pragma omp critical	互斥代码区	高（软件锁）
omp_lock_t	显式锁	高
#pragma omp barrier	显式同步点	中
reduction(+:var)	并行归约	低（树形归约）

报告应包含什么

部分	关键内容	图表要求
log-log 图	串行时间 vs n，验证 O(n) 行为	T vs n, log-log
加速比图	Speedup vs p，理想 vs 实际	S = T₁/Tₚ vs p
时间分解	计算、同步、空闲各占多少	堆叠柱状图
同步描述	用了哪些同步原语？为什么？开销如何？

自测 Quiz

Q1. Cell List 算法中，cell 边长应该如何选择？

Q2. 当两个线程同时更新同一粒子的力时，应该使用什么机制？

Q3. 为什么在并行化力计算时需要注意 False Sharing？

Q4. 在并行化之前，为什么应该先优化串行算法到 O(n)？

Q5. 以下哪种方式实现并行归约性能最好？

← 上一个 HW 下一个 HW →