Consider this code fragment: (1) x = a + b; (2) y = x * 2; (3) x = c - d. What type of dependence exists between instruction (2) and instruction (3)?
ATrue dependence: instruction (3) reads a value written by instruction (2)
BAnti-dependence (write-after-read): instruction (2) reads x before instruction (3) writes x
COutput dependence (write-after-write): both instructions write to the same variable
DNo dependence: instructions (2) and (3) use different variables
Instruction (2) reads x (written by instruction (1)), and instruction (3) later writes to x. This is an anti-dependence (write-after-read): if we reordered and put instruction (3) before instruction (2), then (2) would read the new value of x (c − d) instead of the intended value (a + b), producing a wrong result. Anti-dependencies arise from name reuse — x is being used for two different purposes. They can be eliminated by renaming: if instruction (3) wrote to a new variable x2 instead, the dependence disappears entirely.
Question 2 Multiple Choice
A compiler wants to parallelize the loop: for (i=0; i<n; i++) { a[i] = a[i-1] + 1; }. Which statement is correct?
AThe loop can be fully parallelized because each iteration writes to a different array element
BThe loop has a loop-carried true dependence: iteration i reads a[i-1] which was written by iteration i-1
CThe loop has only an anti-dependence, which can be eliminated by renaming
DThe loop can be parallelized after applying register renaming to the array accesses
Each iteration i reads a[i-1], which was written by the previous iteration (i-1). This is a loop-carried *true dependence* (read-after-write across iterations): iteration i genuinely needs the result of iteration i-1 to compute its own value. Unlike name dependencies, this cannot be eliminated by renaming — the data flow is real. The iterations must execute sequentially in order. In contrast, a loop like `a[i] = b[i] + 1` has no loop-carried dependencies and can be parallelized freely.
Question 3 True / False
Anti-dependencies (write-after-read) and output dependencies (write-after-write) can potentially be eliminated by renaming variables or registers, whereas true dependencies (read-after-write) cannot.
TTrue
FFalse
Answer: True
Anti and output dependencies are 'name dependencies' — they arise because the same variable name or storage location is reused for different values, not because one instruction genuinely needs data produced by another. By introducing new names (SSA form in compilers, register renaming in hardware), each write targets a distinct location and the false dependence disappears. True dependencies cannot be eliminated by renaming because they represent actual data flow: instruction B genuinely requires the value computed by instruction A.
Question 4 True / False
A true dependence between two instructions is a conservative approximation: the compiler may identify a true dependence even when the instructions could safely be reordered.
TTrue
FFalse
Answer: False
True dependencies (read-after-write) represent genuine data flow constraints that cannot be removed. If instruction B reads a value that instruction A wrote, then A must complete before B reads — reordering would give B a wrong value. This is not a conservative approximation; it is an exact constraint. Conservative approximations arise in alias and pointer analysis, where the compiler may be uncertain whether two memory accesses refer to the same location. But a confirmed true dependence is a hard constraint, not an approximation.
Question 5 Short Answer
Explain why anti-dependencies and output dependencies are called 'name dependencies,' and describe one technique compilers use to eliminate them.
Think about your answer, then reveal below.
Model answer: Anti-dependencies and output dependencies arise not from genuine data flow but from the reuse of a single variable name or storage location for different values. An anti-dependence occurs when one instruction reads a variable and a later instruction writes to it — the ordering constraint exists only because both instructions refer to the same name, not because the second instruction needs the first's result. An output dependence similarly arises when two instructions write to the same location. If each write were directed to a distinct location, both dependencies would vanish. Compilers eliminate name dependencies by transforming the program into Static Single Assignment (SSA) form, where each variable is defined exactly once — every write introduces a fresh name, so no two writes share a target.
This insight is also the basis of hardware register renaming, which allows out-of-order processors to exploit instruction-level parallelism by dynamically mapping architectural registers to a larger physical register file, eliminating false dependencies that would otherwise force sequential execution.