Changeset 780a614 for doc/theses/thierry_delisle_PhD
- Timestamp:
- Apr 15, 2021, 1:08:16 PM (3 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 200a229, 76c94bf
- Parents:
- 8590328
- Location:
- doc/theses/thierry_delisle_PhD/code/readyQ_proto
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/readyQ_proto/links.hpp
r8590328 r780a614 117 117 } 118 118 119 long long ts() const {119 unsigned long long ts() const { 120 120 return before._links.ts; 121 121 } -
doc/theses/thierry_delisle_PhD/code/readyQ_proto/links2.hpp
r8590328 r780a614 56 56 template<typename node_t> 57 57 class mpsc_queue : private mcs_queue<node_t> { 58 node_t * volatile head;58 node_t * volatile _head; 59 59 public: 60 mpsc_queue(): mcs_queue<node_t>(), head(nullptr) {}60 mpsc_queue(): mcs_queue<node_t>(), _head(nullptr) {} 61 61 62 62 inline bool empty() const { return mcs_queue<node_t>::empty(); } 63 64 node_t * head() const { return _head; } 63 65 64 66 // Added a new element to the queue … … 66 68 inline node_t * push(node_t * elem) { 67 69 node_t * prev = mcs_queue<node_t>::push(elem); 68 if (!prev) head = elem;70 if (!prev) _head = elem; 69 71 return prev; 70 72 } … … 75 77 // NOT Multi-Thread Safe 76 78 inline node_t * pop(node_t *& next) { 77 node_t * elem = head;79 node_t * elem = _head; 78 80 // If head is empty just return 79 81 if (!elem) return nullptr; … … 81 83 // If there is already someone in the list, then it's easy 82 84 if (elem->_links.next) { 83 head = next = elem->_links.next;85 _head = next = elem->_links.next; 84 86 // force memory sync 85 87 __atomic_thread_fence(__ATOMIC_SEQ_CST); … … 93 95 // at the CAS in advance and therefore can write to head 94 96 // after that point, it could overwrite the write in push 95 head = nullptr;97 _head = nullptr; 96 98 next = mcs_queue<node_t>::advance(elem); 97 99 … … 99 101 // it is the only way we can guarantee we are not overwriting 100 102 // a write made in push 101 if (next) head = next;103 if (next) _head = next; 102 104 } 103 105 -
doc/theses/thierry_delisle_PhD/code/readyQ_proto/work_stealing.hpp
r8590328 r780a614 28 28 template<typename node_t> 29 29 struct __attribute__((aligned(128))) localQ_t { 30 // volatile unsigned long long val = 0; 31 // mpsc_queue<node_t> queue = {}; 32 // spinlock_t lock = {}; 33 intrusive_queue_t<node_t> list; 34 35 inline auto ts() { return list.ts(); } 36 inline auto lock() { return list.lock.lock(); } 37 inline auto try_lock() { return list.lock.try_lock(); } 38 inline auto unlock() { return list.lock.unlock(); } 39 40 inline auto push( node_t * node ) { return list.push( node ); } 41 inline auto pop() { return list.pop(); } 30 #ifdef NO_MPSC 31 intrusive_queue_t<node_t> list; 32 33 inline auto ts() { return list.ts(); } 34 inline auto lock() { return list.lock.lock(); } 35 inline auto try_lock() { return list.lock.try_lock(); } 36 inline auto unlock() { return list.lock.unlock(); } 37 38 inline auto push( node_t * node ) { return list.push( node ); } 39 inline auto pop() { return list.pop(); } 40 #else 41 mpsc_queue<node_t> queue = {}; 42 spinlock_t _lock = {}; 43 44 inline auto ts() { auto h = queue.head(); return h ? h->_links.ts : 0ull; } 45 inline auto lock() { return _lock.lock(); } 46 inline auto try_lock() { return _lock.try_lock(); } 47 inline auto unlock() { return _lock.unlock(); } 48 49 inline auto push( node_t * node ) { return queue.push( node ); } 50 inline auto pop() { return queue.pop(); } 51 #endif 52 53 42 54 }; 43 55 … … 73 85 auto & list = *({ 74 86 unsigned i; 75 do { 87 #ifdef NO_MPSC 88 do { 89 #endif 76 90 tls.stats.push.attempt++; 77 91 // unsigned r = tls.rng1.next(); … … 82 96 i = tls.my_queue + (r % nqueues); 83 97 } 84 } while(!lists[i].try_lock()); 98 #ifdef NO_MPSC 99 } while(!lists[i].try_lock()); 100 #endif 85 101 &lists[i]; 86 102 }); 87 103 88 104 list.push( node ); 89 list.unlock(); 105 #ifdef NO_MPSC 106 list.unlock(); 107 #endif 90 108 // tls.rng2.set_raw_state( tls.rng1.get_raw_state()); 91 109 // count++; … … 95 113 __attribute__((noinline, hot)) node_t * pop() { 96 114 if(tls.my_queue != outside) { 97 if( tls.myfriend == outside ) { 98 auto r = tls.rng1.next(); 99 tls.myfriend = r % numThreads; 100 tls.mytime = lists[(tls.it % nqueues) + tls.my_queue].ts(); 101 // times[tls.myfriend].val = 0; 102 // lists[tls.myfriend].val = 0; 103 } 104 // else if(times[tls.myfriend].val == 0) { 105 // else if(lists[tls.myfriend].val == 0) { 106 else if(times[tls.myfriend].val < tls.mytime) { 107 // else if(times[tls.myfriend].val < lists[(tls.it % nqueues) + tls.my_queue].ts()) { 108 node_t * n = try_pop(tls.myfriend, tls.stats.pop.help); 109 tls.stats.help++; 110 tls.myfriend = outside; 111 if(n) return n; 112 } 115 // if( tls.myfriend == outside ) { 116 // auto r = tls.rng1.next(); 117 // tls.myfriend = r % numThreads; 118 // // assert(lists[(tls.it % nqueues) + tls.my_queue].ts() >= lists[((tls.it + 1) % nqueues) + tls.my_queue].ts()); 119 // tls.mytime = std::min(lists[(tls.it % nqueues) + tls.my_queue].ts(), lists[((tls.it + 1) % nqueues) + tls.my_queue].ts()); 120 // // times[tls.myfriend].val = 0; 121 // // lists[tls.myfriend].val = 0; 122 // } 123 // // else if(times[tls.myfriend].val == 0) { 124 // // else if(lists[tls.myfriend].val == 0) { 125 // else if(times[tls.myfriend].val < tls.mytime) { 126 // // else if(times[tls.myfriend].val < lists[(tls.it % nqueues) + tls.my_queue].ts()) { 127 // node_t * n = try_pop(tls.myfriend, tls.stats.pop.help); 128 // tls.stats.help++; 129 // tls.myfriend = outside; 130 // if(n) return n; 131 // } 113 132 // if( tls.myfriend == outside ) { 114 133 // auto r = tls.rng1.next(); … … 141 160 inline node_t * local() { 142 161 unsigned i = (--tls.it % nqueues) + tls.my_queue; 162 node_t * n = try_pop(i, tls.stats.pop.local); 163 if(n) return n; 164 i = (--tls.it % nqueues) + tls.my_queue; 143 165 return try_pop(i, tls.stats.pop.local); 144 166 } … … 192 214 list.unlock(); 193 215 stat.success++; 194 // times[i].val = 1; 195 times[i].val = node.first->_links.ts; 196 // lists[i].val = node.first->_links.ts; 197 return node.first; 216 #ifdef NO_MPSC 217 // times[i].val = 1; 218 times[i].val = node.first->_links.ts; 219 // lists[i].val = node.first->_links.ts; 220 return node.first; 221 #else 222 times[i].val = node->_links.ts; 223 return node; 224 #endif 198 225 } 199 226
Note: See TracChangeset
for help on using the changeset viewer.