Changeset a82a8f4


Ignore:
Timestamp:
Jul 21, 2020, 4:59:34 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, 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

Location:
doc/theses/thierry_delisle_PhD/code
Files:
2 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

  • doc/theses/thierry_delisle_PhD/code/utils.hpp

    r50d529e ra82a8f4  
    3535};
    3636
     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
     54constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b);
     55constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){
     56    return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b));
     57}
     58constexpr 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
    3762class Random {
    3863private:
    39         unsigned int seed;
     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
     71public:
     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);
    4077public:
    4178        Random(int seed) {
    42                 this->seed = seed;
     79                this->x = seed * a;
    4380        }
    4481
    4582        /** returns pseudorandom x satisfying 0 <= x < n. **/
    4683        unsigned int next() {
    47                 seed ^= seed << 6;
    48                 seed ^= seed >> 21;
    49                 seed ^= seed << 7;
    50                 return seed;
    51         }
     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        }
    52102};
    53103
Note: See TracChangeset for help on using the changeset viewer.