{"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":"<p>Source of funding: <strong>University of Troms\u00f8\u00a0<\/strong><\/p>\n<p><img decoding=\"async\" class=\"size-full wp-image-69 alignright\" style=\"line-height: 24px;font-size: 16px\" src=\"https:\/\/site.uit.no\/arcticgreen\/wp-content\/uploads\/sites\/175\/2014\/01\/UiT.jpg\" alt=\"UiT logo\" width=\"92\" height=\"90\" \/><\/p>\n<p>Project Schedule:\u00a0<strong>2013 &#8212; 2017<\/strong><\/p>\n<p>Sub-projects:<\/p>\n<ol>\n<li>Locality-aware Concurrent Tree<\/li>\n<\/ol>\n<hr \/>\n<h1>1. Locality-aware Concurrent Tree<\/h1>\n<h2>Abstract<\/h2>\n<p title=\"Page 1\"><em>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<p title=\"Page 1\"><em>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<p title=\"Page 1\"><em>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<h2>Researchers<\/h2>\n<p>Ibrahim Umar, Otto J. Anshus, Phuong H. Ha<\/p>\n<h2>Project Schedule<\/h2>\n<p>March 2013\u00a0\u2013 March 2014<\/p>\n<h2>Publications<\/h2>\n<ul>\n<li>Ibrahim Umar, Otto J. Anshus, Phuong H. Ha (2013).\u00a0<strong>DeltaTree: A Practical Locality-aware Concurrent Search Tree<\/strong>, Technical report no. 2013-74, Department of Computer Science, Faculty of Science, University of Troms\u00f8, Norway, Oct. 2013. (<a href=\"http:\/\/arxiv.org\/abs\/1312.2628\">link<\/a>)<\/li>\n<li>\n<div class=\"page\" title=\"Page 10\">\n<div class=\"layoutArea\">\n<div class=\"column\">\n<p>UMAR, I., ANSHUS, O. J., AND HA, P. H. <strong>Deltatree: A locality-aware concurrent search tree<\/strong>. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (2015), SIGMETRICS \u201915, pp. 457\u2013458. (<a href=\"http:\/\/dl.acm.org\/citation.cfm?id=2745891\" target=\"_blank\">link<\/a>)<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/li>\n<\/ul>\n<h2>Code(s)<\/h2>\n<p>GIT:\u00a0<a href=\"https:\/\/github.com\/iambaim\/tree-collection\" target=\"_blank\">https:\/\/github.com\/iambaim\/tree-collection<\/a><\/p>\n<iframe src=\"http:\/\/www.facebook.com\/plugins\/like.php?href=https%3A%2F%2Fsite.uit.no%2Farcticgreen%2Fprojects%2Fdeltatrees%2F&amp;layout=standard&amp;show_faces=true&amp;width=450&amp;action=like&amp;colorscheme=light&amp;height=80\" scrolling=\"no\" frameborder=\"0\" style=\"border:none; overflow:hidden; width:450px; height:80px;\" allowTransparency=\"true\"><\/iframe>","protected":false},"excerpt":{"rendered":"<p>Source of funding: University of Troms\u00f8\u00a0 Project Schedule:\u00a02013 &#8212; 2017 Sub-projects: 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, &hellip; <a href=\"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":308,"featured_media":0,"parent":26,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-45","page","type-page","status-publish","hentry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Efficient Heterogeneous Manycore Computing - Arctic Green Computing Group (AGC)<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Efficient Heterogeneous Manycore Computing - Arctic Green Computing Group (AGC)\" \/>\n<meta property=\"og:description\" content=\"Source of funding: University of Troms\u00f8\u00a0 Project Schedule:\u00a02013 &#8212; 2017 Sub-projects: 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, &hellip; Continue reading &rarr;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/\" \/>\n<meta property=\"og:site_name\" content=\"Arctic Green Computing Group (AGC)\" \/>\n<meta property=\"article:modified_time\" content=\"2015-09-14T15:21:21+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/site.uit.no\/arcticgreen\/wp-content\/uploads\/sites\/175\/2014\/01\/UiT.jpg\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/\",\"url\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/\",\"name\":\"Efficient Heterogeneous Manycore Computing - Arctic Green Computing Group (AGC)\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/wp-content\\\/uploads\\\/sites\\\/175\\\/2014\\\/01\\\/UiT.jpg\",\"datePublished\":\"2014-01-10T21:39:25+00:00\",\"dateModified\":\"2015-09-14T15:21:21+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/#primaryimage\",\"url\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/wp-content\\\/uploads\\\/sites\\\/175\\\/2014\\\/01\\\/UiT.jpg\",\"contentUrl\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/wp-content\\\/uploads\\\/sites\\\/175\\\/2014\\\/01\\\/UiT.jpg\",\"width\":92,\"height\":90,\"caption\":\"UiT logo\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/deltatrees\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Projects\",\"item\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/projects\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Efficient Heterogeneous Manycore Computing\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/#website\",\"url\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/\",\"name\":\"Arctic Green Computing Group (AGC)\",\"description\":\"Department of Computer Science Faculty of Science and Technology University of Troms\u00f8 (UiT)\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/site.uit.no\\\/arcticgreen\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Efficient Heterogeneous Manycore Computing - Arctic Green Computing Group (AGC)","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/","og_locale":"en_US","og_type":"article","og_title":"Efficient Heterogeneous Manycore Computing - Arctic Green Computing Group (AGC)","og_description":"Source of funding: University of Troms\u00f8\u00a0 Project Schedule:\u00a02013 &#8212; 2017 Sub-projects: 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, &hellip; Continue reading &rarr;","og_url":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/","og_site_name":"Arctic Green Computing Group (AGC)","article_modified_time":"2015-09-14T15:21:21+00:00","og_image":[{"url":"https:\/\/site.uit.no\/arcticgreen\/wp-content\/uploads\/sites\/175\/2014\/01\/UiT.jpg","type":"","width":"","height":""}],"twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/","url":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/","name":"Efficient Heterogeneous Manycore Computing - Arctic Green Computing Group (AGC)","isPartOf":{"@id":"https:\/\/site.uit.no\/arcticgreen\/#website"},"primaryImageOfPage":{"@id":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/#primaryimage"},"image":{"@id":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/#primaryimage"},"thumbnailUrl":"https:\/\/site.uit.no\/arcticgreen\/wp-content\/uploads\/sites\/175\/2014\/01\/UiT.jpg","datePublished":"2014-01-10T21:39:25+00:00","dateModified":"2015-09-14T15:21:21+00:00","breadcrumb":{"@id":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/#primaryimage","url":"https:\/\/site.uit.no\/arcticgreen\/wp-content\/uploads\/sites\/175\/2014\/01\/UiT.jpg","contentUrl":"https:\/\/site.uit.no\/arcticgreen\/wp-content\/uploads\/sites\/175\/2014\/01\/UiT.jpg","width":92,"height":90,"caption":"UiT logo"},{"@type":"BreadcrumbList","@id":"https:\/\/site.uit.no\/arcticgreen\/projects\/deltatrees\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/site.uit.no\/arcticgreen\/"},{"@type":"ListItem","position":2,"name":"Projects","item":"https:\/\/site.uit.no\/arcticgreen\/projects\/"},{"@type":"ListItem","position":3,"name":"Efficient Heterogeneous Manycore Computing"}]},{"@type":"WebSite","@id":"https:\/\/site.uit.no\/arcticgreen\/#website","url":"https:\/\/site.uit.no\/arcticgreen\/","name":"Arctic Green Computing Group (AGC)","description":"Department of Computer Science Faculty of Science and Technology University of Troms\u00f8 (UiT)","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/site.uit.no\/arcticgreen\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"_links":{"self":[{"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/pages\/45","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/users\/308"}],"replies":[{"embeddable":true,"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/comments?post=45"}],"version-history":[{"count":9,"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/pages\/45\/revisions"}],"predecessor-version":[{"id":319,"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/pages\/45\/revisions\/319"}],"up":[{"embeddable":true,"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/pages\/26"}],"wp:attachment":[{"href":"https:\/\/site.uit.no\/arcticgreen\/wp-json\/wp\/v2\/media?parent=45"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}