Abstract: Particle-based methods are widely applied in the resolving of complex multi-scale physical phenomena in various science and engineering areas. In order to handle the challenge of increasing computational complexity and declining concurrency for the pair-wised particle searching procedure in massive multi-scale particle-based simulations, a new parallel fast neighbor searching algorithm, which features high-concurrency and low memory footprint, is developed and demonstrated on both many-core CPU and GPU architectures. An inter-level interaction strategy based on the concept of hierarchical nested data structure is proposed to resolve the issue of racing condition in cross-level particle search. An asymmetric mapping method is developed to eliminate the full mapping of particles on each level, which reduces the memory consumption. A set of numerical experiments show that, the proposed algorithm can handle multi-scale problems with particle volume ratio up to 108. Compared with traditional algorithm, the proposed algorithm can achieve 2x~8x speedups and lower memory consumption. The GPU-based implementation of the algorithm achieves state-of-the-art computational efficiency.

Key words: particle-based method, multi-scale simulation, fast neighbor searching, parallel computing