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.

GreenBST: Energy-efficient concurrent search tree

Permanent link
https://hdl.handle.net/10037/10730
DOI
https://doi.org/10.1007/978-3-319-43659-3_37
Thumbnail
View/Open
article.pdf (696.7Kb)
(PDF)
Date
2016-08-09
Type
Conference object
Konferansebidrag

Author
Umar, Ibrahim; Anshus, Otto; Ha, Hoai Phuong
Abstract
Like other fundamental abstractions for energy-efficient com- puting, search trees need to support both high concurrency and fine- grained data locality. However, existing 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 the non-blocking binary search trees do not consider data locality. We present GreenBST, a practical energy-efficient concurrent search tree that supports fine-grained data locality as vEB-based trees do, but unlike vEB-based trees, GreenBST supports high concurrency. GreenBST is a k -ary leaf-oriented tree of GNodes where each GNode is a fixed size tree-container with the van Emde Boas layout. As a result, GreenBST minimizes data transfer between memory levels while supporting highly concurrent (update) operations. Our experimental evaluation using the recent implementation of non-blocking binary search trees, highly con- current B-trees, conventional vEB trees, as well as the portably scalable concurrent trees shows that GreenBST is efficient: its energy efficiency (in operations/Joule) and throughput (in operations/second) are up to 65% and 69% higher, respectively, than the other trees on a high performance computing (HPC) platform (Intel Xeon), an embedded platform (ARM), and an accelerator platform (Intel Xeon Phi). The results also provide insights into how to develop energy-efficient data structures in general
Description
Source:DOI: 10.1007/978-3-319-43659-3_37
Publisher
SpringerLink. European Conference on Parallel Processing, Volume 9833 of the book series Lecture Notes in Computer Science (LNCS)
Citation
Umar I, Anshus O, Ha HP. GreenBST: Energy-efficient concurrent search tree. Lecture Notes in Computer Science. 2016;9833:502-517
Metadata
Show full item record
Collections
  • Artikler, rapporter og annet (informatikk) [306]

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)