# Polyhedral Compilation

## Foundations of Polyhedral Compilation

### 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.

## Historical Papers

### The Parallel Execution of DO Loops.

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

## Footnotes:

1

Prof. Pouchet is an expert in Polyhedral Compilation.

Email: expye@outlook.com

Date: 2020-09-01