sort particles per mesh cell

[alecjohnson]

Particles are currently sorted by MPI subdomain. If one only uses MPI parallelization, then this allows for efficient pushing of particles and summing of moments as long as 10_nxn_nyn_nzn_sizeof(double) fits in cache. But to support effective use of vector units (such as on Intel's Xeon and Xeon Phi processors) to push particles and sum moments, we need to sort particles at the level of individual mesh cells.

Sorting particles at the cell level will have benefits that extend beyond vectorization. Benefits of this fine-grain particle locality include:

• ability to relax the particle distribution to Maxwellian. This will allow for smooth coupling of iPic3D to fluid models.
• ability to efficiently merge and appropriately split or resample particles. This can be used to maintain appropriate resolution of velocity space.
• ability to collide particles. This would allow to extend use of iPic3D to problems that involve interacting species.

If particles are sorted per mesh cell then we can vectorize the task of a single iteration of pushing all particles positioned in a given cell, because pushing them uses the same field data. Note that with each iteration of the particle solver, the position (xp, yp, zp) used to interpolate from the field is updated, and the particles need to be resorted.

To sort particles at the cell level, we can sort by the Z-value of the cell in the mesh of each MPI process. The Z-value is computed by interleaving the bits of the x, y, and z array indices. We can adapt the multisort code that Maria Elena and I worked with at the workshop at Barcelona Supercomputing Centre in July in order to do fast, thread-safe sorting based on the Z-value. An alternative would be to simply walk through the particles and move them if necessary to the correct cell, but doing this in a thread-safe way would take some care.