Improved Loop Tiling based on the Removal of Spurious False Dependences

Riyadh Baghdadi 1 Albert Cohen 1 Sven Verdoolaege 1 Konrad Trifunović 1, 2
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : To preserve the validity of loop nest transformations and parallelization, data-dependences need to be analyzed. Memory dependences come in two varieties: true dependences or false dependences. While true dependences must be satisfied in order to preserve the correct order of computations, false dependences are induced by the reuse of a single memory location to store multiple values. False dependences reduce the degrees of freedom for loop transformations. In particular, loop tiling is severely limited in the presence of these dependences. While array expansion removes all false dependences, the overhead on memory and the detrimental impact on register-level reuse can be catastrophic. We propose and evaluate a compilation technique to safely ignore a large number of false dependences in order to enable loop nest tiling in the polyhedral model. It is based on the precise characterization of interferences between live range intervals, and it does not incur any scalar or array expansion. Our algorithms have been implemented in the Pluto polyhedral compiler, and evaluated on the PolyBench suite.
Type de document :
Article dans une revue
ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2013, 9 (4), <10.1145/2400682.2400711>
Liste complète des métadonnées

https://hal.inria.fr/hal-00786674
Contributeur : Albert Cohen <>
Soumis le : dimanche 10 février 2013 - 01:10:40
Dernière modification le : mardi 13 décembre 2016 - 15:40:46

Identifiants

Collections

Citation

Riyadh Baghdadi, Albert Cohen, Sven Verdoolaege, Konrad Trifunović. Improved Loop Tiling based on the Removal of Spurious False Dependences. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2013, 9 (4), <10.1145/2400682.2400711>. <hal-00786674>

Partager

Métriques

Consultations de la notice

432