Ignore:
Timestamp:
Jun 2, 2020, 2:38:25 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:
16ee228
Parents:
0092853
Message:

Add first draft of SNZI + MASK approach

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

Legend:

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

    r0092853 r47a541d  
    88#define BITMASK 2
    99#define DISCOVER 3
     10#define SNZM 4
    1011
    1112#ifndef VARIANT
     
    2526#include "utils.hpp"
    2627#include "snzi.hpp"
     28#include "snzm.hpp"
    2729
    2830using namespace std;
     
    7173                        "SNZI",
    7274                        "BITMASK",
    73                         "DISCOVER"
     75                        "DISCOVER",
     76                        "SNZI + MASK"
    7477                };
    7578                return names[VARIANT];
     
    8083                , numLists(numLists)
    8184                #if VARIANT == SNZI || VARIANT == DISCOVER
    82                         , snzi( std::log2( numLists / 8 ) )
     85                        , snzi( 1, 8 )
     86                #elif VARIANT == SNZM
     87                        , snzm( numLists )
    8388                #endif
    8489        {
     
    112117                        if( !lists[i].lock.try_lock() ) continue;
    113118
    114                         #if VARIANT != SNZI && VARIANT != DISCOVER
     119                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
    115120                                __attribute__((unused)) int num = numNonEmpty;
    116121                        #endif
     
    126131                                #elif VARIANT == SNZI
    127132                                        snzi.arrive(i);
     133                                #elif VARIANT == SNZM
     134                                        snzm.arrive(i);
    128135                                #elif VARIANT == BITMASK
    129136                                        numNonEmpty++;
     
    138145                                #endif
    139146                        }
    140                         #if VARIANT != SNZI && VARIANT != DISCOVER
     147                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
    141148                                assert(numNonEmpty <= (int)numLists);
    142149                        #endif
     
    147154                        #ifndef NO_STATS
    148155                                tls.pick.push.success++;
    149                                 #if VARIANT != SNZI && VARIANT != DISCOVER
     156                                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
    150157                                        tls.empty.push.value += num;
    151158                                        tls.empty.push.count += 1;
     
    194201                                if(auto node = try_pop(i, j)) return node;
    195202                        }
     203                #elif VARIANT == SNZM
     204                        while(snzm.query()) {
     205                                tls.pick.pop.mask_attempt++;
     206                                unsigned i, j;
     207                                {
     208                                        // Pick two random number
     209                                        unsigned ri = tls.rng.next();
     210                                        unsigned rj = tls.rng.next();
     211
     212                                        // Pick two nodes from it
     213                                        unsigned wdxi = ri & snzm.mask;
     214                                        unsigned wdxj = rj & snzm.mask;
     215
     216                                        // Get the masks from the nodes
     217                                        size_t maski = snzm.masks(wdxi);
     218                                        size_t maskj = snzm.masks(wdxj);
     219
     220                                        if(maski == 0 && maskj == 0) continue;
     221
     222                                        unsigned bi = rand_bit(ri >> snzm.depth, maski);
     223                                        unsigned bj = rand_bit(rj >> snzm.depth, maskj);
     224
     225                                        assertf(bi < 64, "%zu %u", maski, bi);
     226                                        assertf(bj < 64, "%zu %u", maskj, bj);
     227
     228                                        i = (bi << snzm.depth) | wdxi;
     229                                        j = (bj << snzm.depth) | wdxj;
     230
     231                                        assertf(i < numLists, "%u %u", bj, wdxi);
     232                                        assertf(j < numLists, "%u %u", bj, wdxj);
     233                                }
     234
     235                                if(auto node = try_pop(i, j)) return node;
     236                        }
    196237                #elif VARIANT == BITMASK
    197238                        int nnempty;
     
    266307                if( !list.lock.try_lock() ) return nullptr;
    267308
    268                 #if VARIANT != SNZI && VARIANT != DISCOVER
     309                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
    269310                        __attribute__((unused)) int num = numNonEmpty;
    270311                #endif
     
    291332                        #elif VARIANT == SNZI
    292333                                snzi.depart(w);
     334                        #elif VARIANT == SNZM
     335                                snzm.depart(w);
    293336                        #elif VARIANT == BITMASK
    294337                                numNonEmpty--;
     
    306349                // Unlock and return
    307350                list.lock.unlock();
    308                 #if VARIANT != SNZI && VARIANT != DISCOVER
     351                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
    309352                        assert(numNonEmpty >= 0);
    310353                #endif
    311354                #ifndef NO_STATS
    312355                        tls.pick.pop.success++;
    313                         #if VARIANT != SNZI && VARIANT != DISCOVER
     356                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
    314357                                tls.empty.pop.value += num;
    315358                                tls.empty.pop.count += 1;
     
    459502        #if VARIANT == SNZI || VARIANT == DISCOVER
    460503                snzi_t snzi;
     504        #elif VARIANT == SNZM
     505                snzm_t snzm;
    461506        #else
    462507                std::atomic_int numNonEmpty  = { 0 };  // number of non-empty lists
  • doc/theses/thierry_delisle_PhD/code/utils.hpp

    r0092853 r47a541d  
    106106}
    107107
     108static inline unsigned rand_bit(unsigned rnum, size_t mask) __attribute__((artificial));
    108109static inline unsigned rand_bit(unsigned rnum, size_t mask) {
    109110        unsigned bit = mask ? rnum % __builtin_popcountl(mask) : 0;
Note: See TracChangeset for help on using the changeset viewer.