Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata
Contributor : Fabrice Rastello Connect in order to contact the contributor
Submitted on : Tuesday, June 21, 2016 - 9:00:45 PM
Last modification on : Friday, November 18, 2022 - 9:26:49 AM


  • HAL Id : hal-01335355, version 1


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⟩



Record views