Changes in / [9344f0e:6645cda]


Ignore:
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

    r9344f0e r6645cda  
    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

    r9344f0e r6645cda  
    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         // 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(); }
     30        mpsc_queue<node_t> queue = {};
     31        spinlock_t lock = {};
     32        bool needs_help = true;
    4233};
    4334
     
    5344        work_stealing(unsigned _numThreads, unsigned)
    5445                : numThreads(_numThreads * nqueues)
    55                 , lists(new localQ_t<node_t>[numThreads])
    56                 // , lists(new intrusive_queue_t<node_t>[numThreads])
     46                , lists(new intrusive_queue_t<node_t>[numThreads])
    5747                , times(new timestamp_t[numThreads])
    5848                // , snzi( std::log2( numThreads / 2 ), 2 )
     
    6858
    6959        __attribute__((noinline, hot)) void push(node_t * node) {
    70                 node->_links.ts = rdtscl();
    71                 // node->_links.ts = 1;
     60                // node->_links.ts = rdtscl();
     61                node->_links.ts = 1;
    7262
    7363                auto & list = *({
     
    8272                                        i = tls.my_queue + (r % nqueues);
    8373                                }
    84                         } while(!lists[i].try_lock());
     74                        } while(!lists[i].lock.try_lock());
    8575                        &lists[i];
    8676                });
    8777
    8878                list.push( node );
    89                 list.unlock();
     79                list.lock.unlock();
    9080                // tls.rng2.set_raw_state( tls.rng1.get_raw_state());
    9181                // count++;
     
    9484
    9585        __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
    9698                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 
    12799                        node_t * n = local();
    128100                        if(n) return n;
     
    140112private:
    141113        inline node_t * local() {
     114                // unsigned i = (tls.rng2.prev() % 4) + tls.my_queue;
    142115                unsigned i = (--tls.it % nqueues) + tls.my_queue;
    143116                return try_pop(i, tls.stats.pop.local);
     
    180153
    181154                // If we can't get the lock, move on
    182                 if( !list.try_lock() ) { stat.elock++; return nullptr; }
     155                if( !list.lock.try_lock() ) { stat.elock++; return nullptr; }
     156
    183157
    184158                // If list is empty, unlock and retry
    185159                if( list.ts() == 0 ) {
    186                         list.unlock();
     160                        list.lock.unlock();
    187161                        stat.eempty++;
    188162                        return nullptr;
     
    190164
    191165                auto node = list.pop();
    192                 list.unlock();
     166                list.lock.unlock();
    193167                stat.success++;
    194                 // times[i].val = 1;
    195                 times[i].val = node.first->_links.ts;
    196                 // lists[i].val = node.first->_links.ts;
     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);
    197171                return node.first;
    198172        }
     
    217191                unsigned   my_queue = calc_preferred();
    218192                unsigned   myfriend = outside;
    219                 unsigned long long int mytime = 0;
    220193                #if defined(READ)
    221194                        unsigned it = 0;
     
    238211private:
    239212        const unsigned numThreads;
    240         std::unique_ptr<localQ_t<node_t> []> lists;
    241         // std::unique_ptr<intrusive_queue_t<node_t> []> lists;
     213        std::unique_ptr<intrusive_queue_t<node_t> []> lists;
    242214        std::unique_ptr<timestamp_t []> times;
    243215        __attribute__((aligned(128))) std::atomic_size_t count;
Note: See TracChangeset for help on using the changeset viewer.