Reordering Optimization for GPU Implementation of Particle-in-Cell Method

Particle-In-Cell (PIC) method is widely used for plasma simulation and the GPUs appear to be the most efficient way to run this method. In this work we propose a technique that enables to speedup one of the most time-consuming operations in the GPU implementation of the PIC method. The operation is particle reordering, or redistribution of particles between cells, which is performed after pushing. The reordering operation provides data locality which is the key performance issue of the PIC method. We propose to divide the reordering into two stages. First, gather the particles that are going to leave a particular cell into buffer arrays, the number of arrays being equal to number of neighbour cells (26 for 3D case). Second, each  neighbour cell copies the particles from the necessary array to her own particle array. Since the second operation is done in 26 threads independently with no synchronization, waiting and involves no critical sections, semaphores, mutexes, atomic operations etc. It results in the more than 10 times reduce of the reordering
time compared to the straightforward reordering algorithm. Futhermore, we eliminate the 26 buffer arrays in the following way: the particles are just labeled instead of moving to buffer array. It enables to keep all the advantages with no memory wasted for buffer arrays.

Keywords

3D model, plasma, GPU, optimization

Acknowledgements
This work was conducted within the framework of the budget project no. 0315-2019-0009 for ICMMG SB RAS.
CUDA implementation was supported by RFBR grant no. 18-07-00364, and the optimization of the algorithm was
partially supported by RFBR grant no. 19-07-00085