{"id":249,"date":"2011-11-29T14:07:54","date_gmt":"2011-11-29T19:07:54","guid":{"rendered":"https:\/\/www.bu.edu\/exafmm\/?page_id=249"},"modified":"2012-01-13T11:10:06","modified_gmt":"2012-01-13T16:10:06","slug":"features","status":"publish","type":"page","link":"https:\/\/www.bu.edu\/exafmm\/documentation\/features\/","title":{"rendered":"Features"},"content":{"rendered":"<h1><span style=\"font-size: 20px;\">Hybrid treecode\/FMM<\/span><\/h1>\n<p>We developed a new treecode-FMM hybrid algorithm with auto-tuning capabilities, that is <em>O<\/em>(<em>N<\/em>) and chooses the most efficient type of interaction. Auto-tuning is achieved by dynamically selecting the kernels during runtime, which requires a generic and flexible algorithm for traversing the tree.<\/p>\n<p><em>ExaFMM<\/em> uses a <strong>dual tree traversal <\/strong>for the target and source tree. See <strong>Figure 2<\/strong>. In the initial step, both trees are formed and their root cells are paired and pushed to an empty stack. Further iterations consist of popping a pair of cells form the stack, splitting the larger one, and applying an acceptance criterion to determine if multipole interaction is valid or not. If not, a new pair is pushed to the stack.<\/p>\n<p><strong>Figure 2<\/strong> shows three cases: the ones on the left and right satisfy the multipole acceptance criterion (MAC), while the one in the center does not and is pushed to the stack.<\/p>\n<figure id=\"attachment_201\" aria-describedby=\"caption-attachment-201\" style=\"width: 610px\" class=\"wp-caption aligncenter\"><a href=\"\/exafmm\/files\/2011\/06\/treewalk1.png\"><img loading=\"lazy\" class=\"size-full wp-image-201\" title=\"treewalk\" src=\"\/exafmm\/files\/2011\/06\/treewalk1.png\" alt=\"Figure 2\u2014Dual-tree traversal: illustration of the stack-based procedure.\" width=\"600\" height=\"353\" \/><\/a><figcaption id=\"caption-attachment-201\" class=\"wp-caption-text\">Figure 2 (copyrighted) \u2014Dual-tree traversal: illustration of the stack-based procedure. From \u201cHierarchical N-body simulations with auto-tuning for heterogeneous systems\u201d, Rio Yokota, L A Barba. Computing in Science and Engineering (CiSE), 3 January 2012, IEEE Computer Society, doi:10.1109\/MCSE.2012.1.<\/figcaption><\/figure>\n<div style=\"margin-bottom: 10em;\"><span style=\"display: none;\">.<\/span><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hybrid treecode\/FMM We developed a new treecode-FMM hybrid algorithm with auto-tuning capabilities, that is O(N) and chooses the most efficient type of interaction. Auto-tuning is achieved by dynamically selecting the kernels during runtime, which requires a generic and flexible algorithm for traversing the tree. ExaFMM uses a dual tree traversal for the target and source [&hellip;]<\/p>\n","protected":false},"author":3344,"featured_media":0,"parent":20,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/pages\/249"}],"collection":[{"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/users\/3344"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/comments?post=249"}],"version-history":[{"count":7,"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/pages\/249\/revisions"}],"predecessor-version":[{"id":331,"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/pages\/249\/revisions\/331"}],"up":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/pages\/20"}],"wp:attachment":[{"href":"https:\/\/www.bu.edu\/exafmm\/wp-json\/wp\/v2\/media?parent=249"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}