- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
rf0c3120 rb232745 8 8 #define SNZM 4 9 9 #define BIAS 5 10 #define BACK 611 #define BACKBIAS 712 10 13 11 #ifndef VARIANT … … 20 18 21 19 #include <cmath> 22 #include <functional>23 20 #include <memory> 24 21 #include <mutex> 25 #include <thread>26 22 #include <type_traits> 27 23 … … 30 26 #include "links.hpp" 31 27 #include "snzi.hpp" 32 #include "snzi-packed.hpp"33 28 #include "snzm.hpp" 34 29 … … 73 68 "RELAXED: SNZI + DISCOVERED MASK", 74 69 "RELAXED: SNZI + MASK", 75 "RELAXED: SNZI + LOCAL BIAS", 76 "RELAXED: SNZI + REVERSE RNG", 77 "RELAXED: SNZI + LOCAL BIAS + REVERSE RNG" 70 "RELAXED: SNZI + LOCAL BIAS" 78 71 }; 79 72 return names[VARIANT]; … … 83 76 : numLists(numThreads * numQueues) 84 77 , lists(new intrusive_queue_t<node_t>[numLists]) 85 #if VARIANT == SNZI || VARIANT == B ACK78 #if VARIANT == SNZI || VARIANT == BIAS 86 79 , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) 87 #elif VARIANT == BIAS || VARIANT == BACKBIAS88 #ifdef SNZI_PACKED89 , snzi( std::ceil( std::log2(numLists) ) )90 #else91 , snzi( std::log2( numLists / (2 * numQueues) ), 2 )92 #endif93 80 #elif VARIANT == SNZM || VARIANT == DISCOVER 94 81 , snzm( numLists ) … … 109 96 while(true) { 110 97 // Pick a random list 111 unsigned i = idx_from_r(tls.rng1.next(), VARIANT == BIAS || VARIANT == BACKBIAS); 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 112 111 113 112 #ifndef NO_STATS … … 118 117 if( !lists[i].lock.try_lock() ) continue; 119 118 120 #if VARIANT == VANILLA || VARIANT == BITMASK119 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 121 120 __attribute__((unused)) int num = numNonEmpty; 122 121 #endif … … 132 131 #elif VARIANT == SNZI || VARIANT == BIAS 133 132 snzi.arrive(i); 134 #elif VARIANT == BACK || VARIANT == BACKBIAS135 snzi.arrive(i);136 tls.rng2.set_raw_state( tls.rng1.get_raw_state());137 133 #elif VARIANT == SNZM 138 134 snzm.arrive(i); … … 149 145 #endif 150 146 } 151 #if VARIANT == VANILLA || VARIANT == BITMASK147 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 152 148 assert(numNonEmpty <= (int)numLists); 153 149 #endif … … 158 154 #ifndef NO_STATS 159 155 tls.pick.push.success++; 160 #if VARIANT == VANILLA || VARIANT == BITMASK156 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 161 157 tls.empty.push.value += num; 162 158 tls.empty.push.count += 1; … … 175 171 { 176 172 // Pick first list totally randomly 177 i = tls.rng 1.next() % numLists;173 i = tls.rng.next() % numLists; 178 174 179 175 // Pick the other according to the bitmask 180 unsigned r = tls.rng 1.next();176 unsigned r = tls.rng.next(); 181 177 182 178 size_t mask = tls.mask.load(std::memory_order_relaxed); … … 201 197 while(snzi.query()) { 202 198 // Pick two lists at random 203 int i = tls.rng1.next() % numLists; 204 int j = tls.rng1.next() % numLists; 205 206 if(auto node = try_pop(i, j)) return node; 207 } 208 209 #elif VARIANT == BACK 210 while(snzi.query()) { 211 // Pick two lists at random 212 int i = tls.rng2.prev() % numLists; 213 int j = tls.rng2.prev() % numLists; 214 215 if(auto node = try_pop(i, j)) return node; 216 } 217 218 #elif VARIANT == BACKBIAS 219 while(snzi.query()) { 220 // Pick two lists at random 221 int i = idx_from_r(tls.rng2.prev(), true); 222 int j = idx_from_r(tls.rng2.prev(), true); 199 int i = tls.rng.next() % numLists; 200 // int j = tls.rng.next() % numLists; 223 201 224 202 if(auto node = try_pop(i, j)) return node; … … 228 206 while(snzi.query()) { 229 207 // Pick two lists at random 230 unsigned ri = tls.rng 1.next();208 unsigned ri = tls.rng.next(); 231 209 unsigned i; 232 unsigned j = tls.rng 1.next();210 unsigned j = tls.rng.next(); 233 211 if(0 == (ri & 0xF)) { 234 212 i = (ri >> 4) % numLists; … … 250 228 { 251 229 // Pick two random number 252 unsigned ri = tls.rng 1.next();253 unsigned rj = tls.rng 1.next();230 unsigned ri = tls.rng.next(); 231 unsigned rj = tls.rng.next(); 254 232 255 233 // Pick two nodes from it … … 292 270 while(snzm.query()) { 293 271 // Pick two lists at random 294 int i = tls.rng 1.next() % numLists;295 int j = tls.rng 1.next() % numLists;272 int i = tls.rng.next() % numLists; 273 int j = tls.rng.next() % numLists; 296 274 297 275 if(auto node = try_pop(i, j)) return node; … … 307 285 unsigned num = ((numLists - 1) >> 6) + 1; 308 286 309 unsigned ri = tls.rng 1.next();310 unsigned rj = tls.rng 1.next();287 unsigned ri = tls.rng.next(); 288 unsigned rj = tls.rng.next(); 311 289 312 290 unsigned wdxi = (ri >> 6u) % num; … … 336 314 while(numNonEmpty != 0) { 337 315 // Pick two lists at random 338 int i = tls.rng 1.next() % numLists;339 int j = tls.rng 1.next() % numLists;316 int i = tls.rng.next() % numLists; 317 int j = tls.rng.next() % numLists; 340 318 341 319 if(auto node = try_pop(i, j)) return node; … … 370 348 if( !list.lock.try_lock() ) return nullptr; 371 349 372 #if VARIANT == VANILLA || VARIANT == BITMASK350 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 373 351 __attribute__((unused)) int num = numNonEmpty; 374 352 #endif … … 393 371 __attribute__((unused)) bool ret = btr(tls.mask, bit); 394 372 snzm.depart(w); 395 #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS373 #elif VARIANT == SNZI || VARIANT == BIAS 396 374 snzi.depart(w); 397 375 #elif VARIANT == SNZM … … 412 390 // Unlock and return 413 391 list.lock.unlock(); 414 #if VARIANT == VANILLA || VARIANT == BITMASK392 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 415 393 assert(numNonEmpty >= 0); 416 394 #endif 417 395 #ifndef NO_STATS 418 396 tls.pick.pop.success++; 419 #if VARIANT == VANILLA || VARIANT == BITMASK397 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 420 398 tls.empty.pop.value += num; 421 399 tls.empty.pop.count += 1; … … 425 403 } 426 404 427 inline unsigned idx_from_r(unsigned r, bool bias) {428 unsigned i;429 if(bias) {430 if(0 == (r & 0x3F)) {431 i = r >> 6;432 } else {433 i = tls.my_queue + ((r >> 6) % 4);434 tls.pick.push.local++;435 }436 } else {437 i = r;438 }439 return i % numLists;440 }441 405 442 406 public: 443 407 444 408 static __attribute__((aligned(128))) thread_local struct TLS { 445 Random rng1 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) }; 446 Random rng2 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) }; 409 Random rng = { int(rdtscl()) }; 447 410 unsigned my_queue = (ticket++) * 4; 448 411 pick_stat pick; … … 455 418 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists; 456 419 private: 457 #if VARIANT == SNZI || VARIANT == B ACK420 #if VARIANT == SNZI || VARIANT == BIAS 458 421 snzi_t snzi; 459 #elif VARIANT == BIAS || VARIANT == BACKBIAS460 #ifdef SNZI_PACKED461 snzip_t snzi;462 #else463 snzi_t snzi;464 #endif465 422 #elif VARIANT == SNZM || VARIANT == DISCOVER 466 423 snzm_t snzm;
Note: See TracChangeset
for help on using the changeset viewer.
