关键词: 自适应笛卡尔网格, 隐式LU-SGS, GPU, 异构并行, CFD

Abstract: The implicit LU-SGS method on adaptive Cartesian grids, characterized by its high degree of automation in mesh generation, strong feature-adaptive capability, and good numerical stability, has become a key algorithm in the field of CFD. However, the adaptive refinement of Cartesian grids leads to complex topological relationships and irregular data access patterns. Coupled with the inherent strong data dependency of the LU-SGS method, traditional parallelization strategies struggle to fully exploit the computational potential of GPU hardware. Based on a production-level adaptive Cartesian grid CFD software, this paper conducts an in-depth analysis of its computational behavior and memory access patterns. An efficient heterogeneous parallel algorithm for LU-SGS, based on self-scheduling and reordering, is proposed. An objective performance evaluation metric, FVPTS (Finite Volumes solved Per Time-to-Solution), which balances grid scale and time-to-solution, is defined. This algorithm designs a cell-face-driven self-scheduling busy-waiting mechanism, realizing an on-demand-triggered asynchronous parallel mode based on data dependencies, thereby alleviating the limitation of strong data dependencies on GPU parallel efficiency and improving parallelism. Furthermore, a two-stage grid reordering algorithm based on level set and nested dissection is developed, which enhances memory access locality and reduces thread divergence. Test results on typical cases show that, compared to the traditional LU-SGS method and the explicit Runge-Kutta method, the new algorithm achieves a speedup of 2.2× and 4.0× in FVPTS, respectively. Compared to similar commercial software, the CFD software integrated with the new algorithm delivers an FVPTS speedup ranging from 6.1× to 8.8×, with an average speedup of approximately 7.5×.

Key words: adaptive Cartesian grid, implicit LU-SGS, GPU, heterogeneous parallel, CFD