Ph.D
Group : Parallel Architecture
Sub-Polyhedral Compilation using (Unit-)Two-Variables-Per-Inequality Polyhedra
Starts on 01/01/2009
Advisor : COHEN, Albert
Funding : A
Affiliation : Université Paris-Saclay
Laboratory : INRIA Alchemy & LRI Archi
Defended on 13/03/2013, committee :
Cédric Bastoul, Assistant Professor, Université Paris-Sud, Examinateur
Albert Cohen, Directeur de recherche, INRIA, École Normale Supérieure,
Directeur de Thèse
François Irigoin, Professeur, MINES ParisTech, Fontainebleau, Rapporteur
Christian Lengauer, Professor, University of Passau, Germany, Rapporteur
Antoine Miné, Chargé de Recherche, CNRS, École Normale Supérieure, Examinateur
Florent Hivert, Professor, Université Paris-Sud, Examinateur
Sanjay Rajopadhye, Associate Professor, Colorado State University,
USA, Examinateur
Research activities :
Abstract :
The goal of this thesis is to design algorithms that run with low
complexity when compiling or parallelizing loop programs. The
framework within which our algorithms operate is the polyhedral model
of compilation which has been successful in the design and
implementation of complex loop nest optimizers and parallelizing
compilers. The algorithmic complexity and scalability limitations of
the above framework remain one important weakness. We address it by
introducing sub-polyhedral compilation by using
(Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra, namely
polyhedra with restricted constraints of the type ax_{i}+bx_{j}le c
(pm x_{i}pm x_{j}le c).
A major focus of our sub-polyhedral compilation is the introduction of
sub-polyhedral scheduling, where we propose a technique for scheduling
using (U)TVPI polyhedra. As part of this, we introduce algorithms that
can be used to construct under-aproximations of the systems of
constraints resulting from affine scheduling problems. This technique
relies on simple polynomial time algorithms to under-approximate a
general polyhedron into (U)TVPI polyhedra. The above
under-approximation algorithms are generic enough that they can be
used for many kinds of loop parallelization scheduling problems,
reducing each of their complexities to asymptotically polynomial time.
We also introduce sub-polyhedral code-generation where we propose
algorithms to use the improved complexities of (U)TVPI sub-polyhedra
in polyhedral code generation. In this problem, we show that the
exponential complexities associated with the widely used polyhedral
code generators could be reduced to polynomial time using the improved
complexities of (U)TVPI sub-polyhedra.
The above presented sub-polyhedral scheduling techniques are evaluated
in an experimental framework. For this, we modify the state-of-the-art
PLuTo compiler which can parallelize for multi-core architectures
using permutation and tiling transformations. We show that using our
scheduling technique, for a majority of the Polybench (2.0) kernels,
the above under-approximations yield polyhedra that are non-empty.
Solving the under-approximated system leads to asymptotic gains in
complexity, and shows practically significant improvements when
compared to a traditional LP solver. We also verify that code
generated by our sub-polyhedral parallelization prototype matches the
performance of PLuTo-optimized code when the under-approximation
preserves feasibility.
