Dependency VS Hazard

Question

Consider following program is executed on a 5 stage RISC pipeline and stages are IF, ID, EX, MA, WB.

IF = Instruction Fetch

ID = Instruction Decode and fetch register

EX  = Execution Stage

MA = Memory Access

WB = Write back register file

Program:-

I1) ADD R0, R1 R2

I2) ADD R3, R0 R4

I3) ADD R10, R0 R5

I4) ADD R11, R0 R6

I5) ADD R12, R0 R7

I6) ADD R13, R0 R8

I7) ADD R14, R0 R9

Calculate the number of RAW dependency and Hazards.(There is no Structural Dependency)

My Answers -> Dependencies = 6, hazards = 3.

Someone verify these answer.

Comments

correct..

---

Thanks !!!!

---

@joshi_nitish So, Every RAW, WAR, WAW hazards question should also contain information about stages.then only it is possible to get the exact solution. ryt??

---

yes, hazard can be found only by drawing pipeling diagram..

---

For RAW hazards we can know through the pipeline diagram but for WAR and WAW hazards which occur out of order so this information needs to be mentioned whether instruction reordering is allowed or not..

For finding dependencies we can simply do so by using Bernstein's conditions..

---

How hazards are calculated?

and what if pipeline info not given for dependency calculation. Does it matters?

---

Can someone please explain how we got 3 RAW hazards ??

---

Prateek if u draw it's cycle state diagram, then in that I1 will execute from C1 TO C5.

Now I2 is dependent on I1, I2 enter into the pipeline at C2 because we are not using Operator Forwarding so I2 must wait for I1 to produce result r0 and I1 will complete in C5 and from C3 to C5 i2 have to remain in IF stage and this cause hazards or stalls. Thus we have 3 hazards.

---

@  Shubhanshu thank you so much sir for nicely explanation .if we use operand forwarding ,then i think zero RAW hazards we will get .right ??

---

Yeah. From Ex to ID.

---

@Prateek Raghuvanshi @Shubhanshu 

There are stalls in $I2$ because we are waiting for $I1$ to writeback then only $I2$ can start execute phase.

But we can do $execute(I1)$ and $decode(I2)$ in same clock cycle(c3)?

---

we cannot ex(I1) and decode(I2) in cycle 3.

---

@ayush.5 why not?

we can do operand forwarding from EX(I1) to EX(I2). Right?

 

---

We cannot use operand forwarding here because it isn't mentioned. Anyway, if we use it then no. of hazards will be zero.

---

Hazards means no. of stalls ??

---

please tell the number of RAW dependencies in above?

---

SUB R1,R2,R3;

ADD R2,R1,R3;

ADD R3,R1,R2;

SUB R1,R2,R2;

number of raw dependencies here?

---

@harshit, 4 raw dependencies

---

@ayush ,but made easy has given the ans 2

---

They have counted dependencies between adjacent instructions only. It is a misconception that dependency is only between adjacent instructions. Dont trust test series answer. Go through best answer and the comments under it :- https://gateoverflow.in/29896/number-of-war-dependencies

---

Okk @ayush, and what about number of raw hazards??

---

@harshit, in your example:-

1)If we use operand forwarding then no. of RAW hazards will be zero.

2)Without operand forwarding, you will need to draw pipeline diagram:-

  F  D  E  M  W

      F   –   –  D  E  M  W

           F   –  –   –   –  D   E  M  W

                F  –   –   –  –    D  E  M  W

No. of hazards=10

Note: I have overlapped W and D stage. But it can also be the case that you put decode stage of I2 in the next cycle after W stage of I1. In this case hazards will be 12. But you should always overlap unless told in question that you have to non-overlap. Go through this link :- https://gateoverflow.in/1391/gate2005-68?show=95441

---

@ayush, so for hazards we need to draw the diagram

---

yep!

---

@ayush.5 link given by you.. best answer say 9 , arjun sir answer say 11... I also think arjun sir answer is correct.. and yes ME test COA is kind of worst.. instructor have also some of the concepts wrong about cache.

Answer 1

Is it right please verify it

Comments

@Ram Swaroop How can you say that I1 and I3 have RAW dependency? I mean we go for immediate next instruction. There is only one RAW dependency. 

---

dependency doesn't need to be consecutive you can see here : question 3

https://cseweb.ucsd.edu/classes/wi12/cse141-a/solutions/assignment5-soln.pdf

---

@Ram Swaroop @sachin486

why are we not using "split phase" concept for Instruction2 at cycle 5?

---

yeah, there will be 2 hazard and by default split phase should be used