{"id":45,"date":"2014-01-10T22:39:25","date_gmt":"2014-01-10T21:39:25","guid":{"rendered":"https:\/\/site.uit.no\/uitgreen\/?page_id=45"},"modified":"2015-09-14T17:21:21","modified_gmt":"2015-09-14T15:21:21","slug":"deltatrees","status":"publish","type":"page","link":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/","title":{"rendered":"Efficient Heterogeneous Manycore Computing"},"content":{"rendered":"

Source of funding: University of Troms\u00f8\u00a0<\/strong><\/p>\n

\"UiT<\/p>\n

Project Schedule:\u00a02013 — 2017<\/strong><\/p>\n

Sub-projects:<\/p>\n

    \n
  1. Locality-aware Concurrent Tree<\/li>\n<\/ol>\n
    \n

    1. Locality-aware Concurrent Tree<\/h1>\n

    Abstract<\/h2>\n

    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.<\/em><\/p>\n

    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\u2019s 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\u2019s 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\u2019s depth. <\/em><\/p>\n

    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.<\/em><\/p>\n

    Researchers<\/h2>\n

    Ibrahim Umar, Otto J. Anshus, Phuong H. Ha<\/p>\n

    Project Schedule<\/h2>\n

    March 2013\u00a0\u2013 March 2014<\/p>\n

    Publications<\/h2>\n