The following code is a skeleton of an atomic pointer class taken from a simulated annealing application in the PARSEC benchmark suite for shared-memory multiprocessors.
In that application, the central data structure is a graph (more specifically, a netlist of an integrated circuit). Each node in the graph has an attribute indicating its physical location. The algorithm spawns many threads and each thread repeatedly and randomly selects two nodes and exchanges their physical locations if that results in better routing cost for the chip.
Because the graph is huge and any pair of nodes can be chosen by each thread, the only workable solution is a lock-free concurrent data structure (CDS). That's why the following AtomicPtr
class is crucial (it is used to atomically exchange pointers to two physical location objects in a lock-free manner).
The function atomic_load_acq_ptr()
is a defined in assembly code and corresponds closely to std::atomic<T*>::load(memory_order_acquire)
.
I want to implement that CDS using C++11 atomics.
template <typename T>
class AtomicPtr {
private:
typedef long unsigned int ATOMIC_TYPE;
T *p __attribute__ ((aligned (8)));
static const T *ATOMIC_NULL;
inline T *Get() const {
T *val;
do {
val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&p);
} while(val == ATOMIC_NULL);
return val;
}
inline void Swap(AtomicPtr<T> &X) {
// Define partial order in which to acquire elements to prevent deadlocks
AtomicPtr<T> *first;
AtomicPtr<T> *last;
// Always process elements from lower to higher memory addresses
if (this < &X) {
first = this;
last = &X;
} else {
first = &X;
last = this;
}
// Acquire and update elements in correct order
T *valFirst = first->Checkout(); // This sets p to ATOMIC_NULL so all Get() calls will spin.
T *valLast = last->PrivateSet(valFirst);
first->Checkin(valLast); // This restores p to valLast
}
};
The std::atomic<T*>::exchange()
method can only be used to exchange a bare T*
pointer with a std::atomic<T*>
object. How to do exchange of two std::atomic<T*>
objects in a lock-free manner?
What I can think of is that the AtomicPtr
class below can itself be based on std::atomic<T*>
by declaring:
std::atomic<T*> p;
and replacing all atomic_load_acq_ptr()
calls by std::atomic<T*>::load(memory_order_acquire)
and replacing all atomic_store_rel_ptr()
calls by std::atomic<T*>::store(memory_order_release)
. But my first thought was that std::atomic<T*>
should replace AtomicPtr
itself and there may be a clever way to exchange std::atomic<T*>
objects directly. Any thoughts?
std::atomic
s in C++11.AtomicPtr
class already does it by following a check-out\check-in discipline: 1- Any thread that wants to do a swap first checks out the pointer (by writing a sentinel value calledATOMIC_NULL
above) and, when done, checks it in. 2- Any thread that wants to read (i.e., Get()) the pointer value has to keep spinning if the pointer has been checked out.std::atomic<T*>
?