Ignore:
Timestamp:
Apr 15, 2021, 1:08:16 PM (6 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
200a229, 76c94bf
Parents:
8590328
Message:

Added comparison of the mpsc queue to the protoptype.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/code/readyQ_proto/work_stealing.hpp

    r8590328 r780a614  
    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        #ifdef NO_MPSC
     31                intrusive_queue_t<node_t> list;
     32
     33                inline auto ts() { return list.ts(); }
     34                inline auto lock() { return list.lock.lock(); }
     35                inline auto try_lock() { return list.lock.try_lock(); }
     36                inline auto unlock() { return list.lock.unlock(); }
     37
     38                inline auto push( node_t * node ) { return list.push( node ); }
     39                inline auto pop() { return list.pop(); }
     40        #else
     41                mpsc_queue<node_t> queue = {};
     42                spinlock_t _lock = {};
     43
     44                inline auto ts() { auto h = queue.head(); return h ? h->_links.ts : 0ull; }
     45                inline auto lock() { return _lock.lock(); }
     46                inline auto try_lock() { return _lock.try_lock(); }
     47                inline auto unlock() { return _lock.unlock(); }
     48
     49                inline auto push( node_t * node ) { return queue.push( node ); }
     50                inline auto pop() { return queue.pop(); }
     51        #endif
     52
     53
    4254};
    4355
     
    7385                auto & list = *({
    7486                        unsigned i;
    75                         do {
     87                        #ifdef NO_MPSC
     88                                do {
     89                        #endif
    7690                                tls.stats.push.attempt++;
    7791                                // unsigned r = tls.rng1.next();
     
    8296                                        i = tls.my_queue + (r % nqueues);
    8397                                }
    84                         } while(!lists[i].try_lock());
     98                        #ifdef NO_MPSC
     99                                } while(!lists[i].try_lock());
     100                        #endif
    85101                        &lists[i];
    86102                });
    87103
    88104                list.push( node );
    89                 list.unlock();
     105                #ifdef NO_MPSC
     106                        list.unlock();
     107                #endif
    90108                // tls.rng2.set_raw_state( tls.rng1.get_raw_state());
    91109                // count++;
     
    95113        __attribute__((noinline, hot)) node_t * pop() {
    96114                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                         }
     115                        // if( tls.myfriend == outside ) {
     116                        //      auto r  = tls.rng1.next();
     117                        //      tls.myfriend = r % numThreads;
     118                        //      // assert(lists[(tls.it % nqueues) + tls.my_queue].ts() >= lists[((tls.it + 1) % nqueues) + tls.my_queue].ts());
     119                        //      tls.mytime = std::min(lists[(tls.it % nqueues) + tls.my_queue].ts(), lists[((tls.it + 1) % nqueues) + tls.my_queue].ts());
     120                        //      // times[tls.myfriend].val = 0;
     121                        //      // lists[tls.myfriend].val = 0;
     122                        // }
     123                        // // else if(times[tls.myfriend].val == 0) {
     124                        // // else if(lists[tls.myfriend].val == 0) {
     125                        // else if(times[tls.myfriend].val < tls.mytime) {
     126                        // // else if(times[tls.myfriend].val < lists[(tls.it % nqueues) + tls.my_queue].ts()) {
     127                        //      node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);
     128                        //      tls.stats.help++;
     129                        //      tls.myfriend = outside;
     130                        //      if(n) return n;
     131                        // }
    113132                        // if( tls.myfriend == outside ) {
    114133                        //      auto r  = tls.rng1.next();
     
    141160        inline node_t * local() {
    142161                unsigned i = (--tls.it % nqueues) + tls.my_queue;
     162                node_t * n = try_pop(i, tls.stats.pop.local);
     163                if(n) return n;
     164                i = (--tls.it % nqueues) + tls.my_queue;
    143165                return try_pop(i, tls.stats.pop.local);
    144166        }
     
    192214                list.unlock();
    193215                stat.success++;
    194                 // times[i].val = 1;
    195                 times[i].val = node.first->_links.ts;
    196                 // lists[i].val = node.first->_links.ts;
    197                 return node.first;
     216                #ifdef NO_MPSC
     217                        // times[i].val = 1;
     218                        times[i].val = node.first->_links.ts;
     219                        // lists[i].val = node.first->_links.ts;
     220                        return node.first;
     221                #else
     222                        times[i].val = node->_links.ts;
     223                        return node;
     224                #endif
    198225        }
    199226
Note: See TracChangeset for help on using the changeset viewer.