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.
|Title of host publication||2013 IEEE 6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS)|
|Number of pages||10|
|Publication status||Published - 2013|
|Event||6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS 2013) - Edinburgh, United Kingdom|
Duration: 7 Sep 2013 → …
|Workshop||6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS 2013)|
|Period||07/09/2013 → …|