Data Dependency
A data dependency is a relationship between operations that forces one to execute after the other. Dependencies prevent parallelization: computation XY gives a different result from YX. Covered in ECE459 L13.
Why care?
Dependencies set a hard lower bound on runtime (the critical path) no matter how many cores you throw at the problem.
Real-life analogies from the lecture:
- extract the bicycle before closing the garage door
- close the washing-machine door before starting the cycle
- students submit an assignment before it can be marked
Violating the order either gives the wrong result or nothing at all. L13 also assumes no data races throughout; undefined behaviour breaks the reasoning.
Loop-carried dependencies
An iteration depends on the previous one:
for i in 1 .. vec.len() {
vec[i] = vec[i-1] + 1;
}Unrolling shows vec[2] = vec[1] + 1 depends on vec[1] = vec[0] + 1. No out-of-order execution is safe.
A more realistic example is the Mandelbrot iteration (x, y) → (x² − y² + x₀, 2xy + y₀). Each step depends on the previous (x, y). You can’t parallelize the inner loop, but you can compute many starting points in parallel (an “embarrassingly parallel” outer problem).
Stride matters. With vec[i] = vec[i-4] + 1 starting at i = 4, there’s no dependency between adjacent elements, so four iterations can run in parallel.
Memory-carried dependencies
Two functions touching the same memory where order changes the result:
f(&mut acct); // a.balance += 50.0
g(&mut acct); // a.balance *= 1.01Running f then g ≠ running g then f.
RAW / WAR / WAW (from ILP courses)
Bernstein’s three classic kinds of dependency:
- RAW (read-after-write, true / flow):
b = a + 1; c = b * 2;(fundamental) - WAR (write-after-read, anti):
b = a + 1; a = 7;(false, cured by renaming) - WAW (write-after-write, output):
a = 1; a = 2;(also cured by renaming)
Register renaming (hardware) and SSA (compilers) remove WAR/WAW by giving each write its own name. Only RAW is fundamental.