第二十六章 SDE计算的并行化与效率
26.1 传统并行计算的conforming困境
传统并行计算的核心策略是domain decomposition——将计算域分割成不重叠的子域，每个子域分配给一个处理器。子域之间通过共享边界交换信息（ghost cells、halo exchange）。
这是conforming范式在并行计算中的自然延伸——不重叠的域分割、通过共享边界的局域通信。它在局域PDE上非常高效——每个处理器独立计算自己子域内的解，只在共享边界上通信，通信量与子域的表面积成正比（体表面积比使得大规模并行高效）。
但对于非局域问题，这种策略崩溃。非局域算子要求每个点与远处的点直接耦合——这意味着即使两个子域在空间上不相邻，它们之间也可能有大量的通信需求。通信不再局限于共享边界——它变成了全局的。全局通信让并行效率急剧下降。
26.2 伞并行：重叠子域的自然并行
SDE计算的伞模型天然适合一种新型的并行策略——伞并行。
不是把域分成不重叠的子域，而是把伞场分成重叠的子伞场。每个处理器负责一个子伞场，子伞场之间允许重叠。
重叠区恰恰是通信发生的地方——两个子伞场的重叠区中的伞同时被两个处理器"知道"。一个处理器更新了重叠区中某把伞的状态，另一个处理器可以通过重叠区的共享知识"看到"这个更新。
与传统domain decomposition的关键区别：传统方法的通信发生在子域的边界上——一个二维面。伞并行的通信发生在子伞场的重叠区中——一个三维体积。重叠区比边界"厚"——通信的带宽更大、延迟更低。
更重要的是：重叠区的通信是自然的——它不是为了并行而人为添加的ghost cells，而是伞模型本身就有的重叠结构。在SDE数学中，重叠是物理的（不同尺度的纠缠在空间上重叠），不是计算技巧。并行策略直接利用了物理结构，而不是跟物理结构"做斗争"。
26.3 伞状接力通信
传统并行的全局通信（all-to-all）代价是O(P²)，P是处理器数量。对于非局域问题，如果每对处理器都可能需要通信，全局通信不可避免。
但伞模型告诉我们：非局域通信不是全局的——它是伞状接力的。远处的两个处理器之间的信息不需要直接通信——信息从一把伞传到重叠的下一把伞，再传到再下一把，像接力一样传到远处。
这意味着每个处理器只需要跟重叠的邻居通信——通信模式是局部的。但信息通过接力可以到达远处——通信的效果是全局的。
通信代价：每个处理器跟O(k)个重叠邻居通信（k是平均重叠邻居数，由伞半径和伞密度决定）。信息到达距离D处需要D/r步接力（r是伞半径）。总的通信代价是O(P·k)——线性于处理器数量，而不是O(P²)。
这就是大脑并行计算的策略——860亿个神经元不做全局广播，每个神经元只跟几千个突触邻居通信，信息通过突触接力传到远处。全局通信代价是O(N·k)，不是O(N²)。这就是为什么大脑能在20瓦功耗下运行——它的通信效率远超全局广播。
26.4 多层伞并行与异构计算
多层伞场自然产生多层并行结构：
细层（小伞）： 大量的小计算单元，每个做简单的局部计算。适合GPU——大量并行的简单运算。
粗层（大伞）： 少量的大计算单元，每个做复杂的非局域整合。适合CPU——少量并行的复杂运算。
跨层耦合： 细层和粗层之间的信息交换。通过跨层重叠区传递——细层的伞被大层的伞覆盖，它们的重叠区就是跨层通信的通道。
这自然对应异构计算的硬件架构——GPU处理细层（大规模并行的简单运算），CPU处理粗层（少量的复杂运算），GPU-CPU之间的数据传输对应跨层纠缠通信。
传统的异构计算需要程序员手动设计GPU和CPU之间的任务分配和数据传输。在SDE框架中，任务分配和数据传输从多层伞结构中自然产生——细层的伞自动被分配给GPU，粗层的伞自动被分配给CPU，跨层通信自动通过重叠区进行。
26.5 案例：伞场计算的GPU并行化效率估算
考虑一个具体的性能对比：在N=10^6个采样点、M=10^4个伞中心、平均重叠度ω=10的系统上。
传统有限元（GPU）： 矩阵组装：每个单元约10个节点，约10^6个单元→约10^7次局部矩阵组装，高度并行。矩阵求解：稀疏矩阵，约10^7个非零元素，用迭代法（CG/GMRES）求解——迭代次数取决于条件数，通常100-1000次，每次迭代涉及全局稀疏矩阵-向量乘（内存带宽限制）。总FLOPS约10^{10}-10^{11}。
伞场计算（GPU）： 每个采样点：查询覆盖伞列表（ω=10个伞），每个伞计算核函数值并加权求和——约10次乘加。N=10^6个采样点→10^7次乘加。完美并行（无数据依赖）。总FLOPS约10^7-10^8——比有限元少2-3个数量级。
但这个对比不公平——有限元的精度保证（收敛阶、误差估计）远比简单的伞场加权更强。真正的对比应该是：达到同等精度所需的计算量。如果伞场方法需要更多的伞（M更大）或更高的重叠度（ω更大）来达到有限元的精度，那么它的计算优势可能会被抵消。
初步估算：对光滑问题，伞场方法的收敛阶可能跟有限元相当（取决于伞核函数的光滑度和重叠模式）。对含有尖锐特征的问题（激波、断裂面），伞场方法可能有优势——因为伞可以自适应地在尖锐区域密集排列而不需要conforming约束。