GATE IT 2006 | Question: 78

Question

A pipelined processor uses a $4-$stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement $X = (S - R * (P + Q))/T$ is given below. The values of variables $P, Q, R, S$ and $T$ are available in the registers $R0, R1, R2, R3$ and $R4$ respectively, before the execution of the instruction sequence.
$$\begin{array}{ll} \text{ADD} & \text{R5, R0, R1} && \text{; R5 ← R0 + R1} \\  \text{MUL} & \text{R6, R2, R5} && \text{; R6 ← R2 * R5} \\   \text{SUB} & \text{R5, R3, R6} && \text{; R5 ← R3 - R6} \\  \text{DIV} & \text{R6, R5, R4} && \text{; R6 ← R5/R4} \\ \text{STORE} & \text{R6, X} && \text{; X  ← R6} \\ \end{array}$$
The number of Read-After-Write (RAW) dependencies, Write-After-Read( WAR) dependencies, and Write-After-Write (WAW) dependencies in the sequence of instructions are, respectively,

• A. $2, 2, 4$
• B. $3, 2, 3$
• C. $4, 2, 2$
• D. $3, 3, 2$

Comments

@Mk Utkarsh @Shaik Masthan 

Need your help.

In this case if we draw a pipeline , then except RAW hazards  , rests are not actually "hazard" , 

for eg : 

In WAR hazard for R5 , 

SUB should write after MUL reads , and that whats actually happening in basic pipeline ( a pipeline which do not have any forwarding or stall involved coz they are solutions to hazards )  and likewise no WAR or WAW will actually be hazard. ( In DLX we actually avoid them and only hazards we face is RAW ) 

 

So its fine to consider all of them as hazards in general as they have data dependency... But in given 4 stage pipeline , WAW and WAR do not cause any problem like RAW.  

So my doubt is then why we are considering them as hazards even though its not a problem in pipeline.

Please help in this.

Reference : https://youtu.be/OweJGixJVtU

(Prof. Bhaskaran Raman : IIT B )

​​​

---

i didn't get what your question is ?

---

@Shaik Masthan 

I edited it. Please read edited part .( two para just above the vid )

---

So my doubt is then why we are considering them as hazards even though its not a problem in pipeline.

those are not hazards in our pipeline model, but those are hazards in some other pipeline model ( which are not in our GATE syllabus ), so simply we categorize those are hazards.

---

@Shaik Masthan 

yes, u got my point . those are hazards from CISC architecture.  But isnt it wrong to mention these hazards even if they are not in our pipeline. 

Coz question asks for such hazards but they dont exist in our pipeline then why we cout them at the 1st place 

( But they dont mentioned hazard, they mentioned to count dependency , so is it the reason  we counting them  irrespective of pipeline model ?) 

So , if we change the pipeline model also then count will still be same as we are just considering deoendepen , then whats the purpose of mentioning pipeline model ? 

( i really doubt this coz without pipeline model, we cant count the number of hazards )

---

But they dont mentioned hazard, they mentioned to count dependency , so is it the reason  we counting them  irrespective of pipeline model ?

may be this is the reason

may this discussion help you https://gateoverflow.in/287165

---

hmm they are wrong here they compute raw hazards here raw dependencies are 6  here

---

as arjun sir comment below

nopes. We have to see what the programmer intended. R5 is written in I1 and I3, but the write in I3 only is meant to be used in I4

they should specify terms like that  because in paper we noone will ever think about programmer intent

 

---

@Shaik Masthan  

yeah..thanx.  SO link was helpful.

 

@Shaik Masthan @Deepanshu 

Say if I1, I2 ,I3 are in order.  I1 writes value of R1 and I2 overwrite value of R1 which is Read by I3.  Here value is modified by I2 hence I1-I3 is not true dependency hence its not a hazard. But is it a dependency at all ?

---

Let's say 3 instructions are there ( I1, I2, I3) and a data Item R1 is used in all instructions then any type of dependency ( RAW, WAR, WAW) if it is b/w I2 and I3 then that particular type of dependency can't be in b/w I1 and I3.

---

No , RAW dependency is b/w consecutive instructions only but WAR and WAW can be between any two instruction of the pipeline.

see the comments and video

https://gateoverflow.in/blog/6661/pipelining

---

@Satbir Checked your link and it supports my comment. and True data dependency also can be in between 2 non-consecutive instructions. It's just when a particular type of dependency is between 2 instruction then it is not considered with previous instructions also.

---

I still have doubt in your comment.

suppose we have

I1 : r6 <- r3 + r2

I2: r3 <- r5 + r6

I3 : r8 <- r4+r6

---

How many true dependencies will be here ?

---

only 1 True dependency b/w I1 and I2 for register R6, not again b/w I1 and I3 for R6 because when we take care for data hazard b/w I1 & I2 then it will be automatically taken care for I1 & I3 also.

---

Yes correct.

---

RAW dependencies are always sequential ??

---

so this means,

I1 : r6 <- r3 + r2

I2: r101 <- r102 + r103

I3: r3 <- r5 + r6

I3 : r8 <- r4+r6

it will also have RAW b/w l1 and l3 ? , just to make sure , " just a check for terminology \"adjacent\"  "

---

sir, I have small doubt about WAW Dependency

what if the last instruction was "LOAD R6,X" instead of "STORE R6,X"

at that time how many WAW Dependencies will occur due To R6? and what are they?

@Arjun @Deepak Poonia @Sachin Mittal 1

---

what if the last instruction was "LOAD R6,X" instead of "STORE R6,X"

at that time how many WAW Dependencies will occur due To R6? and what are they?

@viniit 2 WAW dependencies in that case.

1: $Mul -Div$

2: $Div – Load$

NOTE that $Mul-Load$ would not be a WAW dependency because in between $Div$ is writting into $R_6.$

 

---

understood sir, thank you

Answer 1

(C) is the correct option for this question:

RAW

1. I1 - I2 (R5)
2. I2 - I3 (R6)
3. I3 - I4 (R5)
4. I4 - I5 (R6)

WAR 

1. I2 - I3 (R5)
2. I3 - I4 (R6)

WAW

1. I1 - I3 (R5)
2. I2 - I4 (R6)

Comments

consider, instead of 4 stage , 5 stage pipeline is used then

RAW will be 6,

The 4 which are mentioned and

I1- I4

I2- I5

 

Correct me, if i am wrong

---

Is there any difference between dependency and hazard? If I remember correctly, dependency is what‘s been calculated in this question, but hazards will not be the same. They will be only those dependencies that are actually affecting our pipeline (i.e those dependencies which are causing stalls).

Are my concepts wrong? Can anyone please clarify?

---

Yes you are right

Answer 2

C : as RAW dependency is 4.