Changeset a82a8f4 for doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
- Timestamp:
- Jul 21, 2020, 4:59:34 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- c0587193
- Parents:
- 50d529e
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
r50d529e ra82a8f4 8 8 #define SNZM 4 9 9 #define BIAS 5 10 #define BACK 6 11 #define BACKBIAS 7 10 12 11 13 #ifndef VARIANT … … 68 70 "RELAXED: SNZI + DISCOVERED MASK", 69 71 "RELAXED: SNZI + MASK", 70 "RELAXED: SNZI + LOCAL BIAS" 72 "RELAXED: SNZI + LOCAL BIAS", 73 "RELAXED: SNZI + REVERSE RNG", 74 "RELAXED: SNZI + LOCAL BIAS + REVERSE RNG" 71 75 }; 72 76 return names[VARIANT]; … … 76 80 : numLists(numThreads * numQueues) 77 81 , lists(new intrusive_queue_t<node_t>[numLists]) 78 #if VARIANT == SNZI || VARIANT == BIAS 82 #if VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS 79 83 , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) 80 84 #elif VARIANT == SNZM || VARIANT == DISCOVER … … 96 100 while(true) { 97 101 // Pick a random list 98 #if VARIANT == BIAS 99 unsigned r = tls.rng.next(); 100 unsigned i; 101 if(0 == (r & 0xF)) { 102 i = r >> 4; 103 } else { 104 i = tls.my_queue + ((r >> 4) % 4); 105 tls.pick.push.local++; 106 } 107 i %= numLists; 108 #else 109 unsigned i = tls.rng.next() % numLists; 110 #endif 102 unsigned i = idx_from_r(tls.rng1.next(), VARIANT == BIAS || VARIANT == BACKBIAS); 111 103 112 104 #ifndef NO_STATS … … 117 109 if( !lists[i].lock.try_lock() ) continue; 118 110 119 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS111 #if VARIANT == VANILLA || VARIANT == BITMASK 120 112 __attribute__((unused)) int num = numNonEmpty; 121 113 #endif … … 131 123 #elif VARIANT == SNZI || VARIANT == BIAS 132 124 snzi.arrive(i); 125 #elif VARIANT == BACK || VARIANT == BACKBIAS 126 snzi.arrive(i); 127 tls.rng2.set_raw_state( tls.rng1.get_raw_state()); 133 128 #elif VARIANT == SNZM 134 129 snzm.arrive(i); … … 145 140 #endif 146 141 } 147 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS142 #if VARIANT == VANILLA || VARIANT == BITMASK 148 143 assert(numNonEmpty <= (int)numLists); 149 144 #endif … … 154 149 #ifndef NO_STATS 155 150 tls.pick.push.success++; 156 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS151 #if VARIANT == VANILLA || VARIANT == BITMASK 157 152 tls.empty.push.value += num; 158 153 tls.empty.push.count += 1; … … 171 166 { 172 167 // Pick first list totally randomly 173 i = tls.rng .next() % numLists;168 i = tls.rng1.next() % numLists; 174 169 175 170 // Pick the other according to the bitmask 176 unsigned r = tls.rng .next();171 unsigned r = tls.rng1.next(); 177 172 178 173 size_t mask = tls.mask.load(std::memory_order_relaxed); … … 197 192 while(snzi.query()) { 198 193 // Pick two lists at random 199 int i = tls.rng.next() % numLists; 200 // int j = tls.rng.next() % numLists; 194 int i = tls.rng1.next() % numLists; 195 int j = tls.rng1.next() % numLists; 196 197 if(auto node = try_pop(i, j)) return node; 198 } 199 200 #elif VARIANT == BACK 201 while(snzi.query()) { 202 // Pick two lists at random 203 int i = tls.rng2.prev() % numLists; 204 int j = tls.rng2.prev() % numLists; 205 206 if(auto node = try_pop(i, j)) return node; 207 } 208 209 #elif VARIANT == BACKBIAS 210 while(snzi.query()) { 211 // Pick two lists at random 212 int i = idx_from_r(tls.rng2.prev(), true); 213 int j = idx_from_r(tls.rng2.prev(), true); 201 214 202 215 if(auto node = try_pop(i, j)) return node; … … 206 219 while(snzi.query()) { 207 220 // Pick two lists at random 208 unsigned ri = tls.rng .next();221 unsigned ri = tls.rng1.next(); 209 222 unsigned i; 210 unsigned j = tls.rng .next();223 unsigned j = tls.rng1.next(); 211 224 if(0 == (ri & 0xF)) { 212 225 i = (ri >> 4) % numLists; … … 228 241 { 229 242 // Pick two random number 230 unsigned ri = tls.rng .next();231 unsigned rj = tls.rng .next();243 unsigned ri = tls.rng1.next(); 244 unsigned rj = tls.rng1.next(); 232 245 233 246 // Pick two nodes from it … … 270 283 while(snzm.query()) { 271 284 // Pick two lists at random 272 int i = tls.rng .next() % numLists;273 int j = tls.rng .next() % numLists;285 int i = tls.rng1.next() % numLists; 286 int j = tls.rng1.next() % numLists; 274 287 275 288 if(auto node = try_pop(i, j)) return node; … … 285 298 unsigned num = ((numLists - 1) >> 6) + 1; 286 299 287 unsigned ri = tls.rng .next();288 unsigned rj = tls.rng .next();300 unsigned ri = tls.rng1.next(); 301 unsigned rj = tls.rng1.next(); 289 302 290 303 unsigned wdxi = (ri >> 6u) % num; … … 314 327 while(numNonEmpty != 0) { 315 328 // Pick two lists at random 316 int i = tls.rng .next() % numLists;317 int j = tls.rng .next() % numLists;329 int i = tls.rng1.next() % numLists; 330 int j = tls.rng1.next() % numLists; 318 331 319 332 if(auto node = try_pop(i, j)) return node; … … 348 361 if( !list.lock.try_lock() ) return nullptr; 349 362 350 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS363 #if VARIANT == VANILLA || VARIANT == BITMASK 351 364 __attribute__((unused)) int num = numNonEmpty; 352 365 #endif … … 371 384 __attribute__((unused)) bool ret = btr(tls.mask, bit); 372 385 snzm.depart(w); 373 #elif VARIANT == SNZI || VARIANT == BIAS 386 #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS 374 387 snzi.depart(w); 375 388 #elif VARIANT == SNZM … … 390 403 // Unlock and return 391 404 list.lock.unlock(); 392 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS405 #if VARIANT == VANILLA || VARIANT == BITMASK 393 406 assert(numNonEmpty >= 0); 394 407 #endif 395 408 #ifndef NO_STATS 396 409 tls.pick.pop.success++; 397 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS410 #if VARIANT == VANILLA || VARIANT == BITMASK 398 411 tls.empty.pop.value += num; 399 412 tls.empty.pop.count += 1; … … 403 416 } 404 417 418 inline unsigned idx_from_r(unsigned r, bool bias) { 419 unsigned i; 420 if(bias) { 421 if(0 == (r & 0xF)) { 422 i = r >> 4; 423 } else { 424 i = tls.my_queue + ((r >> 4) % 4); 425 tls.pick.push.local++; 426 } 427 } else { 428 i = r; 429 } 430 return i % numLists; 431 } 405 432 406 433 public: 407 434 408 435 static __attribute__((aligned(128))) thread_local struct TLS { 409 Random rng = { int(rdtscl()) }; 436 Random rng1 = { int(rdtscl()) }; 437 Random rng2 = { int(rdtscl()) }; 410 438 unsigned my_queue = (ticket++) * 4; 411 439 pick_stat pick; … … 418 446 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists; 419 447 private: 420 #if VARIANT == SNZI || VARIANT == BIAS 448 #if VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS 421 449 snzi_t snzi; 422 450 #elif VARIANT == SNZM || VARIANT == DISCOVER
Note: See TracChangeset
for help on using the changeset viewer.
