SAUCE
Home
Events
Listing
Future
Previous
Accelerated Computing with GPUs 2020
Data Mining - Winter 20/21
High Performance Computing 2019
Einführung in die Bioinformatik WS19/20
Computational Logic
Parallel Algorithms and Architectures 2019
DSEA Praktikum 2018/19
Deep Learning 2018
High Performance Computing 2018
Parallel Algorithms and Architectures 2018
Datenstrukturen und effiziente Algorithmen Ws 18/19
EiP SoSe 18
bio-st-18
EiP WS 2017/18
High Performance Computing 2017
Datenstrukturen und effiziente Algorithmen WiSe 17/18
PS SS 2017
Einfuehrung in die Programmierung SS17
Parallel Algorithms and Architectures 2017
High Performance Computing 2016
DSEA 2016/17
EiP WS2016/17
Parallel Algorithms and Architectures 2016
PS SS 2016
Krypto SS 2016
EiP SS 2016
DSEA Praktikum WS 2015/16
DSEA WS 2015/16
News
Documentation
About
Changelog
Roadmap
Deutsche Dokumentation
Tips and Tricks
Test configuration
Language information
Contact
Login
High Performance Computing 2019
Sheet 10 Redoable
Pair Programming
Sheet 2 (AVX Shuffles, Instruction Parallelism)
Sheet 3 (Stochastic PI, Shallow Deep Learning)
Sheet 4 (Conjugate Gradient with MPI, Asynchronous 2D Jacobi Partitioning)
Sheet 6 (std::async, block-cyclic distribution)
Sheet 7 (Atomics, Queue)
Sheet 8 (Sorting, Riemann Zeta)
Sheet 5 (Reverse-Engineering MPI, SUMMA)
Sheet 9 (Data Dependencies, Triangular Matrix Vector)
Sheet 10: Lockfree Hashmaps
Sheet 11 (Position Based Dynamics)
Sheet 12 ( Outer Product, Kmer Counting)
Tutorial 0: C++ Examples
Tutorials_extra
All Exercises
testSheet
Sheet 2 Redoable
Sheet 3 Redoable
Sheet 4 Redoable
Sheet 5 Redoable
Sheet 6 Redoable
Sheet 7 Redoable
Sheet 8 Redoable
Sheet 9 Redoable
Sheet 10 Redoable
Sheet 11 Redoable
Sheet 12 Redoable
Task 1 (Lockfree Multivalue Hashmap)
Task 1 (Lockfree Multivalue Hashmap)
Task 2 (Lockfree Singlevalue Robin Hood Hashmap)
Task 1 (Lockfree Multivalue Hashmap)
Assignment
Scaffold Head
#include <algorithm> #include <iostream> #include <cstdint> #include <vector> #include <atomic> #include <limits> #include "include/hpc_helpers.hpp" struct murmur_integer_finalizer_hash_uint32_t { // this hash function is magic, nobody knows why uint32_t operator() ( uint32_t x) const { x ^= x >> 16; x *= 0x85ebca6b; x ^= x >> 13; x *= 0xc2b2ae35; x ^= x >> 16; return x; } }; template < typename key_t, typename val_t> struct entry_t { // empty key is encoded as 11111111...1 static constexpr key_t empty_key = std::numeric_limits<key_t>::max(); static constexpr val_t empty_val = std::numeric_limits<val_t>::max(); key_t key; val_t val; void set ( const key_t& key_, const key_t& val_) { key = key_; val = val_; } void set_empty () { set(empty_key, empty_val); } }; template < typename key_t, // data type for keys typename val_t, // data type for values typename fun_t> // hash function acting on keys struct hashmap_t { typedef entry_t<key_t, val_t> slot_t; const uint64_t capacity, num_probes; const fun_t hash_function; std::atomic<slot_t> * slots; hashmap_t ( uint64_t capacity_, fun_t hash_function_) : capacity (capacity_), num_probes (capacity_), hash_function(hash_function_) { // create array of atomic slots slots = new std::atomic<slot_t>[capacity]; // prepare empty slot for initialization slot_t empty_slot; empty_slot.set_empty(); // initialize them with empty slots for (uint64_t index = 0; index < capacity; index++) slots[index].store(empty_slot); } ~hashmap_t () { delete [] slots; } bool is_lock_free () { return slots[0].is_lock_free(); }
Scaffold Foot
std::vector<val_t> query ( key_t key) const { // here we store the values std::vector<val_t> values; // you cannot insert empty keys if (key == slot_t::empty_key) return values; // traverse the probing sequence until you hit an empty slot const uint64_t offset = hash_function(key); for (uint64_t probe = 0; probe < num_probes; probe++) { // linear probing scheme const uint64_t index = (offset+probe) % capacity; // here we can read using relaxed memory order since there no // causal dependencies between individual accesses const slot_t slot = slots[index].load(std::memory_order_relaxed); if (slot.key == key) values.push_back(slot.val); if (slot.key == slot_t::empty_key) { std::sort(values.begin(), values.end()); return values; } } std::sort(values.begin(), values.end()); return values; } }; int main () { typedef uint32_t key_t; typedef uint32_t val_t; const uint64_t capacity = 1UL << 5; murmur_integer_finalizer_hash_uint32_t hash; hashmap_t<key_t, val_t, decltype(hash)> hashmap(capacity, hash); if(!hashmap.is_lock_free()) std::cout << "WARNING: Using slow mutexes!" << std::endl; TIMERSTART(insert) # pragma omp parallel for for (uint64_t index = 0; index < capacity*19/40; index++) if(!hashmap.insert(index, index)) std::cout << "ERROR: Insertion failure: " << index << std::endl; TIMERSTOP(insert) TIMERSTART(update) # pragma omp parallel for for (uint64_t index = 0; index < capacity*19/40; index++) if(!hashmap.insert(index, index+1)) std::cout << "ERROR: Insertion failure: " << index << std::endl; TIMERSTOP(update) TIMERSTART(query_existing_keys) # pragma omp parallel for for (uint64_t index = 0; index < capacity*19/40; index++) { const auto& result = hashmap.query(index); if (!(result.size() == 2 && result[0] == std::min(val_t(index), val_t(index+1)) && result[1] == std::max(val_t(index), val_t(index+1)))) std::cout << "ERROR: Query failure: " << index << std::endl; } TIMERSTOP(query_existing_keys) TIMERSTART(query_nonexisting_keys) # pragma omp parallel for for (uint64_t index = capacity*19/40; index < capacity; index++) { const auto& result = hashmap.query(index); if (result.size()) std::cout << "ERROR: Query failure: " << index << std::endl; } TIMERSTOP(query_nonexisting_keys) std::cout << "Parallel programming is fun!" << std::endl; }
Start time:
Do 10 Okt 2019 10:15:00
End time:
Di 11 Feb 2020 10:15:00
General test timeout:
10.0 seconds
Tests
Comment prefix
#
Given input
Expected output
Parallel programming is fun!