Data Dependency Analysis

Read-After-Write(RAW)

Need to compute X = a + b before c = X + d.
A.K.A True/Flow Dependency
- This is the ONLY true data dependency
Notation: $S_1 \delta^{t} S_2$
- LHS is denoted as source and RHS as sink
- Source must always go before sink in program order

What happens if we execute S2 before S1?
- Assuming that prior to S1, X takes on value X1.
- If S2 goes first, a will be given the value c + d + b rather than X1 + b
A.K.A Anti-Dependency
Notation: $S_1 \delta^{a} S_2$

What happens if we execute S2 before S1?
- After program terminates, X takes on value a + b rather than c + d, resulting in an inconsistent machine state.
A.K.A Output Dependency
Notation: $S_1 \delta^{o} S_2$

WAR & WAW are NOT true data dependency.
- Despite they also limit the amount of parallelism of our program
- But do we really need to execute them in sequence?
  - NO! Compared with true dependency in which data values are NOT ready, in WAR & WAW, the values are ready, but definitions have name collision.
  - Hence, they are also called name dependency
Solution? Register Renaming
- Idea: Out-Of-Order Execution, In-Order Commit

What happens if we execute S2 before S1?
- Nothing happens
- So why do we care about RAR dependency?
  - Data Locality
  - We are reading same variable, change the order would provide incorrect locality information
A.K.A Input Dependency
Notation: $S_1 \delta^{i} S_2$

We categorize loop dependencies in two major classes:
- Loop-Independent Dependency
  - Dependency relationship within the same loop iteration
- Loop-Carried Dependency
  - Dependency relationship across different loop iterations
    Loop-Carried Dependency
Unroll the loop
Observation: The value written in iteration i always read in iteration i + 1.
- Iteration 0: read index a[0] write to a[1]
- Iteration 1: read index a[1] write to a[2]
Notation: $S \delta^{t}_{1} S$. The extra subscript denotes the dependence distance. It shows that the source is always 1 iteration ahead of sink.

$S \delta^{t}_{-1} S$?
- Incorrect! Because dependence distance is always non-negative, as having a negative distance is equivalent of saying that source goes after sink in program order
$S \delta^{a}_{a} S$
- It is an anti-dependence rather than a true dependence

Any dependency?
- No. Since the write index (odd) is always different from the read index(even). Hence, there is no dependency within and across loop iterations

Data Dependency: $S \delta^{t}_{1, -1} S$
- The value written in iteration (i, j) is always read in iteration (i + 1, j - 1)
The order of dependence distance ONLY relates to the loop nest order and has nothing to do with the array indexing order
- What this means is that the dependence vector remains the same even if the body statement is a[j][i] = a[j+1][i-1] + 1
Wait, didn’t we just say that the dependence distance must be non-negative?
- Observation: Iteration (i, j) always goes before (i + 1, j - 1)
- If there is loop-carried dependence, then the dependence distance must be ~~positive~~ lexicographically positive