Abstract: Aiming at the strong data dependence of CFD (computational fluid dynamics) LU-SGS (lower-upper symmetric Gauss-Seidel) time stepping with two dimensional structured meshes, this paper presents a wavefront parallel algorithm, and designs the corresponding data structure, memory access method with better data locality and fractional communication optimization. The experimental results show that the simulation result of the parallel algorithm is as same as the serial algorithm, but runs much faster. The parallel efficiency of 64 processes is up to 85.64% compared with 16 processes on a DMP (distributed memory processing) system. The parallel efficiency of 128 processes is up to 83.68% compared with 16 processes on an SMP (symmetric multiprocessing) system.

Key words: lower-upper symmetric Gauss-Seidel (LU-SGS), computational fluid dynamics (CFD), structured meshes, parallel computing

摘要： 针对二维结构网格CFD（computational fluid dynamics）时间推进LU-SGS（lower-upper symmetric Gauss-
Seidel）存在的强数据依赖的特点，提出了波阵面并行算法，设计了相应的数据结构，以及具有更好数据局部性的访存优化方法和分块通信优化方法。测试结果表明，并行算法可以取得与串行算法完全一致的计算结果，且具有较好的加速效果，在DMP（distributed memory processing）系统下与16个进程相比，64个进程的并行效率达到85.64%，在SMP（symmetric multiprocessing）系统下与16个进程相比，128个进程的并行效率达到83.68%。

关键词: LU-SGS, 计算流体动力学（CFD）, 结构化网格, 并行计算