source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/dynamic_entropy.hpp @ 56c8b86

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 56c8b86 was 56c8b86, checked in by Thierry Delisle <tdelisle@…>, 7 months ago

Added clean version of cforall
(Rather than one buried in a mess of macros)

  • Property mode set to 100644
File size: 5.3 KB
Line 
1#pragma once
2
3#define LIST_VARIANT dyn_ent_list
4
5#include <memory>
6#include <mutex>
7#include <thread>
8
9#include "assert.hpp"
10#include "utils.hpp"
11#include "links.hpp"
12
13std::mutex mtx_;
14
15template<typename node_t>
16class __attribute__((aligned(128))) dyn_ent_list {
17        const unsigned numLists;
18        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists;
19
20public:
21        dyn_ent_list(unsigned numThreads, unsigned)
22                : numLists(numThreads * 4)
23                , lists(new intrusive_queue_t<node_t>[numLists])
24        {
25                std::cout << "Constructing Relaxed List with " << numLists << std::endl;
26        }
27
28        __attribute__((noinline, hot)) void push(node_t * node) {
29                node->_links.ts = rdtscl();
30
31                // Try to pick a lane and lock it
32                unsigned i;
33                do {
34                        // Pick the index of a lane
35                        i = idx_from_r(tls.rng1.next(), tls.my_queue);
36                        // i = ret.first; //local = ret.second;
37                        tls.stats.push.attempt++;
38                } while( !lists[i].lock.try_lock() );
39
40                lists[i].push(node);
41                lists[i].lock.unlock();
42                tls.rng2.set_raw_state( tls.rng1.get_raw_state());
43                tls.stats.push.success++;
44        }
45
46        __attribute__((noinline, hot)) node_t * pop() {
47                for(int n = 0; n < 25; n++) {
48                        // Pick two lists at random
49                        unsigned i, j;
50                        // bool locali, localj;
51                        i = idx_from_r(tls.rng2.prev(), tls.my_queue);
52                        j = idx_from_r(tls.rng2.prev(), tls.my_queue);
53
54                        // i = reti.first; //local = reti.second;
55                        // j = retj.first; //local = retj.second;
56                        tls.stats.pop.attempt++;
57
58                        // try popping from the 2 picked lists
59                        node_t * thrd = try_pop(i, j);
60                        if(thrd) {
61                                tls.stats.pop.success++;
62                                return thrd;
63                        }
64                }
65
66                unsigned offset = tls.rng2.next();
67                for(unsigned i = 0; i < numLists; i++) {
68                        unsigned idx = (offset + i) % numLists;
69                        node_t * thrd = try_pop(idx);
70                        if(thrd) {
71                                return thrd;
72                        }
73                }
74
75                // All lanes where empty return 0p
76                return nullptr;
77        }
78
79private:
80        inline node_t * try_pop(unsigned i, unsigned j) {
81                // Pick the bet list
82                int w = i;
83                if( __builtin_expect(!(lists[j].ts() > 0), true) ) {
84                        w = (lists[i].ts() < lists[j].ts()) ? i : j;
85                }
86
87                return try_pop(w);
88        }
89
90        inline node_t * try_pop(unsigned w) {
91                // If list looks empty retry
92                if( lists[w].ts() == 0 ) { tls.stats.pop.empty++; return nullptr; }
93
94                // If we can't get the lock retry
95                if( !lists[w].lock.try_lock() ) { tls.stats.pop.locked++; return nullptr; }
96
97
98                // If list is empty, unlock and retry
99                if( lists[w].ts() == 0 ) {
100                        tls.stats.pop.both++;
101                        lists[w].lock.unlock();
102                        return nullptr;
103                }
104
105                auto node = lists[w].pop();
106                lists[w].lock.unlock();
107                return node.first;
108        }
109
110        inline unsigned idx_from_r(unsigned r, unsigned preferred) {
111                unsigned i;
112                // bool local;
113                unsigned rlow  = r % 4;
114                unsigned rhigh = r / 4;
115                if((0 != rlow) && preferred != outside) {
116                        // (BIAS - 1) out of BIAS chances
117                        // Use perferred queues
118                        i = preferred + (rhigh % 4);
119                        // local = true;
120                }
121                else {
122                        // 1 out of BIAS chances
123                        // Use all queues
124                        i = rhigh;
125                        // local = false;
126                }
127                return i % numLists;
128        }
129private:
130        static std::atomic_uint32_t ticket;
131        static const unsigned outside = 0xFFFFFFFF;
132
133        static inline unsigned calc_preferred() {
134                unsigned t = ticket++;
135                if(t == 0) return outside;
136                unsigned i = 4 * (t - 1);
137                return i;
138        }
139
140        static __attribute__((aligned(128))) thread_local struct TLS {
141                Random     rng1 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
142                Random     rng2 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
143                unsigned   my_queue = calc_preferred();
144                struct {
145                        struct {
146                                size_t attempt = 0;
147                                size_t success = 0;
148                        } push;
149                        struct {
150                                size_t attempt = 0;
151                                size_t success = 0;
152                                size_t empty   = 0;
153                                size_t locked  = 0;
154                                size_t both    = 0;
155                        } pop;
156                } stats;
157        } tls;
158public:
159        static const char * name() {
160                return "Dynamic Entropy List";
161        }
162
163public:
164        static struct GlobalStats {
165                struct {
166                        std::atomic_size_t attempt = 0;
167                        std::atomic_size_t success = 0;
168                } push;
169                struct {
170                        std::atomic_size_t attempt = 0;
171                        std::atomic_size_t success = 0;
172                        std::atomic_size_t empty   = 0;
173                        std::atomic_size_t locked  = 0;
174                        std::atomic_size_t both    = 0;
175                } pop;
176        } global_stats;
177        static void stats_tls_tally() {
178                global_stats.push.attempt += tls.stats.push.attempt;
179                global_stats.push.success += tls.stats.push.success;
180                global_stats.pop .attempt += tls.stats.pop.attempt;
181                global_stats.pop .success += tls.stats.pop.success;
182                global_stats.pop .empty   += tls.stats.pop.empty;
183                global_stats.pop .locked  += tls.stats.pop.locked;
184                global_stats.pop .both    += tls.stats.pop.both;
185        }
186
187        static void stats_print(std::ostream & os) {
188                        const auto & global = global_stats;
189
190                double push_sur = (100.0 * double(global.push.success) / global.push.attempt);
191                double pop_sur  = (100.0 * double(global.pop .success) / global.pop .attempt);
192
193                double push_len = double(global.push.attempt     ) / global.push.success;
194                double pop_len  = double(global.pop .attempt     ) / global.pop .success;
195
196                os << "Push   Pick   : " << push_sur << " %, len " << push_len << " (" << global.push.attempt      << " / " << global.push.success << ")\n";
197                os << "Pop    Pick   : " << pop_sur  << " %, len " << pop_len  << " (" << global.pop .attempt      << " / " << global.pop .success << ")\n";
198                os << "Pop    Fails  : " << global_stats.pop .empty << "e, " << global_stats.pop .locked << "l, " << global_stats.pop .both << "\n";
199        }
200};
Note: See TracBrowser for help on using the repository browser.