- Timestamp:
- Apr 14, 2021, 12:58:36 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:
- 9344f0e, a33c113
- Parents:
- ea1c97b
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/readyQ_proto/work_stealing.hpp
rea1c97b r634a5c2 15 15 #include "snzi.hpp" 16 16 17 #include <x86intrin.h>17 // #include <x86intrin.h> 18 18 19 19 using namespace std; … … 28 28 template<typename node_t> 29 29 struct __attribute__((aligned(128))) localQ_t { 30 mpsc_queue<node_t> queue = {}; 31 spinlock_t lock = {}; 32 bool needs_help = true; 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(); } 33 42 }; 34 43 … … 44 53 work_stealing(unsigned _numThreads, unsigned) 45 54 : numThreads(_numThreads * nqueues) 46 , lists(new intrusive_queue_t<node_t>[numThreads]) 55 , lists(new localQ_t<node_t>[numThreads]) 56 // , lists(new intrusive_queue_t<node_t>[numThreads]) 47 57 , times(new timestamp_t[numThreads]) 48 58 // , snzi( std::log2( numThreads / 2 ), 2 ) … … 58 68 59 69 __attribute__((noinline, hot)) void push(node_t * node) { 60 //node->_links.ts = rdtscl();61 node->_links.ts = 1;70 node->_links.ts = rdtscl(); 71 // node->_links.ts = 1; 62 72 63 73 auto & list = *({ … … 72 82 i = tls.my_queue + (r % nqueues); 73 83 } 74 } while(!lists[i]. lock.try_lock());84 } while(!lists[i].try_lock()); 75 85 &lists[i]; 76 86 }); 77 87 78 88 list.push( node ); 79 list. lock.unlock();89 list.unlock(); 80 90 // tls.rng2.set_raw_state( tls.rng1.get_raw_state()); 81 91 // count++; … … 84 94 85 95 __attribute__((noinline, hot)) node_t * pop() { 86 if( tls.myfriend == outside ) {87 auto r = tls.rng1.next();88 tls.myfriend = r % numThreads;89 times[tls.myfriend].val = 0;90 }91 else if(times[tls.myfriend].val == 0) {92 node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);93 tls.stats.help++;94 tls.myfriend = outside;95 if(n) return n;96 }97 98 96 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 } 113 // if( tls.myfriend == outside ) { 114 // auto r = tls.rng1.next(); 115 // tls.myfriend = r % numThreads; 116 // tls.mytime = lists[((tls.it + 1) % nqueues) + tls.my_queue].ts(); 117 // } 118 // else { 119 // if(times[tls.myfriend].val + 1000 < tls.mytime) { 120 // node_t * n = try_pop(tls.myfriend, tls.stats.pop.help); 121 // tls.stats.help++; 122 // if(n) return n; 123 // } 124 // tls.myfriend = outside; 125 // } 126 99 127 node_t * n = local(); 100 128 if(n) return n; … … 112 140 private: 113 141 inline node_t * local() { 114 // unsigned i = (tls.rng2.prev() % 4) + tls.my_queue;115 142 unsigned i = (--tls.it % nqueues) + tls.my_queue; 116 143 return try_pop(i, tls.stats.pop.local); … … 153 180 154 181 // If we can't get the lock, move on 155 if( !list.lock.try_lock() ) { stat.elock++; return nullptr; } 156 182 if( !list.try_lock() ) { stat.elock++; return nullptr; } 157 183 158 184 // If list is empty, unlock and retry 159 185 if( list.ts() == 0 ) { 160 list. lock.unlock();186 list.unlock(); 161 187 stat.eempty++; 162 188 return nullptr; … … 164 190 165 191 auto node = list.pop(); 166 list. lock.unlock();192 list.unlock(); 167 193 stat.success++; 168 times[i].val = 1; //node.first->_links.ts;169 // count--;170 // _mm_stream_si64((long long int*)×[i].val, node.first->_links.ts);194 // times[i].val = 1; 195 times[i].val = node.first->_links.ts; 196 // lists[i].val = node.first->_links.ts; 171 197 return node.first; 172 198 } … … 191 217 unsigned my_queue = calc_preferred(); 192 218 unsigned myfriend = outside; 219 unsigned long long int mytime = 0; 193 220 #if defined(READ) 194 221 unsigned it = 0; … … 211 238 private: 212 239 const unsigned numThreads; 213 std::unique_ptr<intrusive_queue_t<node_t> []> lists; 240 std::unique_ptr<localQ_t<node_t> []> lists; 241 // std::unique_ptr<intrusive_queue_t<node_t> []> lists; 214 242 std::unique_ptr<timestamp_t []> times; 215 243 __attribute__((aligned(128))) std::atomic_size_t count;
Note: See TracChangeset
for help on using the changeset viewer.