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.
Type de document :
Communication dans un congrès
Proceedings of the 25th International Conference on Compiler Construction, CC 2016, Mar 2016, Barcelona, Spain
Liste complète des métadonnées

https://hal.inria.fr/hal-01335355
Contributeur : Fabrice Rastello <>
Soumis le : mardi 21 juin 2016 - 21:00:45
Dernière modification le : jeudi 11 janvier 2018 - 06:27:21

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

160