Skip to content

Instantly share code, notes, and snippets.

@adam-morrison

adam-morrison/galoisLF.md Secret

Last active December 18, 2015 14:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save adam-morrison/4d332ecf7d6733af4308 to your computer and use it in GitHub Desktop.
Save adam-morrison/4d332ecf7d6733af4308 to your computer and use it in GitHub Desktop.
Download ZIP
Lock-free work lists for Galois
Raw
galoisLF.md

Lock-free work lists for Galois

This patch adds lock-free versions of the chunked FIFO and LIFO work lists to the Galois graph analytics system.

The patch is against Galois 2.2.1.

Important note: The included implementations do not handle memory reclamation and are thus not safe against the ABA problem. They can be safely used with Galois programs that work in phases, in which work lists are first populated and then emptied. In these programs, there are no concurrent insertions and removals, and so the ABA problem cannot occur.

Raw
lockfree.diff
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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment