Analysis of parallel spatial partitioning algorithms for GPU based DEM

The capability of solving a geotechnical discrete element method (DEM) applications is determined by the complexity of the simulation and its computational requirements. Collision detection algorithms are fundamental to resolve the mechanical collisions between millions of particles efficiently. These algorithms are a bottleneck for many DEM applications resulting in excessive memory usage or poor computational performance. In particular, for GPU based DEM, there are many factors for a user to consider when deciding on an algorithm. This study discusses a set of diverse classes of geotechnical problems and the impact of algorithm choice. Four factors were considered: i) the world domain size, number of particles and particle density, ii) polydispersity in size, iii) the time evolution and iv) the particle shape. This study shows that for spherical particles, the choice of broad-phase collision detection algorithm has the most impact on computational performance. The computational cost for convex polyhedral particles is dominated by the selection of the particles' bounding volumes and their intersection tests over the selection of the broad-phase collision detection algorithm. On average for convex polyhedral particles, the broad-phase occupies at most 1.3% of the total runtime, while the narrow-phase collision detection and collision response require more than 87% of the runtime. A combination of bounding spheres and axis-aligned bounding boxes for use as bounding volumes of particles showed the best performance reducing the computational cost by 20%. This study serves as a guide for further research in the field of GPU based DEM collision detection and the application in geotechnics.