Changeset b232745
- Timestamp:
- Jun 22, 2020, 4:29:05 PM (4 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:
- 13c5e19
- Parents:
- 0f89d4f
- Location:
- doc/theses/thierry_delisle_PhD/code
- Files:
-
- 2 added
- 2 edited
-
links.hpp (added)
-
relaxed_list.cpp (modified) (13 diffs)
-
relaxed_list.hpp (modified) (27 diffs)
-
work_stealing.hpp (added)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.cpp
r0f89d4f rb232745 1 #include "relaxed_list.hpp" 1 #if !defined(LIST_VARIANT_HPP) 2 #define LIST_VARIANT_HPP "relaxed_list.hpp" 3 #endif 4 5 #include LIST_VARIANT_HPP 6 #if !defined(LIST_VARIANT) 7 #error not variant selected 8 #endif 2 9 3 10 #include <array> … … 35 42 36 43 template<> 37 thread_local relaxed_list<Node>::TLS relaxed_list<Node>::tls = {};44 thread_local LIST_VARIANT<Node>::TLS LIST_VARIANT<Node>::tls = {}; 38 45 39 46 template<> 40 relaxed_list<Node> * relaxed_list<Node>::head = nullptr;47 std::atomic_uint32_t LIST_VARIANT<Node>::ticket = { 0 }; 41 48 42 49 #ifndef NO_STATS 43 50 template<> 44 relaxed_list<Node>::GlobalStats relaxed_list<Node>::global_stats = {};51 LIST_VARIANT<Node>::GlobalStats LIST_VARIANT<Node>::global_stats = {}; 45 52 #endif 46 53 … … 120 127 atomic_min(global.valmin, local.valmin); 121 128 122 relaxed_list<Node>::stats_tls_tally();129 LIST_VARIANT<Node>::stats_tls_tally(); 123 130 } 124 131 … … 199 206 std::cout << "Total ops : " << ops << "(" << global.in << "i, " << global.out << "o, " << global.empty << "e)\n"; 200 207 #ifndef NO_STATS 201 relaxed_list<Node>::stats_print(std::cout);208 LIST_VARIANT<Node>::stats_print(std::cout); 202 209 #endif 203 210 } … … 216 223 unsigned nslots, 217 224 local_stat_t & local, 218 relaxed_list<Node> & list225 LIST_VARIANT<Node> & list 219 226 ) { 220 227 while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) { … … 254 261 std::cout << "Initializing "; 255 262 size_t npushed = 0; 256 relaxed_list<Node> list = { nthread *nqueues };263 LIST_VARIANT<Node> list = { nthread, nqueues }; 257 264 { 258 265 Node** all_nodes[nthread]; … … 340 347 unsigned nnodes, 341 348 local_stat_t & local, 342 relaxed_list<Node> & list349 LIST_VARIANT<Node> & list 343 350 ) { 344 351 Node * nodes[nnodes]; … … 384 391 std::cout << "Initializing "; 385 392 // List being tested 386 relaxed_list<Node> list = { nthread *nqueues };393 LIST_VARIANT<Node> list = { nthread, nqueues }; 387 394 { 388 395 enable_stats = true; … … 441 448 int nslots, 442 449 local_stat_t & local, 443 relaxed_list<Node> & list450 LIST_VARIANT<Node> & list 444 451 ) { 445 452 while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) { … … 518 525 519 526 // List being tested 520 relaxed_list<Node> list = { nthread *nqueues };527 LIST_VARIANT<Node> list = { nthread, nqueues }; 521 528 { 522 529 Random rand(rdtscl()); … … 593 600 unsigned nnodes, 594 601 local_stat_t & local, 595 relaxed_list<Node> & list602 LIST_VARIANT<Node> & list 596 603 ) { 597 604 Node * nodes[nnodes]; … … 653 660 654 661 // List being tested 655 relaxed_list<Node> list = { nthread *nqueues };662 LIST_VARIANT<Node> list = { nthread, nqueues }; 656 663 { 657 664 enable_stats = true; … … 921 928 922 929 std::cout << "Running " << nthreads << " threads (" << (nthreads * nqueues) << " queues) for " << duration << " seconds" << std::endl; 923 std::cout << "Relaxed list variant: " << relaxed_list<Node>::name() << std::endl;930 std::cout << "Relaxed list variant: " << LIST_VARIANT<Node>::name() << std::endl; 924 931 switch(benchmark) { 925 932 case Churn: -
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
r0f89d4f rb232745 1 1 #pragma once 2 3 #define MACRO_XSTR(s) MACRO_STR(s) 4 #define MACRO_STR(s) #s 2 #define LIST_VARIANT relaxed_list 5 3 6 4 #define VANILLA 0 … … 9 7 #define DISCOVER 3 10 8 #define SNZM 4 9 #define BIAS 5 11 10 12 11 #ifndef VARIANT … … 25 24 #include "assert.hpp" 26 25 #include "utils.hpp" 26 #include "links.hpp" 27 27 #include "snzi.hpp" 28 28 #include "snzm.hpp" 29 29 30 30 using namespace std; 31 32 extern bool enable_stats;33 31 34 32 struct pick_stat { … … 36 34 size_t attempt = 0; 37 35 size_t success = 0; 36 size_t local = 0; 38 37 } push; 39 38 struct { … … 42 41 size_t mask_attempt = 0; 43 42 size_t mask_reset = 0; 43 size_t local = 0; 44 44 } pop; 45 45 }; … … 57 57 58 58 template<typename node_t> 59 struct _LinksFields_t {60 node_t * prev = nullptr;61 node_t * next = nullptr;62 unsigned long long ts = 0;63 };64 65 template<typename node_t>66 59 class __attribute__((aligned(128))) relaxed_list { 67 60 static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field"); … … 70 63 static const char * name() { 71 64 const char * names[] = { 72 "VANILLA", 73 "SNZI", 74 "BITMASK", 75 "SNZI + DISCOVERED MASK", 76 "SNZI + MASK" 65 "RELAXED: VANILLA", 66 "RELAXED: SNZI", 67 "RELAXED: BITMASK", 68 "RELAXED: SNZI + DISCOVERED MASK", 69 "RELAXED: SNZI + MASK", 70 "RELAXED: SNZI + LOCAL BIAS" 77 71 }; 78 72 return names[VARIANT]; 79 73 } 80 74 81 relaxed_list(unsigned num Lists)82 : lists(new intrusive_queue_t[numLists])83 , numLists(numLists)84 #if VARIANT == SNZI 85 , snzi( std::log2( numLists / 8), 2 )75 relaxed_list(unsigned numThreads, unsigned numQueues) 76 : numLists(numThreads * numQueues) 77 , lists(new intrusive_queue_t<node_t>[numLists]) 78 #if VARIANT == SNZI || VARIANT == BIAS 79 , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) 86 80 #elif VARIANT == SNZM || VARIANT == DISCOVER 87 81 , snzm( numLists ) … … 89 83 { 90 84 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists"); 91 // assert(sizeof(*this) == 128);92 85 std::cout << "Constructing Relaxed List with " << numLists << std::endl; 93 94 #ifndef NO_STATS95 if(head) this->next = head;96 head = this;97 #endif98 86 } 99 87 … … 108 96 while(true) { 109 97 // 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 110 109 unsigned i = tls.rng.next() % numLists; 110 #endif 111 111 112 112 #ifndef NO_STATS … … 117 117 if( !lists[i].lock.try_lock() ) continue; 118 118 119 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 119 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 120 120 __attribute__((unused)) int num = numNonEmpty; 121 121 #endif … … 129 129 bts(tls.mask, bit); 130 130 snzm.arrive(i); 131 #elif VARIANT == SNZI 131 #elif VARIANT == SNZI || VARIANT == BIAS 132 132 snzi.arrive(i); 133 133 #elif VARIANT == SNZM … … 145 145 #endif 146 146 } 147 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 147 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 148 148 assert(numNonEmpty <= (int)numLists); 149 149 #endif … … 154 154 #ifndef NO_STATS 155 155 tls.pick.push.success++; 156 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 156 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 157 157 tls.empty.push.value += num; 158 158 tls.empty.push.count += 1; … … 198 198 // Pick two lists at random 199 199 int i = tls.rng.next() % numLists; 200 int j = tls.rng.next() % numLists; 200 // int j = tls.rng.next() % numLists; 201 202 if(auto node = try_pop(i, j)) return node; 203 } 204 205 #elif VARIANT == BIAS 206 while(snzi.query()) { 207 // Pick two lists at random 208 unsigned ri = tls.rng.next(); 209 unsigned i; 210 unsigned j = tls.rng.next(); 211 if(0 == (ri & 0xF)) { 212 i = (ri >> 4) % numLists; 213 } else { 214 i = tls.my_queue + ((ri >> 4) % 4); 215 j = tls.my_queue + ((j >> 4) % 4); 216 tls.pick.pop.local++; 217 } 218 i %= numLists; 219 j %= numLists; 201 220 202 221 if(auto node = try_pop(i, j)) return node; … … 214 233 // Pick two nodes from it 215 234 unsigned wdxi = ri & snzm.mask; 216 unsigned wdxj = rj & snzm.mask;235 // unsigned wdxj = rj & snzm.mask; 217 236 218 237 // Get the masks from the nodes 219 size_t maski = snzm.masks(wdxi);238 // size_t maski = snzm.masks(wdxi); 220 239 size_t maskj = snzm.masks(wdxj); 221 240 … … 224 243 #if defined(__BMI2__) 225 244 uint64_t idxsi = _pext_u64(snzm.indexes, maski); 226 uint64_t idxsj = _pext_u64(snzm.indexes, maskj);245 // uint64_t idxsj = _pext_u64(snzm.indexes, maskj); 227 246 228 247 auto pi = __builtin_popcountll(maski); 229 auto pj = __builtin_popcountll(maskj);248 // auto pj = __builtin_popcountll(maskj); 230 249 231 250 ri = pi ? ri & ((pi >> 3) - 1) : 0; … … 329 348 if( !list.lock.try_lock() ) return nullptr; 330 349 331 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 350 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 332 351 __attribute__((unused)) int num = numNonEmpty; 333 352 #endif … … 352 371 __attribute__((unused)) bool ret = btr(tls.mask, bit); 353 372 snzm.depart(w); 354 #elif VARIANT == SNZI 373 #elif VARIANT == SNZI || VARIANT == BIAS 355 374 snzi.depart(w); 356 375 #elif VARIANT == SNZM … … 371 390 // Unlock and return 372 391 list.lock.unlock(); 373 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 392 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 374 393 assert(numNonEmpty >= 0); 375 394 #endif 376 395 #ifndef NO_STATS 377 396 tls.pick.pop.success++; 378 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 397 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS 379 398 tls.empty.pop.value += num; 380 399 tls.empty.pop.count += 1; … … 384 403 } 385 404 386 private:387 388 class __attribute__((aligned(128))) intrusive_queue_t {389 public:390 typedef spinlock_t lock_t;391 392 friend class relaxed_list<node_t>;393 394 struct stat {395 ssize_t diff = 0;396 size_t push = 0;397 size_t pop = 0;398 };399 400 private:401 struct sentinel_t {402 _LinksFields_t<node_t> _links;403 };404 405 lock_t lock;406 sentinel_t before;407 sentinel_t after;408 #ifndef NO_STATS409 stat s;410 #endif411 412 #pragma GCC diagnostic push413 #pragma GCC diagnostic ignored "-Winvalid-offsetof"414 static constexpr auto fields_offset = offsetof( node_t, _links );415 #pragma GCC diagnostic pop416 public:417 intrusive_queue_t()418 : before{{ nullptr, tail() }}419 , after {{ head(), nullptr }}420 {421 /* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));422 /* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));423 /* paranoid */ assert(head()->_links.prev == nullptr);424 /* paranoid */ assert(head()->_links.next == tail() );425 /* paranoid */ assert(tail()->_links.next == nullptr);426 /* paranoid */ assert(tail()->_links.prev == head() );427 /* paranoid */ assert(sizeof(*this) == 128);428 /* paranoid */ assert((intptr_t(this) % 128) == 0);429 }430 431 ~intrusive_queue_t() = default;432 433 inline node_t * head() const {434 node_t * rhead = reinterpret_cast<node_t *>(435 reinterpret_cast<uintptr_t>( &before ) - fields_offset436 );437 assert(rhead);438 return rhead;439 }440 441 inline node_t * tail() const {442 node_t * rtail = reinterpret_cast<node_t *>(443 reinterpret_cast<uintptr_t>( &after ) - fields_offset444 );445 assert(rtail);446 return rtail;447 }448 449 inline bool push(node_t * node) {450 assert(lock);451 assert(node->_links.ts != 0);452 node_t * tail = this->tail();453 454 node_t * prev = tail->_links.prev;455 // assertf(node->_links.ts >= prev->_links.ts,456 // "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);457 node->_links.next = tail;458 node->_links.prev = prev;459 prev->_links.next = node;460 tail->_links.prev = node;461 #ifndef NO_STATS462 if(enable_stats) {463 s.diff++;464 s.push++;465 }466 #endif467 if(before._links.ts == 0l) {468 before._links.ts = node->_links.ts;469 assert(node->_links.prev == this->head());470 return true;471 }472 return false;473 }474 475 inline std::pair<node_t *, bool> pop() {476 assert(lock);477 node_t * head = this->head();478 node_t * tail = this->tail();479 480 node_t * node = head->_links.next;481 node_t * next = node->_links.next;482 if(node == tail) return {nullptr, false};483 484 head->_links.next = next;485 next->_links.prev = head;486 487 #ifndef NO_STATS488 if(enable_stats) {489 s.diff--;490 s.pop ++;491 }492 #endif493 if(next == tail) {494 before._links.ts = 0l;495 return {node, true};496 }497 else {498 assert(next->_links.ts != 0);499 before._links.ts = next->_links.ts;500 assert(before._links.ts != 0);501 return {node, false};502 }503 }504 505 long long ts() const {506 return before._links.ts;507 }508 };509 510 405 511 406 public: … … 513 408 static __attribute__((aligned(128))) thread_local struct TLS { 514 409 Random rng = { int(rdtscl()) }; 410 unsigned my_queue = (ticket++) * 4; 515 411 pick_stat pick; 516 412 empty_stat empty; … … 519 415 520 416 private: 521 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;522 417 const unsigned numLists; 418 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists; 523 419 private: 524 #if VARIANT == SNZI 420 #if VARIANT == SNZI || VARIANT == BIAS 525 421 snzi_t snzi; 526 422 #elif VARIANT == SNZM || VARIANT == DISCOVER … … 534 430 535 431 public: 536 static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t); 432 static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t<node_t>); 433 static std::atomic_uint32_t ticket; 537 434 538 435 #ifndef NO_STATS 539 static void stats_print(std::ostream & os) {540 auto it = head;541 while(it) {542 it->stats_print_local(os);543 it = it->next;544 }545 }546 547 436 static void stats_tls_tally() { 548 437 global_stats.pick.push.attempt += tls.pick.push.attempt; 549 438 global_stats.pick.push.success += tls.pick.push.success; 439 global_stats.pick.push.local += tls.pick.push.local; 550 440 global_stats.pick.pop .attempt += tls.pick.pop.attempt; 551 441 global_stats.pick.pop .success += tls.pick.pop.success; 552 442 global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt; 553 443 global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset; 444 global_stats.pick.pop .local += tls.pick.pop.local; 554 445 555 446 global_stats.qstat.push.value += tls.empty.push.value; … … 565 456 std::atomic_size_t attempt = { 0 }; 566 457 std::atomic_size_t success = { 0 }; 458 std::atomic_size_t local = { 0 }; 567 459 } push; 568 460 struct { … … 571 463 std::atomic_size_t mask_attempt = { 0 }; 572 464 std::atomic_size_t mask_reset = { 0 }; 465 std::atomic_size_t local = { 0 }; 573 466 } pop; 574 467 } pick; … … 585 478 } global_stats; 586 479 587 // Link list of all lists for stats 588 __attribute__((aligned(64))) relaxed_list<node_t> * next = nullptr; 589 590 static relaxed_list<node_t> * head; 591 592 void stats_print_local(std::ostream & os ) { 480 public: 481 static void stats_print(std::ostream & os ) { 593 482 std::cout << "----- Relaxed List Stats -----" << std::endl; 594 // {595 // ssize_t diff = 0;596 // size_t num = 0;597 // ssize_t max = 0;598 599 // for(size_t i = 0; i < numLists; i++) {600 // const auto & list = lists[i];601 // diff+= list.s.diff;602 // num ++;603 // max = std::abs(max) > std::abs(list.s.diff) ? max : list.s.diff;604 // os << "Local Q ops : " << (list.s.push + list.s.pop) << "(" << list.s.push << "i, " << list.s.pop << "o)\n";605 // }606 607 // os << "Difference : " << ssize_t(double(diff) / num ) << " avg\t" << max << "max" << std::endl;608 // }609 483 610 484 const auto & global = global_stats; … … 631 505 os << "Pop Avg Qs : " << avgQ_pop << " (" << global.qstat.pop .count << "ops)\n"; 632 506 os << "Global Avg Qs : " << avgQ << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n"; 507 508 os << "Local Push : " << global.pick.push.local << "\n"; 509 os << "Local Pop : " << global.pick.pop .local << "\n"; 633 510 } 634 511 #endif
Note: See TracChangeset
for help on using the changeset viewer.
