Changes in / [f4ec4a90:42cd451]
- Location:
- doc/theses/thierry_delisle_PhD/code
- Files:
-
- 1 deleted
- 3 edited
-
relaxed_list.hpp (modified) (22 diffs)
-
snzi-packed.hpp (deleted)
-
snzi.hpp (modified) (4 diffs)
-
utils.hpp (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
rf4ec4a90 r42cd451 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; -
doc/theses/thierry_delisle_PhD/code/snzi.hpp
rf4ec4a90 r42cd451 14 14 15 15 void arrive(int idx) { 16 idx >>= 2;17 16 idx %= mask; 18 17 nodes[idx].arrive(); … … 20 19 21 20 void depart(int idx) { 22 idx >>= 2;23 21 idx %= mask; 24 22 nodes[idx].depart(); … … 84 82 if( x.cnt == val_t::Half ) { 85 83 /* paranoid */ assert(parent); 86 if(undoArr == 2) { 87 undoArr--; 88 } else { 89 parent->arrive(); 90 } 84 parent->arrive(); 91 85 if( !value.cas(x, 1, x.ver) ) { 92 86 undoArr = undoArr + 1; … … 157 151 { 158 152 int width = std::pow(base, depth); 159 std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ") " << (sizeof(snzi_t::node) * (root + 1)) << " bytes" << std::endl;153 std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ")" << std::endl; 160 154 for(int i = 0; i < root; i++) { 161 std::cout << i << " -> " << (i / base) + width << std::endl; 162 nodes[i].parent = &nodes[(i / base) + width]; 155 nodes[i].parent = &nodes[(i / base) + width ]; 163 156 } 164 157 } -
doc/theses/thierry_delisle_PhD/code/utils.hpp
rf4ec4a90 r42cd451 35 35 }; 36 36 37 // class Random {38 // private:39 // unsigned int seed;40 // public:41 // Random(int seed) {42 // this->seed = seed;43 // }44 45 // /** returns pseudorandom x satisfying 0 <= x < n. **/46 // unsigned int next() {47 // seed ^= seed << 6;48 // seed ^= seed >> 21;49 // seed ^= seed << 7;50 // return seed;51 // }52 // };53 54 constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b);55 constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){56 return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b));57 }58 constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b){59 return (b==0) ? 0 : extendedEuclidX(b, a - b * (a / b)) - (a / b) * extendedEuclidY(b, a - b * (a / b));60 }61 62 37 class Random { 63 38 private: 64 uint64_t x; 65 66 static constexpr const uint64_t M = 1ul << 48ul; 67 static constexpr const uint64_t A = 25214903917; 68 static constexpr const uint64_t C = 11; 69 static constexpr const uint64_t D = 16; 70 39 unsigned int seed; 71 40 public: 72 static constexpr const uint64_t m = M; 73 static constexpr const uint64_t a = A; 74 static constexpr const uint64_t c = C; 75 static constexpr const uint64_t d = D; 76 static constexpr const uint64_t ai = extendedEuclidX(A, M); 77 public: 78 Random(unsigned int seed) { 79 this->x = seed * a; 41 Random(int seed) { 42 this->seed = seed; 80 43 } 81 44 82 45 /** returns pseudorandom x satisfying 0 <= x < n. **/ 83 46 unsigned int next() { 84 //nextx = (a * x + c) % m; 85 x = (A * x + C) & (M - 1); 86 return x >> D; 87 } 88 unsigned int prev() { 89 //prevx = (ainverse * (x - c)) mod m 90 unsigned int r = x >> D; 91 x = ai * (x - C) & (M - 1); 92 return r; 93 } 94 95 void set_raw_state(uint64_t _x) { 96 this->x = _x; 97 } 98 99 uint64_t get_raw_state() { 100 return this->x; 101 } 47 seed ^= seed << 6; 48 seed ^= seed >> 21; 49 seed ^= seed << 7; 50 return seed; 51 } 102 52 }; 103 53
Note: See TracChangeset
for help on using the changeset viewer.
