TreeSplicer is a Java source to source transformation framework to enhance temporal locality for repeated tree traversals.
It utilizes two novel concepts:
- Point blocking, introduced in our OOPSLA 2011 paper.
- Traversal splicing, introduced in our OOPSLA 2012 paper.
TreeSplicer is a transformation framework, which can automatically apply point blocking, traversal splicing or both combined, and use autotuning techniques to choose good transformation parameters (e.g., block size, splice depth). It can automatically transform tree traversal programs to deliver speedups of up to 9x, just from better locality!
TreeSplicer was built on top of JastAdd. We provide our customized JastAdd grammar files, and JastAdd generated AST files which implement TreeSplicer. The JastAdd framework itself is available from the JastAdd site. We provide 5 benchmarks to demonstrate the efficacy of TreeSplicer. The benchmarks are:
- Barnes-Hut
- Point Correlation
- Nearest Neighbor
- k-Nearest Neighbor
- Ball Tree
The ball tree benchmark is adapted from the WEKA data mining software, and the other benchmarks are adapted from the Lonestar benchmark suite.
If you find this software useful in academic work, please cite the following publications:
- Automatically Enhancing Locality for Tree Traversals with Traversal Splicing
Youngjoon Jo and Milind Kulkarni
Object-Oriented Programming, Systems, Languages & Applications (OOPSLA 2012) - Enhancing Locality for Recursive Traversals of Recursive Structures
Youngjoon Jo and Milind Kulkarni
Object-Oriented Programming, Systems, Languages & Applications (OOPSLA 2011) - Lonestar: A Suite of Parallel Irregular Programs
Milind Kulkarni, Martin Burtscher, Keshav Pingali and Calin Cascaval
International Symposium on Performance Analysis of Systems and Software (ISPASS 2009)
Last updated: June 12, 2013