# Polyhedral Compilation

## Table of Contents

## Foundations of Polyhedral Compilation

- link: https://www.cs.colostate.edu/~pouchet/
^{1}

### Three stage process of polyhedral compilation

- Analysis: from code to model
- Transformation in the model
- Code generation: from mode to code

### Motivation example

for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) A[i][j] = i * j;

In the above example, a same statement is execute 9 times with different \(i,j\) associated with each instance, and there is an execution order on them.

How do you define a representation that modeled the 3 characteristics?

- instance graph: 1 node per instance, edges reflect dependency (ordering).
- …

### Issues

Some problems we face for modeling 1 statement:

- Memory consumption
- Conditions
- Loop bound
- Non-unit strides
- …

### Polyhedral model

- Iteration domain: set of ordered n-dim vectors.
- iteration vector: \(\vec{x}_S=(i,j)\)
- iteration domain: the set of values of \(\vec{x}_S\)

- Polytopes model sets of totally ordered n-dim vectors.
- Condition: the set must be convex.

#### Convexity

**Theorem** : statement surrounded by loops with unit-stride, no conditional and
simple loop bounds has a convex iteration domain.

#### Some definitions

**Affine Functions**: A function \(f\) is affine if there exists a \(A\) and \(b\) such that

\[ \forall \vec{x} \in \mathbb{K}^m, f(\vec{x}) = A\vec{x} + \vec{b} \]

**Affine half-space**: An affine space is defined as the sets of points

\[ \{ \vec{x} \in \mathbb{K}^{m} | \vec{a}\vec{x} \leq \vec{b} \}\]

**Polyhedron**: intersection of finitely many half-spaces:

\[ \mathcal{P} = \{\vec{x} \in \mathbb{K}^m | A\vec{x} \leq \vec{b}\} \]

**Polytope**: a bounded polyhedron.

**Integer Polyhedron**: a polyhedron whose extreme points are integer valued.

**Integer Hull**: the integer hall of \(\mathcal{P}\) refers to the largest set of integer
points so that all of them are in \(\mathcal{P}\) .

#### Modeling loop with polyhedron

for loop \(0\leq i \leq 2, 0 \leq j \leq 2\), we can formulate the constraint as follows:

The polytope dimension refers to the number of surrounding loops.

### Dual view

## Historical Papers

### The Organization of Computations for Uniform Recurrence Equations.

### The Parallel Execution of DO Loops.

Link: https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Parallel-Execution-of-DO-Loops.pdf

The paper describes Lamport's early attempts in parallelizing for-loops.

#### Hyperplane Method

- Example

Considering the following loop.

The loop body is executed for each point \((I,J,K)\) in the index set $S =\{(i,j,k) : 1 ≤ i ≤ L, 2 ≤ j ≤ M, 2 ≤ k ≤ N\} $ .

The proposed approach is to concurrently execute \((I,J,K)\) in \(S\) along a plane: for the above example, all points \((I,J,K)\) lying in \(2I + J + K = constant\) can be executed concurrently.

We increment the constant by one at a time until the loop body has been executed for all points in \(S\) .

Then we can choose a set of new index \((\bar{I}, \bar{J], \bar{K})\) and rewrite the program as:

where

`CONC FOR`

means each instance is assigned to a processor (like`omp parallel`

in OpenMP). - TODO General Methods

#### Coordinate Method

## Algorithms

### Pluto algorithm

- zhihu link(chinese): https://zhuanlan.zhihu.com/p/199683290

### Feautrier algorithm

- zhihu link(chinese): https://zhuanlan.zhihu.com/p/232070003

### Scheduling algorithm in ISL

- zhihu link(chinese): https://zhuanlan.zhihu.com/p/259311866

## Footnotes:

^{1}

Prof. Pouchet is an expert in Polyhedral Compilation.