HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

A polyhedral compilation framework for loops with dynamic data-dependent bounds

Jie Zhao 1 Michael Kruse 1 Albert Cohen 1
1 Parkas - Parallélisme de Kahn Synchrone
Inria de Paris, DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique
Abstract : We study the parallelizing compilation and loop nest optimization of an important class of programs where counted loops have a dynamic data-dependent upper bound. Such loops are amenable to a wider set of transformations than general while loops with inductively defined termination conditions: for example, the substitution of closed forms for induction variables remains applicable, removing the loop-carried data dependences induced by termination conditions. We propose an automatic compilation approach to parallelize and optimize dynamic counted loops. Our approach relies on affine relations only, as implemented in state-of-the-art polyhedral libraries. Revisiting a state-of-the-art framework to parallelize arbitrary while loops, we introduce additional control dependences on data-dependent predicates. Our method goes beyond the state of the art in fully automating the process, specializing the code generation algorithm to the case of dynamic counted loops and avoiding the introduction of spurious loop-carried dependences. We conduct experiments on representative irregular computations, from dynamic programming, computer vision and finite element methods to sparse matrix linear algebra. We validate that the method is applicable to general affine transformations for locality optimization, vectorization and parallelization.
Document type :
Conference papers
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

Contributor : Jie Zhao Connect in order to contact the contributor
Submitted on : Monday, June 11, 2018 - 10:21:16 PM
Last modification on : Thursday, March 17, 2022 - 10:08:53 AM
Long-term archiving on: : Wednesday, September 12, 2018 - 11:36:48 PM


Explicit agreement for this submission




Jie Zhao, Michael Kruse, Albert Cohen. A polyhedral compilation framework for loops with dynamic data-dependent bounds. CC'18 - 27th International Conference on Compiler Construction, Feb 2018, Vienna, Austria. ⟨10.1145/3178372.3179509⟩. ⟨hal-01720368⟩



Record views


Files downloads