面向离散粒子多尺度分析CPU/GPU架构的并行近邻搜索算法  

A parallel fast neighbor searching algorithm for particle-based methods on CPU and GPU architectures in multi-scale simulation

作　　者：代长威 孔瑞林 季哲 DAI Chang-wei;KONG Rui-lin;JI Zhe(School of Software,Northwestern Polytechnical University,Xi’an 710129;Yangtze River Delta Research Institute,Northwestern Polytechnical University,Suzhou 215400;Shenzhen Research Institute,Northwestern Polytechnical University,Shenzhen 518063,China)

机构地区：[1]西北工业大学软件学院,陕西西安710129 [2]西北工业大学太仓长三角研究院,江苏苏州215400 [3]西北工业大学深圳研究院,广东深圳518063

出　　处：《计算机工程与科学》2024年第8期1349-1360,共12页Computer Engineering & Science

基　　金：中央高校基本科研业务费专项资金(D5000210971);广东省基础与应用基础研究基金(2022A1515110314)。

摘　　要：离散粒子法在解决前沿科学和工程领域中的复杂多尺度问题中具有广泛的应用。针对离散粒子大规模多尺度计算中相邻粒子对搜索过程计算复杂度显著增加和并发度下降的问题,提出了一种适用于众核架构(CPU/GPU)的高并发、低内存占用并行近邻搜索算法。通过提出一种基于多层嵌套网格概念的层间相互作用方法,解决了不同层级间粒子对相互搜索时的数据竞争问题;通过引入非对称映射方法,避免了粒子在多级链表上的全映射,降低了内存消耗。一系列数值实验表明,该算法可有效处理108量级粒子体积跨度变化的多尺度问题,相较于传统算法可取得2~8倍的加速效果和更低的内存消耗特性,基于GPU的算法实现可达到当前领先的计算效率。Particle-based methods are widely applied in the resolving of complex multi-scale physical phenomena in various science and engineering areas.In order to handle the challenge of increasing computational complexity and declining concurrency for the pair-wised particle searching procedure in massive multi-scale particle-based simulations,a new parallel fast neighbor searching algorithm,which features high-concurrency and low memory footprint,is developed and demonstrated on both many-core CPU and GPU architectures.An inter-level interaction strategy based on the concept of hierarchical nested data structure is proposed to resolve the issue of racing condition in cross-level particle search.An asymmetric mapping method is developed to eliminate the full mapping of particles on each level,which reduces the memory consumption.A set of numerical experiments show that,the proposed algorithm can handle multi-scale problems with particle volume ratio up to 108.Compared with traditional algorithm,the proposed algorithm can achieve 2x~8x speedups and lower memory consumption.The GPU-based implementation of the algorithm achieves state-of-the-art computational efficiency.

关 键 词：离散粒子法 多尺度分析 近邻搜索 并行算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]