Changes in / [a0e7d3c:92b9958]

Location:

libcfa/src/concurrency

Files:

• kernel.hfa (modified) (1 diff)
• kernel_private.hfa (modified) (1 diff)
• ready_queue.cfa (modified) (11 diffs)

libcfa/src/concurrency/kernel.hfa

@@ -145 +145 @@
 void ^?{}(__intrusive_lane_t & this);
 
+// Counter used for wether or not the lanes are all empty
+struct __attribute__((aligned(128))) __snzi_node_t;
+struct __snzi_t {
+        unsigned mask;
+        int root;
+        __snzi_node_t * nodes;
+};
+
+void  ?{}( __snzi_t & this, unsigned depth );
+void ^?{}( __snzi_t & this );
+
 //TODO adjust cache size to ARCHITECTURE
 // Structure holding the relaxed ready queue
 struct __ready_queue_t {
+        // Data tracking how many/which lanes are used
+        // Aligned to 128 for cache locality
+        __snzi_t snzi;
+
         // Data tracking the actual lanes
         // On a seperate cacheline from the used struct since

libcfa/src/concurrency/kernel_private.hfa

@@ -284 +284 @@
 // Ready-Queue API
 //-----------------------------------------------------------------------
+// pop thread from the ready queue of a cluster
+// returns 0p if empty
+__attribute__((hot)) bool query(struct cluster * cltr);
+
+//-----------------------------------------------------------------------
 // push thread onto a ready queue for a cluster
 // returns true if the list was previously empty, false otherwise

libcfa/src/concurrency/ready_queue.cfa

@@ -17 +17 @@
 // #define __CFA_DEBUG_PRINT_READY_QUEUE__
 
+// #define USE_SNZI
 // #define USE_MPSC
 
@@ -28 +29 @@
 #include <unistd.h>
 
+#include "snzi.hfa"
 #include "ready_subqueue.hfa"
 
@@ -200 +202 @@
 void ^?{}(__ready_queue_t & this) with (this) {
         verify( 1 == lanes.count );
+        #ifdef USE_SNZI
+                verify( !query( snzi ) );
+        #endif
         free(lanes.data);
 }
 
 //-----------------------------------------------------------------------
+__attribute__((hot)) bool query(struct cluster * cltr) {
+        #ifdef USE_SNZI
+                return query(cltr->ready_queue.snzi);
+        #endif
+        return true;
+}
+
 static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) {
         unsigned i;
@@ -281 +293 @@
 
         // Actually push it
+        #ifdef USE_SNZI
+                bool lane_first =
+        #endif
+
         push(lanes.data[i], thrd);
+
+        #ifdef USE_SNZI
+                // If this lane used to be empty we need to do more
+                if(lane_first) {
+                        // Check if the entire queue used to be empty
+                        first = !query(snzi);
+
+                        // Update the snzi
+                        arrive( snzi, i );
+                }
+        #endif
 
         #if !defined(USE_MPSC)
@@ -324 +351 @@
 
         // As long as the list is not empty, try finding a lane that isn't empty and pop from it
-        for(25) {
+        #ifdef USE_SNZI
+                while( query(snzi) ) {
+        #else
+                for(25) {
+        #endif
                 // Pick two lists at random
                 // unsigned ri = __tls_rand();
@@ -416 +447 @@
         /* paranoid */ verify(lane.lock);
 
+        #ifdef USE_SNZI
+                // If this was the last element in the lane
+                if(emptied) {
+                        depart( snzi, w );
+                }
+        #endif
+
         // Unlock and return
         __atomic_unlock(&lane.lock);
@@ -446 +484 @@
 
                                 removed = true;
+                                #ifdef USE_SNZI
+                                        if(emptied) {
+                                                depart( snzi, i );
+                                        }
+                                #endif
                         }
                 __atomic_unlock(&lane.lock);
@@ -528 +571 @@
         // grow the ready queue
         with( cltr->ready_queue ) {
+                #ifdef USE_SNZI
+                        ^(snzi){};
+                #endif
+
                 // Find new count
                 // Make sure we always have atleast 1 list
@@ -551 +598 @@
                 // Update original
                 lanes.count = ncount;
+
+                #ifdef USE_SNZI
+                        // Re-create the snzi
+                        snzi{ log2( lanes.count / 8 ) };
+                        for( idx; (size_t)lanes.count ) {
+                                if( !is_empty(lanes.data[idx]) ) {
+                                        arrive(snzi, idx);
+                                }
+                        }
+                #endif
         }
 
@@ -574 +631 @@
 
         with( cltr->ready_queue ) {
+                #ifdef USE_SNZI
+                        ^(snzi){};
+                #endif
+
                 // Remember old count
                 size_t ocount = lanes.count;
@@ -624 +685 @@
                         fix(lanes.data[idx]);
                 }
+
+                #ifdef USE_SNZI
+                        // Re-create the snzi
+                        snzi{ log2( lanes.count / 8 ) };
+                        for( idx; (size_t)lanes.count ) {
+                                if( !is_empty(lanes.data[idx]) ) {
+                                        arrive(snzi, idx);
+                                }
+                        }
+                #endif
         }