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

    Nonblocking data structures in shared memory

    tbottom

      Hello.

       

      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.

       

      Thanks,

       

      Tom B

      Undergraduate, Computer Science

      Rochester Institute of Technology

      --

      Researcher, Parallel Computing

      University of Rochester