SIMTree is a C++ source to source transformation framework to facilitate vectorization of tree traversal codes.
SIMTree is introduced in our PACT 2013 paper. It uses point blocking (introduced in our OOPLSA 2011 paper) to create a vectorizable dense loop in tree traversal codes, and traversal splicing (introduced in our OOPSLA 2012 paper) to dynamically group similar traversals together to increase SIMD utilization. It performs a AoS (array of structures) to SoA (structure of arrays) transformation for efficient SIMD execution based on a novel inter-procedural, flow-insensitive, access path analysis.
SIMTree is built on top of the ROSE compiler infrastructure. We provide the source code of SIMTree, and five benchmarks to demonstrate its efficacy. The benchmarks are:
- Barnes-Hut
- Nearest Neighbor
- Point Correlation
- Photon Mapping
- Vantage Point
The Photon Mapping benchmark is adapted from HeatRay, an open source ray tracer/photon mapper with an OpenGL viewer. The Vantage Point benchmark is adapted from an open source implementation. The other benchmarks are adapted from the Lonestar benchmark suite.
If you find this software useful in academic work, please cite the following publications:
- Automatic Vectorization of Tree Traversals
Youngjoon Jo, Michael Goldfarb and Milind Kulkarni
Parallel Architectures and Compilation Techniques (PACT 2013) - 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)
Last updated: June 6, 2013