ub.xmlui.mirage2.page-structure.muninLogoub.xmlui.mirage2.page-structure.openResearchArchiveLogo
    • EnglishEnglish
    • norsknorsk
  • Velg spraaknorsk 
    • EnglishEnglish
    • norsknorsk
  • Administrasjon/UB
Vis innførsel 
  •   Hjem
  • Fakultet for naturvitenskap og teknologi
  • Institutt for informatikk
  • Artikler, rapporter og annet (informatikk)
  • Vis innførsel
  •   Hjem
  • Fakultet for naturvitenskap og teknologi
  • Institutt for informatikk
  • Artikler, rapporter og annet (informatikk)
  • Vis innførsel
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 lenke
https://hdl.handle.net/10037/17871
DOI
https://doi.org/10.1109/TPDS.2019.2892968
Thumbnail
Åpne
article.pdf (608.8Kb)
Akseptert manusversjon (PDF)
Dato
2019-01-14
Type
Journal article
Tidsskriftartikkel
Peer reviewed

Forfatter
Ha, Hoai Phuong; Anshus, Otto; Umar, Ibrahim
Sammendrag
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.
Beskrivelse
© 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
Forlag
IEEE
Sitering
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
Vis full innførsel
Samlinger
  • Artikler, rapporter og annet (informatikk) [477]
© 2019 IEEE

Bla

Bla i hele MuninEnheter og samlingerForfatterlisteTittelDatoBla i denne samlingenForfatterlisteTittelDato
Logg inn

Statistikk

Antall visninger
UiT

Munin bygger på DSpace

UiT Norges Arktiske Universitet
Universitetsbiblioteket
uit.no/ub - munin@ub.uit.no

Tilgjengelighetserklæring