Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

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-Sud
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.

Ph.D. dissertations & Faculty habilitations
The original manuscript conceptualizes the recent rise of digital platforms along three main dimensions: their nature of coordination devices fueled by data, the ensuing transformations of labor, and the accompanying promises of societal innovation. The overall ambition is to unpack the coordination role of the platform and where it stands in the horizon of the classical firm – market duality. It is also to precisely understand how it uses data to do so, where it drives labor, and how it accommodates socially innovative projects. I extend this analysis to show continuity between today’s society dominated by platforms and the “organizational society”, claiming that platforms are organized structures that distribute resources, produce asymmetries of wealth and power, and push social innovation to the periphery of the system. I discuss the policy implications of these tendencies and propose avenues for follow-up research.