Index: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (revision 42cd451e139b4d6ef2dc72aebb910104dd7f1fbc) +++ doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (revision f4ec4a90525683f9f79fa4d1595d00d4819ca521) @@ -8,4 +8,6 @@ #define SNZM 4 #define BIAS 5 +#define BACK 6 +#define BACKBIAS 7 #ifndef VARIANT @@ -18,6 +20,8 @@ #include +#include #include #include +#include #include @@ -26,4 +30,5 @@ #include "links.hpp" #include "snzi.hpp" +#include "snzi-packed.hpp" #include "snzm.hpp" @@ -68,5 +73,7 @@ "RELAXED: SNZI + DISCOVERED MASK", "RELAXED: SNZI + MASK", - "RELAXED: SNZI + LOCAL BIAS" + "RELAXED: SNZI + LOCAL BIAS", + "RELAXED: SNZI + REVERSE RNG", + "RELAXED: SNZI + LOCAL BIAS + REVERSE RNG" }; return names[VARIANT]; @@ -76,6 +83,12 @@ : numLists(numThreads * numQueues) , lists(new intrusive_queue_t[numLists]) - #if VARIANT == SNZI || VARIANT == BIAS + #if VARIANT == SNZI || VARIANT == BACK , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) + #elif VARIANT == BIAS || VARIANT == BACKBIAS + #ifdef SNZI_PACKED + , snzi( std::ceil( std::log2(numLists) ) ) + #else + , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) + #endif #elif VARIANT == SNZM || VARIANT == DISCOVER , snzm( numLists ) @@ -96,17 +109,5 @@ while(true) { // Pick a random list - #if VARIANT == BIAS - unsigned r = tls.rng.next(); - unsigned i; - if(0 == (r & 0xF)) { - i = r >> 4; - } else { - i = tls.my_queue + ((r >> 4) % 4); - tls.pick.push.local++; - } - i %= numLists; - #else - unsigned i = tls.rng.next() % numLists; - #endif + unsigned i = idx_from_r(tls.rng1.next(), VARIANT == BIAS || VARIANT == BACKBIAS); #ifndef NO_STATS @@ -117,5 +118,5 @@ if( !lists[i].lock.try_lock() ) continue; - #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS + #if VARIANT == VANILLA || VARIANT == BITMASK __attribute__((unused)) int num = numNonEmpty; #endif @@ -131,4 +132,7 @@ #elif VARIANT == SNZI || VARIANT == BIAS snzi.arrive(i); + #elif VARIANT == BACK || VARIANT == BACKBIAS + snzi.arrive(i); + tls.rng2.set_raw_state( tls.rng1.get_raw_state()); #elif VARIANT == SNZM snzm.arrive(i); @@ -145,5 +149,5 @@ #endif } - #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS + #if VARIANT == VANILLA || VARIANT == BITMASK assert(numNonEmpty <= (int)numLists); #endif @@ -154,5 +158,5 @@ #ifndef NO_STATS tls.pick.push.success++; - #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS + #if VARIANT == VANILLA || VARIANT == BITMASK tls.empty.push.value += num; tls.empty.push.count += 1; @@ -171,8 +175,8 @@ { // Pick first list totally randomly - i = tls.rng.next() % numLists; + i = tls.rng1.next() % numLists; // Pick the other according to the bitmask - unsigned r = tls.rng.next(); + unsigned r = tls.rng1.next(); size_t mask = tls.mask.load(std::memory_order_relaxed); @@ -197,6 +201,24 @@ while(snzi.query()) { // Pick two lists at random - int i = tls.rng.next() % numLists; - // int j = tls.rng.next() % numLists; + int i = tls.rng1.next() % numLists; + int j = tls.rng1.next() % numLists; + + if(auto node = try_pop(i, j)) return node; + } + + #elif VARIANT == BACK + while(snzi.query()) { + // Pick two lists at random + int i = tls.rng2.prev() % numLists; + int j = tls.rng2.prev() % numLists; + + if(auto node = try_pop(i, j)) return node; + } + + #elif VARIANT == BACKBIAS + while(snzi.query()) { + // Pick two lists at random + int i = idx_from_r(tls.rng2.prev(), true); + int j = idx_from_r(tls.rng2.prev(), true); if(auto node = try_pop(i, j)) return node; @@ -206,7 +228,7 @@ while(snzi.query()) { // Pick two lists at random - unsigned ri = tls.rng.next(); + unsigned ri = tls.rng1.next(); unsigned i; - unsigned j = tls.rng.next(); + unsigned j = tls.rng1.next(); if(0 == (ri & 0xF)) { i = (ri >> 4) % numLists; @@ -228,6 +250,6 @@ { // Pick two random number - unsigned ri = tls.rng.next(); - unsigned rj = tls.rng.next(); + unsigned ri = tls.rng1.next(); + unsigned rj = tls.rng1.next(); // Pick two nodes from it @@ -270,6 +292,6 @@ while(snzm.query()) { // Pick two lists at random - int i = tls.rng.next() % numLists; - int j = tls.rng.next() % numLists; + int i = tls.rng1.next() % numLists; + int j = tls.rng1.next() % numLists; if(auto node = try_pop(i, j)) return node; @@ -285,6 +307,6 @@ unsigned num = ((numLists - 1) >> 6) + 1; - unsigned ri = tls.rng.next(); - unsigned rj = tls.rng.next(); + unsigned ri = tls.rng1.next(); + unsigned rj = tls.rng1.next(); unsigned wdxi = (ri >> 6u) % num; @@ -314,6 +336,6 @@ while(numNonEmpty != 0) { // Pick two lists at random - int i = tls.rng.next() % numLists; - int j = tls.rng.next() % numLists; + int i = tls.rng1.next() % numLists; + int j = tls.rng1.next() % numLists; if(auto node = try_pop(i, j)) return node; @@ -348,5 +370,5 @@ if( !list.lock.try_lock() ) return nullptr; - #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS + #if VARIANT == VANILLA || VARIANT == BITMASK __attribute__((unused)) int num = numNonEmpty; #endif @@ -371,5 +393,5 @@ __attribute__((unused)) bool ret = btr(tls.mask, bit); snzm.depart(w); - #elif VARIANT == SNZI || VARIANT == BIAS + #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS snzi.depart(w); #elif VARIANT == SNZM @@ -390,10 +412,10 @@ // Unlock and return list.lock.unlock(); - #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS + #if VARIANT == VANILLA || VARIANT == BITMASK assert(numNonEmpty >= 0); #endif #ifndef NO_STATS tls.pick.pop.success++; - #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER && VARIANT != BIAS + #if VARIANT == VANILLA || VARIANT == BITMASK tls.empty.pop.value += num; tls.empty.pop.count += 1; @@ -403,9 +425,24 @@ } + inline unsigned idx_from_r(unsigned r, bool bias) { + unsigned i; + if(bias) { + if(0 == (r & 0x3F)) { + i = r >> 6; + } else { + i = tls.my_queue + ((r >> 6) % 4); + tls.pick.push.local++; + } + } else { + i = r; + } + return i % numLists; + } public: static __attribute__((aligned(128))) thread_local struct TLS { - Random rng = { int(rdtscl()) }; + Random rng1 = { unsigned(std::hash{}(std::this_thread::get_id()) ^ rdtscl()) }; + Random rng2 = { unsigned(std::hash{}(std::this_thread::get_id()) ^ rdtscl()) }; unsigned my_queue = (ticket++) * 4; pick_stat pick; @@ -418,6 +455,12 @@ __attribute__((aligned(64))) std::unique_ptr []> lists; private: - #if VARIANT == SNZI || VARIANT == BIAS + #if VARIANT == SNZI || VARIANT == BACK snzi_t snzi; + #elif VARIANT == BIAS || VARIANT == BACKBIAS + #ifdef SNZI_PACKED + snzip_t snzi; + #else + snzi_t snzi; + #endif #elif VARIANT == SNZM || VARIANT == DISCOVER snzm_t snzm; Index: doc/theses/thierry_delisle_PhD/code/snzi-packed.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/snzi-packed.hpp (revision f4ec4a90525683f9f79fa4d1595d00d4819ca521) +++ doc/theses/thierry_delisle_PhD/code/snzi-packed.hpp (revision f4ec4a90525683f9f79fa4d1595d00d4819ca521) @@ -0,0 +1,179 @@ +#pragma once + +#define SNZI_PACKED + +#include "utils.hpp" + + +class snzip_t { + class node; + class node_aligned; +public: + const unsigned mask; + const int root; + std::unique_ptr leafs; + std::unique_ptr nodes; + + snzip_t(unsigned depth); + + void arrive(int idx) { + // idx >>= 1; + idx %= mask; + leafs[idx].arrive(); + } + + void depart(int idx) { + // idx >>= 1; + idx %= mask; + leafs[idx].depart(); + } + + bool query() const { + return nodes[root].query(); + } + + +private: + class __attribute__((aligned(32))) node { + friend class snzip_t; + private: + + union val_t { + static constexpr char Half = -1; + + uint64_t _all; + struct __attribute__((packed)) { + char cnt; + uint64_t ver:56; + }; + + bool cas(val_t & exp, char _cnt, uint64_t _ver) volatile { + val_t t; + t.ver = _ver; + t.cnt = _cnt; + /* paranoid */ assert(t._all == ((_ver << 8) | ((unsigned char)_cnt))); + return __atomic_compare_exchange_n(&this->_all, &exp._all, t._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); + } + + bool cas(val_t & exp, const val_t & tar) volatile { + return __atomic_compare_exchange_n(&this->_all, &exp._all, tar._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); + } + + val_t() : _all(0) {} + val_t(const volatile val_t & o) : _all(o._all) {} + }; + + //-------------------------------------------------- + // Hierarchical node + void arrive_h() { + int undoArr = 0; + bool success = false; + while(!success) { + auto x{ value }; + /* paranoid */ assert(x.cnt <= 120); + if( x.cnt >= 1 ) { + if( value.cas(x, x.cnt + 1, x.ver ) ) { + success = true; + } + } + /* paranoid */ assert(x.cnt <= 120); + if( x.cnt == 0 ) { + if( value.cas(x, val_t::Half, x.ver + 1) ) { + success = true; + x.cnt = val_t::Half; + x.ver = x.ver + 1; + } + } + /* paranoid */ assert(x.cnt <= 120); + if( x.cnt == val_t::Half ) { + /* paranoid */ assert(parent); + if(undoArr == 2) { + undoArr--; + } else { + parent->arrive(); + } + if( !value.cas(x, 1, x.ver) ) { + undoArr = undoArr + 1; + } + } + } + + for(int i = 0; i < undoArr; i++) { + /* paranoid */ assert(parent); + parent->depart(); + } + } + + void depart_h() { + while(true) { + auto x = (const val_t)value; + /* paranoid */ assertf(x.cnt >= 1, "%d", x.cnt); + if( value.cas( x, x.cnt - 1, x.ver ) ) { + if( x.cnt == 1 ) { + /* paranoid */ assert(parent); + parent->depart(); + } + return; + } + } + } + + //-------------------------------------------------- + // Root node + void arrive_r() { + __atomic_fetch_add(&value._all, 1, __ATOMIC_SEQ_CST); + } + + void depart_r() { + __atomic_fetch_sub(&value._all, 1, __ATOMIC_SEQ_CST); + } + + private: + volatile val_t value; + class node * parent = nullptr; + + bool is_root() { + return parent == nullptr; + } + + public: + void arrive() { + if(is_root()) arrive_r(); + else arrive_h(); + } + + void depart() { + if(is_root()) depart_r(); + else depart_h(); + } + + bool query() { + /* paranoid */ assert(is_root()); + return value._all > 0; + } + }; + + class __attribute__((aligned(128))) node_aligned : public node {}; +}; + +snzip_t::snzip_t(unsigned depth) + : mask( std::pow(2, depth) ) + , root( ((std::pow(2, depth + 1) - 1) / (2 -1)) - 1 - mask ) + , leafs(new node[ mask ]()) + , nodes(new node_aligned[ root + 1 ]()) +{ + int width = std::pow(2, depth); + int hwdith = width / 2; + std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ") " << (sizeof(snzip_t::node) * (root + 1)) << " bytes" << std::endl; + for(int i = 0; i < width; i++) { + int idx = i % hwdith; + std::cout << i << " -> " << idx + width << std::endl; + leafs[i].parent = &nodes[ idx ]; + } + + for(int i = 0; i < root; i++) { + int idx = (i / 2) + hwdith; + std::cout << i + width << " -> " << idx + width << std::endl; + nodes[i].parent = &nodes[ idx ]; + } +} Index: doc/theses/thierry_delisle_PhD/code/snzi.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/snzi.hpp (revision 42cd451e139b4d6ef2dc72aebb910104dd7f1fbc) +++ doc/theses/thierry_delisle_PhD/code/snzi.hpp (revision f4ec4a90525683f9f79fa4d1595d00d4819ca521) @@ -14,4 +14,5 @@ void arrive(int idx) { + idx >>= 2; idx %= mask; nodes[idx].arrive(); @@ -19,4 +20,5 @@ void depart(int idx) { + idx >>= 2; idx %= mask; nodes[idx].depart(); @@ -82,5 +84,9 @@ if( x.cnt == val_t::Half ) { /* paranoid */ assert(parent); - parent->arrive(); + if(undoArr == 2) { + undoArr--; + } else { + parent->arrive(); + } if( !value.cas(x, 1, x.ver) ) { undoArr = undoArr + 1; @@ -151,7 +157,8 @@ { int width = std::pow(base, depth); - std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ")" << std::endl; + std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ") " << (sizeof(snzi_t::node) * (root + 1)) << " bytes" << std::endl; for(int i = 0; i < root; i++) { - nodes[i].parent = &nodes[(i / base) + width ]; + std::cout << i << " -> " << (i / base) + width << std::endl; + nodes[i].parent = &nodes[(i / base) + width]; } } Index: doc/theses/thierry_delisle_PhD/code/utils.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/utils.hpp (revision 42cd451e139b4d6ef2dc72aebb910104dd7f1fbc) +++ doc/theses/thierry_delisle_PhD/code/utils.hpp (revision f4ec4a90525683f9f79fa4d1595d00d4819ca521) @@ -35,19 +35,69 @@ }; +// class Random { +// private: +// unsigned int seed; +// public: +// Random(int seed) { +// this->seed = seed; +// } + +// /** returns pseudorandom x satisfying 0 <= x < n. **/ +// unsigned int next() { +// seed ^= seed << 6; +// seed ^= seed >> 21; +// seed ^= seed << 7; +// return seed; +// } +// }; + +constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b); +constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){ + return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b)); +} +constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b){ + return (b==0) ? 0 : extendedEuclidX(b, a - b * (a / b)) - (a / b) * extendedEuclidY(b, a - b * (a / b)); +} + class Random { private: - unsigned int seed; + uint64_t x; + + static constexpr const uint64_t M = 1ul << 48ul; + static constexpr const uint64_t A = 25214903917; + static constexpr const uint64_t C = 11; + static constexpr const uint64_t D = 16; + public: - Random(int seed) { - this->seed = seed; + static constexpr const uint64_t m = M; + static constexpr const uint64_t a = A; + static constexpr const uint64_t c = C; + static constexpr const uint64_t d = D; + static constexpr const uint64_t ai = extendedEuclidX(A, M); +public: + Random(unsigned int seed) { + this->x = seed * a; } /** returns pseudorandom x satisfying 0 <= x < n. **/ unsigned int next() { - seed ^= seed << 6; - seed ^= seed >> 21; - seed ^= seed << 7; - return seed; - } + //nextx = (a * x + c) % m; + x = (A * x + C) & (M - 1); + return x >> D; + } + unsigned int prev() { + //prevx = (ainverse * (x - c)) mod m + unsigned int r = x >> D; + x = ai * (x - C) & (M - 1); + return r; + } + + void set_raw_state(uint64_t _x) { + this->x = _x; + } + + uint64_t get_raw_state() { + return this->x; + } };