000203822 001__ 203822
000203822 005__ 20190317000050.0
000203822 037__ $$aREP_WORK
000203822 245__ $$aDesigning ASCY-compliant Concurrent Search Data Structures
000203822 269__ $$a2014
000203822 260__ $$aLausanne$$c2014
000203822 300__ $$a23
000203822 336__ $$aReports
000203822 500__ $$aAuthors appear in alphabetical order.
000203822 520__ $$aThis 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.
000203822 6531_ $$aConcurrency
000203822 6531_ $$aData structures
000203822 6531_ $$aScalability
000203822 6531_ $$aHash tables
000203822 6531_ $$aBinary Search Trees
000203822 700__ $$0246554$$aDavid, Tudor Alexandru$$g199587
000203822 700__ $$0240335$$aGuerraoui, Rachid$$g105326
000203822 700__ $$0247118$$aChe, Tong$$g225769
000203822 700__ $$0245903$$aTrigonakis, Vasileios$$g210576
000203822 8564_ $$uhttp://lpd.epfl.ch/site/ascylib$$zURL
000203822 8564_ $$uhttps://github.com/LPD-EPFL/CLHT$$zURL
000203822 8564_ $$uhttps://github.com/LPD-EPFL/ASCYLIB$$zURL
000203822 8564_ $$s376090$$uhttps://infoscience.epfl.ch/record/203822/files/Tech_report_CLHT_BSTTK.pdf$$yn/a$$zn/a
000203822 909C0 $$0252114$$pDCL$$xU10407
000203822 909CO $$ooai:infoscience.tind.io:203822$$pIC$$preport$$qGLOBAL_SET
000203822 917Z8 $$x210576
000203822 917Z8 $$x210576
000203822 937__ $$aEPFL-REPORT-203822
000203822 973__ $$aEPFL
000203822 980__ $$aREPORT