Detecting Data Dependencies in Pipelines

Identify Read-After-Write, Write-After-Read, and Write-After-Write dependencies that occur between instructions executing in overlapping stages.

In this lesson, you will learn how to identify the three primary types of data dependencies that create hazards in a pipelined processor.

Understanding Data Dependencies

In a single-cycle processor, an instruction completes entirely before the next begins. In a pipeline, instructions overlap. Because they overlap, a later instruction might try to use a piece of data before a previous instruction has finished "creating" it. We call this a data dependency.

There are three main types, named by the order in which they access a register or memory location:

1. Read-After-Write (RAW) - The "True" Dependency

This is the most common hazard. It occurs when Instruction B needs to read a register that Instruction A is still calculating.

Example:
```
ADD R1, R2, R3  ; R1 = R2 + R3
SUB R4, R1, R5  ; R4 = R1 - R5
```
The SUB instruction cannot finish its calculation until the ADD instruction writes the result into R1. If SUB hits the register file before ADD finishes its write-back stage, SUB will use "stale" (old) data.

2. Write-After-Read (WAR) - The "Anti-Dependency"

This occurs when Instruction B tries to write to a register before Instruction A has finished reading it.

Example:
```
ADD R4, R1, R5  ; Needs to read R1
SUB R1, R2, R3  ; Wants to write new value to R1
```
In a simple in-order pipeline, this is rarely an issue because instructions read early and write late. However, if the pipeline reorders execution, you must ensure ADD reads the old R1 before SUB overwrites it.

3. Write-After-Write (WAW) - The "Output Dependency"

This happens when both instructions write to the same register, and we must ensure the final value in the register is from the correct instruction.

Example:
```
ADD R1, R2, R3
SUB R1, R4, R5
```
If ADD finishes after SUB, the register file will end up with the ADD result instead of the SUB result, causing a logic error.

Key Takeaway: Data dependencies arise when instructions share registers; RAW hazards are the most frequent, occurring when a subsequent instruction depends on the result of a preceding one currently moving through the pipeline.