Instruction-Level Parallelism and Dependences

A dependence is a relationship between two instructions that constrains the order in which they may correctly execute. Dependences are properties of the program — they exist whether or not the hardware is pipelined, superscalar, or in-order. A hazard is what happens when the hardware's actual execution order threatens to violate a dependence; hazards are properties of the machine and schedule, and they are what stalls, bypassing logic, or renaming must resolve. This distinction — dependence in the program, hazard in the machine — is the single most important conceptual separation in this topic, and it is frequently blurred in casual usage. There are three categories of dependence between two instructions $i$ (earlier) and $j$ (later) that touch a common storage location (register or memory address):

• True (data, RAW — read-after-write): $j$ reads a value that $i$ writes. This reflects genuine data flow: $j$ needs $i$'s result. RAW dependences can never be eliminated — they are the actual computation.
• Anti (WAR — write-after-read): $j$ writes a location that $i$ reads. If $j$'s write happened before $i$'s read, $i$ would read the wrong (new) value. This is not about data flowing from $i$ to $j$; it's a name collision — $i$ and $j$ happen to use the same register or address.
• Output (WAW — write-after-write): both $i$ and $j$ write the same location. If reordered, whichever write actually lands last determines the final value seen by later readers, so the two writes must resolve in program order (or an equivalent state must be maintained).

WAR and WAW are jointly called name dependences: they exist only because a finite set of register names (or memory addresses) gets reused across a program, not because data actually flows between the two instructions. A machine with an unlimited supply of unique register names (register renaming) can eliminate WAR/WAW hazards entirely, because each write could simply get its own fresh name. RAW dependences admit no such trick — the value must exist before it can be consumed. Separately, a control dependence ties an instruction's execution to the outcome of a preceding branch: instruction $j$ is control-dependent on branch $b$ if whether $j$ executes at all depends on $b$'s direction. Control dependences constrain which instructions may be fetched and committed, and they are resolved (or speculated around) by branch prediction rather than by forwarding or renaming.

Detecting and reasoning about dependences is mechanical: scan the instruction stream, and for every pair of instructions that share a register or memory operand, classify the relationship by which one reads and which one writes. The corresponding hazard arises only if the hardware's execution timing would let the later instruction's action (read or write) occur before the earlier one's, in a way that produces a result different from strict program order.

Data hazard resolution in an in-order 5-stage pipeline (IF, ID, EX, MEM, WB) has three canonical hardware responses: 1. Stall — hold the dependent instruction in decode until the value is ready. 2. Forward (bypass) — route the result directly from the producing stage's output to the consuming stage's input, skipping the register file. 3. Reorder / rename (in more aggressive machines) — let independent instructions proceed while the dependent one waits, tracked via renaming tables or scoreboards. The following pseudocode formalizes dependence detection — the first step any scheduler, compiler, or hazard-detection unit performs — followed by a simple greedy list scheduler that shows how detected dependences translate into a lower bound on cycles, foreshadowing what out-of-order hardware does dynamically. ```

# Step 1: Build the dependence graph for a basic block of instructions

# Each instruction has: dest register (or none), list of source registers,

# and (optionally) a memory address class for loads/stores. function BUILD_DEPENDENCE_GRAPH(instructions): n = length(instructions) edges = [] # (i, j, type) meaning instr i must precede instr j for i in 0 .. n-1: for j in i+1 .. n-1: I, J = instructions[i], instructions[j]

# RAW: later instr reads what earlier instr writes if I.dest is not None and I.dest in J.sources: edges.append((i, j, "RAW"))

# WAR: later instr writes what earlier instr reads if J.dest is not None and J.dest in I.sources: edges.append((i, j, "WAR"))

# WAW: both write the same destination if I.dest is not None and J.dest is not None and I.dest == J.dest: edges.append((i, j, "WAW"))

# Memory RAW/WAR/WAW use address analysis (may be conservative,

# i.e., assume dependence unless addresses are provably distinct) return edges

# Step 2: Compute the critical path length — this is the true ILP bound.

# Only RAW edges impose real latency; WAR/WAW just impose an ORDERING

# constraint, not a latency constraint (assuming renaming is available). function CRITICAL_PATH_LENGTH(instructions, edges, latency): n = length(instructions) finish = array of size n, initialized to 0 for i in 0 .. n-1: # process in program order

# (a valid topological order for

# a basic block's RAW edges) ready_time = 0 for (p, q, kind) in edges: if q == i and kind == "RAW": ready_time = max(ready_time, finish[p]) finish[i] = ready_time + latency[instructions[i].op] return max(finish) # length of the longest true-dependence chain

# Step 3 (illustrative): greedy scheduler assigning ops to W parallel

# functional units, respecting RAW order, to show achievable speedup. function GREEDY_SCHEDULE(instructions, edges, W, latency): ready_at = array of size n, filled via CRITICAL_PATH_LENGTH logic cycle = 0 scheduled = set() slot_used = {} # cycle -> count of units busy while length(scheduled) < n: candidates = [i for i in 0..n-1 if i not in scheduled and all RAW-predecessors of i are in scheduled and ready_at[i] <= cycle] issue_count = min(W, length(candidates)) for k in 0 .. issue_count-1: mark candidates[k] as scheduled cycle = cycle + 1 return cycle # total cycles used — compare to n/W (ideal) vs

# critical path length (true lower bound) ``` The key move is in `CRITICAL_PATH_LENGTH`: only RAW edges are used to compute `ready_time`. WAR and WAW edges are ordering constraints that a renaming mechanism can satisfy for free (by giving the writer a new physical register), so they don't lengthen the true data-flow critical path — they only matter for machines without renaming, where they'd force additional stalls or serialization.

Detecting dependences for a basic block of $n$ instructions by pairwise comparison, as in `BUILD_DEPENDENCE_GRAPH`, costs $O(n^2)$ time in the worst case, since every pair of instructions is inspected once. In practice, register dependences can be found in $O(n)$ using a "last writer" and "last readers" table per register (scan once, keep the index of the most recent instruction that wrote or read each register), because a register file has a small, fixed number of names. Memory dependences are harder: determining whether two computed addresses can alias is undecidable in general, so real compilers and hardware use conservative approximations — if it cannot be proven that two addresses differ, a dependence is assumed. This conservatism is correctness-preserving (never misses a real hazard) at the cost of precision (sometimes creates false dependences that block legal reordering).

Computing the critical path length (`CRITICAL_PATH_LENGTH`) is $O(n + e)$ where $e$ is the number of RAW edges, since it's a single dynamic-programming pass over a DAG in topological (here, program) order — each edge relaxes one node's finish time exactly once, identical in structure to longest-path-in-a-DAG. Program order is guaranteed to be a valid topological order for the RAW edges within a basic block, because a RAW edge always points from an earlier instruction to a later one by definition (you cannot read a value before some instruction — including possibly a much later one, which would be illegal — writes it; well-formed single-pass programs only reference prior writes).

Correctness argument for the critical-path lower bound. Let $C$ be the length (in cycles, summing operation latencies) of the longest chain of RAW-dependent instructions in a program. Claim: no machine, however wide or however cleverly it reorders independent work, can finish the program in fewer than $C$ cycles. Proof sketch: each instruction on the critical chain must genuinely wait for its immediate predecessor's result — this is what RAW means — so the finish time of the $k$-th instruction on the chain is at least (finish time of instruction $k{-}1$) + (its own latency). By induction, the last instruction on the chain cannot finish before the sum of all latencies along the chain, i.e., before cycle $C$. Since the program cannot be considered "done" before its last-finishing instruction, total execution time $\geq C$. This holds regardless of issue width, functional-unit count, or scheduling cleverness, because none of those resources can make an instruction execute before the value it needs exists.

Why WAR/WAW don't belong in this bound. A machine with renaming can always give instruction $j$'s write a brand-new physical register distinct from anything instruction $i$ reads or writes, making the WAR/WAW ordering requirement trivially satisfiable with zero added latency — the writes/reads just target different physical storage, and a rename table maps architectural names to the correct physical ones for later readers. This is exactly why the pseudocode excludes WAR/WAW from `ready_time`: they constrain which values end up visible to whom, not how long you must wait for a value to be computed.

Tradeoffs. The bound $C$ is a lower bound, not automatically achievable — an in-order pipeline with no forwarding, for instance, will do far worse than $C$ because of unnecessary stalls, and even an ideal out-of-order machine with infinite resources is bounded below by $C$ but also constrained above by finite issue width, finite renaming resources (reorder buffer size), and branch misprediction penalties from control dependences. Memory disambiguation conservatism can also inflate the effective critical path beyond the true one, since false address dependences serialize instructions that are actually independent.

Consider this instruction sequence (register-register ALU ops, single-cycle latency 1 except MUL/DIV at 3 and load latency 2): ``` I1: LOAD R1, 0(R2) ; R1 = Mem[R2] I2: ADD R3, R1, R4 ; uses R1 I3: MUL R5, R3, R3 ; uses R3 I4: ADD R6, R7, R8 ; independent of R1..R5 I5: SUB R4, R6, R9 ; uses R6 (from I4); ALSO writes R4 (WAR vs I2 which reads R4) I6: ADD R1, R2, R2 ; writes R1 again (WAW vs I1's write target; WAR vs I2's read) ```

Step 1 — classify dependences:

Step 2 — critical path (RAW-only) computation, with latencies LOAD=2, ADD/SUB=1, MUL=3:

Critical path length $C = \max(2, 3, 6, 1, 2, 1) = 6$ cycles — the chain I1→I2→I3 dominates.

Step 3 — what a renaming machine achieves. The WAR edges (I2→I5, I2→I6) and the WAW edge (I1→I6) are all satisfiable by giving I5's and I6's destination registers fresh physical names; they add zero cycles to the true bound. So an ideal machine with enough functional units and a 2-wide issue could, in principle, finish everything in 6 cycles (bounded by the RAW chain), overlapping I4/I5/I6 entirely underneath the I1→I2→I3 chain, e.g.:

Contrast this with a naive in-order machine without renaming, forced to respect WAR by delaying I5's write until after I2's read completes and I6's write until after I1's completion and I2's read: it could add several stall cycles beyond 6, purely from name conflicts that carry no real data — exactly the waste that register renaming exists to eliminate, foreshadowing Out-of-Order Execution.

The formal vocabulary of data, anti-, and output dependences, along with the recognition that name dependences are removable via renaming while true dependences are not, crystallized in the compiler and computer-architecture literature of the 1960s–1980s, as machines began attempting instruction-level overlap beyond simple pipelining.

Every commercial superscalar processor — from ARM's Cortex-X and Apple's Firestorm/Icestorm cores to Intel's and AMD's desktop and server chips — is built around dynamically detecting and resolving exactly the dependences described here. Register renaming hardware (a Tomasulo-style rename table or reorder buffer) exists specifically to convert WAR/WAW name dependences into non-issues, freeing the machine to chase the RAW-bound critical path as aggressively as reorder-buffer size and functional-unit count allow. Compilers performing instruction scheduling, software pipelining, and loop unrolling for VLIW and DSP architectures rely on the same dependence graph to decide legal reorderings statically, since those architectures have no hardware renaming. Vectorizing and auto-parallelizing compilers use memory dependence analysis (alias analysis) to decide whether a loop's iterations are safe to run concurrently — directly building on the RAW/WAR/WAW taxonomy applied to array accesses instead of registers. Understanding these dependence limits is also what justifies why deeper pipelines and wider issue eventually hit diminishing returns without techniques covered next in Superscalar Execution and Out-of-Order Execution.

Ask the tutor: How does register renaming in a Tomasulo-style scheduler concretely map architectural registers to physical ones to eliminate WAR/WAW hazards during execution?