相关疑难解决方法(0)

以下代码是一个原子指针类的框架,它取自PARSEC基准套件中用于共享内存多处理器的模拟退火应用程序.

在该应用中,中央数据结构是图(更具体地,集成电路的网表).图中的每个节点都有一个指示其物理位置的属性.该算法产生许多线程并且每个线程重复并随机选择两个节点并交换它们的物理位置,如果这导致芯片的更好的路由成本.

因为图形很大并且每个线程都可以选择任何一对节点,所以唯一可行的解​​决方案是无锁并发数据结构(CDS).这就是为什么以下AtomicPtr类是至关重要的(它用于以无锁方式原子地交换指向两个物理位置对象的指针).该函数atomic_load_acq_ptr()是在汇编代码中定义的并且与之紧密对应std::atomic<T*>::load(memory_order_acquire).

我想用C++ 11原子实现该CDS.

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 …