Changeset 815943f for libcfa/src/concurrency/kernel

Timestamp:

Oct 5, 2022, 10:10:59 PM (23 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master

Children:

265e460

Parents:

ae151cf (diff), 0deeaad (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

Location:

libcfa/src/concurrency/kernel

Files:

• cluster.cfa (modified) (1 diff)
• cluster.hfa (modified) (5 diffs)
• private.hfa (modified) (1 diff)

libcfa/src/concurrency/kernel/cluster.cfa

@@ -221 +221 @@
 static const unsigned __readyq_single_shard = 2;
 
+void  ?{}(__timestamp_t & this) { this.t.tv = 0; this.t.ma = 0; }
+void ^?{}(__timestamp_t &) {}
+
 //-----------------------------------------------------------------------
 // Check that all the intrusive queues in the data structure are still consistent

libcfa/src/concurrency/kernel/cluster.hfa

@@ -18 +18 @@
 #include "device/cpu.hfa"
 #include "kernel/private.hfa"
+#include "math.hfa"
 
 #include <limits.h>
@@ -23 +24 @@
 #include "clock.hfa"
 
+#if   defined(READYQ_USE_LINEAR_AVG)
+
+// no conversion needed in this case
+static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return intsc; }
+
+// warn normally all ints
+#define warn_large_before warnf( !strict || old_avg < 33_000_000_000, "Suspiciously large previous average: %'llu (%llx), %'ldms \n", old_avg, old_avg, program()`ms )
+#define warn_large_after warnf( !strict || ret < 33_000_000_000, "Suspiciously large new average after %'ldms cputime: %'llu (%llx) from %'llu-%'llu (%'llu, %'llu) and %'llu\n", program()`ms, ret, ret, currtsc, intsc, new_val, new_val / 1000000, old_avg )
+
+// 8X linear factor is just 8 * x
+#define AVG_FACTOR( x ) (8 * (x))
+
+#elif defined(READYQ_USE_LOGDBL_AVG)
+
+// convert to log2 scale but using double
+static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { if(unlikely(0 == intsc)) return 0.0; else return log2(intsc); }
+
+#define warn_large_before warnf( !strict || old_avg < 35.0, "Suspiciously large previous average: %'lf, %'ldms \n", old_avg, program()`ms )
+#define warn_large_after warnf( !strict || ret < 35.3, "Suspiciously large new average after %'ldms cputime: %'lf from %'llu-%'llu (%'llu, %'llu) and %'lf\n", program()`ms, ret, currtsc, intsc, new_val, new_val / 1000000, old_avg ); \
+verify(ret >= 0)
+
+// 8X factor in logscale is log2(8X) = log2(8) + log2(X) = 3 + log2(X)
+#define AVG_FACTOR( x ) (3.0 + (x))
+
+// we need to overload the __atomic_load_n because they don't support double
+static inline double __atomic_load_n(volatile double * ptr, int mem) {
+        volatile uint64_t * uptr = (volatile uint64_t *)ptr;
+        _Static_assert(sizeof(*uptr) == sizeof(*ptr));
+        uint64_t ret = 0;
+        ret = __atomic_load_n(uptr, mem);
+        uint64_t *rp = &ret;
+        double ret = *(volatile double *)rp;
+        /* paranoid */ verify( ret == 0 || ret > 3e-100 );
+        return ret;
+}
+
+// we need to overload the __atomic_store_n because they don't support double
+static inline void __atomic_store_n(volatile double * ptr, double val, int mem) {
+        /* paranoid */ verify( val == 0 || val > 3e-100 );
+        volatile uint64_t * uptr = (volatile uint64_t *)ptr;
+        _Static_assert(sizeof(*uptr) == sizeof(*ptr));
+        uint64_t * valp = (uint64_t *)&val;
+        __atomic_store_n(uptr, *valp, mem);
+}
+
+#elif defined(READYQ_USE_LOGDBL_AVG)
+
+//convert to log2 scale but with fix point u32.32 values
+static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return ulog2_32_32(tsc); }
+
+// 8X factor, +3 in logscale (see above) is + 0x3.00000000
+#define AVG_FACTOR( x ) (0x3_00000000ull + (x))
+
+#else
+#error must pick a scheme for averaging
+#endif
+
 //-----------------------------------------------------------------------
 // Calc moving average based on existing average, before and current time.
-static inline unsigned long long moving_average(unsigned long long currtsc, unsigned long long instsc, unsigned long long old_avg, bool strict) {
+static inline __readyQ_avg_t moving_average(unsigned long long currtsc, unsigned long long intsc, __readyQ_avg_t old_avg, bool strict) {
         (void)strict; // disable the warning around the fact this is unused in release.
-        /* paranoid */ warnf( !strict || old_avg < 33_000_000_000, "Suspiciously large previous average: %'llu (%llx), %'ldms \n", old_avg, old_avg, program()`ms );
+        /* paranoid */ warn_large_before;
 
-        const unsigned long long new_val = currtsc > instsc ? currtsc - instsc : 0;
-        const unsigned long long total_weight = 16;
-        const unsigned long long new_weight   = 4;
-        const unsigned long long old_weight = total_weight - new_weight;
-        const unsigned long long ret = ((new_weight * new_val) + (old_weight * old_avg)) / total_weight;
+        const unsigned long long new_val = currtsc > intsc ? currtsc - intsc : 0;
+        const __readyQ_avg_t total_weight = 16;
+        const __readyQ_avg_t new_weight   = 12;
+        const __readyQ_avg_t old_weight = total_weight - new_weight;
+        const __readyQ_avg_t ret = ((new_weight * __to_readyQ_avg(new_val)) + (old_weight * old_avg)) / total_weight;
 
-        /* paranoid */ warnf( !strict || ret < 33_000_000_000, "Suspiciously large new average after %'ldms cputime: %'llu (%llx) from %'llu-%'llu (%'llu, %'llu) and %'llu\n", program()`ms, ret, ret, currtsc, instsc, new_val, new_val / 1000000, old_avg );
+        /* paranoid */ warn_large_after;
         return ret;
 }
@@ -42 +100 @@
         if (ts_next == ULLONG_MAX) return;
         unsigned long long now = rdtscl();
-        unsigned long long pma = __atomic_load_n(&tscs[ idx ].t.ma, __ATOMIC_RELAXED);
+        __readyQ_avg_t pma = __atomic_load_n(&tscs[ idx ].t.ma, __ATOMIC_RELAXED);
         __atomic_store_n(&tscs[ idx ].t.tv, ts_next, __ATOMIC_RELAXED);
         __atomic_store_n(&tscs[ idx ].t.ma, moving_average(now, ts_prev, pma, strict), __ATOMIC_RELAXED);
@@ -50 +108 @@
 // Calc age a timestamp should be before needing help.
 forall(Data_t * | { unsigned long long ts(Data_t & this); })
-static inline unsigned long long calc_cutoff(
+static inline __readyQ_avg_t calc_cutoff(
         const unsigned long long ctsc,
         unsigned procid,
@@ -60 +118 @@
 ) {
         unsigned start = procid;
-        unsigned long long max = 0;
+        __readyQ_avg_t max = 0;
         for(i; shard_factor) {
                 unsigned long long ptsc = ts(data[start + i]);
                 if(ptsc != ULLONG_MAX) {
                         /* paranoid */ verify( start + i < count );
-                        unsigned long long tsc = moving_average(ctsc, ptsc, tscs[start + i].t.ma, strict);
-                        if(tsc > max) max = tsc;
+                        __readyQ_avg_t avg = moving_average(ctsc, ptsc, tscs[start + i].t.ma, strict);
+                        if(avg > max) max = avg;
                 }
         }
-        return 8 * max;
+        return AVG_FACTOR( max );
 }
 

libcfa/src/concurrency/kernel/private.hfa

@@ -49 +49 @@
 #endif
 
+// #define READYQ_USE_LINEAR_AVG
+#define READYQ_USE_LOGDBL_AVG
+// #define READYQ_USE_LOGINT_AVG
+
+#if   defined(READYQ_USE_LINEAR_AVG)
+typedef unsigned long long __readyQ_avg_t;
+#elif defined(READYQ_USE_LOGDBL_AVG)
+typedef double __readyQ_avg_t;
+#elif defined(READYQ_USE_LOGDBL_AVG)
+typedef unsigned long long __readyQ_avg_t;
+#else
+#error must pick a scheme for averaging
+#endif
+
 //-----------------------------------------------------------------------------
 // Scheduler
+union __attribute__((aligned(64))) __timestamp_t {
+        struct {
+                volatile unsigned long long tv;
+                volatile __readyQ_avg_t ma;
+        } t;
+        char __padding[192];
+};
+
 extern "C" {
         void disable_interrupts() OPTIONAL_THREAD;