Contention adapting search trees
2015 (English)In: Proc. 14th International Symposium on Parallel and Distributed Computing, IEEE conference proceedings, 2015, 215-224 p.Conference paper (Refereed)
With multicores being ubiquitous, concurrent data structures are becoming increasingly important. This paper proposes a novel approach to concurrent data structure design where the data structure collects statistics about contention and adapts dynamically according to this statistics. We use this approach to create a contention adapting binary search tree (CA tree) that can be used to implement concurrent ordered sets and maps. Our experimental evaluation shows that CA trees scale similar to recently proposed algorithms on a big multicore machine on various scenarios with a larger set size, and outperform the same data structures in more contended scenarios and in sequential performance. We also show that CA trees are well suited for optimization with hardware lock elision. In short, we propose a practically useful and easy to implement and show correct concurrent search tree that naturally adapts to the level of contention.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2015. 215-224 p.
IdentifiersURN: urn:nbn:se:uu:diva-272365DOI: 10.1109/ISPDC.2015.32ISI: 000380396000027ISBN: 9781467371476OAI: oai:DiVA.org:uu-272365DiVA: diva2:893836
ISPDC 2015, June 29 – July 1, Limassol, Cyprus
FunderSwedish Research Council