Changes in / [42cd451e:f4ec4a90]


Ignore:
Location:
doc/theses/thierry_delisle_PhD/code
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed

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

    r42cd451e rf4ec4a90  
    88#define SNZM 4
    99#define BIAS 5
     10#define BACK 6
     11#define BACKBIAS 7
    1012
    1113#ifndef VARIANT
    … …  
    1820
    1921#include <cmath>
     22#include <functional>
    2023#include <memory>
    2124#include <mutex>
     25#include <thread>
    2226#include <type_traits>
    2327
    … …  
    2630#include "links.hpp"
    2731#include "snzi.hpp"
     32#include "snzi-packed.hpp"
    2833#include "snzm.hpp"
    2934
    … …  
    6873                        "RELAXED: SNZI + DISCOVERED MASK",
    6974                        "RELAXED: SNZI + MASK",
    70                         "RELAXED: SNZI + LOCAL BIAS"
     75                        "RELAXED: SNZI + LOCAL BIAS",
     76                        "RELAXED: SNZI + REVERSE RNG",
     77                        "RELAXED: SNZI + LOCAL BIAS + REVERSE RNG"
    7178                };
    7279                return names[VARIANT];
    … …  
    7683                : numLists(numThreads * numQueues)
    7784                , lists(new intrusive_queue_t<node_t>[numLists])
    78                 #if VARIANT == SNZI || VARIANT == BIAS
     85                #if VARIANT == SNZI || VARIANT == BACK
    7986                        , snzi( std::log2( numLists / (2 * numQueues) ), 2 )
     87                #elif VARIANT == BIAS || VARIANT == BACKBIAS
     88                        #ifdef SNZI_PACKED
     89                                , snzi( std::ceil( std::log2(numLists) ) )
     90                        #else
     91                                , snzi( std::log2( numLists / (2 * numQueues) ), 2 )
     92                        #endif
    8093                #elif VARIANT == SNZM || VARIANT == DISCOVER
    8194                        , snzm( numLists )
    … …  
    96109                while(true) {
    97110                        // 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
     111                        unsigned i = idx_from_r(tls.rng1.next(), VARIANT == BIAS || VARIANT == BACKBIAS);
    111112
    112113                        #ifndef NO_STATS
    … …  
    117118                        if( !lists[i].lock.try_lock() ) continue;
    118119
    119                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     120                        #if VARIANT == VANILLA || VARIANT == BITMASK
    120121                                __attribute__((unused)) int num = numNonEmpty;
    121122                        #endif
    … …  
    131132                                #elif VARIANT == SNZI || VARIANT == BIAS
    132133                                        snzi.arrive(i);
     134                                #elif VARIANT == BACK || VARIANT == BACKBIAS
     135                                        snzi.arrive(i);
     136                                        tls.rng2.set_raw_state( tls.rng1.get_raw_state());
    133137                                #elif VARIANT == SNZM
    134138                                        snzm.arrive(i);
    … …  
    145149                                #endif
    146150                        }
    147                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     151                        #if VARIANT == VANILLA || VARIANT == BITMASK
    148152                                assert(numNonEmpty <= (int)numLists);
    149153                        #endif
    … …  
    154158                        #ifndef NO_STATS
    155159                                tls.pick.push.success++;
    156                                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     160                                #if VARIANT == VANILLA || VARIANT == BITMASK
    157161                                        tls.empty.push.value += num;
    158162                                        tls.empty.push.count += 1;
    … …  
    171175                                {
    172176                                        // Pick first list totally randomly
    173                                         i = tls.rng.next() % numLists;
     177                                        i = tls.rng1.next() % numLists;
    174178
    175179                                        // Pick the other according to the bitmask
    176                                         unsigned r = tls.rng.next();
     180                                        unsigned r = tls.rng1.next();
    177181
    178182                                        size_t mask = tls.mask.load(std::memory_order_relaxed);
    … …  
    197201                        while(snzi.query()) {
    198202                                // Pick two lists at random
    199                                 int i = tls.rng.next() % numLists;
    200                                 // int j = tls.rng.next() % numLists;
     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);
    201223
    202224                                if(auto node = try_pop(i, j)) return node;
    … …  
    206228                        while(snzi.query()) {
    207229                                // Pick two lists at random
    208                                 unsigned ri = tls.rng.next();
     230                                unsigned ri = tls.rng1.next();
    209231                                unsigned i;
    210                                 unsigned j = tls.rng.next();
     232                                unsigned j = tls.rng1.next();
    211233                                if(0 == (ri & 0xF)) {
    212234                                        i = (ri >> 4) % numLists;
    … …  
    228250                                {
    229251                                        // Pick two random number
    230                                         unsigned ri = tls.rng.next();
    231                                         unsigned rj = tls.rng.next();
     252                                        unsigned ri = tls.rng1.next();
     253                                        unsigned rj = tls.rng1.next();
    232254
    233255                                        // Pick two nodes from it
    … …  
    270292                        while(snzm.query()) {
    271293                                // Pick two lists at random
    272                                 int i = tls.rng.next() % numLists;
    273                                 int j = tls.rng.next() % numLists;
     294                                int i = tls.rng1.next() % numLists;
     295                                int j = tls.rng1.next() % numLists;
    274296
    275297                                if(auto node = try_pop(i, j)) return node;
    … …  
    285307                                        unsigned num = ((numLists - 1) >> 6) + 1;
    286308
    287                                         unsigned ri = tls.rng.next();
    288                                         unsigned rj = tls.rng.next();
     309                                        unsigned ri = tls.rng1.next();
     310                                        unsigned rj = tls.rng1.next();
    289311
    290312                                        unsigned wdxi = (ri >> 6u) % num;
    … …  
    314336                        while(numNonEmpty != 0) {
    315337                                // Pick two lists at random
    316                                 int i = tls.rng.next() % numLists;
    317                                 int j = tls.rng.next() % numLists;
     338                                int i = tls.rng1.next() % numLists;
     339                                int j = tls.rng1.next() % numLists;
    318340
    319341                                if(auto node = try_pop(i, j)) return node;
    … …  
    348370                if( !list.lock.try_lock() ) return nullptr;
    349371
    350                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER  && VARIANT != BIAS
     372                #if VARIANT == VANILLA || VARIANT == BITMASK
    351373                        __attribute__((unused)) int num = numNonEmpty;
    352374                #endif
    … …  
    371393                                __attribute__((unused)) bool ret = btr(tls.mask, bit);
    372394                                snzm.depart(w);
    373                         #elif VARIANT == SNZI || VARIANT == BIAS
     395                        #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS
    374396                                snzi.depart(w);
    375397                        #elif VARIANT == SNZM
    … …  
    390412                // Unlock and return
    391413                list.lock.unlock();
    392                 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     414                #if VARIANT == VANILLA || VARIANT == BITMASK
    393415                        assert(numNonEmpty >= 0);
    394416                #endif
    395417                #ifndef NO_STATS
    396418                        tls.pick.pop.success++;
    397                         #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS
     419                        #if VARIANT == VANILLA || VARIANT == BITMASK
    398420                                tls.empty.pop.value += num;
    399421                                tls.empty.pop.count += 1;
    … …  
    403425        }
    404426
     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        }
    405441
    406442public:
    407443
    408444        static __attribute__((aligned(128))) thread_local struct TLS {
    409                 Random     rng = { int(rdtscl()) };
     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()) };
    410447                unsigned   my_queue = (ticket++) * 4;
    411448                pick_stat  pick;
    … …  
    418455        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists;
    419456private:
    420         #if VARIANT == SNZI || VARIANT == BIAS
     457        #if VARIANT == SNZI || VARIANT == BACK
    421458                snzi_t snzi;
     459        #elif VARIANT == BIAS || VARIANT == BACKBIAS
     460                #ifdef SNZI_PACKED
     461                        snzip_t snzi;
     462                #else
     463                        snzi_t snzi;
     464                #endif
    422465        #elif VARIANT == SNZM || VARIANT == DISCOVER
    423466                snzm_t snzm;

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

    r42cd451e rf4ec4a90  
    1414
    1515        void arrive(int idx) {
     16                idx >>= 2;
    1617                idx %= mask;
    1718                nodes[idx].arrive();
    … …  
    1920
    2021        void depart(int idx) {
     22                idx >>= 2;
    2123                idx %= mask;
    2224                nodes[idx].depart();
    … …  
    8284                                if( x.cnt == val_t::Half ) {
    8385                                        /* paranoid */ assert(parent);
    84                                         parent->arrive();
     86                                        if(undoArr == 2) {
     87                                                undoArr--;
     88                                        } else {
     89                                                parent->arrive();
     90                                        }
    8591                                        if( !value.cas(x, 1, x.ver) ) {
    8692                                                undoArr = undoArr + 1;
    … …  
    151157{
    152158        int width = std::pow(base, depth);
    153         std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ")" << std::endl;
     159        std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ") " << (sizeof(snzi_t::node) * (root + 1)) << " bytes" << std::endl;
    154160        for(int i = 0; i < root; i++) {
    155                 nodes[i].parent = &nodes[(i / base) + width ];
     161                std::cout << i << " -> " << (i / base) + width << std::endl;
     162                nodes[i].parent = &nodes[(i / base) + width];
    156163        }
    157164}

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

    r42cd451e rf4ec4a90  
    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
    4071public:
    41         Random(int seed) {
    42                 this->seed = seed;
     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);
     77public:
     78        Random(unsigned int 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.