Brief Announcement: Locality-enhancing Transformations for Tree Traversal Algorithms

Youngjoon Jo and Milind Kulkarni

SPAA 2011 · Symposium on Parallelism in Algorithms and Architectures · June 2011 · pp. 263-264

Superseded by OOPSLA 2011

Abstract

In this paper, we discuss transformations that can be applied to irregular programs that perform tree traversals, which can be seen as analogs of the popular regular transformations of loop tiling. We demonstrate the utility of these transformations on two tree traversal algorithms, the Barnes-Hut algorithm and raytracing, achieving speedups of up to 237% over the baseline implementation.

BibTeX

@inproceedings{jo11spaa,
  author    = {Youngjoon Jo and Milind Kulkarni},
  title     = {Brief Announcement: Locality-enhancing Transformations for Tree Traversal Algorithms},
  booktitle = {Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  pages     = {263--264},
  publisher = {ACM},
  address   = {San Jose, California, USA},
  year      = {2011},
  month     = jun,
  doi       = {10.1145/1989493.1989534}
}

Group members