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:

poly-constaints.png

The polytope dimension refers to the number of surrounding loops.

Dual view

poly-dual-view.png

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.

    polyhedral_0.png

    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:

    pfor-idx.png

    where CONC FOR means each instance is assigned to a processor (like omp parallel in OpenMP).

  • TODO General Methods

Coordinate Method

Algorithms

Pluto algorithm

Feautrier algorithm

Scheduling algorithm in ISL

Footnotes:

1

Prof. Pouchet is an expert in Polyhedral Compilation.

Author: expye(Zihao Ye)

Email: expye@outlook.com

Date: 2020-09-01

Last modified: 2021-02-19 Fri 21:14

Licensed under CC BY-NC 4.0