论文部分内容阅读
粒子碰撞检测是为了发现整个场景所有粒子之间存在的物理相互作用,在离散元方法(Discrete Element Method,简称DEM)[1]、分子动力学(Molecular Dynamics,简称MD)[2][3]和流体动力学(Smoothed Particle Hydrodynamics)[4]等许多领域有着非常重要的作用。粒子仿真通常都是将连续时间划分成许多小的时间片,每经过一个时间片进行一次计算,再更新粒子的状态,而在每次计算中有个非常耗时的过程就是检测所有粒子对之间是否发生物理碰撞[5],所以粒子间的碰撞检测算法一定程度上决定了实际物理模拟的效果。随着人们研究的问题越来越复杂,粒子规模变得越来越大,如果直接两两进行碰撞检测,那么时间复杂度就是2O(n),在大规模的粒子系统中是不可接受的,所以研究者提出了许多复杂度为O(nlogn)和O(n)的算法,包括ADT(Alternating Digital Tree)[6],ASDT(Augmented Spatial Digital Tree)[7],链式单元法(Linked-Cell Method)[8][9][10],NBS(no binary search)[11],单层盒(Level Boxing)[12],多层次盒(Multilevel Boxing)[12][13][14][16][17][18][19],索引盒(Indexed-level Boxing)[12],多层次网格(Multigrid Contact Detection Method,简称MGCD)[20]等,在不同的场景中选择适当的算法会达到更好的效果。同时,随着不同的并行编程模型的快速发展,将粒子碰撞检测算法并行化成了一种非常有效的提高效率的手段。本文在深入理解各个碰撞检测算法以及并行化手段的基础上,提出两种基于多层次碰撞检测技术的并行化算法(以下称为算法二和算法三)。不同于传统的直接等分空间(以下称为算法一)来实现并行化,算法二和算法三都采用预估计算量来达到负载均衡,算法二通过计算量来划分空间以实现并行化,算法三考虑到划分空间产生的边界问题以及由粒子运动产生的负载不均衡,先按照粒子大小将空间分层,然后按照计算量和空间层次划分粒子数据。最后,使用MPI实现三种算法,设计多组实验场景,算法二和算法三在不同场景下均能较好的达到负载均衡,效率优于算法一;算法三的效率最高,在负载均衡和通信开销上均优于其他两种算法。