Hi. I am using CUDA for parallel processing of moving particles.
I am struggling to write an alogithm to implement particle shifting from cell to cell.
Here is a logic. There are millions of particles and each of these particles are connected to a certain cell number depending on their positions.
Each particle has the information (cell No., and the cell slot No.). In the meantime, cells are also having the list of particles which belong to itself.
For example, if the cellno 10 has particles of No.1,No.4,No.7 and No.9.
there are a double array named ‘cellplist(cellnumber,slotnumber)’ and
==> cellplist(10,0)=1, cellplist(10,1)=4, cellplist(10,2)=7, and cellplist(10,3)=9;
also, there are two arrays named cellidx(particleno), and cellslot(particleno)
==> cellidx(1)=10; cellslot(1)=0; (cellidx is cell no. and cellslot is cell slot number)
There is a possibility that particle can shift from a cell to another.
Let us assume that at a certain point, the particle No.7 moves from cell No.10, to cell No.11 (the cells are not necessarily to adjacent).
Then, I want to vacate the original slot, and then write the particle information(No.7) to the cell 11.
To do this in PARALLEL, there is a buffer array named ‘cellpfresh(cellnumber,100)’. After the particle shift detects, I am trying to write the cellpfresh(11,s)=7. Here, the slot number s is a random number between 0-99 (doesn’t have to be written orderly). The maximum number of particle that can move into a slot simultaneously is around 10-20, so the space itself (100 slot for each cell) is enough.
However, The PROBLEM is, there is a possibility that one slot is ‘overwritten’ by two threads. If I make the number of slot larger, the possibility may decrease, but it’s not zero (and also memory waste becomes larger).
Can anyone give me a suggestion to avoid the overwritting? Once the ‘cellpfresh’ list is written without overwritting, I can’t re-arrage the ‘cellplist’ by sorting cellfresh and cellplist.