Simplification and Run-time Resolution of Data Dependence Constraints for Loop Transformations

Abstract : Loop transformations such as tiling, parallelization or vector-ization are essential tools in the quest for high-performance program execution. But precise data dependence analysis is required to determine the validity of a loop transformation, and whether the compiler can apply it or not. In particular , current static analyses typically fail to provide precise enough dependence information when the code contains indirect memory accesses or even polynomial subscript functions to index arrays. This leads to considering superfluous may-dependences between instructions, in turn preventing many loop transformations to be applied. In this work we present a new framework to overcome several limitations of static dependence analyses, to enable aggressive loop transformations on programs with may-dependences. We statically generate a test to be evaluated at runtime which uses data dependence information to determine whether a program transformation is valid, and if so triggers the execution of the transformed code, falling back to the original code otherwise. These tests, originally constructed as a loop-based code with O(n 2d) iterations (d being the maximal loop depth of the program, n being the loop trip count), are reduced to a loop-free test of O(1) complexity thanks to a new quantifier elimination scheme that we introduce in this paper. The precision and low overhead of our method is demonstrated over 25 kernels containing may-alias memory pointers and polynomial memory access subscripts.
Type de document :
Communication dans un congrès
ICS 2017 - International Conference on Supercomputing, Jun 2017, Chicago, United States. pp.1-11, 〈10.1145/3079079.3079098〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01653819
Contributeur : Fabrice Rastello <>
Soumis le : mardi 5 décembre 2017 - 19:43:22
Dernière modification le : jeudi 11 janvier 2018 - 06:27:21

Fichier

Identifiants

Collections

Citation

Diogo Sampaio, Louis-Noël Pouchet, Fabrice Rastello. Simplification and Run-time Resolution of Data Dependence Constraints for Loop Transformations. ICS 2017 - International Conference on Supercomputing, Jun 2017, Chicago, United States. pp.1-11, 〈10.1145/3079079.3079098〉. 〈hal-01653819〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

6