Show simple item record

dc.contributor.authorUmar, Ibrahim
dc.contributor.authorAnshus, Otto
dc.contributor.authorHa, Hoai Phuong
dc.date.accessioned2017-03-16T11:37:51Z
dc.date.available2017-03-16T11:37:51Z
dc.date.issued2016-08-09
dc.description.abstractLike 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 generalen_US
dc.descriptionSource:<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.citationUmar I, Anshus O, Ha HP. GreenBST: Energy-efficient concurrent search tree. Lecture Notes in Computer Science. 2016;9833:502-517en_US
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.otherFRIDAID 1376543
dc.identifier.other10.1007/978-3-319-43659-3_37
dc.identifier.urihttps://hdl.handle.net/10037/10730
dc.language.isoengen_US
dc.publisherSpringerLink. European Conference on Parallel Processing, Volume 9833 of the book series Lecture Notes in Computer Science (LNCS)en_US
dc.relation.journalLecture Notes in Computer Science
dc.relation.projectIDEU: 611183en_US
dc.relation.projectIDNorges forskningsråd: 231746en_US
dc.relation.projectIDNotur/NorStore: NN9342Ken_US
dc.rights.accessRightsopenAccessen_US
dc.subjectVDP::Mathematics and natural science: 400en_US
dc.titleGreenBST: Energy-efficient concurrent search treeen_US
dc.typeConference objecten_US
dc.typeKonferansebidragno


File(s) in this item

Thumbnail

This item appears in the following collection(s)

Show simple item record