Automatically enhancing locality for tree traversals with traversal splicing
Automatically enhancing locality for tree traversals with traversal splicing
复制标题
通过遍历拼接自动增强树遍历的局部性
DOI：
10.1145/2384616.2384643
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
Milind Kulkarni
中科院分区：
文献类型：
--
作者：
Youngjoon Jo;Milind Kulkarni
通常，在基于指针的数据结构（例如树木和图形）上运行的不规则程序中，通常适用于改善不规则程序中的时间区域。专注于不规则程序的子集，即，像Barnes-Hut和最近的邻居这样的树遍历算法，以前的工作提出了点阻滞，这是一种类似于常规程序中循环的技术，以改善区域。但是，点阻断高度取决于点分类，这是一种重新排序点的技术，因此连续点将具有相似的遍历。进行此类先验需要了解算法的语义以及高度应用特定的技术。在这项工作中，我们提出了针对不规则树遍历代码的新型，一般的自动局部性优化，对点顺序不太敏感，因此即使没有语义信息也可以提供更好的性能。对于六种基准算法，我们表明遍历剪接可以在基线实现上提供高达9.147（几何平均值：3.095）的单线程加速度，而在侧面块实现上最多可提供4.752（几何平均值：2.079）。此外，我们表明，在许多情况下，自动将遍历剪接应用于基线实现会产生比仔细的手工优化实现更好的性能。
Generally applicable techniques for improving temporal locality in irregular programs, which operate over pointer-based data structures such as trees and graphs, are scarce. Focusing on a subset of irregular programs, namely, tree traversal algorithms like Barnes-Hut and nearest neighbor, previous work has proposed point blocking, a technique analogous to loop tiling in regular programs, to improve locality. However point blocking is highly dependent on point sorting, a technique to reorder points so that consecutive points will have similar traversals. Performing this a priori sort requires an understanding of the semantics of the algorithm and hence highly application specific techniques. In this work, we propose traversal splicing, a new, general, automatic locality optimization for irregular tree traversal codes, that is less sensitive to point order, and hence can deliver substantially better performance, even in the absence of semantic information. For six benchmark algorithms, we show that traversal splicing can deliver single-thread speedups of up to 9.147 (geometric mean: 3.095) over baseline implementations, and up to 4.752 (geometric mean: 2.079) over point-blocked implementations. Further, we show that in many cases, automatically applying traversal splicing to a baseline implementation yields performance that is better than carefully hand-optimized implementations.