Index: libcfa/src/concurrency/io.cfa =================================================================== --- libcfa/src/concurrency/io.cfa (revision 33e4968e2b4f6edd578608d8c459a3f3d2cf9479) +++ libcfa/src/concurrency/io.cfa (revision 31c967b40fdb700cadb78ef6b9488cfa9dea77f2) @@ -243,6 +243,6 @@ /* 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; Index: libcfa/src/concurrency/kernel.hfa =================================================================== --- libcfa/src/concurrency/kernel.hfa (revision 33e4968e2b4f6edd578608d8c459a3f3d2cf9479) +++ libcfa/src/concurrency/kernel.hfa (revision 31c967b40fdb700cadb78ef6b9488cfa9dea77f2) @@ -181,14 +181,8 @@ // 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 &); Index: libcfa/src/concurrency/kernel/cluster.cfa =================================================================== --- libcfa/src/concurrency/kernel/cluster.cfa (revision 33e4968e2b4f6edd578608d8c459a3f3d2cf9479) +++ libcfa/src/concurrency/kernel/cluster.cfa (revision 31c967b40fdb700cadb78ef6b9488cfa9dea77f2) @@ -221,4 +221,7 @@ 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 Index: libcfa/src/concurrency/kernel/cluster.hfa =================================================================== --- libcfa/src/concurrency/kernel/cluster.hfa (revision 33e4968e2b4f6edd578608d8c459a3f3d2cf9479) +++ libcfa/src/concurrency/kernel/cluster.hfa (revision 31c967b40fdb700cadb78ef6b9488cfa9dea77f2) @@ -18,4 +18,5 @@ #include "device/cpu.hfa" #include "kernel/private.hfa" +#include "math.hfa" #include @@ -23,17 +24,75 @@ #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) { 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; + double c = 3e-100; + /* 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 = 4; + 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,5 +101,5 @@ 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,5 +109,5 @@ // 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,14 +119,14 @@ ) { 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 ); } Index: libcfa/src/concurrency/kernel/private.hfa =================================================================== --- libcfa/src/concurrency/kernel/private.hfa (revision 33e4968e2b4f6edd578608d8c459a3f3d2cf9479) +++ libcfa/src/concurrency/kernel/private.hfa (revision 31c967b40fdb700cadb78ef6b9488cfa9dea77f2) @@ -49,6 +49,28 @@ #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; Index: libcfa/src/concurrency/ready_queue.cfa =================================================================== --- libcfa/src/concurrency/ready_queue.cfa (revision 33e4968e2b4f6edd578608d8c459a3f3d2cf9479) +++ libcfa/src/concurrency/ready_queue.cfa (revision 31c967b40fdb700cadb78ef6b9488cfa9dea77f2) @@ -139,6 +139,6 @@ /* 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) {