Show simple item record

dc.contributor.authorUmar, Ibrahim
dc.contributor.authorAnshus, Otto
dc.contributor.authorHa, Hoai Phuong
dc.date.accessioned2013-12-20T07:15:38Z
dc.date.available2013-12-20T07:15:38Z
dc.date.issued2013
dc.description.abstractAs other fundamental programming abstractions in energy-e cient computing, search trees are expected to support both high parallelism and data locality. However, existing highly-concurrent search trees such as red-black trees and AVL trees do not consider data locality while existing locality-aware search trees such as those based on the van Emde Boas layout (vEB-based trees), poorly support concurrent (update) operations. This paper presents DeltaTree, a practical locality-aware concurrent search tree that combines both locality-optimisation techniques from vEB-based trees and concurrency-optimisation techniques from non-blocking highly-concurrent search trees. DeltaTree is a k-ary leaf-oriented tree of DeltaNodes in which each DeltaNode is a size- xed tree-container with the van Emde Boas layout. The expected memory transfer costs of DeltaTree's Search, Insert and Delete operations are O(logBN), where N;B are the tree size and the unknown memory block size in the ideal cache model, respectively. DeltaTree's Search operation is wait-free, providing prioritised lanes for Search operations, the dominant operation in search trees. Its Insert and Delete operations are non-blocking to other Search, Insert and Delete operations, but they may be occasionally blocked by maintenance operations that are sometimes triggered to keep DeltaTree in good shape. Our experimental evaluation using the latest implementation of AVL, red-black, and speculation friendly trees from the Synchrobench benchmark has shown that DeltaTree is up to 5 times faster than all of the three concurrent search trees for searching operations and up to 1.6 times faster for update operations when the update contention is not too high.en
dc.identifier.cristinIDFRIDAID 1075833
dc.identifier.urihttps://hdl.handle.net/10037/5673
dc.identifier.urnURN:NBN:no-uit_munin_5377
dc.language.isoengen
dc.publisherUiT Norges arktiske universiteten
dc.publisherUiT The Arctic University of Norwayen
dc.rights.accessRightsopenAccess
dc.subjectVDP::Mathematics and natural science: 400::Information and communication science: 420::Algorithms and computability theory: 422en
dc.subjectVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422en
dc.titleDeltaTree: A Practical Locality-aware Concurrent Search Treeen
dc.typeResearch reporten
dc.typeForskningsrapporten


File(s) in this item

Thumbnail
Thumbnail

This item appears in the following collection(s)

Show simple item record