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

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-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
APPRENTISSAGE ET OPTIMISATION SUR LES GRAPHES


ANALYSE DE DONNéES MULTI-MODALES POUR LES PATHOLOGIES COMPLEXES PAR LA CONCEPTION ET L’IMPLéMENTATION DE PROTOCOLES REPRODUCTIBLES ET RéUTILISABLES


DESIGNING INTERACTIVE TOOLS FOR CREATORS AND CREATIVE WORK
Creative work has been at the core of research in Human-Computer Interaction (HCI). I describe the results of a series of studies that look at how creators work, where creators include artists with years of professional practice, as well as learners, or novices and casual makers. My research focuses on three creation activities: drawing, physical modeling, and music composition. For these activities, I examine how artists switch between representations and how these representations evolve throughout their creative process, from early sketches to fine-grained forms or structured vocabularies. I present interactive systems that enrich their workflow (i) by extending their computer tools with physical user interfaces, or (ii) by making physical materials interactive. I also argue that sketch-based representations can allow for user interfaces that are more personal and less rigid. My presentation will reflect on lessons and limitations of this work and discuss challenges for future design-support tools.