Changeset 04b5cef

Timestamp:

Jun 19, 2020, 11:22:32 AM (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:

64a7146

Parents:

37ba662

Message:

Added BIAS option to ready_queue
Added yield test for LibFibre?
Fixed some alignments and minor optimizations

Files:

• benchmark/readyQ/yield.cfa (modified) (2 diffs)
• benchmark/readyQ/yield.cpp (added)
• libcfa/src/concurrency/kernel.cfa (modified) (1 diff)
• libcfa/src/concurrency/ready_queue.cfa (modified) (4 diffs)
• libcfa/src/containers/stackLockFree.hfa (modified) (3 diffs)

benchmark/readyQ/yield.cfa

@@ -22 +22 @@
 volatile unsigned long long global_counter;
 
-thread __attribute__((aligned(64))) Yielder {
+thread __attribute__((aligned(128))) Yielder {
         unsigned long long counter;
 };
@@ -113 +113 @@
                         {
                                 Yielder threads[nthreads];
+                                bool is_tty = isatty(STDOUT_FILENO);
                                 printf("Starting\n");
                                 start = getTime();
                                 run = true;
 
-                                bool is_tty = isatty(STDOUT_FILENO);
                                 for(i; nthreads) {
                                         unpark( threads[i] __cfaabi_dbg_ctx2 );

libcfa/src/concurrency/kernel.cfa

@@ -342 +342 @@
                                 /* paranoid */ verifyf( readyThread->state == Ready || readyThread->preempted != __NO_PREEMPTION, "state : %d, preempted %d\n", readyThread->state, readyThread->preempted);
                                 /* paranoid */ verifyf( readyThread->link.next == 0p, "Expected null got %p", readyThread->link.next );
+                                __builtin_prefetch( readyThread->context.SP );
 
                                 // We found a thread run it

libcfa/src/concurrency/ready_queue.cfa

@@ -24 +24 @@
 #include "math.hfa"
 
+#include <unistd.h>
+
 static const size_t cache_line_size = 64;
 
@@ -31 +33 @@
         #define __CFA_MAX_PROCESSORS__ 1024
 #endif
+
+#define BIAS 64
 
 // returns the maximum number of processors the RWLock support
@@ -568 +572 @@
         do {
                 // Pick the index of a lane
-                i = __tls_rand() % lanes.count;
+                #if defined(BIAS)
+                        unsigned r = __tls_rand();
+                        unsigned rlow  = r % BIAS;
+                        unsigned rhigh = r / BIAS;
+                        if(0 != (rlow % BIAS) && kernelTLS.this_processor) {
+                                // (BIAS - 1) out of BIAS chances
+                                // Use perferred queues
+                                i = (kernelTLS.this_processor->id * 4) + (rhigh % 4);
+                        }
+                        else {
+                                // 1 out of BIAS chances
+                                // Use all queues
+                                i = rhigh;
+                        }
+                #else
+                        i = __tls_rand();
+                #endif
+
+                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
 
                 #if !defined(__CFA_NO_STATISTICS__)
@@ -666 +688 @@
         while( query(snzi) ) {
                 // Pick two lists at random
-                int i = __tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
-                int j = __tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
+                #if defined(BIAS)
+                        unsigned i = __tls_rand();
+                        unsigned j = __tls_rand();
+
+                        if(0 == (i % BIAS)) {
+                                i = i / BIAS;
+                        }
+                        else {
+                                i = ((kernelTLS.this_processor->id * 4) + ((i / BIAS) % 4));
+                                j = ((kernelTLS.this_processor->id * 4) + ((j / BIAS) % 4));
+                        }
+                #else
+                        unsigned i = __tls_rand();
+                        unsigned j = __tls_rand();
+                #endif
+
+                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
+                j %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
 
                 // try popping from the 2 picked lists

libcfa/src/containers/stackLockFree.hfa

@@ -1 @@
-// 
+//
 // Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
 // The contents of this file are covered under the licence agreement in the
 // file "LICENCE" distributed with Cforall.
 //
-// stackLockFree.hfa -- 
-// 
+// stackLockFree.hfa --
+//
 // Author           : Peter A. Buhr
 // Created On       : Wed May 13 20:58:58 2020
@@ -11 +11 @@
 // Last Modified On : Mon May 18 13:30:08 2020
 // Update Count     : 55
-// 
+//
 
 #pragma once
@@ -20 +20 @@
 union Link {
         struct {                                                                        // 32/64-bit x 2
-                T * top;                                                                // pointer to stack top
+                T * volatile top;                                                               // pointer to stack top
                 uintptr_t count;                                                // count each push
         };