Designing ASCY-compliant Concurrent Search Data Structures
This report details the design of two new concurrent data structures, a hash table, called CLHT, and a binary search tree (BST), called BST-TK. Both designs are based on asynchronized concurrency (ASCY), a paradigm consisting of four complementary programming patterns. ASCY calls for the design of concurrent search data structures to resemble that of their sequential counterparts. CLHT (cache-line hash table) uses cache-line-sized buckets and performs in-place updates. As a cache-line block is the granularity of the cache-coherence protocols, CLHT ensures that most operations are completed with at most one cache-line transfer. BST-TK reduces the number of cache-line transfers by acquiring less locks than existing BSTs.
- URL: http://lpd.epfl.ch/site/ascylib
- URL: https://github.com/LPD-EPFL/CLHT
- URL: https://github.com/LPD-EPFL/ASCYLIB
Authors appear in alphabetical order.
Record created on 2014-12-18, modified on 2016-08-09