Balancing core load when number of particles in cells vary (PIC on GPU)

Question

Consider this basic scheme for particle in cell simulations ( with just short-range interactions ):

1. assign particles to disjunct cells
2. for cell $A$ go over neighboring cells $B$
   • for each particle $a_i$ in $A$ interact with all $b_i$ in $B$
3. move all particles

For GPU is very important memory locality. Therefore it make sense to assign each cell-cell interaction $(A,B)$ to one work-group, which can share __local buffer of $a_i$s. But it may very well happen that some cells are empty and other are filled with very varying numbers of particles $n$. => each work group would have to process very different number of interaction $N = n_A . n_B$ between particle pairs $(a_i,b_i)$. They will have problem to synchronize.

I guess this is some commonplace problem in PIC, GPGPU and parallel computing. But I have seen just introductory tutorials and codes, without much care of optimizations. I would be happy for reference to good and concise learning resources.

Answer 1

You ought to be interested in this preprint in which we discuss exactly the sort of questions you seem to be having: https://arxiv.org/abs/1612.03369