A More Efficient Parallel Method For Neighbour Search Using CUDA

Abstract

In particle systems simulation, the procedure of neighbour searching is usually a bottleneck in terms of computational cost. Several techniques have been developed to solve this problem; one of particular interest is the cell-based spatial division, where each cell is tagged by a hash function. One of the most useful features of this technique is that it can be easily parallelized to reduce computational costs. However, the parallelizing process has some drawbacks associated to data memory management. Also, when parallelizing neighbour search, the location of neighbouring particles between adjacent cells is also costly. To solve these shortcomings we have developed a method that reduces the search space by considering the relative position of each particles in its own cell. This method, parallelized using CUDA, shows improvements in processing time and memory management over other ''standard'' spatial division techniques.