Changeset 815943f for libcfa/src

Timestamp:

Oct 5, 2022, 10:10:59 PM (3 years 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

Files:

• concurrency/io.cfa (modified) (1 diff)
• concurrency/kernel.hfa (modified) (1 diff)
• concurrency/kernel/cluster.cfa (modified) (1 diff)
• concurrency/kernel/cluster.hfa (modified) (5 diffs)
• concurrency/kernel/private.hfa (modified) (1 diff)
• concurrency/ready_queue.cfa (modified) (1 diff)
• math.hfa (modified) (3 diffs)

libcfa/src/concurrency/io.cfa

@@ -243 +243 @@
                                 /* paranoid */ verify( io.tscs[target].t.tv != ULLONG_MAX );
                                 HELP: if(target < ctxs_count) {
-                                        const unsigned long long cutoff = calc_cutoff(ctsc, ctx->cq.id, ctxs_count, io.data, io.tscs, __shard_factor.io, false);
-                                        const unsigned long long age = moving_average(ctsc, io.tscs[target].t.tv, io.tscs[target].t.ma, false);
+                                        const __readyQ_avg_t cutoff = calc_cutoff(ctsc, ctx->cq.id, ctxs_count, io.data, io.tscs, __shard_factor.io, false);
+                                        const __readyQ_avg_t age = moving_average(ctsc, io.tscs[target].t.tv, io.tscs[target].t.ma, false);
                                         __cfadbg_print_safe(io, "Kernel I/O: Help attempt on %u from %u, age %'llu vs cutoff %'llu, %s\n", target, ctx->cq.id, age, cutoff, age > cutoff ? "yes" : "no");
                                         if(age <= cutoff) break HELP;

libcfa/src/concurrency/kernel.hfa

@@ -181 +181 @@
 
 // Aligned timestamps which are used by the ready queue and io subsystem
-union __attribute__((aligned(64))) __timestamp_t {
-        struct {
-                volatile unsigned long long tv;
-                volatile unsigned long long ma;
-        } t;
-        char __padding[192];
-};
-
-static inline void  ?{}(__timestamp_t & this) { this.t.tv = 0; this.t.ma = 0; }
-static inline void ^?{}(__timestamp_t &) {}
+union __attribute__((aligned(64))) __timestamp_t;
+
+void  ?{}(__timestamp_t & this);
+void ^?{}(__timestamp_t &);
 
 

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;

libcfa/src/concurrency/ready_queue.cfa

@@ -139 +139 @@
                 /* paranoid */ verify( readyQ.tscs[target].t.tv != ULLONG_MAX );
                 if(target < lanes_count) {
-                        const unsigned long long cutoff = calc_cutoff(ctsc, proc->rdq.id, lanes_count, cltr->sched.readyQ.data, cltr->sched.readyQ.tscs, __shard_factor.readyq, true);
-                        const unsigned long long age = moving_average(ctsc, readyQ.tscs[target].t.tv, readyQ.tscs[target].t.ma, false);
+                        const __readyQ_avg_t cutoff = calc_cutoff(ctsc, proc->rdq.id, lanes_count, cltr->sched.readyQ.data, cltr->sched.readyQ.tscs, __shard_factor.readyq, true);
+                        const __readyQ_avg_t age = moving_average(ctsc, readyQ.tscs[target].t.tv, readyQ.tscs[target].t.ma, false);
                         __cfadbg_print_safe(ready_queue, "Kernel : Help attempt on %u from %u, age %'llu vs cutoff %'llu, %s\n", target, this, age, cutoff, age > cutoff ? "yes" : "no");
                         if(age > cutoff) {

libcfa/src/math.hfa

@@ -22 +22 @@
 
 #include "common.hfa"
+#include "bits/debug.hfa"
 
 //---------------------- General ----------------------
@@ -307 +308 @@
         // forall( T | { T ?+?( T, T ); T ?-?( T, T ); T ?%?( T, T ); } )
         // T ceiling_div( T n, T align ) { verify( is_pow2( align ) );return (n + (align - 1)) / align; }
-        
+
         // gcc notices the div/mod pair and saves both so only one div.
         signed char ceiling( signed char n, signed char align ) { return floor( n + (n % align != 0 ? align - 1 : 0), align ); }
@@ -429 +430 @@
 } // distribution
 
+static inline unsigned long long log2_u32_32(unsigned long long val) {
+        enum {
+                TABLE_BITS = 6,
+                TABLE_SIZE = (1 << TABLE_BITS) + 2,
+        };
+        // for(i; TABLE_SIZE) {
+        //      table[i] = (unsigned long long)(log2(1.0 + i / pow(2, TABLE_BITS)) * pow(2, 32)));
+        // }
+        static const unsigned long long table[] = {
+                0x0000000000, 0x0005b9e5a1, 0x000b5d69ba, 0x0010eb389f,
+                0x001663f6fa, 0x001bc84240, 0x002118b119, 0x002655d3c4,
+                0x002b803473, 0x00309857a0, 0x00359ebc5b, 0x003a93dc98,
+                0x003f782d72, 0x00444c1f6b, 0x0049101eac, 0x004dc4933a,
+                0x005269e12f, 0x00570068e7, 0x005b888736, 0x006002958c,
+                0x00646eea24, 0x0068cdd829, 0x006d1fafdc, 0x007164beb4,
+                0x00759d4f80, 0x0079c9aa87, 0x007dea15a3, 0x0081fed45c,
+                0x0086082806, 0x008a064fd5, 0x008df988f4, 0x0091e20ea1,
+                0x0095c01a39, 0x009993e355, 0x009d5d9fd5, 0x00a11d83f4,
+                0x00a4d3c25e, 0x00a8808c38, 0x00ac241134, 0x00afbe7fa0,
+                0x00b3500472, 0x00b6d8cb53, 0x00ba58feb2, 0x00bdd0c7c9,
+                0x00c1404ead, 0x00c4a7ba58, 0x00c80730b0, 0x00cb5ed695,
+                0x00ceaecfea, 0x00d1f73f9c, 0x00d53847ac, 0x00d8720935,
+                0x00dba4a47a, 0x00ded038e6, 0x00e1f4e517, 0x00e512c6e5,
+                0x00e829fb69, 0x00eb3a9f01, 0x00ee44cd59, 0x00f148a170,
+                0x00f446359b, 0x00f73da38d, 0x00fa2f045e, 0x00fd1a708b,
+                0x0100000000, 0x0102dfca16,
+        };
+        _Static_assert((sizeof(table) / sizeof(table[0])) == TABLE_SIZE, "TABLE_SIZE should be accurate");
+        // starting from val = (2 ** i)*(1 + f) where 0 <= f < 1
+        // log identities mean log2(val) = log2((2 ** i)*(1 + f)) = log2(2**i) + log2(1+f)
+        //
+        // getting i is easy to do using builtin_clz (count leading zero)
+        //
+        // we want to calculate log2(1+f) independently to have a many bits of precision as possible.
+        //     val = (2 ** i)*(1 + f) = 2 ** i   +   f * 2 ** i
+        // isolating f we get
+        //     val - 2 ** i = f * 2 ** i
+        //     (val - 2 ** i) / 2 ** i = f
+        //
+        // we want to interpolate from the table to get the values
+        // and compromise by doing quadratic interpolation (rather than higher degree interpolation)
+        //
+        // for the interpolation we want to shift everything the fist sample point
+        // so our parabola becomes x = 0
+        // this further simplifies the equations
+        //
+        // the consequence is that we need f in 2 forms:
+        //  - finding the index of x0
+        //  - finding the distance between f and x0
+        //
+        // since sample points are equidistant we can significantly simplify the equations
+
+        // get i
+        const unsigned long long bits = sizeof(val) * __CHAR_BIT__;
+        const unsigned long long lz = __builtin_clzl(val);
+        const unsigned long long i = bits - 1 - lz;
+
+        // get the fractinal part as a u32.32
+        const unsigned long long frac = (val << (lz + 1)) >> 32;
+
+        // get high order bits for the index into the table
+        const unsigned long long idx0 = frac >> (32 - TABLE_BITS);
+
+        // get the x offset, i.e., the difference between the first sample point and the actual fractional part
+        const long long udx = frac - (idx0 << (32 - TABLE_BITS));
+        /* paranoid */ verify((idx0 + 2) < TABLE_SIZE);
+
+        const long long y0 = table[idx0 + 0];
+        const long long y1 = table[idx0 + 1];
+        const long long y2 = table[idx0 + 2];
+
+        // from there we can quadraticly interpolate to get the data, using the lagrange polynomial
+        // normally it would look like:
+        //     double r0 = y0 * ((x - x1) / (x0 - x1)) * ((x - x2) / (x0 - x2));
+        //     double r1 = y1 * ((x - x0) / (x1 - x0)) * ((x - x2) / (x1 - x2));
+        //     double r2 = y2 * ((x - x0) / (x2 - x0)) * ((x - x1) / (x2 - x1));
+        // but since the spacing between sample points is fixed, we can simplify it and extract common expressions
+        const long long f1 = (y1 - y0);
+        const long long f2 = (y2 - y0);
+        const long long a = f2 - (f1 * 2l);
+        const long long b = (f1 * 2l) - a;
+
+        // Now we can compute it in the form (ax + b)x + c (which avoid repeating steps)
+        long long sum = ((a*udx) >> (32 - TABLE_BITS))  + b;
+        sum = (sum*udx) >> (32 - TABLE_BITS + 1);
+        sum = y0 + sum;
+
+        return (i << 32) + (sum);
+}
+
 // Local Variables: //
 // mode: c //