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:

Last updated: June 6, 2013