Changeset 634a5c2


Ignore:
Timestamp:
Apr 14, 2021, 12:58:36 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
9344f0e, a33c113
Parents:
ea1c97b
Message:

New changes to the prototype with Andrew's comments

Location:
doc/theses/thierry_delisle_PhD/code/readyQ_proto
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/thierry_delisle_PhD/code/readyQ_proto/utils.hpp

    rea1c97b r634a5c2  
    1111#include <sys/sysinfo.h>
    1212
    13 #include <x86intrin.h>
     13// #include <x86intrin.h>
    1414
    1515// class Random {

  • doc/theses/thierry_delisle_PhD/code/readyQ_proto/work_stealing.hpp

    rea1c97b r634a5c2  
    1515#include "snzi.hpp"
    1616
    17 #include <x86intrin.h>
     17// #include <x86intrin.h>
    1818
    1919using namespace std;
    … …  
    2828template<typename node_t>
    2929struct __attribute__((aligned(128))) localQ_t {
    30         mpsc_queue<node_t> queue = {};
    31         spinlock_t lock = {};
    32         bool needs_help = true;
     30        // volatile unsigned long long val = 0;
     31        // mpsc_queue<node_t> queue = {};
     32        // spinlock_t lock = {};
     33        intrusive_queue_t<node_t> list;
     34
     35        inline auto ts() { return list.ts(); }
     36        inline auto lock() { return list.lock.lock(); }
     37        inline auto try_lock() { return list.lock.try_lock(); }
     38        inline auto unlock() { return list.lock.unlock(); }
     39
     40        inline auto push( node_t * node ) { return list.push( node ); }
     41        inline auto pop() { return list.pop(); }
    3342};
    3443
    … …  
    4453        work_stealing(unsigned _numThreads, unsigned)
    4554                : numThreads(_numThreads * nqueues)
    46                 , lists(new intrusive_queue_t<node_t>[numThreads])
     55                , lists(new localQ_t<node_t>[numThreads])
     56                // , lists(new intrusive_queue_t<node_t>[numThreads])
    4757                , times(new timestamp_t[numThreads])
    4858                // , snzi( std::log2( numThreads / 2 ), 2 )
    … …  
    5868
    5969        __attribute__((noinline, hot)) void push(node_t * node) {
    60                 // node->_links.ts = rdtscl();
    61                 node->_links.ts = 1;
     70                node->_links.ts = rdtscl();
     71                // node->_links.ts = 1;
    6272
    6373                auto & list = *({
    … …  
    7282                                        i = tls.my_queue + (r % nqueues);
    7383                                }
    74                         } while(!lists[i].lock.try_lock());
     84                        } while(!lists[i].try_lock());
    7585                        &lists[i];
    7686                });
    7787
    7888                list.push( node );
    79                 list.lock.unlock();
     89                list.unlock();
    8090                // tls.rng2.set_raw_state( tls.rng1.get_raw_state());
    8191                // count++;
    … …  
    8494
    8595        __attribute__((noinline, hot)) node_t * pop() {
    86                 if( tls.myfriend == outside ) {
    87                         auto r  = tls.rng1.next();
    88                         tls.myfriend = r % numThreads;
    89                         times[tls.myfriend].val = 0;
    90                 }
    91                 else if(times[tls.myfriend].val == 0) {
    92                         node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);
    93                         tls.stats.help++;
    94                         tls.myfriend = outside;
    95                         if(n) return n;
    96                 }
    97 
    9896                if(tls.my_queue != outside) {
     97                        if( tls.myfriend == outside ) {
     98                                auto r  = tls.rng1.next();
     99                                tls.myfriend = r % numThreads;
     100                                tls.mytime = lists[(tls.it % nqueues) + tls.my_queue].ts();
     101                                // times[tls.myfriend].val = 0;
     102                                // lists[tls.myfriend].val = 0;
     103                        }
     104                        // else if(times[tls.myfriend].val == 0) {
     105                        // else if(lists[tls.myfriend].val == 0) {
     106                        else if(times[tls.myfriend].val < tls.mytime) {
     107                        // else if(times[tls.myfriend].val < lists[(tls.it % nqueues) + tls.my_queue].ts()) {
     108                                node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);
     109                                tls.stats.help++;
     110                                tls.myfriend = outside;
     111                                if(n) return n;
     112                        }
     113                        // if( tls.myfriend == outside ) {
     114                        //      auto r  = tls.rng1.next();
     115                        //      tls.myfriend = r % numThreads;
     116                        //      tls.mytime = lists[((tls.it + 1) % nqueues) + tls.my_queue].ts();
     117                        // }
     118                        // else {
     119                        //      if(times[tls.myfriend].val + 1000 < tls.mytime) {
     120                        //              node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);
     121                        //              tls.stats.help++;
     122                        //              if(n) return n;
     123                        //      }
     124                        //      tls.myfriend = outside;
     125                        // }
     126
    99127                        node_t * n = local();
    100128                        if(n) return n;
    … …  
    112140private:
    113141        inline node_t * local() {
    114                 // unsigned i = (tls.rng2.prev() % 4) + tls.my_queue;
    115142                unsigned i = (--tls.it % nqueues) + tls.my_queue;
    116143                return try_pop(i, tls.stats.pop.local);
    … …  
    153180
    154181                // If we can't get the lock, move on
    155                 if( !list.lock.try_lock() ) { stat.elock++; return nullptr; }
    156 
     182                if( !list.try_lock() ) { stat.elock++; return nullptr; }
    157183
    158184                // If list is empty, unlock and retry
    159185                if( list.ts() == 0 ) {
    160                         list.lock.unlock();
     186                        list.unlock();
    161187                        stat.eempty++;
    162188                        return nullptr;
    … …  
    164190
    165191                auto node = list.pop();
    166                 list.lock.unlock();
     192                list.unlock();
    167193                stat.success++;
    168                 times[i].val = 1; //node.first->_links.ts;
    169                 // count--;
    170                 // _mm_stream_si64((long long int*)&times[i].val, node.first->_links.ts);
     194                // times[i].val = 1;
     195                times[i].val = node.first->_links.ts;
     196                // lists[i].val = node.first->_links.ts;
    171197                return node.first;
    172198        }
    … …  
    191217                unsigned   my_queue = calc_preferred();
    192218                unsigned   myfriend = outside;
     219                unsigned long long int mytime = 0;
    193220                #if defined(READ)
    194221                        unsigned it = 0;
    … …  
    211238private:
    212239        const unsigned numThreads;
    213         std::unique_ptr<intrusive_queue_t<node_t> []> lists;
     240        std::unique_ptr<localQ_t<node_t> []> lists;
     241        // std::unique_ptr<intrusive_queue_t<node_t> []> lists;
    214242        std::unique_ptr<timestamp_t []> times;
    215243        __attribute__((aligned(128))) std::atomic_size_t count;
Note: See TracChangeset for help on using the changeset viewer.