Ignore:
Timestamp:
Jul 21, 2020, 4:59:34 PM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
c0587193
Parents:
50d529e
Message:

Added two new variants to the ready queue which are based on the idea of running the RNG backwards in certain cases

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

    r50d529e ra82a8f4  
    88#define SNZM 4
    99#define BIAS 5
     10#define BACK 6
     11#define BACKBIAS 7
    1012
    1113#ifndef VARIANT
     
    6870                        "RELAXED: SNZI + DISCOVERED MASK",
    6971                        "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"
    7175                };
    7276                return names[VARIANT];
     
    7680                : numLists(numThreads * numQueues)
    7781                , lists(new intrusive_queue_t<node_t>[numLists])
    78                 #if VARIANT == SNZI || VARIANT == BIAS
     82                #if VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS
    7983                        , snzi( std::log2( numLists / (2 * numQueues) ), 2 )
    8084                #elif VARIANT == SNZM || VARIANT == DISCOVER
     
    96100                while(true) {
    97101                        // 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);
    111103
    112104                        #ifndef NO_STATS
     
    117109                        if( !lists[i].lock.try_lock() ) continue;
    118110
    119                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     111                        #if VARIANT == VANILLA || VARIANT == BITMASK
    120112                                __attribute__((unused)) int num = numNonEmpty;
    121113                        #endif
     
    131123                                #elif VARIANT == SNZI || VARIANT == BIAS
    132124                                        snzi.arrive(i);
     125                                #elif VARIANT == BACK || VARIANT == BACKBIAS
     126                                        snzi.arrive(i);
     127                                        tls.rng2.set_raw_state( tls.rng1.get_raw_state());
    133128                                #elif VARIANT == SNZM
    134129                                        snzm.arrive(i);
     
    145140                                #endif
    146141                        }
    147                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     142                        #if VARIANT == VANILLA || VARIANT == BITMASK
    148143                                assert(numNonEmpty <= (int)numLists);
    149144                        #endif
     
    154149                        #ifndef NO_STATS
    155150                                tls.pick.push.success++;
    156                                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     151                                #if VARIANT == VANILLA || VARIANT == BITMASK
    157152                                        tls.empty.push.value += num;
    158153                                        tls.empty.push.count += 1;
     
    171166                                {
    172167                                        // Pick first list totally randomly
    173                                         i = tls.rng.next() % numLists;
     168                                        i = tls.rng1.next() % numLists;
    174169
    175170                                        // Pick the other according to the bitmask
    176                                         unsigned r = tls.rng.next();
     171                                        unsigned r = tls.rng1.next();
    177172
    178173                                        size_t mask = tls.mask.load(std::memory_order_relaxed);
     
    197192                        while(snzi.query()) {
    198193                                // 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);
    201214
    202215                                if(auto node = try_pop(i, j)) return node;
     
    206219                        while(snzi.query()) {
    207220                                // Pick two lists at random
    208                                 unsigned ri = tls.rng.next();
     221                                unsigned ri = tls.rng1.next();
    209222                                unsigned i;
    210                                 unsigned j = tls.rng.next();
     223                                unsigned j = tls.rng1.next();
    211224                                if(0 == (ri & 0xF)) {
    212225                                        i = (ri >> 4) % numLists;
     
    228241                                {
    229242                                        // 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();
    232245
    233246                                        // Pick two nodes from it
     
    270283                        while(snzm.query()) {
    271284                                // 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;
    274287
    275288                                if(auto node = try_pop(i, j)) return node;
     
    285298                                        unsigned num = ((numLists - 1) >> 6) + 1;
    286299
    287                                         unsigned ri = tls.rng.next();
    288                                         unsigned rj = tls.rng.next();
     300                                        unsigned ri = tls.rng1.next();
     301                                        unsigned rj = tls.rng1.next();
    289302
    290303                                        unsigned wdxi = (ri >> 6u) % num;
     
    314327                        while(numNonEmpty != 0) {
    315328                                // 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;
    318331
    319332                                if(auto node = try_pop(i, j)) return node;
     
    348361                if( !list.lock.try_lock() ) return nullptr;
    349362
    350                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER  && VARIANT != BIAS
     363                #if VARIANT == VANILLA || VARIANT == BITMASK
    351364                        __attribute__((unused)) int num = numNonEmpty;
    352365                #endif
     
    371384                                __attribute__((unused)) bool ret = btr(tls.mask, bit);
    372385                                snzm.depart(w);
    373                         #elif VARIANT == SNZI || VARIANT == BIAS
     386                        #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS
    374387                                snzi.depart(w);
    375388                        #elif VARIANT == SNZM
     
    390403                // Unlock and return
    391404                list.lock.unlock();
    392                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     405                #if VARIANT == VANILLA || VARIANT == BITMASK
    393406                        assert(numNonEmpty >= 0);
    394407                #endif
    395408                #ifndef NO_STATS
    396409                        tls.pick.pop.success++;
    397                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     410                        #if VARIANT == VANILLA || VARIANT == BITMASK
    398411                                tls.empty.pop.value += num;
    399412                                tls.empty.pop.count += 1;
     
    403416        }
    404417
     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        }
    405432
    406433public:
    407434
    408435        static __attribute__((aligned(128))) thread_local struct TLS {
    409                 Random     rng = { int(rdtscl()) };
     436                Random     rng1 = { int(rdtscl()) };
     437                Random     rng2 = { int(rdtscl()) };
    410438                unsigned   my_queue = (ticket++) * 4;
    411439                pick_stat  pick;
     
    418446        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists;
    419447private:
    420         #if VARIANT == SNZI || VARIANT == BIAS
     448        #if VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS
    421449                snzi_t snzi;
    422450        #elif VARIANT == SNZM || VARIANT == DISCOVER
Note: See TracChangeset for help on using the changeset viewer.