2 Replies Latest reply on Jul 4, 2011 1:27 AM by saibbot

    Nonblocking data structures in shared memory




      I am trying to determine whether or not it is possible to implement a nonblocking queue based on compare-and-swap for the SCCs shared memory space.


      I don't know precisely how the instruction (CMPXCHG) is going to interact with memory in a non-cache coherent environment.


      The instruction works like this:


      compare-exchange(shared,old,new) { shared == old ? shared = new : old = shared;}


      but does this atomically. My concern is that when the shared value is read it will may be read from cache instead of shared memory space and I would have no means to ensure the most recent value is being read.


      My idea is to build a fixed length nonblocking queue with a circular list based on a finite array. So long as I can find a way to guarantee that the compare-and-swap is working on the most recent copy of the data I can create a nonblocking queue where multiple enqueues and dequeues can operate concurrently and independently with no additional managment.


      Anyone have any ideas? This is the first project I am working on with the SCC so I am still a bit unfamilliar with all of the architectural peculiarities. Even a push in the right direction would be appreciated.




      Tom B

      Undergraduate, Computer Science

      Rochester Institute of Technology


      Researcher, Parallel Computing

      University of Rochester