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.


Year:
2014
Publisher:
Lausanne
Keywords:
Note:
Authors appear in alphabetical order.
Laboratories:




 Record created 2014-12-18, last modified 2018-06-22

n/a:
Download fulltextPDF
External links:
Download fulltextURL
Download fulltextURL
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)