ub.xmlui.mirage2.page-structure.muninLogoub.xmlui.mirage2.page-structure.openResearchArchiveLogo
    • EnglishEnglish
    • norsknorsk
  • Velg spraakEnglish 
    • EnglishEnglish
    • norsknorsk
  • Administration/UB
View Item 
  •   Home
  • Fakultet for naturvitenskap og teknologi
  • Institutt for informatikk
  • Artikler, rapporter og annet (informatikk)
  • View Item
  •   Home
  • Fakultet for naturvitenskap og teknologi
  • Institutt for informatikk
  • Artikler, rapporter og annet (informatikk)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Efficient concurrent search trees using portable fine-grained locality

Permanent link
https://hdl.handle.net/10037/17871
DOI
https://doi.org/10.1109/TPDS.2019.2892968
Thumbnail
View/Open
article.pdf (608.8Kb)
Accepted manuscript version (PDF)
Date
2019-01-14
Type
Journal article
Tidsskriftartikkel
Peer reviewed

Author
Ha, Hoai Phuong; Anshus, Otto; Umar, Ibrahim
Abstract
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.
Description
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works
Publisher
IEEE
Citation
Ha HP, Anshus O, Umar I. Efficient concurrent search trees using portable fine-grained locality. IEEE Transactions on Parallel and Distributed Systems. 2019;30(7):1580-1595
Metadata
Show full item record
Collections
  • Artikler, rapporter og annet (informatikk) [478]
© 2019 IEEE

Browse

Browse all of MuninCommunities & CollectionsAuthor listTitlesBy Issue DateBrowse this CollectionAuthor listTitlesBy Issue Date
Login

Statistics

View Usage Statistics
UiT

Munin is powered by DSpace

UiT The Arctic University of Norway
The University Library
uit.no/ub - munin@ub.uit.no

Accessibility statement (Norwegian only)