Linked Lists

Is it possible to create linked lists on a device in CUDA dynamically?

If so, is this done via the usual way in C?

If not, why not?

The reason I ask this is because I am looking to find all interactions between fluid particles. The algorithm I have been working on lately has been lifted straight from a book and translated into CUDA, and although has been implemented in CUDA on several C870 it is still slower than expected. This involved creating pairs of interactions saved in int arrays of a static size, and to calculate any physical property would mean looping over these arrays. The benefit of this is that the particle interactions are found only once.

But I recently came across a paper describing body interactions which uses shared memory in a tiled algorithm. This could be much faster than the algorithm I am using now but it would involve having to find all the interactions again and again if I wanted calculate other physical properties, such as aritificial viscosity.

I could declare static arrays with a maximum number of interactions per particle, but I would rather have ALL interactions saved only once, and for this I see linked lists as the solution. Hence my question.

Except that you will have to do the memory management yourself (you can not call malloc from your kernel) and that you have to be very, very careful to avoid getting horrible performance (e.g. due to uncoalesced reads) it is the same I’d say.