Efficient Heterogeneous Manycore Computing

Source of funding: University of Tromsø 

UiT logo

Project Schedule: 2013 — 2017

Sub-projects:

  1. Locality-aware Concurrent Tree

1. Locality-aware Concurrent Tree

Abstract

As other fundamental programming abstractions in energy-efficient computing, search trees are expected to support both high parallelism and data locality. However, existing locality-aware search trees such as those based on the van Emde Boas layout (vEB-based trees), poorly support concurrent (update) operations while existing highly-concurrent search trees such as red-black trees and AVL trees, do not consider data locality.

We present 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 fixed size tree-container with the van Emde Boas layout. The expected memory transfer costs of DeltaTree’s Search, Insert and Delete operations are O(logB N), 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 sometimes are triggered to minimise DeltaTree’s depth.

Our experimental evaluation using the recent implementation of non-blocking binary search trees, as well as the AVL, red-black, and speculation friendly trees from the Synchrobench benchmark, has shown that DeltaTree is up to 1.4 times faster and 2.5 times more energy efficient than the other trees in search-intensive benchmarks.

Researchers

Ibrahim Umar, Otto J. Anshus, Phuong H. Ha

Project Schedule

March 2013 – March 2014

Publications

  • Ibrahim Umar, Otto J. Anshus, Phuong H. Ha (2013). DeltaTree: A Practical Locality-aware Concurrent Search Tree, Technical report no. 2013-74, Department of Computer Science, Faculty of Science, University of Tromsø, Norway, Oct. 2013. (link)
  • UMAR, I., ANSHUS, O. J., AND HA, P. H. Deltatree: A locality-aware concurrent search tree. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (2015), SIGMETRICS ’15, pp. 457–458. (link)

Code(s)

GIT: https://github.com/iambaim/tree-collection

Share