Changeset 25a1cb0 for libcfa/src/concurrency/ready_queue.cfa

Timestamp:

Sep 1, 2020, 1:18:10 PM (4 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

86c1f1c3, a77496cb

Parents:

8d8ac3b (diff), d3aa64f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• libcfa/src/concurrency/ready_queue.cfa (modified) (11 diffs)

libcfa/src/concurrency/ready_queue.cfa

@@ -215 +215 @@
 }
 
+static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) {
+        unsigned i;
+        bool local;
+        #if defined(BIAS)
+                unsigned rlow  = r % BIAS;
+                unsigned rhigh = r / BIAS;
+                if((0 != rlow) && preferred >= 0) {
+                        // (BIAS - 1) out of BIAS chances
+                        // Use perferred queues
+                        i = preferred + (rhigh % 4);
+                        local = true;
+                }
+                else {
+                        // 1 out of BIAS chances
+                        // Use all queues
+                        i = rhigh;
+                        local = false;
+                }
+        #else
+                i = r;
+                local = false;
+        #endif
+        return [i, local];
+}
+
 //-----------------------------------------------------------------------
 __attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
@@ -222 +247 @@
         thrd->link.ts = rdtscl();
 
-        #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__)
-                bool local = false;
-                int preferred =
+        __attribute__((unused)) bool local;
+        __attribute__((unused)) int preferred;
+        #if defined(BIAS)
+                preferred =
                         //*
                         kernelTLS.this_processor ? kernelTLS.this_processor->id * 4 : -1;
@@ -230 +256 @@
                         thrd->link.preferred * 4;
                         //*/
-
-
         #endif
 
@@ -238 +262 @@
         do {
                 // Pick the index of a lane
-                #if defined(BIAS)
-                        unsigned r = __tls_rand();
-                        unsigned rlow  = r % BIAS;
-                        unsigned rhigh = r / BIAS;
-                        if((0 != rlow) && preferred >= 0) {
-                                // (BIAS - 1) out of BIAS chances
-                                // Use perferred queues
-                                i = preferred + (rhigh % 4);
-
-                                #if !defined(__CFA_NO_STATISTICS__)
-                                        local = true;
-                                        __tls_stats()->ready.pick.push.local++;
-                                #endif
-                        }
-                        else {
-                                // 1 out of BIAS chances
-                                // Use all queues
-                                i = rhigh;
-                                local = false;
-                        }
-                #else
-                        i = __tls_rand();
+                // unsigned r = __tls_rand();
+                unsigned r = __tls_rand_fwd();
+                [i, local] = idx_from_r(r, preferred);
+
+                #if !defined(__CFA_NO_STATISTICS__)
+                        if(local) {
+                                __tls_stats()->ready.pick.push.local++;
+                        }
                 #endif
 
@@ -274 +284 @@
 
         // Actually push it
-        bool lane_first = push(lanes.data[i], thrd);
+        #ifdef USE_SNZI
+                bool lane_first =
+        #endif
+
+        push(lanes.data[i], thrd);
 
         #ifdef USE_SNZI
@@ -287 +301 @@
         #endif
 
+        __tls_rand_advance_bck();
+
         // Unlock and return
         __atomic_unlock( &lanes.data[i].lock );
@@ -311 +327 @@
         /* paranoid */ verify( lanes.count > 0 );
         unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
+        int preferred;
         #if defined(BIAS)
                 // Don't bother trying locally too much
                 int local_tries = 8;
-        #endif
+                preferred = kernelTLS.this_processor->id * 4;
+        #endif
+
 
         // As long as the list is not empty, try finding a lane that isn't empty and pop from it
@@ -323 +342 @@
         #endif
                 // Pick two lists at random
-                unsigned i,j;
-                #if defined(BIAS)
-                        #if !defined(__CFA_NO_STATISTICS__)
-                                bool local = false;
-                        #endif
-                        uint64_t r = __tls_rand();
-                        unsigned rlow  = r % BIAS;
-                        uint64_t rhigh = r / BIAS;
-                        if(local_tries && 0 != rlow) {
-                                // (BIAS - 1) out of BIAS chances
-                                // Use perferred queues
-                                unsigned pid = kernelTLS.this_processor->id * 4;
-                                i = pid + (rhigh % 4);
-                                j = pid + ((rhigh >> 32ull) % 4);
-
-                                // count the tries
-                                local_tries--;
-
-                                #if !defined(__CFA_NO_STATISTICS__)
-                                        local = true;
-                                        __tls_stats()->ready.pick.pop.local++;
-                                #endif
-                        }
-                        else {
-                                // 1 out of BIAS chances
-                                // Use all queues
-                                i = rhigh;
-                                j = rhigh >> 32ull;
-                        }
-                #else
-                        i = __tls_rand();
-                        j = __tls_rand();
+                // unsigned ri = __tls_rand();
+                // unsigned rj = __tls_rand();
+                unsigned ri = __tls_rand_bck();
+                unsigned rj = __tls_rand_bck();
+
+                unsigned i, j;
+                __attribute__((unused)) bool locali, localj;
+                [i, locali] = idx_from_r(ri, preferred);
+                [j, localj] = idx_from_r(rj, preferred);
+
+                #if !defined(__CFA_NO_STATISTICS__)
+                        if(locali) {
+                                __tls_stats()->ready.pick.pop.local++;
+                        }
+                        if(localj) {
+                                __tls_stats()->ready.pick.pop.local++;
+                        }
                 #endif
 
@@ -364 +368 @@
                 if(thrd) {
                         #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__)
-                                if( local ) __tls_stats()->ready.pick.pop.lsuccess++;
+                                if( locali || localj ) __tls_stats()->ready.pick.pop.lsuccess++;
                         #endif
                         return thrd;
@@ -543 +547 @@
 
                 // Allocate new array (uses realloc and memcpies the data)
-                lanes.data = alloc(lanes.data, ncount);
+                lanes.data = alloc( ncount, lanes.data`realloc );
 
                 // Fix the moved data
@@ -634 +638 @@
 
                 // Allocate new array (uses realloc and memcpies the data)
-                lanes.data = alloc(lanes.data, lanes.count);
+                lanes.data = alloc( lanes.count, lanes.data`realloc );
 
                 // Fix the moved data