基于射线穿透法的GPU并行阶梯型有限差分网格生成算法

三维大规模有限差分网格生成技术是三维有限差分计算的基础，网格生成效率是三维有限差分网格生成的研究热点。传统的阶梯型有限差分网格生成方法主要有射线穿透法和切片法。本文在传统串行射线穿透法的基础上，提出了基于GPU （graphic processing unit）并行计算技术的并行阶梯型有限差分网格生成算法。并行算法应用基于分批次的数据传输策略，使得算法能够处理的数据规模不依赖于GPU内存大小，平衡了数据传输效率和网格生成规模之间的关系。为了减少数据传输量，本文提出的并行算法可以在GPU线程内部相互独立的生成射线起点坐标，进一步提高了并行算法的执行效率和并行化程度。通过数值试验的对比可以看出，并行算法的执行效率远远高于传统射线穿透法。最后，通过有限差分计算实例可以证实并行算法能够满足复杂模型大规模数值模拟的需求。

A GPU parallel staircase finite difference mesh generation algorithm based on the ray casting method

Three-dimensional large-scale finite difference mesh generation technology is the basis of three-dimensional finite difference computation, and the efficiency of mesh generation is a research hotspot of three-dimensional finite difference mesh generation. The traditional staircase finite difference mesh generation algorithm mainly includes ray casting algorithm and slicing algorithm. Based on the traditional serial ray casting algorithm, a parallel staircase finite difference mesh generation algorithm based on GPU (graphic processing unit) is proposed in this paper. Parallel algorithm uses batch-based data transmission strategy, which makes the scale of mesh generation independent of GPU memory size, and balances the relationship between data transmission efficiency and mesh generation scale. In order to reduce the time consumption of data transmission between the host memory and the device memory, the parallel algorithm proposed in this paper can generate ray starting coordinates independently within GPU threads, which further improves the execution efficiency and parallelization degree of the parallel algorithm. The comparison of numerical experiments shows that the efficiency of parallel algorithm is much higher than that of traditional ray casting algorithm. Finally, an example of finite difference calculation shows that the parallel algorithm can meet the requirement of large-scale numerical simulation of complex models.