Brief Announcement: Locality-enhancing Transformations for Tree Traversal Algorithms
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}
}