On fusing recursive traversals of K-d trees

Abstract : Loop fusion is a key program transformation for data locality optimization that is implemented in production compilers. But optimizing compilers for imperative languages currently cannot exploit fusion opportunities across a set of recursive tree traversal computations with producer-consumer relationships. In this paper, we develop a compile-time approach to dependence characterization and program transformation to enable fusion across recursively specified traversals over k-d trees. We present the FuseT source-to-source code transformation framework to automatically generate fused composite recursive operators from an input program containing a sequence of primitive recursive operators. We use our framework to implement fused operators for MADNESS, Multiresolution Adaptive Numerical Environment for Scientific Simulation. We show that locality optimization through fusion can offer significant performance improvement.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01335355
Contributor : Fabrice Rastello <>
Submitted on : Tuesday, June 21, 2016 - 9:00:45 PM
Last modification on : Thursday, October 11, 2018 - 8:48:05 AM

Identifiers

  • HAL Id : hal-01335355, version 1

Collections

Citation

Rajbhandari Samyam, Kim Jinsung, Sriram Krishnamoorthy, Louis-Noël Pouchet, Fabrice Rastello, et al.. On fusing recursive traversals of K-d trees. Proceedings of the 25th International Conference on Compiler Construction, CC 2016, Mar 2016, Barcelona, Spain. ⟨hal-01335355⟩

Share

Metrics

Record views

246