An improved particle neighbor search algorithm with multi-level cache optimization strategy for discrete element method using GPU
李弘泽，冯春*，冯吉利*
Keywords: Neighbor search; Discrete element method; Morton encoding; Cell linked list method; Verlet table method
DOI: 10.1016/j.partic.2025.09.013
本文提出一种面向大规模颗粒系统模拟的改进型邻居搜索算法。该算法将模拟空间划分为规则网格，并结合Morton编码，以确保相邻网格在内存中也保持相邻，从而提升数据访问的局部性，降低缓存未命中率；在粒子排序阶段，利用Morton编码对粒子进行重排，增强内存连续性，充分发挥硬件缓存预取机制；引入Verlet表思想，通过设定排序阈值，以避免重复计算和不必要的排序操作。通过上述措施构建了一种多级缓存优化策略，显著提升了计算效率与内存利用效率。由试验结果进一步验证了该算法在大规模颗粒模拟中的显著优势，同时兼具高效性与可扩展性。
相关研究成果发表于PARTICUOLOGY（Volume 107），欢迎感兴趣的读者扫描下方二维码或者点击文末“阅读原文”进入ScienceDirect官网阅读、下载！
亮点
1. 提出一种面向大规模颗粒系统模拟的改进型邻居搜索算法
2. 在网格划分、粒子排序及排序优化模块中，算法结合了Cell linked list方法与Morton编码以及Verlet表的思想
3. 算法通过多重措施，构建了一种多级缓存优化策略，显著提升了计算效率与内存利用效率
研究背景
离散元方法（DEM）是一种模拟颗粒材料行为的重要工具，广泛应用于岩土、制药、化工等诸多领域。随着模拟规模的扩大，甚至扩大至数百万乃至数十亿颗粒，导致传统的邻居搜索算法遇到了计算瓶颈。尽管Graphics Processing Units（GPU）并行计算为加速DEM提供了新途径，但现有的方法在内存访问效率、负载均衡和算法扩展性等方面仍面临挑战。因此，亟需开发高效的邻居搜索算法来提升大规模颗粒模拟性能。
要点精读
1. 计算域离散化
算法首先将空间划分为均匀网格，并将粒子映射到对应网格中，以避免全粒子对距离计算的复杂度；随后采用Morton编码将网格坐标转化为一维哈希值，使物理相邻的网格在内存中也相邻，从而保持空间局部性，如图1所示。这种设计显著提升了GPU缓存命中率，减少了显存访问延迟，同时Morton编码计算简单、易于并行化，在算法层面形成隐式缓存机制，有效提升了粒子数据访问效率。
图1. 网格单元的Morton哈希索引示意图
2. 基于阈值的排序优化
通过保持空间与内存局部性，排序可以显著提升邻居搜索效率。但另一方面，排序本身也是一种消耗计算资源的过程。当粒子数庞大时，频繁的重排会抵消性能收益。由此，借鉴Verlet表的思想，引入排序阈值动态控制重排频率，如图2所示，先按Verlet系数计算包围边界Rskin，每步累计粒子位移，仅当任一粒子越过Rskin时才触发全局重排，从而在保证精度的同时减少了不必要的排序。与传统Verlet表方法相比，该策略仅通过阈值隐式缓存粒子相对位置而无需额外内存维护Verlet列表，既降低了内存占用，又消除了列表维护，形成算法级隐式缓存机制，显著降低了计算成本，提升了整体性能。
图2. 排序阈值示意图
3. 粒子重排
通过粒子重排，使同一网格单元内的粒子信息在内存中变为连续存储。访问同一网格内的粒子时，数据地址相邻，GPU可一次性加载，提高了缓存命中率。如图3所示，算法流程可分为三步：①将所有粒子映射到对应网格；②按网格的Morton哈希值升序，重排粒子索引，并同步重排位置、速度等全部属性，以保持数据一致；③记录每个网格首尾粒子的新索引。后续只需根据首尾索引即可快速定位该网格的全部粒子，再搜索相邻网格，即可构建邻居列表。重排后的连续性显著降低了显存访问的延迟，从而提高了整体计算效率。
图3. 排序过程示意图
4. 算法验证
分别对60万、80万、100万和120万粒子组成的立方体坍塌过程进行了模拟。1万步迭代内，本文提出的算法运行时间分别为496秒、668秒、833秒和1011秒。而对于100万粒子的案例，采用CPU串行的Cell linked list方法运行耗时约21.8小时。相比之下，本文提出的优化算法实现了94倍的加速。另外，显存占用呈线性增长，依次为3.6GB、4.4GB、5.3GB和6.1GB。结果表明，对于大规模颗粒系统，即使达到百万颗粒级别，算法仍保持高计算效率和良好的可扩展性。
图4. 大规模颗粒塌落过程模拟
主要结论与展望
本文提出一种粒子邻居搜索算法，通过多级缓存优化策略，显著提升了大规模颗粒系统模拟的效率。在网格划分、粒子排序及排序优化等模块中，算法融合了Morton编码、硬件缓存机制与Verlet表思想，有效降低了内存访问延迟和计算复杂度，使计算性能得以全面提升。尤其在处理大规模颗粒系统时，通过优化空间局部性和内存使用，大幅提高了计算速度与内存效率，为涉及颗粒材料系统模拟的工业应用提供了一种可行方案。未来研究可继续探索更多排序优化策略，以进一步提升算法在更加复杂环境下的计算性能。
通讯作者简介
冯春，中国科学院力学研究所，项目研究员。主要从事连续-非连续耦合数值分析方法、岩土工程及爆炸冲击领域自主CAE软件开发等方面的研究。主导研发了连续-非连续数值分析系统（CDEM），在模拟静动载荷及多场耦合下固体材料渐进破坏过程方面具有明显优势，已被国内百余家单位使用，成功服务于岩土、采矿、交通、水电、爆破等多个领域的科学研究及工程分析。发表相关学术论文百余篇。先后主持国家科技重大专项课题1项，国家重点研发计划项目课题2项，重大企业委托项目10余项等，获省部级及一级行业学会奖10余项。
供稿：原文作者
排版：《颗粒学报》编辑部
文章信息
Li, H., Feng, C., & Feng, J. (2025). An improved particle neighbor search algorithm with multi-level cache optimization strategy for discrete element method using GPU. Particuology, 107, 1-10. https://doi.org/10.1016/j.partic.2025.09.013.