CODEWITHSUNDEEP
algorithmdata-structuresparallel-processinggpgpu
geometrian
geometrian

Reputation: 15387

Data Structure Parallel Add Serial Remove Needed

I'm working on a dynamically branching particle system on the GPU. I need a parallel data structure with the following properties:

  1. One thread must be able to remove elements one by one, in constant time. The element returned isn't important to the algorithm--just so long as some element is returned when nonempty. For extra awesomeness, change to any number of threads.
  2. Any number of threads must be able to add elements to the data structure in constant time. Note that some locking is allowed, (and necessary) but it must still scale with no relation on the number of threads. I.e., more threads shouldn't slow it down.

Basic synchronization primitives (mutexes, semaphores), and anything that can be implemented using them, are available.

I had toyed with the idea of a linked list, but this violates condition two (since adding would be O(m) for m threads, since locking must be taken into consideration). I'm not sure such a data structure exists--but I thought I would ask.

Upvotes: 1

Views: 138

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Without knowing more about how you want your data organized (sorted? FIFO? LIFO?) I'm. Or sure whether I can give you an exact answer. However, what you're describing sounds like the definition of a lock-free structure. Lock-free implementations of stacks and queues exist, which do support O(1) insertions and deletions even when there are a lot of threads modifying the structure concurrently. They're usually based on atomic test-and-set operations.

If locks are okay and you just want a highly-concurrent data structure that's sorted, consider looking into concurrent skip lists, which provide O(log n) sorted insertion and deletion with multiple active threads.

Hope this helps!

Upvotes: 1

Related Questions