Ignore:
Timestamp:
Jun 22, 2020, 4:29:05 PM (18 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast, new-ast-unique-expr
Children:
13c5e19
Parents:
0f89d4f
Message:

Several changes to relaxed list prototype and added workstealing for comparison

Location:
doc/theses/thierry_delisle_PhD/code
Files:
2 added
2 edited

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
    29
    310#include <array>
     
    3542
    3643template<>
    37 thread_local relaxed_list<Node>::TLS relaxed_list<Node>::tls = {};
     44thread_local LIST_VARIANT<Node>::TLS LIST_VARIANT<Node>::tls = {};
    3845
    3946template<>
    40 relaxed_list<Node> * relaxed_list<Node>::head = nullptr;
     47std::atomic_uint32_t LIST_VARIANT<Node>::ticket = { 0 };
    4148
    4249#ifndef NO_STATS
    4350template<>
    44 relaxed_list<Node>::GlobalStats relaxed_list<Node>::global_stats = {};
     51LIST_VARIANT<Node>::GlobalStats LIST_VARIANT<Node>::global_stats = {};
    4552#endif
    4653
     
    120127        atomic_min(global.valmin, local.valmin);
    121128
    122         relaxed_list<Node>::stats_tls_tally();
     129        LIST_VARIANT<Node>::stats_tls_tally();
    123130}
    124131
     
    199206        std::cout << "Total ops     : " << ops << "(" << global.in << "i, " << global.out << "o, " << global.empty << "e)\n";
    200207        #ifndef NO_STATS
    201                 relaxed_list<Node>::stats_print(std::cout);
     208                LIST_VARIANT<Node>::stats_print(std::cout);
    202209        #endif
    203210}
     
    216223        unsigned nslots,
    217224        local_stat_t & local,
    218         relaxed_list<Node> & list
     225        LIST_VARIANT<Node> & list
    219226) {
    220227        while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) {
     
    254261        std::cout << "Initializing ";
    255262        size_t npushed = 0;
    256         relaxed_list<Node> list = { nthread * nqueues };
     263        LIST_VARIANT<Node> list = { nthread, nqueues };
    257264        {
    258265                Node** all_nodes[nthread];
     
    340347        unsigned nnodes,
    341348        local_stat_t & local,
    342         relaxed_list<Node> & list
     349        LIST_VARIANT<Node> & list
    343350) {
    344351        Node * nodes[nnodes];
     
    384391        std::cout << "Initializing ";
    385392        // List being tested
    386         relaxed_list<Node> list = { nthread * nqueues };
     393        LIST_VARIANT<Node> list = { nthread, nqueues };
    387394        {
    388395                enable_stats = true;
     
    441448        int nslots,
    442449        local_stat_t & local,
    443         relaxed_list<Node> & list
     450        LIST_VARIANT<Node> & list
    444451) {
    445452        while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) {
     
    518525
    519526        // List being tested
    520         relaxed_list<Node> list = { nthread * nqueues };
     527        LIST_VARIANT<Node> list = { nthread, nqueues };
    521528        {
    522529                Random rand(rdtscl());
     
    593600        unsigned nnodes,
    594601        local_stat_t & local,
    595         relaxed_list<Node> & list
     602        LIST_VARIANT<Node> & list
    596603) {
    597604        Node * nodes[nnodes];
     
    653660
    654661        // List being tested
    655         relaxed_list<Node> list = { nthread * nqueues };
     662        LIST_VARIANT<Node> list = { nthread, nqueues };
    656663        {
    657664                enable_stats = true;
     
    921928
    922929        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;
    924931        switch(benchmark) {
    925932                case Churn:
  • doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

    r0f89d4f rb232745  
    11#pragma once
    2 
    3 #define MACRO_XSTR(s) MACRO_STR(s)
    4 #define MACRO_STR(s) #s
     2#define LIST_VARIANT relaxed_list
    53
    64#define VANILLA 0
     
    97#define DISCOVER 3
    108#define SNZM 4
     9#define BIAS 5
    1110
    1211#ifndef VARIANT
     
    2524#include "assert.hpp"
    2625#include "utils.hpp"
     26#include "links.hpp"
    2727#include "snzi.hpp"
    2828#include "snzm.hpp"
    2929
    3030using namespace std;
    31 
    32 extern bool enable_stats;
    3331
    3432struct pick_stat {
     
    3634                size_t attempt = 0;
    3735                size_t success = 0;
     36                size_t local = 0;
    3837        } push;
    3938        struct {
     
    4241                size_t mask_attempt = 0;
    4342                size_t mask_reset = 0;
     43                size_t local = 0;
    4444        } pop;
    4545};
     
    5757
    5858template<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>
    6659class __attribute__((aligned(128))) relaxed_list {
    6760        static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
     
    7063        static const char * name() {
    7164                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"
    7771                };
    7872                return names[VARIANT];
    7973        }
    8074
    81         relaxed_list(unsigned numLists)
    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 )
    8680                #elif VARIANT == SNZM || VARIANT == DISCOVER
    8781                        , snzm( numLists )
     
    8983        {
    9084                assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
    91                 // assert(sizeof(*this) == 128);
    9285                std::cout << "Constructing Relaxed List with " << numLists << std::endl;
    93 
    94                 #ifndef NO_STATS
    95                         if(head) this->next = head;
    96                         head = this;
    97                 #endif
    9886        }
    9987
     
    10896                while(true) {
    10997                        // 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
    110109                        unsigned i = tls.rng.next() % numLists;
     110                        #endif
    111111
    112112                        #ifndef NO_STATS
     
    117117                        if( !lists[i].lock.try_lock() ) continue;
    118118
    119                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
     119                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
    120120                                __attribute__((unused)) int num = numNonEmpty;
    121121                        #endif
     
    129129                                        bts(tls.mask, bit);
    130130                                        snzm.arrive(i);
    131                                 #elif VARIANT == SNZI
     131                                #elif VARIANT == SNZI || VARIANT == BIAS
    132132                                        snzi.arrive(i);
    133133                                #elif VARIANT == SNZM
     
    145145                                #endif
    146146                        }
    147                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
     147                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
    148148                                assert(numNonEmpty <= (int)numLists);
    149149                        #endif
     
    154154                        #ifndef NO_STATS
    155155                                tls.pick.push.success++;
    156                                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
     156                                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
    157157                                        tls.empty.push.value += num;
    158158                                        tls.empty.push.count += 1;
     
    198198                                // Pick two lists at random
    199199                                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;
    201220
    202221                                if(auto node = try_pop(i, j)) return node;
     
    214233                                        // Pick two nodes from it
    215234                                        unsigned wdxi = ri & snzm.mask;
    216                                         unsigned wdxj = rj & snzm.mask;
     235                                        // unsigned wdxj = rj & snzm.mask;
    217236
    218237                                        // Get the masks from the nodes
    219                                         size_t maski = snzm.masks(wdxi);
     238                                        // size_t maski = snzm.masks(wdxi);
    220239                                        size_t maskj = snzm.masks(wdxj);
    221240
     
    224243                                        #if defined(__BMI2__)
    225244                                                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);
    227246
    228247                                                auto pi = __builtin_popcountll(maski);
    229                                                 auto pj = __builtin_popcountll(maskj);
     248                                                // auto pj = __builtin_popcountll(maskj);
    230249
    231250                                                ri = pi ? ri & ((pi >> 3) - 1) : 0;
     
    329348                if( !list.lock.try_lock() ) return nullptr;
    330349
    331                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
     350                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER  && VARIANT != BIAS
    332351                        __attribute__((unused)) int num = numNonEmpty;
    333352                #endif
     
    352371                                __attribute__((unused)) bool ret = btr(tls.mask, bit);
    353372                                snzm.depart(w);
    354                         #elif VARIANT == SNZI
     373                        #elif VARIANT == SNZI || VARIANT == BIAS
    355374                                snzi.depart(w);
    356375                        #elif VARIANT == SNZM
     
    371390                // Unlock and return
    372391                list.lock.unlock();
    373                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
     392                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
    374393                        assert(numNonEmpty >= 0);
    375394                #endif
    376395                #ifndef NO_STATS
    377396                        tls.pick.pop.success++;
    378                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
     397                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
    379398                                tls.empty.pop.value += num;
    380399                                tls.empty.pop.count += 1;
     
    384403        }
    385404
    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_STATS
    409                         stat s;
    410                 #endif
    411 
    412 #pragma GCC diagnostic push
    413 #pragma GCC diagnostic ignored "-Winvalid-offsetof"
    414                 static constexpr auto fields_offset = offsetof( node_t, _links );
    415 #pragma GCC diagnostic pop
    416         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_offset
    436                         );
    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_offset
    444                         );
    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_STATS
    462                                 if(enable_stats) {
    463                                         s.diff++;
    464                                         s.push++;
    465                                 }
    466                         #endif
    467                         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_STATS
    488                                 if(enable_stats) {
    489                                         s.diff--;
    490                                         s.pop ++;
    491                                 }
    492                         #endif
    493                         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 
    510405
    511406public:
     
    513408        static __attribute__((aligned(128))) thread_local struct TLS {
    514409                Random     rng = { int(rdtscl()) };
     410                unsigned   my_queue = (ticket++) * 4;
    515411                pick_stat  pick;
    516412                empty_stat empty;
     
    519415
    520416private:
    521         __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
    522417        const unsigned numLists;
     418        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists;
    523419private:
    524         #if VARIANT == SNZI
     420        #if VARIANT == SNZI || VARIANT == BIAS
    525421                snzi_t snzi;
    526422        #elif VARIANT == SNZM || VARIANT == DISCOVER
     
    534430
    535431public:
    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;
    537434
    538435#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 
    547436        static void stats_tls_tally() {
    548437                global_stats.pick.push.attempt += tls.pick.push.attempt;
    549438                global_stats.pick.push.success += tls.pick.push.success;
     439                global_stats.pick.push.local += tls.pick.push.local;
    550440                global_stats.pick.pop .attempt += tls.pick.pop.attempt;
    551441                global_stats.pick.pop .success += tls.pick.pop.success;
    552442                global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
    553443                global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset;
     444                global_stats.pick.pop .local += tls.pick.pop.local;
    554445
    555446                global_stats.qstat.push.value += tls.empty.push.value;
     
    565456                                std::atomic_size_t attempt = { 0 };
    566457                                std::atomic_size_t success = { 0 };
     458                                std::atomic_size_t local = { 0 };
    567459                        } push;
    568460                        struct {
     
    571463                                std::atomic_size_t mask_attempt = { 0 };
    572464                                std::atomic_size_t mask_reset = { 0 };
     465                                std::atomic_size_t local = { 0 };
    573466                        } pop;
    574467                } pick;
     
    585478        } global_stats;
    586479
    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 ) {
     480public:
     481        static void stats_print(std::ostream & os ) {
    593482                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                 // }
    609483
    610484                const auto & global = global_stats;
     
    631505                os << "Pop    Avg Qs : " << avgQ_pop  << " (" << global.qstat.pop .count << "ops)\n";
    632506                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";
    633510        }
    634511#endif
Note: See TracChangeset for help on using the changeset viewer.