Parallelization

Data Dependence

We define four types of data dependence

Flow (true) dependence: A statement $S_i$ precedes a statement $S_j$ in execution and $\bf S_i$ computes a data value that $\bf S_j$ uses
- Implies that $S_i$ must execute before $S_j$
- Notion: $S_i \delta^{t} S_j$
  - $S_1 \delta^{t} S_2$
  - $S_2 \delta^{t} S_4$
Anti dependence: A statement $S_i$ precedes a statement $S_j$ in execution and $\bf S_i$ uses a data value that $\bf S_j$ computes
- Implies that $S_i$ must execute before $S_j$
- Notion: $S_i \delta^{a} S_j$
  - $S_2 \delta^{a} S_3$
Output dependence: A statement $S_i$ precedes a statement $S_j$ in execution and $\bf S_i$ computes a data value that $\bf S_j$ computes
- Notion: $S_i \delta^{o} S_j$
  - $S_1 \delta^{o} S_3$
  - $S_3 \delta^{o} S_4$
Input dependence: A statement $S_i$ precedes a statement $S_j$ in execution and $\bf S_i$ uses a data value that $\bf S_j$ uses
- Notion: $S_i \delta^{i} S_j$
  - $S_3 \delta^{i} S_4$
The dependence is said to flow from $S_i$ to $S_j$ because $S_i$ precedes $S_j$ in execution.
$S_i$ is said to be the source of the dependence. $S_j$ is said to be the sink of the dependence.
The only true dependence is flow dependence; it represents the flow of data in the program
The other types of dependence are caused by programming style; They may be eliminated by re-naming

Data dependence in a program may be represented using a dependence graph G = (V, E), where the nodes V represent statements in the program, and the directed edges E represent dependence relations.

There is an instance of $S_1$ that precedes an instance $S_2$ in execution and $S_1$ produces data that $S_2$ consumes
$S_1$ is the source of the dependence; $S_2$ is the sink of the dependence
The dependence flows between instances of statements in the same iteration (loop-independent dependence)
The number of iterations between source and sink (dependence distance) is 0. The dependence direction is =
- $S_1 \delta^{t}_{=} S_2$ or
- $S_1 \delta^{t}_{0} S_2$

There is an instance of $S_1$ that precedes an instance $S_2$ in execution and $S_1$ produces data that $S_2$ consumes
$S_1$ is the source of the dependence; $S_2$ is the sink of the dependence
The dependence flows between instances of statements in different iterations (loop-carried dependence)
The dependence distance is 1. The direction is position (<)
- $S_1 \delta^{t}_{<} S_2$ or
- $S_1 \delta^{t}_{1} S_2$

There is an instance of $S_2$ that precedes an instance of $S_1$ in execution and $S_2$ consumes data that $S_1$ produces
$S_2$ is the source of the dependence; $S_1$ is the sink of th dependence
The dependence is loop-carried
The dependence distance is 1.
- $S_2 \delta^{a}_{<} S_1$ or
- $S_2 \delta^{a}_{1} S_1$

An instance of S precedes another instance of S and S produces data the S consumes.
S is both source and sink
The dependence is loop-carried
The dependence distance is (1, -1)
- $S \delta^{t}_{(<, >)} S$ or
- $S \delta^{t}_{(1, -1)} S$

Dependence will exist if there exists two iteration vectors $\vec{k}$ and $\vec{j}$ such that $\vec{L} \leq \vec{k} \leq \vec{j} \leq \vec{U}$ and:
That is:
Dependence testing is equivalent to an integer linear programming of 2d variables & m + d constraints
An algorithm that determines if there exists two iteration vectors $\vec{k}$ and $\vec{j}$ that satisfies these constraints is called a dependence tester
The dependence distance vector is given by $\vec{j} - \vec{k}$
The dependence direction vector is given by sign($\vec{j} - \vec{k}$)
Dependence testing is NPC
A dependence test that reports dependence only when there is dependence is said to be exact. Otherwise, it is in-exact
A dependence test mus tbe conservative; if the existence of dependence cannot be ascertained, dependence must be assumed.

Does there exist two iteration vectors $i_1$ and $i_2$, such that $2 \leq i_1 \leq i_2 \leq 4$ and such that $\bf i_1 = i_2 - 1$?
- $i_1 = 2, i_2 = 3$
- $i_1 = 3, i_2 = 4$
Hence, there is dependence
The dependence distance vector is $i_2 - i_1 = 1$
The dependence direction vector is sign(1) = <

Does there exist two iteration vectors $i_1$ and $i_2$, such that $2 \leq i_1 \leq i_2 \leq 4$ and such that $\bf i_1 = i_2 + 1$?
- $i_1 = 3, i_2 = 2$
- $i_1 = 4, i_2 = 3$
Hence, there is dependence
The dependence distance vector is $i_2 - i_1 = -1$
The dependence direction vector is sign(-1) = >

Does there exist two iteration vectors $i_1$ and $i_2$, such that $1 \leq i_1 \leq i_2 \leq 10$ and such that $\bf 2 * i_1 = 2 * i_2 + 1$?
No, since left is always even and right is always odd
Hence, there is no dependence

Given the following equation:
- $\sum_{i=1}^{n} a_ix_i = c$ $a_i$ and c are integers
- an integer solution exists iff:
  - gcd($\bf a_1, a_2, …, a_n$) divides c
Problems:
- Ignores loop bounds
- Gives no information on distance or direction of dependence
- Often gcd is 1 which always divides c, resulting in false dependence
Example:
- Does there exist two iteration vectors $i_1$ and $i_2$ such that $1 \leq i_1 \leq i_2 \leq 10$ and such that:
  - $2 * i_1 = 2 * i_2 -1$? or
  - $2 * i_2 - 2 * i_1 = 1$
- There will be an integer solution iff gcd(2, -2) divides1
- This is not the case, and hence, there is no dependence!
Example2:
- Does there exist two iteration vectors $i_1$ and $i_2$ such that $1 \leq i_1 \leq i_2 \leq 10$ and such that:
  - $i_1 = i_2 - 100$? or
  - $i_2 - i_1 = 100$
- There will be an integer solution iff gcd(1, -1) divides 100
- This is the case, and hence, there is dependence
  - BUT Look on the loop boundaries, there is only 10 iterations which cannot lead to dependence

A dependence is said to be carried by a loop if the loop is the outmost loop whose removal eliminates the dependence. If a dependence is not carried by the loop, it is loop-independent

outermost loop with a non “=” direction carries dependence
The iterations of a loop may be executed in parallel with one another if and only if no dependencies are carried by the loop
Example1:
- Iteration of loop j must be executed sequentially, but the iteration of loop i may be executed in parallel
- Outer loop parallelism
Example2:
- Iteration of loop i must be executed sequentially, but the iteration of loop j may be executed in parallel
- Inner loop parallelism

Loop Interchange changes the order of the loops to improve the spatial locality of a program