Advanced Compilers: Loop Transformations and High-Level Synthesis

Tomofumi Yuki (CR Inria, contact person) and Christophe Alias (CR Inria).
(possibly with the help of Alain Darte)

Prerequisites

Overview

The main topic of this course is to understand high-level (loop-level) transformations employed by "optimizing" compilers and the techniques used in these compilers to reason about such optimizations. The two key performance principles in optimizing compilers are parallelism and data locality, and compilers must reason at the level of loop nests to identify and to fully exploit opportunities for improvement. These principles are applicable to most architecture in use today, general purpose CPUs, GPUs, distributed memory computing, and even to FPGAs/hardware with the increasing maturity of High-Level Synthesis tools.

In this course, we will cover various techniques and frameworks for reasoning about programs, with emphasis on the polyhedral model, which is one of the most successful formalism for automatic parallelization today. We will also interact with a number of research tools that implement the techniques covered in the course.

Course Outline

Part I. Loop Transformations (8 lectures)

  1. Introduction
  2. Dependence Analysis
  3. Transformations
  4. Scheduling
  5. Loop Tiling
  6. Code Generation
  7. Beyond Loop Transformations
  8. Memory + Power

Part II. Application to High-Level Synthesis (4 lectures)

  1. Execution Models (KPN, CRP, PPN, ...)
  2. Control & Data-path Synthesis
  3. Internal Communications
  4. External Communications

Evaluation

Homework/presentation of a research paper.

References