parallelization Directory Reference

Directories
	analysis
	passes
	transformations

Files
	parallelization.h

Detailed Description

Auto-Parallelization: Reasoning About Independent Iterations

Most loops in real programs are written sequentially — one iteration after another — even when the work of each iteration is completely independent of the others. A modern machine, however, wants the opposite: dozens of CPU cores, or thousands of GPU threads, each running a different iteration at the same time. The job of auto-parallelization is to look at an ordinary sequential loop and decide, safely and automatically, whether its iterations may be run in any order — including all at once.

Consider the simplest possible loop, adding two arrays element-wise:

void add(float* A, float* B, float* C, int N) {
    for (int i = 0; i < N; i++) {
        C[i] = A[i] + B[i];
    }
}

Iteration i reads A[i], B[i] and writes C[i]. Iteration i+1 touches A[i+1], B[i+1], C[i+1] — a completely different set of memory cells. No iteration ever reads a value that another iteration produces, so the iterations do not communicate. We may run them in reverse, shuffled, or all in parallel, and the result is identical. This loop is data-parallel: in this module it is lowered from a sequential For into a Map, the parallel-iteration primitive.

Now change one character:

void prefix(float* A, int N) {
    for (int i = 1; i < N; i++) {
        A[i] = A[i - 1] + A[i];   // reads A[i-1], written by the PREVIOUS iteration
    }
}

Iteration i reads A[i-1] — the exact cell that iteration i-1 just wrote. The iterations are now chained: iteration i cannot start until iteration i-1 has finished. Running them in parallel would let a thread read A[i-1] before it has been updated, producing a wrong (and non-deterministic) answer. This coupling — where an iteration depends on a value produced by an earlier iteration of the same loop — is called a loop-carried dependency, and it is the central obstacle to parallelization. The whole module exists to answer one question precisely: does this loop carry a dependency across its iterations, and if so, of what kind?

What Is a Loop-Carried Dependency?

A dependency between two memory accesses exists when they touch the same memory cell and at least one of them writes. Two reads of the same cell never conflict — reading is order-independent — so a dependency always involves a write.

A dependency is loop-carried when the two conflicting accesses happen in different iterations of the loop. If instead both accesses always happen within the same iteration (C[i] = A[i] + B[i] reads and writes only index i), the dependency is loop-independent and harmless to parallelization: each iteration is self-contained.

Intuition. Draw an arrow from every write to every later access of the same cell. If an arrow ever jumps between iterations of the loop, that loop is carried. If every arrow stays inside a single iteration, the loop is free to run in parallel. Auto-parallelization is the search for those cross-iteration arrows.

Definition (loop-carried dependency). For a loop L with induction variable $i_L$, two accesses $u$ and $v$ to the same container form a loop-carried dependency if there exist iterations $i_L = a$ and $i_L = b$ with $a \neq b$ such that $u$ (in iteration $a$) and $v$ (in iteration $b$) address the same memory cell, and at least one of $u, v$ is a write.

The iteration distance $b - a$ is the dependence distance. In the prefix example, the write A[i] and the read A[i-1] alias when the write's index equals the read's index, i.e. $a = b - 1$, giving distance $1$: iteration $b$ depends on the iteration one step before it. This module represents the full set of such distances symbolically as a delta set (symbolic::maps::DependenceDeltas), computed with the ISL integer-set solver; an empty delta set is the proof that no cross-iteration arrow exists.

The Three Flavors: RAW, WAW, WAR

Since a dependency always involves a write, the two accesses are either (write, read), (write, write), or (read, write). Classic dependence theory names these by the order in which they occur in the original sequential program:

Name	Pattern	Also called	Example (carried)
RAW	write, then a later read	true / flow dependence	A[i] = A[i-1] + x — read A[i-1] after its write
WAW	write, then a later write	output dependence	M[i%2] = f(i) — two iterations write the same slot
WAR	read, then a later write	anti dependence	A[i] = A[i+1] — write A[i+1] after it was read

The crucial distinction for parallelization is true versus false dependencies.

• RAW is a true dependency. A later iteration genuinely consumes a value produced by an earlier one. The data must flow from producer to consumer, so the order is a real constraint that cannot be wished away. A loop-carried RAW is the hazard that blocks parallelization.
• WAW and WAR are false (name) dependencies. No value flows between the iterations; they merely reuse the same storage location. The conflict is about the name of the cell, not about data. Give each iteration its own private copy of that cell (privatization), or a fresh name (renaming), and the conflict disappears — the iterations become independent.

Intuition. Ask: does the second access need the value the first one put there? If yes (RAW), the dependency is real and the loop is sequential in that variable. If the second access is simply going to overwrite (WAW) or stomp on a location that was already read (WAR), then it does not need the old value — it only needs somewhere to write, and giving each iteration its own scratch cell removes the conflict entirely.

A classic example of a removable WAW:

void scale(float* A, float* B, int N) {
    float t;                          // one shared temporary — a false dependency
    for (int i = 0; i < N; i++) {
        t = A[i] * 2.0f;              // every iteration writes t   (WAW across iterations)
        B[i] = t + 1.0f;              // and reads it back in-iteration (loop-independent)
    }
}

Every iteration writes the shared t, so t carries a WAW dependency. But no iteration ever needs the t value from another iteration — the read of t is loop-*independent* (same iteration). Declaring t inside the loop gives each iteration its own copy, and the loop parallelizes. This is why the classifier does not reject a WAW outright: it only requires that the offending container be loop-local (privatizable) storage.

How the Analysis Sees It: LoopCarriedDependencyAnalysis

LoopCarriedDependencyAnalysis (LCDA) computes, for each loop, exactly which containers carry a cross-iteration dependency and of what kind. It does not scan every pair of statements blindly; it rides on top of DataDependencyAnalysis (DDA), which already summarizes each loop by two boundary sets:

• upward-exposed reads $\mathrm{ue}(L)$ — reads inside the loop that consume a value from outside the current iteration (a candidate consumer);
• escaping definitions $\mathrm{esc}(L)$ — writes inside the loop whose value is still live at the iteration boundary (a candidate producer).

A cross-iteration arrow can only run from a producer to a consumer, so LCDA only has to test those two boundary sets against each other:

$$ \begin{aligned} \text{pairs}(L) \;=\; &\, (W, R,\ \textbf{RAW},\ \Delta_L(W,R)) : W \in \mathrm{esc}(L),\ R \in \mathrm{ue}(L),\ \mathrm{cont}(W)=\mathrm{cont}(R),\ \Delta \neq \varnothing \,