Iteration Domains, Access Functions, and Dependencies

To effectively analyze and transform the loop nests common in tensor computations, the polyhedral model employs a precise mathematical framework. This framework relies on three fundamental components: iteration domains to define when computations happen, access functions to define what data is touched, and dependence analysis to understand the constraints on reordering computations.

Iteration Domains: Defining the Execution Space

Each execution of a statement inside a potentially nested loop structure occurs at a specific point defined by the values of the surrounding loop indices. We call such a specific execution a statement instance. The polyhedral model captures the set of all possible integer index vectors for which a statement executes. This set is known as the Iteration Domain.

Formally, for a statement $S$ nested within $d$ loops with index variables $i_1, i_2, \ldots, i_d$, the iteration domain $D_S$ is a set of integer vectors $iter = (i_1, i_2, \ldots, i_d) \in \mathbb{Z}^d$. This set is defined by the loop bounds, which must be expressible as affine inequalities involving the loop indices and potentially symbolic constants (parameters) representing unknown problem sizes (like matrix dimensions).

An iteration domain $D_S$ can be represented as:

$$D_S = \{ iter \in \mathbb{Z}^d \mid A \cdot iter + b \ge 0 \}$$

Here, $A$ is an integer matrix and $b$ is an integer vector representing the constraints derived from the loop bounds. The inequality is element-wise. Any set of integers definable by such linear inequalities forms an integer polyhedron.

Example: Matrix Multiplication

For example, the core computation in matrix multiplication $C = A \times B$:

// Assuming C is initialized to zero
for (int i = 0; i < M; ++i) {      // Loop index i
  for (int j = 0; j < N; ++j) {    // Loop index j
    for (int k = 0; k < P; ++k) {  // Loop index k
      // Statement S1:
      C[i][j] = C[i][j] + A[i][k] * B[k][j];
    }
  }
}

The statement $S_1$ is nested within three loops. An instance of $S_1$ is identified by the vector $iter = (i, j, k)$. The iteration domain $D_{S1}$ is the set of all valid $(i, j, k)$ tuples defined by the loop bounds:

$$D_{S1} = \{ (i, j, k) \in \mathbb{Z}^3 \mid 0 \le i < M, 0 \le j < N, 0 \le k < P \}$$

This can be written using affine inequalities: $i \ge 0$ $-i + (M-1) \ge 0$ (equivalent to $i \le M-1$, or $i < M$) $j \ge 0$ $-j + (N-1) \ge 0$ $k \ge 0$ $-k + (P-1) \ge 0$

This forms a bounded integer polyhedron (a rectangular prism) in the 3D iteration space $(i, j, k)$. $M, N, P$ are symbolic parameters.

Access Functions: Mapping Iterations to Data

Within each iteration $iter \in D_S$, the statement $S$ typically reads from or writes to memory locations, often elements of arrays (tensors). An Access Function describes which memory location is accessed by a particular statement instance.

The polyhedral model requires these access functions to be affine functions of the iteration vector $iter$. For an array access like Array[index_expr_1]...[index_expr_n], the function maps the iteration vector $iter$ to the array index vector $(index\_expr\_1, \ldots, index\_expr\_n)$. This mapping must take the form:

$$F(iter) = M \cdot iter + c$$

where $M$ is an integer matrix and $c$ is an integer vector.

Example: Matrix Multiplication Accesses

Continuing with the matrix multiplication example, statement $S_1$ involves four accesses: a read and write to C, a read from A, and a read from B. Let the iteration vector be $iter = (i, j, k)$.

1. Write to C[i][j]: The accessed index is $(i, j)$. The access function $F_{C, write}$ maps $(i, j, k)$ to $(i, j)$.

   $$F_{C, write}(i, j, k) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} i \\ j \\ k \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} i \\ j \end{pmatrix}$$

   This is affine.

2. Read from C[i][j]: The accessed index is $(i, j)$. The access function $F_{C, read}$ is identical to $F_{C, write}$.

   $$F_{C, read}(i, j, k) = \begin{pmatrix} i \\ j \end{pmatrix}$$

3. Read from A[i][k]: The accessed index is $(i, k)$. The access function $F_{A, read}$ maps $(i, j, k)$ to $(i, k)$.

   $$F_{A, read}(i, j, k) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} i \\ j \\ k \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} i \\ k \end{pmatrix}$$

   This is affine.

4. Read from B[k][j]: The accessed index is $(k, j)$. The access function $F_{B, read}$ maps $(i, j, k)$ to $(k, j)$.

   $$F_{B, read}(i, j, k) = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} i \\ j \\ k \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} k \\ j \end{pmatrix}$$

   This is also affine.

Since all iteration domains are defined by affine inequalities and all access functions are affine, the loop nest is suitable for analysis within the polyhedral model.

Data Dependencies: Understanding Execution Constraints

Optimizations like changing loop order, tiling, or parallelization are only valid if they preserve the program's semantics. This requires understanding the data dependencies between different statement instances. A data dependence exists between two statement instances if they access the same memory location and at least one of the accesses is a write.

The standard types of data dependencies are:

1. Flow (True) Dependence (Read-After-Write, RAW): Statement instance $S_1(iter_1)$ writes to a location that is later read by $S_2(iter_2)$. This dictates that $S_1(iter_1)$ must execute before $S_2(iter_2)$.
2. Anti Dependence (Write-After-Read, WAR): $S_1(iter_1)$ reads from a location that is later overwritten by $S_2(iter_2)$. $S_1(iter_1)$ must still execute before $S_2(iter_2)$ to read the original value.
3. Output Dependence (Write-After-Write, WAW): $S_1(iter_1)$ writes to a location that is later overwritten by $S_2(iter_2)$. The order matters for the final value stored. $S_1(iter_1)$ must execute before $S_2(iter_2)$.
4. Input Dependence (Read-After-Read, RAR): $S_1(iter_1)$ reads from a location that is later read by $S_2(iter_2)$. This doesn't impose an ordering constraint for correctness, but it can be relevant for locality optimizations.

To formally identify dependencies using the polyhedral framework, we look for pairs of iterations $(iter_1, iter_2)$ such that:

• $iter_1 \in D_{S1}$ and $iter_2 \in D_{S2}$ (Both instances are valid execution points).
• $iter_1$ executes before $iter_2$. In the original code, this is determined by the lexicographical order of the iteration vectors. We denote this as $iter_1 \prec iter_2$.
• They access the same memory location: $F_{S1, mem}(iter_1) = F_{S2, mem}(iter_2)$, where $F_{S1, mem}$ and $F_{S2, mem}$ are the access functions for the relevant memory reference in $S_1$ and $S_2$, respectively.
• At least one of the accesses ($S_1(iter_1)$ or $S_2(iter_2)$) is a write operation.

The set of all pairs $(iter_1, iter_2)$ satisfying these conditions for a specific type of dependence (e.g., flow) defines the dependence relation. This relation itself can often be represented as another polyhedron.

Example: Dependence in a Simple Loop

Here's this loop:

for (int i = 1; i < N; ++i) {
  A[i] = A[i-1] + B[i]; // Statement S
}

• Iteration Domain: $D_S = \{ i \in \mathbb{Z} \mid 1 \le i < N \}$
• Access Functions (for array A):
  • Write to A[i]: $F_{write}(i) = i$
  • Read from A[i-1]: $F_{read}(i) = i - 1$

Let's find flow dependencies (Write then Read). We need $iter_1 = i_1$ and $iter_2 = i_2$ such that:

1. $i_1 \in D_S$, $i_2 \in D_S$
2. $i_1 \prec i_2$ (which means $i_1 < i_2$ since it's a single loop)
3. The write access at $i_1$ corresponds to the read access at $i_2$: $F_{write}(i_1) = F_{read}(i_2)$ $$i_1 = i_2 - 1$$

Combining these conditions: $1 \le i_1 < N$, $1 \le i_2 < N$, $i_1 < i_2$, and $i_1 = i_2 - 1$. This simplifies to: for any $i_2$ such that $2 \le i_2 < N$, there is a flow dependence from iteration $i_1 = i_2 - 1$. The dependence exists from iteration $i$ to iteration $i+1$ for all $i$ from $1$ to $N-2$. The dependence vector is $d = iter_2 - iter_1 = i_2 - i_1 = 1$. This indicates that iteration $i+1$ depends on the result computed in iteration $i$.

Flow dependencies in the example loop. Each iteration $i$ writes to A[i], which is read by the next iteration $i+1$. The dependence vector is constant, $d=(1)$.

Dependence Analysis in Matrix Multiplication

Applying this to the matrix multiplication example for the accesses to C[i][j]:

• $S_1(i, j, k)$ writes to $C[i][j]$.
• $S_1(i, j, k+1)$ reads from $C[i][j]$ (for $k < P-1$). This is a flow dependence: $iter_1 = (i, j, k)$, $iter_2 = (i, j, k+1)$. $iter_1 \prec iter_2$. Access functions $F_C(iter_1) = F_C(iter_2) = (i, j)$. The dependence vector is $d = iter_2 - iter_1 = (0, 0, 1)$. This dependence is carried by the innermost loop $k$.
• Similarly, $S_1(i, j, k)$ writes to $C[i][j]$ and $S_1(i, j, k+1)$ also writes to $C[i][j]$. This is an output dependence, also with dependence vector $d=(0, 0, 1)$.

These dependencies tell us that, for a given $(i, j)$, the iterations of the $k$ loop cannot be arbitrarily reordered or fully parallelized without mechanisms like reductions, because each iteration depends on the previous one's partial sum stored in $C[i][j]$. However, iterations with different $(i, j)$ values are independent concerning the $C$ array accesses.

By precisely defining iteration domains, access functions, and the resulting data dependencies, the polyhedral model provides the foundation needed to mathematically reason about loop nests and derive complex, correctness-preserving transformations for performance optimization. The next step involves using this dependence information to construct valid schedules that map iterations to execution time steps, enabling optimizations like tiling and parallelization.