Aim of the tutorial

Loop transformation frameworks such as the polyhedral model enable expressing complex loop nests and composing transformations on such loop nests. The transformations enable parallelism and improve data locality by modifying the schedule of the loop and in some cases transformations are applied to the underlying data as well. The limit that such transformation frameworks are only applicable when loop bounds and memory accesses are affine is starting to be overcome with transformation frameworks that cater to various forms of irregular computations. The general concepts of modeling the set of computation with an iteration space, modeling how “iterations” access data, and then providing transformation specifications that can be checked for correctness are similar. What is new is how information that is not known until runtime is represented and transformed at compile time.

This tutorial will review the concept of representing computations as sets and loop transformations being applied to those set. There will then be three different perspectives for representing and transforming sparse computations, based on three recent lines of work: the Sparse Polyhedral Framework, which builds inspector-executor frameworks for handling sparse computations through runtime scheduling; decomposing sparse irregular computations into sets of regular computations to enable compile-time transformation; and the PolyRec framework, which handles certain recursive irregular computations at compile time through new representations of iterations and transformations. We will provide high level overviews of at least two frameworks and provide examples of the uses of each, including discussions of when each framework might be applicable.

Outline

1. Introduction to concepts for analyzing and transforming affine programs, and discussion of limitations
2. Introduction to Sparse Polyhedral framework, discussion of applicability, and examples
3. Introduction to PolyRec, discussion of applicability, and examples

Prerequisite knowledge

Basic familiarity with loop transformations, though we will start with an introduction to the overall topic.