Enhancing locality for recursive traversals of recursive structures
Enhancing locality for recursive traversals of recursive structures
复制标题
增强递归结构的递归遍历的局部性
DOI：
10.1145/2048066.2048104
复制
发表时间：
2011
影响因子：
2.9
通讯作者：
Milind Kulkarni
中科院分区：
文献类型：
--
作者：
Youngjoon Jo;Milind Kulkarni
虽然已经有几十年的工作来为在密集矩阵和数组上操作的常规程序开发自动的、局部性增强的转换，但对于在基于指针的数据结构(如图、树和列表)上操作的不规则程序的这种转换几乎没有研究。在这篇文章中，我们认为，对于一类称为遍历码的不规则应用程序，存在大量的数据重用，因此存在局部性开发的机会。受经典的平铺循环变换的启发，我们提出了一种称为点分块的优化方法，并证明了它可以显著提高遍历码的时间局部性。然后，我们提出了一个名为TreeTeller的转换和优化框架，该框架自动检测应用点阻塞的机会并应用转换。TreeTeller使用自动调优技术来确定转换的适当参数。对于从真实应用程序中提取的一系列遍历算法，我们表明TreeTeller能够提供比优化(但未转换)并行基准高达245%的性能改进，在某些情况下，可伸缩性明显更好。
While there has been decades of work on developing automatic, locality-enhancing transformations for regular programs that operate over dense matrices and arrays, there has been little investigation of such transformations for irregular programs, which operate over pointer-based data structures such as graphs, trees and lists. In this paper, we argue that, for a class of irregular applications we call traversal codes, there exists substantial data reuse and hence opportunity for locality exploitation. We develop a novel optimization called point blocking, inspired by the classic tiling loop transformation, and show that it can substantially enhance temporal locality in traversal codes. We then present a transformation and optimization framework called TreeTiler that automatically detects opportunities for applying point blocking and applies the transformation. TreeTiler uses autotuning techniques to determine appropriate parameters for the transformation. For a series of traversal algorithms drawn from real-world applications, we show that TreeTiler is able to deliver performance improvements of up to 245% over an optimized (but non-transformed) parallel baseline, and in several cases, significantly better scalability.