Bonnichsen, Lars Frydendal2; Karlsson, Sven1; Probst, Christian W.1
1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Embedded Systems Engineering, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 Language-Based Technology, Department of Applied Mathematics and Computer Science, Technical University of Denmark
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.
2013 Ieee 6th International Workshop on Multi-/many-core Computing Systems (mucocos), 2013
Main Research Area:
6th International Workshop on Multi-/Many-core Computing Systems (MuCoCoS 2013)