ELB-trees an efficient and lock-free B-tree derivative

Lars Frydendal Bonnichsen, Sven Karlsson, Christian W. Probst

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

As computer systems scale in the number of processors, scalable data structures with good parallel performance become increasingly important. Lock-free data structures promise such improved parallel performance at the expense of higher algorithmic complexity and higher sequential execution time overhead. All lock-free data structures are based on simple atomic operations that, though supported by modern processors, are expensive in execution time. We present a lock-free data structure, ELB-trees, which under certain assumptions can be used as multimaps as well as priority queues. Specifically it cannot store duplicate key-value pairs, and it is not linearizable. Compared to existing data structures, ELB-trees require fewer atomic operations leading to improved performance. We measure the parallel performance of ELB-trees using a set of benchmarks and observe that ELB-trees are up to almost 30 times faster than library multimap implementations.
Original languageEnglish
Title of host publication2013 IEEE 6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS)
Number of pages10
PublisherIEEE
Publication date2013
DOIs
Publication statusPublished - 2013
Event6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS 2013) - Edinburgh, United Kingdom
Duration: 7 Sep 2013 → …
http://www.ida.liu.se/conferences/mucocos2013/

Workshop

Workshop6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS 2013)
CountryUnited Kingdom
CityEdinburgh
Period07/09/2013 → …
Internet address

Fingerprint Dive into the research topics of 'ELB-trees an efficient and lock-free B-tree derivative'. Together they form a unique fingerprint.

Cite this