Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rb232745 rf0c3120  
    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;
Note: See TracChangeset for help on using the changeset viewer.