Efficient Concurrent Search Trees Using Portable Fine-Grained Locality

• Published in: IEEE transactions on parallel and distributed systems 2019-07, Vol.30 (7), p.1580-1595
• Main Authors: Ha, Phuong Hoai, Anshus, Otto J., Umar, Ibrahim
• Format: Article
• Language: English
• Subjects: Benchmarks; Computation; Concurrency; Concurrent computing; Concurrent data abstractions; data locality; Data models; Data storage; Data structures; Energy efficiency; Energy storage; Informasjons- og kommunikasjonsvitenskap: 420; Information and communication science: 420; Layout; Matematikk og Naturvitenskap: 400; Mathematics and natural science: 400; Methodology; performance optimization; Portability; Power efficiency; Random access memory; Searching; System-on-chip; Trees; Upper bound; VDP; Viability
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2019.2892968

Concurrent search trees are crucial data abstractions widely used in many important systems such as databases, file systems and data storage. Like other fundamental abstractions for energy-efficient computing, concurrent search trees should support both high concurrency and fine-grained data locality in a platform-independent manner. However, existing portable fine-grained locality-aware search trees such as ones based on the van Emde Boas layout (vEB-based trees) poorly support concurrent update operations while existing highly-concurrent search trees such as non-blocking search trees do not consider fine-grained data locality. In this paper, we first present a novel methodology to achieve both portable fine-grained data locality and high concurrency for search trees. Based on the methodology, we devise a novel locality-aware concurrent search tree called GreenBST. To the best of our knowledge, GreenBST is the first practical search tree that achieves both portable fine-grained data locality and high concurrency. We analyze and compare GreenBST energy efficiency (in operations/Joule) and performance (in operations/second) with seven prominent concurrent search trees on a high performance computing (HPC) platform (Intel Xeon), an embedded platform (ARM), and an accelerator platform (Intel Xeon Phi) using parallel micro- benchmarks (Synchrobench). Our experimental results show that GreenBST achieves the best energy efficiency and performance on all the different platforms. GreenBST achieves up to 50 percent more energy efficiency and 60 percent higher throughput than the best competitor in the parallel benchmarks. These results confirm the viability of our new methodology to achieve both portable fine-grained data locality and high concurrency for search trees.