An Improved Parallel Technique for Neighbour Search on CUDA

Abstract

In Computer Graphics is usual the modelling of dynamic systems through particles. The simulation of liquids, cloths, gas, smoke... are highlighted examples of that modelling. In this scope, is particularly relevant the procedure of neighbour particles searching, which represents a bottleneck in terms of computational cost. One of the most used searching techniques is the cell– based spatial division by cubes, where each cell is tagged by a hash value. Thus, all particles located into each cell have the same tag and are the candidate to be neighbours. The most useful feature of this technique is that it can be easily parallelized, what reduces the computational costs. Nevertheless, the parallelizing process has some drawbacks associated with data memory management. Also, during the process of neighbour search, it is necessary to trace into the adjacent cells to find neighbour particles, as a consequence, the computational cost is increased. To solve these shortcomings, we have developed a method that reduces the search space by considering the relative position of each particle in its own cell. This method, parallelized using CUDA, shows improvements in processing time and memory management over other “standard” spatial division techniques. (see http://www.acm.org/about/class/class/2012)