TreeFuser: a framework for analyzing and fusing general recursive tree traversals
TreeFuser: a framework for analyzing and fusing general recursive tree traversals
复制标题
TreeFuser：分析和融合一般递归树遍历的框架
DOI：
10.1145/3133900
复制
发表时间：
2017
影响因子：
--
通讯作者：
Milind Kulkarni
中科院分区：
文献类型：
--
作者：
Laith Sakka;Kirshanthan Sundararajah;Milind Kulkarni
树结构的一系列遍历出现在许多上下文中：编译器通道中的抽象语法树遍历，Web浏览器中的DOM渲染遍历，计算模拟代码中的kd树遍历。在这些设置中的每一个中，树被遍历多次以计算各种值并修改树的各个部分。虽然将这些遍历作为单独的小更新写入树相对容易，但出于效率原因，遍历通常被手动融合以减少树的每个部分被遍历的次数：通过同时对树执行多个操作，树的每个节点可以被访问更少的次数，增加优化的机会并减少缓存压力和其他开销。这个融合过程通常是手动完成的，需要仔细理解树的每个遍历是如何交互的。本文提出了一种自动的遍历融合方法：树遍历可以独立编写，然后我们的框架分析遍历之间的依赖关系，以确定如何将它们融合，以减少对树中每个节点的访问次数。我们的框架的一个关键方面是，它利用两个机会来增加融合的量：i）它自动集成代码运动，ii）它支持部分融合，其中一个遍历的部分可以与另一个融合，允许减少节点访问，而不需要完全融合两个遍历。我们在Clang中实现了我们的框架，并通过几个案例研究表明，我们可以成功地融合复杂的树遍历，减少遍历的总数，并大大提高局部性和性能。
Series of traversals of tree structures arise in numerous contexts: abstract syntax tree traversals in compiler passes, rendering traversals of the DOM in web browsers, kd-tree traversals in computational simulation codes. In each of these settings, a tree is traversed multiple times to compute various values and modify various portions of the tree. While it is relatively easy to write these traversals as separate small updates to the tree, for efficiency reasons, traversals are often manually fused to reduce the number of times that each portion of the tree is traversed: by performing multiple operations on the tree simultaneously, each node of the tree can be visited fewer times, increasing opportunities for optimization and decreasing cache pressure and other overheads. This fusion process is often done manually, requiring careful understanding of how each of traversals of the tree interact. This paper presents an automatic approach to traversal fusion: tree traversals can be written independently, and then our framework analyzes the dependences between the traversals to determine how they can be fused to reduce the number of visits to each node in the tree. A critical aspect of our framework is that it exploits two opportunities to increase the amount of fusion: i) it automatically integrates code motion, and ii) it supports partial fusion, where portions of one traversal can be fused with another, allowing for a reduction in node visits without requiring that two traversals be fully fused. We implement our framework in Clang, and show across several case studies that we can successfully fuse complex tree traversals, reducing the overall number of traversals and substantially improving locality and performance.