Index: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (revision 2e5fd8b6bb9a252b9bf620b39f5a73f2f2d9360a) +++ doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (revision f0c3120ef113f46364e3c1cf53b2ccae87a6da3b) @@ -30,4 +30,5 @@ #include "links.hpp" #include "snzi.hpp" +#include "snzi-packed.hpp" #include "snzm.hpp" @@ -82,6 +83,12 @@ : numLists(numThreads * numQueues) , lists(new intrusive_queue_t[numLists]) - #if VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS - , snzi( std::log2( numLists / (numQueues) ), 2 ) + #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 ) @@ -421,8 +428,8 @@ unsigned i; if(bias) { - if(0 == (r & 0xF)) { - i = r >> 4; + if(0 == (r & 0x3F)) { + i = r >> 6; } else { - i = tls.my_queue + ((r >> 4) % 4); + i = tls.my_queue + ((r >> 6) % 4); tls.pick.push.local++; } @@ -448,6 +455,12 @@ __attribute__((aligned(64))) std::unique_ptr []> lists; private: - #if VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS + #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 f0c3120ef113f46364e3c1cf53b2ccae87a6da3b) +++ doc/theses/thierry_delisle_PhD/code/snzi-packed.hpp (revision f0c3120ef113f46364e3c1cf53b2ccae87a6da3b) @@ -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 2e5fd8b6bb9a252b9bf620b39f5a73f2f2d9360a) +++ doc/theses/thierry_delisle_PhD/code/snzi.hpp (revision f0c3120ef113f46364e3c1cf53b2ccae87a6da3b) @@ -157,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]; } }