基于纯矩阵运算的粒子系统邻域搜索快速算法及其在离散元模拟中的高性能计算应用

《Powder Technology》：Fast matrix computing method of neighbor searching for particle systems

本文提出了一种基于纯矩阵运算的新型邻域搜索算法，通过替换、排序和算术计算等矩阵操作构建邻域矩阵，有效解决了传统链表法在计算速度和复杂度上的瓶颈。该算法在200至2,000,000元素范围内展现出最高约13倍的速度优势，且因其矩阵化特性高度适配GPU计算，为粒子系统（如DEM、SPH）的大规模仿真提供了高性能解决方案。

　　

^亮点聚焦

^{算法的基本思想}

该算法的核心在于通过特定操作高效缩小邻域元素的搜索范围（就像用智能筛网快速过滤目标）。初步筛选后，再通过距离验证来最终确定邻域矩阵（好比用精密卡尺进行最终测量）。

首先，算法根据元素坐标和相互作用半径确定背景网格的大小（图1b）。随后将计算区域离散化为一系列均匀单元（图1c）。这里的关键发现是：每个元素的潜在邻居仅存在于其自身所在单元及相邻单元中。通过将元素系统性地分配到这些单元中，算法大幅减少了需要直接进行距离检查的元素对数量。

^{离散元法及建模软件}

本研究提出的邻域搜索算法为离散元法（DEM）中的传统邻域搜索方法提供了一种新颖高效的替代方案。在DEM实现中，该算法通过将邻域搜索重新表述为一系列矩阵运算，使其具有高度可并行性，更适用于高性能GPU。

在DEM框架中，岩土系统被建模为离散颗粒的集合，其相互作用由牛顿第二定律控制。每个颗粒的运动和相互作用通过显式时间积分方案进行求解。所提出的算法通过提供所有颗粒的邻域矩阵，无缝集成到DEM计算循环中。该矩阵便于在单个时间步内有效计算接触力。

^{GPU架构对算法效率的影响}

GPU硬件性能在决定邻域搜索算法的计算效率方面起着关键作用，尤其是在处理大规模粒子系统时。为了系统评估这种关系，我们使用标准的立方密排颗粒模型进行了一系列基准测试，遵循第3章建立的实验设置。这些数值测试使用CUDA 12.2版和Python 3.12.8进行。这些测试中的颗粒数量从100,000到1,000,000不等。测试平台配备了NVIDIA GeForce RTX 4090 GPU和Intel Core i9-14900K CPU。

结果表明，随着GPU计算核心数量和内存带宽的增加，算法性能显著提升。对于超过500,000个颗粒的系统，在高端GPU上观察到近乎线性的加速比。然而，也发现当颗粒数量超过GPU的并行处理能力时，性能会达到平台期。这凸显了根据目标问题规模优化GPU硬件选择的重要性。

^结论

本研究提出了一种基于纯矩阵运算的新型邻域搜索算法，显著加速了基于粒子的模拟中的邻域搜索。传统方法依赖动态链表和嵌套循环来计算可变的粒子相互作用。与这些方法不同，所提出的方法在加速大规模DEM模拟方面特别有效。它通过使用纯矩阵运算（包括替换、排序和算术计算）来实现这种加速，这些运算天然适合GPU的并行架构。数值实验证明，该算法在200到2,000,000个元素的测试范围内，其速度始终优于传统的链表方法，最高性能优势可达约13倍。该算法为高性能计算环境下的高效粒子模拟铺平了道路。