兼顾隐式迭代更新和数据局部性的非结构网格重排序算法研究

RESEARCH ON UNSTRUCTURED MESH REORDERING ALGORITHMS BALANCING IMPLICIT ITERATIVE UPDATES AND DATA LOCALITY

  • 摘要: 基于隐式时间推进的非结构网格有限体积法是最常用的计算流体力学(CFD)数值格式,由于非结构网格单元排序的不规则性,以及计算过程中需要频繁读取邻居单元信息,非结构网格单元的排序优劣会直接影响计算效率。常用的Reverse Cuthill-Mckee(RCM)重排序算法可以大幅降低隐式算子带宽,减少隐式迭代次数;而基于Hilbert空间填充曲线的重排序算法已被证明可以很好地提高数据局部性。为寻找可以兼顾隐式迭代更新和数据局部性的重排序算法,以空间填充曲线为基础,将Morton空间填充曲线和Peano空间填充曲线推广到非结构网格的重排序算法中,并将二者与RCM算法和基于Hilbert空间填充曲线的重排序算法对比。研究发现:基于Morton空间填充曲线的重排序算法具备RCM算法的特征,同时又具有空间填充曲线可以提高数据局部性的固有属性。算例测试结果表明:基于Morton空间填充曲线的重排序算法相比于初始网格排序可以减少40%~50%执行时间;与RCM和基于Hilbert空间填充曲线的重排序算法相比,执行时间可进一步降低10%左右。

     

    Abstract: The unstructured-grid finite volume method based on implicit time stepping is one of the most commonly used numerical schemes in computational fluid dynamics (CFD). Due to the irregularity of unstructured grid cell ordering and to the frequent need to access neighboring cell information during a computation, the quality of the grid cell ordering directly impacts the computational efficiency. The widely used Reverse Cuthill-McKee (RCM) reordering algorithm can significantly reduce the bandwidth of implicit operators and decrease the number of implicit iterations. Meanwhile, the reordering algorithm based on the Hilbert space-filling curve has been demonstrated to effectively improve data locality. To develop a reordering algorithm that balances both implicit iterative updates and data locality, the Morton and Peano space-filling curves are extended to unstructured grid reordering and compared with the RCM algorithm and the Hilbert-based reordering method. The study finds that the Morton space-filling curve-based reordering algorithm possesses characteristics similar to those of the RCM algorithm while retaining the inherent property of space-filling curves to enhance data locality. Test research results show that the Morton-based reordering algorithm reduces the execution time by 40% ~ 50% compared to the initial grid ordering, and achieves approximately 10% greater reduction in the execution time than those of both the RCM and Hilbert-based reordering algorithms.

     

/

返回文章
返回