Changeset 47a541d

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:

• relaxed_list.hpp (modified) (13 diffs)
• snzm.hpp (added)
• utils.hpp (modified) (1 diff)

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -8 +8 @@
 #define BITMASK 2
 #define DISCOVER 3
+#define SNZM 4
 
 #ifndef VARIANT
@@ -25 +26 @@
 #include "utils.hpp"
 #include "snzi.hpp"
+#include "snzm.hpp"
 
 using namespace std;
@@ -71 +73 @@
                         "SNZI",
                         "BITMASK",
-                        "DISCOVER"
+                        "DISCOVER",
+                        "SNZI + MASK"
                 };
                 return names[VARIANT];
@@ -80 +83 @@
                 , numLists(numLists)
                 #if VARIANT == SNZI || VARIANT == DISCOVER
-                        , snzi( std::log2( numLists / 8 ) )
+                        , snzi( 1, 8 )
+                #elif VARIANT == SNZM
+                        , snzm( numLists )
                 #endif
         {
@@ -112 +117 @@
                         if( !lists[i].lock.try_lock() ) continue;
 
-                        #if VARIANT != SNZI && VARIANT != DISCOVER
+                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
                                 __attribute__((unused)) int num = numNonEmpty;
                         #endif
@@ -126 +131 @@
                                 #elif VARIANT == SNZI
                                         snzi.arrive(i);
+                                #elif VARIANT == SNZM
+                                        snzm.arrive(i);
                                 #elif VARIANT == BITMASK
                                         numNonEmpty++;
@@ -138 +145 @@
                                 #endif
                         }
-                        #if VARIANT != SNZI && VARIANT != DISCOVER
+                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
                                 assert(numNonEmpty <= (int)numLists);
                         #endif
@@ -147 +154 @@
                         #ifndef NO_STATS
                                 tls.pick.push.success++;
-                                #if VARIANT != SNZI && VARIANT != DISCOVER
+                                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
                                         tls.empty.push.value += num;
                                         tls.empty.push.count += 1;
@@ -194 +201 @@
                                 if(auto node = try_pop(i, j)) return node;
                         }
+                #elif VARIANT == SNZM
+                        while(snzm.query()) {
+                                tls.pick.pop.mask_attempt++;
+                                unsigned i, j;
+                                {
+                                        // Pick two random number
+                                        unsigned ri = tls.rng.next();
+                                        unsigned rj = tls.rng.next();
+
+                                        // Pick two nodes from it
+                                        unsigned wdxi = ri & snzm.mask;
+                                        unsigned wdxj = rj & snzm.mask;
+
+                                        // Get the masks from the nodes
+                                        size_t maski = snzm.masks(wdxi);
+                                        size_t maskj = snzm.masks(wdxj);
+
+                                        if(maski == 0 && maskj == 0) continue;
+
+                                        unsigned bi = rand_bit(ri >> snzm.depth, maski);
+                                        unsigned bj = rand_bit(rj >> snzm.depth, maskj);
+
+                                        assertf(bi < 64, "%zu %u", maski, bi);
+                                        assertf(bj < 64, "%zu %u", maskj, bj);
+
+                                        i = (bi << snzm.depth) | wdxi;
+                                        j = (bj << snzm.depth) | wdxj;
+
+                                        assertf(i < numLists, "%u %u", bj, wdxi);
+                                        assertf(j < numLists, "%u %u", bj, wdxj);
+                                }
+
+                                if(auto node = try_pop(i, j)) return node;
+                        }
                 #elif VARIANT == BITMASK
                         int nnempty;
@@ -266 +307 @@
                 if( !list.lock.try_lock() ) return nullptr;
 
-                #if VARIANT != SNZI && VARIANT != DISCOVER
+                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
                         __attribute__((unused)) int num = numNonEmpty;
                 #endif
@@ -291 +332 @@
                         #elif VARIANT == SNZI
                                 snzi.depart(w);
+                        #elif VARIANT == SNZM
+                                snzm.depart(w);
                         #elif VARIANT == BITMASK
                                 numNonEmpty--;
@@ -306 +349 @@
                 // Unlock and return
                 list.lock.unlock();
-                #if VARIANT != SNZI && VARIANT != DISCOVER
+                #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
                         assert(numNonEmpty >= 0);
                 #endif
                 #ifndef NO_STATS
                         tls.pick.pop.success++;
-                        #if VARIANT != SNZI && VARIANT != DISCOVER
+                        #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER
                                 tls.empty.pop.value += num;
                                 tls.empty.pop.count += 1;
@@ -459 +502 @@
         #if VARIANT == SNZI || VARIANT == DISCOVER
                 snzi_t snzi;
+        #elif VARIANT == SNZM
+                snzm_t snzm;
         #else
                 std::atomic_int numNonEmpty  = { 0 };  // number of non-empty lists

doc/theses/thierry_delisle_PhD/code/utils.hpp

@@ -106 +106 @@
 }
 
+static inline unsigned rand_bit(unsigned rnum, size_t mask) __attribute__((artificial));
 static inline unsigned rand_bit(unsigned rnum, size_t mask) {
         unsigned bit = mask ? rnum % __builtin_popcountl(mask) : 0;