Ignore:
Timestamp:
Sep 23, 2021, 1:02:46 PM (2 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
master
Children:
fcd65ca
Parents:
bc4a433
Message:

Changed cpu schedulig to use moving average.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.