模拟分四类
离散事件、粒子系统、ODEs、PDEs。每类有不同的并行化策略。
CS267 · 第 5 课 · James Demmel
并行性和数据局部性是性能的关键。真实世界的问题天然具有并行性和局部性：许多对象独立运行，依赖近处多于远处，远处依赖可以简化。
科学计算模拟可以分为四大类：
| 类型 | 时间 | 空间 | 示例 |
|---|---|---|---|
| 离散事件系统 | 离散 | 离散 | Game of Life、制造系统、电路 |
| 粒子系统 | 连续 | 离散（粒子） | N-body、分子动力学 |
| 集中参数系统 (ODEs) | 连续 | 离散（变量） | 电路模拟、结构力学 |
| 分布参数系统 (PDEs) | 连续 | 连续 | 热传导、流体力学 |
| 类型 | 描述 | 示例 |
|---|---|---|
| Synchronous | 每个时间步评估所有转移函数 | Game of Life |
| Asynchronous | 仅在输入变化时评估（事件驱动） | 电路模拟、交通仿真 |
每个新网格单元仅依赖于旧网格中的 9 个单元（自身 + 8 邻居）。
并行化策略：Domain Decomposition（区域分解）
对于 n×n 网格，p 个处理器：
| 分区方式 | 边交叉数 |
|---|---|
| 条状 (slab) | \(n \cdot (p-1)\) |
| 块状 (block) | \(2n(\sqrt{p} - 1)\) |
结论：最小化通信 = 最小化分区表面积/体积比
保守调度 (Conservative)：仅模拟到输入消息的最小时间戳。
投机调度 (Speculative/Optimistic)：假设无新输入，继续模拟。
\[\text{force} = \text{external\_force} + \text{nearby\_force} + \text{far\_field\_force}\]
| 力类型 | 并行性 | 通信需求 |
|---|---|---|
| 外力 | "尴尬并行"（Embarrassingly Parallel） | 无需通信 |
| 近邻力 | Domain Decomposition | 近邻通信 |
| 远场力 | 需要巧妙算法 | 全对全（All-to-all） |
// 每个粒子独立计算
for each particle p on processor
apply_external_force(p)
// 可能需要 reduce 计算全局时间步任意分布均可，局部性不是问题。
挑战 1：边界交互
挑战 2：负载不均衡
复杂度：\(O(n \log n)\) 或 \(O(n)\)
远处粒子群的力可以近似为单个大粒子：
复杂度：\(O(n \log n)\) 或 \(O(n)\)
状态变量：
方程（KCL、KVL、欧姆定律）：
\[\begin{pmatrix} 0 & A & 0 \\ A^T & 0 & -I \\ 0 & R & -I \end{pmatrix} \begin{pmatrix} v_n \\ 0 \\ i_b \end{pmatrix} = \begin{pmatrix} S \\ 0 \\ 0 \end{pmatrix}\]
假设 ODE 为 \(x'(t) = f(x) = A \cdot x(t)\)，其中 A 是稀疏矩阵：
// Forward Euler
x[i+1] = x[i] + dt * A * x[i] // 稀疏矩阵-向量乘法优点：简单（只需 SpMV）
缺点：稳定性问题，刚性系统需要极小时间步
// Backward Euler
(I - dt*A) * x[i+1] = x[i] // 需要求解稀疏线性系统优点：可取更大时间步，尤其适合刚性问题
缺点：每步需要求解线性系统
CSR (Compressed Sparse Row) 格式：
for each row i
for k = ptr[i] to ptr[i+1]-1
y[i] = y[i] + val[k] * x[ind[k]]分区策略：
Owner-Computes 规则：拥有数据的处理器负责计算。
理想结构：块对角矩阵（无通信）
目标：
Q1：粒子系统中，哪种力的计算是"尴尬并行"的？
Q2：对于 2D 网格，哪种分区方式通信量更小？
Q3：Particle-Mesh 方法的主要优势是什么？
Q4：显式方法求解 ODE 的主要缺点是什么？
Q5：并行 SpMV 中，Owner-Computes 规则是什么？
离散事件、粒子系统、ODEs、PDEs。每类有不同的并行化策略。
将物理区域划分给处理器，最小化表面积/体积比以减少通信。
Particle-Mesh 和 Tree 方法将全对全交互从 O(n²) 降到 O(n log n)。
SpMV 是许多算法的核心。图分区决定并行效率和通信量。