并行求解器与共轭梯度法实现的研究与实践

### 并行求解器与共轭梯度法实现的研究与实践 在科学计算领域，并行化技术已经成为提升计算效率的关键手段。本文将深入探讨并行平滑器以及共轭梯度法的不同并行实现方式，包括块红黑排序的高斯 - 赛德尔平滑器及其改进版本，还有基于软件事务内存（STM）、OpenMP 和 Pthreads 的共轭梯度法并行实现。 #### 块红黑排序的高斯 - 赛德尔平滑器 ##### 块红黑排序技术 块红黑排序技术用于并行化高斯 - 赛德尔（GS）平滑器。该方法将分析网格划分为多个块，并对这些块应用红黑排序。在这种排序下，每个轴的处理方式与传统红黑高斯 - 赛德尔（RB - GS）类似，但当块大小极大时，其效果近似于顺序 GS 平滑。虽然在这两个极端块大小之间的收敛情况需要结合实际问题进行研究，但后续的数值测试支持了预期效果。 此外，缓存分块技术可轻松应用于块红黑高斯 - 赛德尔（BRB - GS）。使用该技术时，只需将块大小设置为与缓存大小匹配，并在每个块的平滑步骤之后或之前执行限制或延长操作。由于该技术使缓存行的利用率提高了一倍，因此能显著提高缓存命中率，进而提升性能。 ##### 改进的块红黑高斯 - 赛德尔平滑器 为提高整体求解器性能，引入了改进版本的块红黑高斯 - 赛德尔平滑器（mBRB - GS）。在这个版本中，每个红/黑块中的 GS 迭代次数从 1 增加到 α > 1。该平滑器被视为一种乘法 Schwarz 平滑器，而非基于并行排序的并行 GS 平滑器。 一般来说，增加整个网格空间平滑步骤的迭代次数 β 会提高收敛性，但由于网格通常远大于缓存大小，一次平滑步骤的计算成本也会与 β 成比例增加。而在 BRB - GS 中增加块内的 GS 步骤数 α 则有不同表现。设 ts 为块中第一次平滑步骤所需的计算时间，当块大小小于缓存大小时，后续平滑步骤的计算时间 ˜ts 会远小于 ts，因为是在缓存内进行计算。因此，mBRB - GS(α) 一次平滑步骤的计算时间 tm 约为： tm ≈ ts + (α - 1)˜ts < αts 这意味着即使收敛性的改善未达到 α 倍，通过增加块内的 GS 步骤数，总计算时间仍可减少。 ##### 数值测试 为了评估所开发的多重网格泊松求解器，在京都大学的 T2K 开放超级计算机上进行了数值测试。该并行超级计算机由对称多处理（SMP）节点组成，每个节点包含四个 AMD 四核 Opteron 8356（2.3 GHz）处理器和 32 GB（DDR2 - 667）共享内存。代码使用 Fortran90 和 MPI 编写，采用扁平 MPI 并行编程模型。 测试模型的分析域 Ω 为 [-0.5, 0.5]³，边界条件为 φ = 0 的狄利克雷边界条件，源项定义为： ρ(r) = 1, if r ≤ 0.015 0, otherwise 其中 r 是到原点的距离。为评估弱可扩展性，每个进程的最细网格大小固定为 128³。 表 1 列出了多重网格求解器在 1、8、64 和 216 个核心（进程）下的计算时间和循环次数。 | 进程数 | Seq.GS | Hybrid | RB - GS | BRB - GS | | ---- | ---- | ---- | ---- | ---- | | 1 | 3.55(10) | - | 4.84(9) | 4.33(11) | | 8 | - | 9.99(17) | 8.83(11) | 6.22(11) | | 64 | - | 14.08(17) | 11.39(10) | 8.40(11) | | 216 | - | 15.08(17) | 12.22(10) | 9.43(11) | 从表中可以看出，混合平滑器的收敛速度比顺序 GS 平滑器慢 1.7 倍，其并行加速比受限。RB - GS 和 BRB - GS 平滑器的收敛率与顺序 GS 平滑器相当，但由于跨步内存访问，RB - GS 一次多重网格循环的计算时间比顺序 GS 更长。而 BRB - GS 由于更高效的缓存利用，在每个循环的计算时间上比 RB - GS 更具优势，216 个进程时的弱缩放加速比达到 81.3。 接下来对 mBRB - GS 的性能进行了测试。在 216 个进程的多进程并行处理中，表 2 展示了使用 mBRB - GS(pr) 和 mBRB - GS(po) 分别进行预平滑和后平滑步骤时的计算时间和迭代次数。 | po \ pr | 1 | 2 | 3 | 4 | 5 | 6 | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | 1 | 10.38/11 | 8.23/9 | 8.33/9 | 7.58/8 | 7.84/8 | 8.12/8 | | 2 | 8.10/9 | 7.42/8 | 6.69/7 | 7.21/