dc.contributor.author | Umar, Ibrahim | |
dc.contributor.author | Anshus, Otto | |
dc.contributor.author | Ha, Hoai Phuong | |
dc.date.accessioned | 2017-03-16T11:37:51Z | |
dc.date.available | 2017-03-16T11:37:51Z | |
dc.date.issued | 2016-08-09 | |
dc.description.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 | en_US |
dc.description | Source:<a href=http://link.springer.com/chapter/10.1007/978-3-319-43659-3_37>DOI: 10.1007/978-3-319-43659-3_37</a> | en_US |
dc.identifier.citation | Umar I, Anshus O, Ha HP. GreenBST: Energy-efficient concurrent search tree. Lecture Notes in Computer Science. 2016;9833:502-517 | en_US |
dc.identifier.cristinID | FRIDAID 1376543 | |
dc.identifier.doi | 10.1007/978-3-319-43659-3_37 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.issn | 1611-3349 | |
dc.identifier.uri | https://hdl.handle.net/10037/10730 | |
dc.language.iso | eng | en_US |
dc.publisher | SpringerLink. European Conference on Parallel Processing, Volume 9833 of the book series Lecture Notes in Computer Science (LNCS) | en_US |
dc.relation.journal | Lecture Notes in Computer Science | |
dc.relation.projectID | EU: 611183 | en_US |
dc.relation.projectID | Norges forskningsråd: 231746 | en_US |
dc.relation.projectID | Notur/NorStore: NN9342K | en_US |
dc.rights.accessRights | openAccess | en_US |
dc.subject | VDP::Mathematics and natural science: 400 | en_US |
dc.title | GreenBST: Energy-efficient concurrent search tree | en_US |
dc.type | Conference object | en_US |
dc.type | Konferansebidrag | no |