Hash Functions and GPU Algorithm of Infinite Grid Method for Contact Search


  • Ruslan Pacevič Vilnius Gediminas Technical University
  • Arnas Kačeniauskas Vilnius Gediminas Technical University, Lithuania




parallel computing, GPGPU computing, OpenCL, contact search, infinite grid method, discrete element method, hash functions


The paper presents the memory-saving GPU algorithm of the infinite grid method with various hash functions
for contact search in discrete element computations. The implemented hash table of fixed size has the added
benefit of allowing the grid to be potentially infinite in size, which is particularly suitable for a large number
of discrete particles, moving in large computational domains with empty regions. Research on the application
of various hash functions and hash table sizes was performed to preserve the computational performance of
the developed memory-saving GPU algorithm and its OpenCL implementation. The performance of the developed software was evaluated by solving the hopper fill and discharge as well as the artificial avalanche problems
on the NVIDIA® Tesla™ P100 GPU. The performance achieved by using the memory-saving implementation
of contact search was compared with that attained by using the standard implementation of the uniform grid
method. The performed analysis revealed that the developed GPU algorithm and its OpenCL implementation
reduced the GPU memory consumed by the uniform grid method up to 69.7 times, which resulted in the contact
search memory equal to 1.86% of the total memory required by DEM computations. Moreover, the application
of the Morton hash function and the proper hash table size allowed for preserving high computational performance of the infinite grid method and the developed GPU software.

Author Biographies

Ruslan Pacevič, Vilnius Gediminas Technical University

Department of Graphical Systems, Associate Professor

Arnas Kačeniauskas, Vilnius Gediminas Technical University, Lithuania