Ignore:
Timestamp:
Oct 3, 2022, 4:37:59 PM (3 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, master
Children:
d1cd4c4
Parents:
890f67a
Message:

Changed ready-queue so I can easily change the averaging algorithm.
Changed averaging to use logscale.

Location:
libcfa/src/concurrency
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/io.cfa

    r890f67a r31c967b  
    243243                                /* paranoid */ verify( io.tscs[target].t.tv != ULLONG_MAX );
    244244                                HELP: if(target < ctxs_count) {
    245                                         const unsigned long long cutoff = calc_cutoff(ctsc, ctx->cq.id, ctxs_count, io.data, io.tscs, __shard_factor.io, false);
    246                                         const unsigned long long age = moving_average(ctsc, io.tscs[target].t.tv, io.tscs[target].t.ma, false);
     245                                        const __readyQ_avg_t cutoff = calc_cutoff(ctsc, ctx->cq.id, ctxs_count, io.data, io.tscs, __shard_factor.io, false);
     246                                        const __readyQ_avg_t age = moving_average(ctsc, io.tscs[target].t.tv, io.tscs[target].t.ma, false);
    247247                                        __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");
    248248                                        if(age <= cutoff) break HELP;

  • libcfa/src/concurrency/kernel.hfa

    r890f67a r31c967b  
    181181
    182182// Aligned timestamps which are used by the ready queue and io subsystem
    183 union __attribute__((aligned(64))) __timestamp_t {
    184         struct {
    185                 volatile unsigned long long tv;
    186                 volatile unsigned long long ma;
    187         } t;
    188         char __padding[192];
    189 };
    190 
    191 static inline void  ?{}(__timestamp_t & this) { this.t.tv = 0; this.t.ma = 0; }
    192 static inline void ^?{}(__timestamp_t &) {}
     183union __attribute__((aligned(64))) __timestamp_t;
     184
     185void  ?{}(__timestamp_t & this);
     186void ^?{}(__timestamp_t &);
    193187
    194188

  • libcfa/src/concurrency/kernel/cluster.cfa

    r890f67a r31c967b  
    221221static const unsigned __readyq_single_shard = 2;
    222222
     223void  ?{}(__timestamp_t & this) { this.t.tv = 0; this.t.ma = 0; }
     224void ^?{}(__timestamp_t &) {}
     225
    223226//-----------------------------------------------------------------------
    224227// Check that all the intrusive queues in the data structure are still consistent

  • libcfa/src/concurrency/kernel/cluster.hfa

    r890f67a r31c967b  
    1818#include "device/cpu.hfa"
    1919#include "kernel/private.hfa"
     20#include "math.hfa"
    2021
    2122#include <limits.h>
    … …  
    2324#include "clock.hfa"
    2425
     26#if   defined(READYQ_USE_LINEAR_AVG)
     27
     28// no conversion needed in this case
     29static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return intsc; }
     30
     31// warn normally all ints
     32#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 )
     33#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 )
     34
     35// 8X linear factor is just 8 * x
     36#define AVG_FACTOR( x ) (8 * (x))
     37
     38#elif defined(READYQ_USE_LOGDBL_AVG)
     39
     40// convert to log2 scale but using double
     41static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return log2(intsc); }
     42
     43#define warn_large_before warnf( !strict || old_avg < 35.0, "Suspiciously large previous average: %'lf, %'ldms \n", old_avg, program()`ms )
     44#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 ); \
     45verify(ret >= 0)
     46
     47// 8X factor in logscale is log2(8X) = log2(8) + log2(X) = 3 + log2(X)
     48#define AVG_FACTOR( x ) (3.0 + (x))
     49
     50// we need to overload the __atomic_load_n because they don't support double
     51static inline double __atomic_load_n(volatile double * ptr, int mem) {
     52        volatile uint64_t * uptr = (volatile uint64_t *)ptr;
     53        _Static_assert(sizeof(*uptr) == sizeof(*ptr));
     54        uint64_t ret = 0;
     55        ret = __atomic_load_n(uptr, mem);
     56        uint64_t *rp = &ret;
     57        double ret = *(volatile double *)rp;
     58        double c = 3e-100;
     59        /* paranoid */ verify( ret == 0 || ret > 3e-100 );
     60        return ret;
     61}
     62
     63// we need to overload the __atomic_store_n because they don't support double
     64static inline void __atomic_store_n(volatile double * ptr, double val, int mem) {
     65        /* paranoid */ verify( val == 0 || val > 3e-100 );
     66        volatile uint64_t * uptr = (volatile uint64_t *)ptr;
     67        _Static_assert(sizeof(*uptr) == sizeof(*ptr));
     68        uint64_t * valp = (uint64_t *)&val;
     69        __atomic_store_n(uptr, *valp, mem);
     70}
     71
     72#elif defined(READYQ_USE_LOGDBL_AVG)
     73
     74//convert to log2 scale but with fix point u32.32 values
     75static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return ulog2_32_32(tsc); }
     76
     77// 8X factor, +3 in logscale (see above) is + 0x3.00000000
     78#define AVG_FACTOR( x ) (0x3_00000000ull + (x))
     79
     80#else
     81#error must pick a scheme for averaging
     82#endif
     83
    2584//-----------------------------------------------------------------------
    2685// Calc moving average based on existing average, before and current time.
    27 static inline unsigned long long moving_average(unsigned long long currtsc, unsigned long long instsc, unsigned long long old_avg, bool strict) {
     86static inline __readyQ_avg_t moving_average(unsigned long long currtsc, unsigned long long intsc, __readyQ_avg_t old_avg, bool strict) {
    2887        (void)strict; // disable the warning around the fact this is unused in release.
    29         /* paranoid */ warnf( !strict || old_avg < 33_000_000_000, "Suspiciously large previous average: %'llu (%llx), %'ldms \n", old_avg, old_avg, program()`ms );
     88        /* paranoid */ warn_large_before;
    3089
    31         const unsigned long long new_val = currtsc > instsc ? currtsc - instsc : 0;
    32         const unsigned long long total_weight = 16;
    33         const unsigned long long new_weight   = 4;
    34         const unsigned long long old_weight = total_weight - new_weight;
    35         const unsigned long long ret = ((new_weight * new_val) + (old_weight * old_avg)) / total_weight;
     90        const unsigned long long new_val = currtsc > intsc ? currtsc - intsc : 0;
     91        const __readyQ_avg_t total_weight = 16;
     92        const __readyQ_avg_t new_weight   = 4;
     93        const __readyQ_avg_t old_weight = total_weight - new_weight;
     94        const __readyQ_avg_t ret = ((new_weight * __to_readyQ_avg(new_val)) + (old_weight * old_avg)) / total_weight;
    3695
    37         /* 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 );
     96        /* paranoid */ warn_large_after;
    3897        return ret;
    3998}
    … …  
    42101        if (ts_next == ULLONG_MAX) return;
    43102        unsigned long long now = rdtscl();
    44         unsigned long long pma = __atomic_load_n(&tscs[ idx ].t.ma, __ATOMIC_RELAXED);
     103        __readyQ_avg_t pma = __atomic_load_n(&tscs[ idx ].t.ma, __ATOMIC_RELAXED);
    45104        __atomic_store_n(&tscs[ idx ].t.tv, ts_next, __ATOMIC_RELAXED);
    46105        __atomic_store_n(&tscs[ idx ].t.ma, moving_average(now, ts_prev, pma, strict), __ATOMIC_RELAXED);
    … …  
    50109// Calc age a timestamp should be before needing help.
    51110forall(Data_t * | { unsigned long long ts(Data_t & this); })
    52 static inline unsigned long long calc_cutoff(
     111static inline __readyQ_avg_t calc_cutoff(
    53112        const unsigned long long ctsc,
    54113        unsigned procid,
    … …  
    60119) {
    61120        unsigned start = procid;
    62         unsigned long long max = 0;
     121        __readyQ_avg_t max = 0;
    63122        for(i; shard_factor) {
    64123                unsigned long long ptsc = ts(data[start + i]);
    65124                if(ptsc != ULLONG_MAX) {
    66125                        /* paranoid */ verify( start + i < count );
    67                         unsigned long long tsc = moving_average(ctsc, ptsc, tscs[start + i].t.ma, strict);
    68                         if(tsc > max) max = tsc;
     126                        __readyQ_avg_t avg = moving_average(ctsc, ptsc, tscs[start + i].t.ma, strict);
     127                        if(avg > max) max = avg;
    69128                }
    70129        }
    71         return 8 * max;
     130        return AVG_FACTOR( max );
    72131}
    73132

  • libcfa/src/concurrency/kernel/private.hfa

    r890f67a r31c967b  
    4949#endif
    5050
     51// #define READYQ_USE_LINEAR_AVG
     52#define READYQ_USE_LOGDBL_AVG
     53// #define READYQ_USE_LOGINT_AVG
     54
     55#if   defined(READYQ_USE_LINEAR_AVG)
     56typedef unsigned long long __readyQ_avg_t;
     57#elif defined(READYQ_USE_LOGDBL_AVG)
     58typedef double __readyQ_avg_t;
     59#elif defined(READYQ_USE_LOGDBL_AVG)
     60typedef unsigned long long __readyQ_avg_t;
     61#else
     62#error must pick a scheme for averaging
     63#endif
     64
    5165//-----------------------------------------------------------------------------
    5266// Scheduler
     67union __attribute__((aligned(64))) __timestamp_t {
     68        struct {
     69                volatile unsigned long long tv;
     70                volatile __readyQ_avg_t ma;
     71        } t;
     72        char __padding[192];
     73};
     74
    5375extern "C" {
    5476        void disable_interrupts() OPTIONAL_THREAD;

  • libcfa/src/concurrency/ready_queue.cfa

    r890f67a r31c967b  
    139139                /* paranoid */ verify( readyQ.tscs[target].t.tv != ULLONG_MAX );
    140140                if(target < lanes_count) {
    141                         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);
    142                         const unsigned long long age = moving_average(ctsc, readyQ.tscs[target].t.tv, readyQ.tscs[target].t.ma, false);
     141                        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);
     142                        const __readyQ_avg_t age = moving_average(ctsc, readyQ.tscs[target].t.tv, readyQ.tscs[target].t.ma, false);
    143143                        __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");
    144144                        if(age > cutoff) {
Note: See TracChangeset for help on using the changeset viewer.