Name
Title | ||
|---|---|---|
Simplification and runtime resolution of data dependence constraints for loop transformations. |
Abstract | ||
|---|---|---|
Loop transformations such as tiling, parallelization or vectorization are essential tools in the quest for high-performance program execution. Precise data dependence analysis is required to determine whether the compiler can apply a transformation or not. In particular, current static analyses typically fail to provide precise enough dependence information when the code contains indirect memory accesses or polynomial subscript functions to index arrays. This leads to considering superfluous may-dependences between instructions that prevent many loop transformations to be applied. In this work we present a new hybrid (static/dynamic) framework that allows to overcome several limitations of purely static dependence analyses: For a given loop transformation, we statically generate a test to be evaluated at runtime. This test allows to determine whether the transformation is valid, and if so triggers the execution of the transformed code, falling back to the original code otherwise. Such test, originally constructed as a loop-based code with O(n2) iterations (n being the number of iterations of the original loop-nest), 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3079079.3079098 | ICS |
Field | DocType | Citations |
Loop fusion,Loop nest optimization,Loop dependence analysis,Computer science,Loop fission,Parallel computing,Loop optimization,Algorithm,Loop inversion,Loop tiling,Loop unrolling | Conference | 1 |
PageRank | References | Authors |
0.35 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Diogo Sampaio | 1 | 48 | 3.84 |
| Louis-noël Pouchet | 2 | 880 | 47.61 |
| Fabrice Rastello | 3 | 482 | 38.30 |