Simplification and Run-time Resolution of Data Dependence Constraints for Loop Transformations - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (2) , (1)
1
2

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.
Fichier principal
Vignette du fichier
ics17.pdf (840.46 Ko) Télécharger le fichier

Dates and versions

hal-01653819 , version 1 (05-12-2017)

Identifiers

Cite

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⟩
488 View
231 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More