Ignore:
Timestamp:
Sep 23, 2021, 1:02:46 PM (3 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, enum, forall-pointer-decay, master, pthread-emulation, qualifiedEnum
Children:
fcd65ca
Parents:
bc4a433
Message:

Changed cpu schedulig to use moving average.

Location:
libcfa/src/concurrency
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/concurrency/kernel.hfa

    rbc4a433 r089d30c  
    151151struct __attribute__((aligned(128))) __timestamp_t {
    152152        volatile unsigned long long tv;
    153 };
    154 
    155 static inline void  ?{}(__timestamp_t & this) { this.tv = 0; }
     153        volatile unsigned long long ma;
     154};
     155
     156// Aligned timestamps which are used by the relaxed ready queue
     157struct __attribute__((aligned(128))) __help_cnts_t {
     158        volatile unsigned long long src;
     159        volatile unsigned long long dst;
     160        volatile unsigned long long tri;
     161};
     162
     163static inline void  ?{}(__timestamp_t & this) { this.tv = 0; this.ma = 0; }
    156164static inline void ^?{}(__timestamp_t & this) {}
    157165
     
    169177                // Array of times
    170178                __timestamp_t * volatile tscs;
     179
     180                // Array of stats
     181                __help_cnts_t * volatile help;
    171182
    172183                // Number of lanes (empty or not)
  • libcfa/src/concurrency/ready_queue.cfa

    rbc4a433 r089d30c  
    246246// Cforall Ready Queue used for scheduling
    247247//=======================================================================
     248unsigned long long moving_average(unsigned long long nval, unsigned long long oval) {
     249        const unsigned long long tw = 16;
     250        const unsigned long long nw = 4;
     251        const unsigned long long ow = tw - nw;
     252        return ((nw * nval) + (ow * oval)) / tw;
     253}
     254
    248255void ?{}(__ready_queue_t & this) with (this) {
    249256        #if defined(USE_CPU_WORK_STEALING)
     
    251258                lanes.data = alloc( lanes.count );
    252259                lanes.tscs = alloc( lanes.count );
     260                lanes.help = alloc( cpu_info.hthrd_count );
    253261
    254262                for( idx; (size_t)lanes.count ) {
    255263                        (lanes.data[idx]){};
    256264                        lanes.tscs[idx].tv = rdtscl();
     265                        lanes.tscs[idx].ma = rdtscl();
     266                }
     267                for( idx; (size_t)cpu_info.hthrd_count ) {
     268                        lanes.help[idx].src = 0;
     269                        lanes.help[idx].dst = 0;
     270                        lanes.help[idx].tri = 0;
    257271                }
    258272        #else
    259273                lanes.data  = 0p;
    260274                lanes.tscs  = 0p;
     275                lanes.help  = 0p;
    261276                lanes.count = 0;
    262277        #endif
     
    270285        free(lanes.data);
    271286        free(lanes.tscs);
     287        free(lanes.help);
    272288}
    273289
     
    332348                processor * const proc = kernelTLS().this_processor;
    333349                const int start = map.self * READYQ_SHARD_FACTOR;
     350                const unsigned long long ctsc = rdtscl();
    334351
    335352                // Did we already have a help target
    336353                if(proc->rdq.target == -1u) {
    337                         // if We don't have a
    338                         unsigned long long min = ts(lanes.data[start]);
     354                        unsigned long long max = 0;
    339355                        for(i; READYQ_SHARD_FACTOR) {
    340                                 unsigned long long tsc = ts(lanes.data[start + i]);
    341                                 if(tsc < min) min = tsc;
    342                         }
    343                         proc->rdq.cutoff = min;
    344 
     356                                unsigned long long tsc = moving_average(ctsc - ts(lanes.data[start + i]), lanes.tscs[start + i].ma);
     357                                if(tsc > max) max = tsc;
     358                        }
     359                         proc->rdq.cutoff = (max + 2 * max) / 2;
    345360                        /* paranoid */ verify(lanes.count < 65536); // The following code assumes max 65536 cores.
    346361                        /* paranoid */ verify(map.count < 65536); // The following code assumes max 65536 cores.
    347362
    348                         if(0 == (__tls_rand() % 10_000)) {
     363                        if(0 == (__tls_rand() % 100)) {
    349364                                proc->rdq.target = __tls_rand() % lanes.count;
    350365                        } else {
     
    358373                }
    359374                else {
    360                         const unsigned long long bias = 0; //2_500_000_000;
    361                         const unsigned long long cutoff = proc->rdq.cutoff > bias ? proc->rdq.cutoff - bias : proc->rdq.cutoff;
     375                        unsigned long long max = 0;
     376                        for(i; READYQ_SHARD_FACTOR) {
     377                                unsigned long long tsc = moving_average(ctsc - ts(lanes.data[start + i]), lanes.tscs[start + i].ma);
     378                                if(tsc > max) max = tsc;
     379                        }
     380                        const unsigned long long cutoff = (max + 2 * max) / 2;
    362381                        {
    363382                                unsigned target = proc->rdq.target;
    364383                                proc->rdq.target = -1u;
    365                                 if(lanes.tscs[target].tv < cutoff && ts(lanes.data[target]) < cutoff) {
     384                                lanes.help[target].tri++;
     385                                if(moving_average(ctsc - lanes.tscs[target].tv, lanes.tscs[target].ma) > cutoff) {
    366386                                        thread$ * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
    367387                                        proc->rdq.last = target;
    368388                                        if(t) return t;
     389                                        else proc->rdq.target = -1u;
    369390                                }
     391                                else proc->rdq.target = -1u;
    370392                        }
    371393
     
    645667        // Actually pop the list
    646668        struct thread$ * thrd;
     669        unsigned long long tsc_before = ts(lane);
    647670        unsigned long long tsv;
    648671        [thrd, tsv] = pop(lane);
     
    658681        __STATS( stats.success++; )
    659682
    660         #if defined(USE_WORK_STEALING)
     683        #if defined(USE_WORK_STEALING) || defined(USE_CPU_WORK_STEALING)
     684                unsigned long long now = rdtscl();
    661685                lanes.tscs[w].tv = tsv;
     686                lanes.tscs[w].ma = moving_average(now > tsc_before ? now - tsc_before : 0, lanes.tscs[w].ma);
    662687        #endif
    663688
  • libcfa/src/concurrency/thread.cfa

    rbc4a433 r089d30c  
    2525#include "invoke.h"
    2626
     27uint64_t thread_rand();
     28
    2729//-----------------------------------------------------------------------------
    2830// Thread ctors and dtors
     
    4143        link.next = 0p;
    4244        link.ts   = -1llu;
    43         preferred = -1u;
     45        preferred = thread_rand() % cl.ready_queue.lanes.count;
    4446        last_proc = 0p;
    4547        #if defined( __CFA_WITH_VERIFY__ )
Note: See TracChangeset for help on using the changeset viewer.