|
diff --git a/include/Galois/WorkList/Chunked.h b/include/Galois/WorkList/Chunked.h |
|
index 932f5e5..de760e0 100644 |
|
--- a/include/Galois/WorkList/Chunked.h |
|
+++ b/include/Galois/WorkList/Chunked.h |
|
@@ -270,6 +270,14 @@ template<int ChunkSize=64, typename T = int, bool Concurrent=true> |
|
class ChunkedLIFO : public ChunkedMaster<T, ConExtLinkedStack, false, true, ChunkSize, Concurrent> {}; |
|
GALOIS_WLCOMPILECHECK(ChunkedLIFO) |
|
|
|
+template<int ChunkSize=64, typename T = int, bool Concurrent=true> |
|
+class ChunkedLockFreeLIFO : public ChunkedMaster<T, ConExtLinkedLockFreeStack, false, true, ChunkSize, Concurrent> {}; |
|
+GALOIS_WLCOMPILECHECK(ChunkedLockFreeLIFO) |
|
+ |
|
+template<int ChunkSize=64, typename T = int, bool Concurrent=true> |
|
+class ChunkedLockFreeFIFO : public ChunkedMaster<T, ConExtLinkedLockFreeQueue, false, false, ChunkSize, Concurrent> {}; |
|
+GALOIS_WLCOMPILECHECK(ChunkedLockFreeFIFO) |
|
+ |
|
/** |
|
* Distributed chunked FIFO. A more scalable version of {@link ChunkedFIFO}. |
|
* |
|
diff --git a/include/Galois/WorkList/WorkListHelpers.h b/include/Galois/WorkList/WorkListHelpers.h |
|
index b2c0ff2..523e537 100644 |
|
--- a/include/Galois/WorkList/WorkListHelpers.h |
|
+++ b/include/Galois/WorkList/WorkListHelpers.h |
|
@@ -42,6 +42,21 @@ public: |
|
}; |
|
|
|
template<typename T> |
|
+class ConExtValListNode { |
|
+ ConExtValListNode<T>* next; |
|
+ T* value; |
|
+public: |
|
+ ConExtValListNode() : next(0), value(0) {} |
|
+ ConExtValListNode<T>*& getNext() { return next; } |
|
+ ConExtValListNode<T>*const& getNext() const { return next; } |
|
+ T*& getValue() { return value; } |
|
+ T*const& getValue() const { return value; } |
|
+ inline bool CAS(ConExtValListNode<T>* oldval, ConExtValListNode<T>* newval) { |
|
+ return __sync_bool_compare_and_swap(&next, oldval, newval); |
|
+ } |
|
+}; |
|
+ |
|
+template<typename T> |
|
class ConExtIterator: public boost::iterator_facade< |
|
ConExtIterator<T>, T, boost::forward_traversal_tag> { |
|
friend class boost::iterator_core_access; |
|
@@ -62,6 +77,146 @@ public: |
|
explicit ConExtIterator(T* x): at(x) { } |
|
}; |
|
|
|
+// Michael & Scott's lock-free FIFO queue |
|
+template<typename T, bool concurrent> |
|
+class ConExtLinkedLockFreeQueue { |
|
+ Runtime::MM::FixedSizeAllocator heap; |
|
+ Runtime::LL::CacheLineStorage<Runtime::LL::PtrLock<ConExtValListNode<T>, concurrent>> head; |
|
+ Runtime::LL::CacheLineStorage<Runtime::LL::PtrLock<ConExtValListNode<T>, concurrent>> tail; |
|
+ |
|
+public: |
|
+ typedef ConExtValListNode<T> ListNode; |
|
+ |
|
+ ConExtLinkedLockFreeQueue() : heap(sizeof(ListNode)) { |
|
+ ListNode *n = new (heap.allocate(sizeof(ListNode))) ListNode(); |
|
+ head.data.setValue(n); |
|
+ tail.data.setValue(n); |
|
+ } |
|
+ |
|
+ bool empty() const { |
|
+ return head.data.getValue() == tail.data.getValue(); |
|
+ } |
|
+ |
|
+ void push(T* C) { |
|
+ ListNode* last; |
|
+ ListNode* next; |
|
+ |
|
+ ListNode* n = new (heap.allocate(sizeof(ListNode))) ListNode(); |
|
+ n->getValue() = C; |
|
+ |
|
+ while (true) { |
|
+ last = tail.data.getValue(); |
|
+ next = last->getNext(); |
|
+ |
|
+ if (last != tail.data.getValue()) |
|
+ continue; |
|
+ |
|
+ if (!next) { |
|
+ if (last->CAS(next, n)) |
|
+ break; |
|
+ } else { |
|
+ tail.data.CAS(last, next); |
|
+ } |
|
+ } |
|
+ |
|
+ tail.data.CAS(last, n); |
|
+ } |
|
+ |
|
+ T* pop() { |
|
+ T* first; |
|
+ T* ret; |
|
+ |
|
+ while (true) { |
|
+ ListNode* first = head.data.getValue(); |
|
+ ListNode* last = tail.data.getValue(); |
|
+ ListNode* next = first->getNext(); |
|
+ |
|
+ if (first != head.data.getValue()) |
|
+ continue; |
|
+ |
|
+ if (first == last) { |
|
+ if (!next) |
|
+ return 0; |
|
+ tail.data.CAS(last, next); |
|
+ } else { |
|
+ ret = next->getValue(); |
|
+ if (head.data.CAS(first, next)) { |
|
+ heap.deallocate(first); |
|
+ break; |
|
+ } |
|
+ } |
|
+ } |
|
+ |
|
+ return ret; |
|
+ } |
|
+ |
|
+ //! iterators not safe with concurrent modifications |
|
+ typedef T value_type; |
|
+ typedef T& reference; |
|
+ typedef ConExtIterator<T> iterator; |
|
+ typedef ConExtIterator<const T> const_iterator; |
|
+ |
|
+ iterator begin() { return iterator(head.data.getValue()); } |
|
+ iterator end() { return iterator(); } |
|
+ |
|
+ const_iterator begin() const { return const_iterator(head.data.getValue()); } |
|
+ const_iterator end() const { return const_iterator(); } |
|
+}; |
|
+ |
|
+// Treiber's lock-free LIFO queue |
|
+template<typename T, bool concurrent> |
|
+class ConExtLinkedLockFreeStack { |
|
+ Runtime::LL::CacheLineStorage<Runtime::LL::PtrLock<T, concurrent>> head; |
|
+ |
|
+public: |
|
+ typedef ConExtListNode<T> ListNode; |
|
+ |
|
+ bool empty() const { |
|
+ return !head.data.getValue(); |
|
+ } |
|
+ |
|
+ void push(T* C) { |
|
+ T* oldhead(0); |
|
+ |
|
+ while (true) { |
|
+ oldhead = head.data.getValue(); |
|
+ C->getNext() = oldhead; |
|
+ |
|
+ if (head.data.CAS(oldhead, C)) |
|
+ break; |
|
+ } |
|
+ } |
|
+ |
|
+ T* pop() { |
|
+ T* oldhead; |
|
+ |
|
+ while (true) { |
|
+ oldhead = head.data.getValue(); |
|
+ |
|
+ if (!oldhead) |
|
+ break; |
|
+ |
|
+ T* C = oldhead->getNext(); |
|
+ |
|
+ if (head.data.CAS(oldhead, C)) |
|
+ break; |
|
+ } |
|
+ return oldhead; |
|
+ } |
|
+ |
|
+ //! iterators not safe with concurrent modifications |
|
+ typedef T value_type; |
|
+ typedef T& reference; |
|
+ typedef ConExtIterator<T> iterator; |
|
+ typedef ConExtIterator<const T> const_iterator; |
|
+ |
|
+ iterator begin() { return iterator(head.data.getValue()); } |
|
+ iterator end() { return iterator(); } |
|
+ |
|
+ const_iterator begin() const { return const_iterator(head.data.getValue()); } |
|
+ const_iterator end() const { return const_iterator(); } |
|
+}; |
|
+ |
|
template<typename T, bool concurrent> |
|
class ConExtLinkedStack { |
|
Runtime::LL::PtrLock<T, concurrent> head; |