Changeset 47a541d for doc/theses/thierry_delisle_PhD
- Timestamp:
- Jun 2, 2020, 2:38:25 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 16ee228
- Parents:
- 0092853
- Location:
- doc/theses/thierry_delisle_PhD/code
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
r0092853 r47a541d 8 8 #define BITMASK 2 9 9 #define DISCOVER 3 10 #define SNZM 4 10 11 11 12 #ifndef VARIANT … … 25 26 #include "utils.hpp" 26 27 #include "snzi.hpp" 28 #include "snzm.hpp" 27 29 28 30 using namespace std; … … 71 73 "SNZI", 72 74 "BITMASK", 73 "DISCOVER" 75 "DISCOVER", 76 "SNZI + MASK" 74 77 }; 75 78 return names[VARIANT]; … … 80 83 , numLists(numLists) 81 84 #if VARIANT == SNZI || VARIANT == DISCOVER 82 , snzi( std::log2( numLists / 8 ) ) 85 , snzi( 1, 8 ) 86 #elif VARIANT == SNZM 87 , snzm( numLists ) 83 88 #endif 84 89 { … … 112 117 if( !lists[i].lock.try_lock() ) continue; 113 118 114 #if VARIANT != SNZ I && VARIANT != DISCOVER119 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 115 120 __attribute__((unused)) int num = numNonEmpty; 116 121 #endif … … 126 131 #elif VARIANT == SNZI 127 132 snzi.arrive(i); 133 #elif VARIANT == SNZM 134 snzm.arrive(i); 128 135 #elif VARIANT == BITMASK 129 136 numNonEmpty++; … … 138 145 #endif 139 146 } 140 #if VARIANT != SNZ I && VARIANT != DISCOVER147 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 141 148 assert(numNonEmpty <= (int)numLists); 142 149 #endif … … 147 154 #ifndef NO_STATS 148 155 tls.pick.push.success++; 149 #if VARIANT != SNZ I && VARIANT != DISCOVER156 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 150 157 tls.empty.push.value += num; 151 158 tls.empty.push.count += 1; … … 194 201 if(auto node = try_pop(i, j)) return node; 195 202 } 203 #elif VARIANT == SNZM 204 while(snzm.query()) { 205 tls.pick.pop.mask_attempt++; 206 unsigned i, j; 207 { 208 // Pick two random number 209 unsigned ri = tls.rng.next(); 210 unsigned rj = tls.rng.next(); 211 212 // Pick two nodes from it 213 unsigned wdxi = ri & snzm.mask; 214 unsigned wdxj = rj & snzm.mask; 215 216 // Get the masks from the nodes 217 size_t maski = snzm.masks(wdxi); 218 size_t maskj = snzm.masks(wdxj); 219 220 if(maski == 0 && maskj == 0) continue; 221 222 unsigned bi = rand_bit(ri >> snzm.depth, maski); 223 unsigned bj = rand_bit(rj >> snzm.depth, maskj); 224 225 assertf(bi < 64, "%zu %u", maski, bi); 226 assertf(bj < 64, "%zu %u", maskj, bj); 227 228 i = (bi << snzm.depth) | wdxi; 229 j = (bj << snzm.depth) | wdxj; 230 231 assertf(i < numLists, "%u %u", bj, wdxi); 232 assertf(j < numLists, "%u %u", bj, wdxj); 233 } 234 235 if(auto node = try_pop(i, j)) return node; 236 } 196 237 #elif VARIANT == BITMASK 197 238 int nnempty; … … 266 307 if( !list.lock.try_lock() ) return nullptr; 267 308 268 #if VARIANT != SNZ I && VARIANT != DISCOVER309 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 269 310 __attribute__((unused)) int num = numNonEmpty; 270 311 #endif … … 291 332 #elif VARIANT == SNZI 292 333 snzi.depart(w); 334 #elif VARIANT == SNZM 335 snzm.depart(w); 293 336 #elif VARIANT == BITMASK 294 337 numNonEmpty--; … … 306 349 // Unlock and return 307 350 list.lock.unlock(); 308 #if VARIANT != SNZ I && VARIANT != DISCOVER351 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 309 352 assert(numNonEmpty >= 0); 310 353 #endif 311 354 #ifndef NO_STATS 312 355 tls.pick.pop.success++; 313 #if VARIANT != SNZ I && VARIANT != DISCOVER356 #if VARIANT != SNZM && VARIANT != SNZI && VARIANT != DISCOVER 314 357 tls.empty.pop.value += num; 315 358 tls.empty.pop.count += 1; … … 459 502 #if VARIANT == SNZI || VARIANT == DISCOVER 460 503 snzi_t snzi; 504 #elif VARIANT == SNZM 505 snzm_t snzm; 461 506 #else 462 507 std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists -
doc/theses/thierry_delisle_PhD/code/utils.hpp
r0092853 r47a541d 106 106 } 107 107 108 static inline unsigned rand_bit(unsigned rnum, size_t mask) __attribute__((artificial)); 108 109 static inline unsigned rand_bit(unsigned rnum, size_t mask) { 109 110 unsigned bit = mask ? rnum % __builtin_popcountl(mask) : 0;
Note: See TracChangeset
for help on using the changeset viewer.