How many RAW dependencies are present in these instructions?

Question

What is the number of RAW dependencies in below set of instructions?

I1: R1 = R2 - R3
I2: R2 = R1 + R3
I3: R3 = R1 + R2
I4: R1 = R2 - R2

I can see the following RAW dependencies in it:

$I_2-I_1\ for\ R_1$ ......... (a)

$I_3-I_1\ for\ R_1$ ......... (b)

$I_3-I_2\ for\ R_2$ ......... (c)

$I_4-I_2\ for\ R_2$ ......... (d)

I think taking (a) and (b) implies that (c) has already been included. So, should this be counted as 4 RAW dependencies or 3 RAW dependencies?

https://en.wikipedia.org/wiki/Hazard_(computer_architecture)#Read_after_write_(RAW)

Answer 1

TL;DR: According to a 5-stage pipeline scenario, there are just two true RAW hazards:

1. I2 to I1 for R1 
2. I3 to I2 for R2

---

Explanation

The answer might depend on the pipeline stages. For the sake of this question, let's consider a basic 5-stage pipeline: Instruction Fetch (IF), Decode (DE), Execute (EX), Memory Op (MEM) and Writeback (WB).

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8   
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- 
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1                    
  I2: R2 = R1 + R3        IF   DE    EX2   MEM   WB2              
  I3: R3 = R1 + R2             IF    DE    EX3   MEM   WB3        
  I4: R1 = R2 - R2                   IF    DE    EX4   MEM   WB4  

At first, it may seem like there are many RAW dependencies in this instruction sequence but let's analyze how the pipeline behaves with this sequence. The above table might indicate the following:

1. EX2 depends on WB1 (WB1->EX2)
2. EX3 depends on WB1 (WB1->EX3)
3. EX3 depends on WB2 (WB2->EX3)
4. EX4 depends on WB2 (WB2->EX4)

After the first stall in the pipeline by EX2, the scenario changes a bit. WB1->EX2 (1) was a true dependency. But, WB1->EX3 (2) is no more a dependency:

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10  
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- ----- 
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1                                
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2              
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   MEM   WB3        
  I4: R1 = R2 - R2                   IF    IF    IF    DE    EX4   MEM   WB4  

After the second stall in the pipeline by EX3 (3) (which truly waits for WB2), the scenario changes again. Clearly, WB2->EX4 (4) is revealed to be no more a dependency.

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10   C11   C12  
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1                                            
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2                          
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   EX3   EX3   MEM   WB3        
  I4: R1 = R2 - R2                   IF    IF    IF    DE    DE    DE    EX4   MEM   WB4  

Therefore from our original list above, only following true RAW hazards are revealed:

1. EX2 depends on WB1 (WB1->EX2)
2. EX3 depends on WB2 (WB2->EX3)