Polyhedral School

May 13-17, 2013 in Saint Germain au Mont d’Or, near Lyon.

The design of polyhedral code analysis and optimizations constitute a research area by itself, with many applications in particular in the development of compilers for parallel computing. The underlying theory dates back to seminal contributions such as “The Organization of Computations for Uniform Recurrence Equations” by Karp, Miller, and Winograd in 1967, “Dataflow Analysis of Array and Scalar References” by Feautrier in 1991, the work of Quinton, Rajopadhye, Delosme, etc. on the automatic synthesis of systolic arrays from recurrence equations at the end of the 80s and the introduction of the Alpha language, the development of optimizations tools such as PIP (parametric integer programming) in 1988 or Polylib with Chernikova algorithm in 1993. The 1978 seminal paper on abstract interpretation “Automatic Discovery of Linear Restraints Among Variables of a Program” by Cousot and Halbwachs can also be considered as one axis of foundations for polyhedral analysis, even if it gave rise to an initially-disjoint community.

Since then, in the last 20 years, the research community has extended the theory and the polyhedral software tools (with Ehrhart polynomials, an implementation of Barvinok’s algorithm, algorithms for code generation, Omega and ISL libraries, array region analysis, etc.), and has increased the field of applications in a wide range of directions such as:

  • Scheduling theory
    • Automatic vectorization and parallelization of nested loops
    • Loop tiling and tiling models
    • Computability and program termination
  • Data-flow algorithms
    • Array expansion and single assignment
    • Liveness and reuse analysis of array elements
    • Array region analysis and approximations
  • Mapping algorithms
    • Systolic array design
    • Memory mapping with memory reuse (folding)
    • Communication optimizations
  • Counting and Ehrhart polynomials
    • Analysis of cache misses
    • Memory size computations
    • Iteration counting (WCET)
  • Parallelizing compiler developments
    • Hardware synthesis
    • Automatic vectorizers/parallelizers
    • Development of HPC languages
    • Compilation for GPUs

The research community in polyhedral code analysis and optimizations has recently started to meet in a formally-identified way, through the now-annual International Workshop on Polyhedral Compilation Techniques (IMPACT), which was held with  the conferences CGO then HIPEAC, in Chamonix (2011), Paris (2012), and Berlin (2013). The goal of the IMPACT series is to present on-going work. The goal of this polyhedral school is complementary: it is to teach polyhedral techniques and tools to new comers (typically PhD students or researchers interested to bring such techniques to their application field) and to help polyhedral specialists discuss and establish the state-of-the-art of their field.

For all general questions concerning this polyhedral school, please contact Alain Darte at polyhedral-school@ens-lyon.fr.