Polyhedral Compilation without Polyhedra
Polyhedral compilation is widely used in high-level synthesis tools and
in production compilers such as gcc, LLVM and IBM/XL and is still being
actively developed by several research groups across the globe,
resulting in highly attended IMPACT workshops and a recent polyhedral school.
It is based on the
polyhedral model, a powerful abstraction for analyzing and transforming
(parts of) programs that are "sufficiently regular".
The key feature of this model is that it is instance based,
allowing for a representation and treatment of individual dynamic
executions of a statement inside a loop nest and/or individual array elements.
The name of the model derives from the mathematical objects called polyhedra
that are used internally to describe these instances.
These polyhedra are often represented using matrices, giving the impression
to outsiders that the polyhedral model is difficult to use.
In this tutorial, we follow the tradition of the Omega Project and
use a slightly higher-level representation based on integer tuples
bounded by quasi-affine constraints, which we call named Presburger sets.
In particular, we will address
the following topics:
An earlier version of part of this tutorial was presented as the first half
lecture at the polyhedral school,
but a lot of extra material was added, mainly about dependence
and dataflow analysis.
- How to model various aspects of a piece of code
using Presburger sets and relations.
- Which basic operations are available on such sets and relations,
without going into details on how these operations are implemented.
- How to use these operations to mainly analyze but also
- Which tools are available for polyhedral compilation.
- A small selection of some of the results that may
be achieved through polyhedral compilation.
and select the tutorial.
The tutorial will take place in room G109
(and not in room E001 as previously announced).
Preparing for the tutorial
The tutorial will include a (small) number of hands-on exercises
You may want to install the barvinok package on your laptop
beforehand using the following instructions.
(More detailed instructions are available in the README
of the barvinok package.)
sudo apt-get install libgmp3-dev libntl-dev rlwrap # On Ubuntu
tar xf barvinok-0.37.tar.bz2
make -j 4
rlwrap ./iscc # or just ./iscc if you don't have rlwrap
Alternatively, you can use the
Sven Verdoolaege is a senior researcher at INRIA (France). In general,
his main research interests are in Polyhedral Compilation. He earned
his master degrees in Computer Science (1998) and Artificial Intelligence
(1999) as well as his PhD on polyhedral loop transformations and counting
integer points in polyhedra in Computer Science (2005) from the Katholieke
Universiteit Leuven (Belgium). He continued his research on integer
point counting, contributing to primal and weighted counting algorithms.
As a postdoc, he successively investigated polyhedral process networks,
including non-affine extensions, at Leiden University (Netherlands)
and equivalence verification at KU Leuven (Belgium). From 2010, he
has been conducting research in the group of Albert Cohen at INRIA and
ENS (France) on topics such as transitive closures and parallelization
for GPUs. His research has culminated in various widely used software
packages such as
an integer set and polyhedral compilation library;
a library for (weighted) counting of integer sets;
a polyhedral parser; and
PPCG, a polyhedral parallelizer.
Tobias is a postdoctoral researcher at ETH Zürich interested in program
optimization for parallel architectures. He received his Diploma from the
University of Passau (Germany), where he started his work on automatic program
transformations using polyhedral modeling. Working in an ENS/INRIA research lab
(France) with Albert Cohen and Sven Verdoolaege he received his PhD from
Universite Pierre et Marie Curie for work on the efficient execution of stencil
computations and the development of new integer set based code generation
For his PhD Tobias has been awarded a prestigious 3-year Google European
Doctoral Fellowship. He has been interning at ARM, AMD and Google and spent six
month as a research scholar at Ohio State University. As an active contributer
to LLVM and gcc, he leads the development of the Polly loop optimization
infrastructure, mentors PhD and Master students in the context of Google Summer
of code projects and regularly participates to the organization of the yearly
European LLVM conference.