Polyhedral Compilation
Table of Contents
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.
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 FORmeans each instance is assigned to a processor (likeomp parallelin 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:
Prof. Pouchet is an expert in Polyhedral Compilation.