The Gateway to Computer Science Excellence
+15 votes
3.2k views

no of RAW,WAR and WAW ?

in CO and Architecture by Veteran (57.2k points)
retagged by | 3.2k views
0
RAW- 5, WAW-1,WAR-2?
0
please explain in answer/comment
0
RAW:
I1-I2
I1-I4
I2-I3
I2-I4
I4-I5
WAW
I2-I4
WAR-
I3-I4,I2-I4
0
please explain 2-3 and 4-5 RAW
0
respected people can you please explain what is RAW WAW and War
i am not able to understand Read After write,write after read and write after write hazard can you please explain in simple words?
0
I3 instruction is reading the value written by I2. I3 is depending on I2 for ACC (I3 is reading after I2 has written it)
same with I4-I5
I5 is depending on I4 for ACC
0
@anusha i think  I1-I4 and I2-I4 are not RAW hazard ??
0
respected please i beg you please sir and madam  i touch your feets please tell me what is WAW ,WAR RAW,
0
@saurabh why?
0
@anusha  there is RAW dependency for I1-I4 and I2-I4  but not Hazard due to processor organization ...
In simple words suppose 2 raw dependent instruction are very far 2 each other
I1:
:
:
:
:
:
I2 like this
0
thanks @anusha, I got confused in:out register comparison :)

anyway 2-5 also RAW
0
solution given as 6 - 1- 2
0
@debashish ll u plzz explain how I2 -I5 is a RAW hazard ??

nd what is source of question ??
0

yr made easy !!

is it wrong according to you ?

+2
@debashish.. i have little doubt with I2-I5. please see this
there is dependency between I2 and I4 which means I4 will execute after I2. now I4 is overwriting value written by I2. I5 has problem only with this updated value i.e I4. i think I2-I4 and I4-I5 are dependencies and I2-I5 is not RAW.
0
That what u showing is RAW dependency ...
can u plzz explain  this Hazard via pipeline if ??
0
i think it is true  I2-I5 is not RAW.
0
@anusha is there RAW hazard  I1-I4 how ??
+1
I understand @saurav and @anusha regarding recent dependency. Yes what you have said is true.

(just forwarding my idea)  $I_5$ not supposed to read before any of $I_2$ and $I_4$. If it does it creates in consistency.

But in the other way (going by your point) even if $I_2$ finishes first $I_5$ can not read Acc untill $I_4$ writes Acc. So, it seems, we should not say RAW between $I_2$  and $I_5$
0
@Debashish, saurabh.

Its same concept as conflict serializability. Same procedure as we do for drawing the graph is followed hre. The reasonn is the sequnce of actual execution may be changed for some reasons (e.g optimization).
0
ok. your answer ? (no_of RAW,no_of WAR,no_of WAW)
0
Its same but I have justified at the bottom of Habib's answer.
0
very interesting question !
0
how to  upload any image here ???
0
@arjun sir pls tell me answer RAW=6, WAW=1, WAR=6  is correct or not
which is explained in answer...?
0
Correct according to me.

2 Answers

+18 votes
Best answer

In this question , it is necessary to mind the keyword :

No of possible RAW , WAR  and WAW hazards..

Now the word "possible" is used because the WAR and WAW hazards do not occur always ; they are possible if out of order execution..In normal flow of execution of instructions , WAR and WAW hazards never occur  ..Only what can occur in inorder execution which is normal execution is RAW hazard..

So to find each of these hazards , we define 2 things here :

a) Read set of an instruction (denoted by R(I)) : 

This set of each instruction contains all the operands which are read in an instruction..For example in the 2nd instruction of the given question , we have read set : {R0 , ACC}

b) Write set of an instruction (denoted by R(I)) : 

This set of each instruction contains the operand to which write has been performed in an instruction..For example in the 2nd instruction of the given question , we have read set : {ACC}

So let us find the read and write set of each instruction first :

Instruction                   Read set (R(Ii))                 Write set (W(Ii))

I1                                 {R0}                               {R0}

I2                                 {ACC,R0}                       {ACC}

I3                                 {ACC}                            {R1}

I4                                 {ACC,R0}                       {ACC}

I5                                 {ACC}                            {Mem}

Now having mentioned that , now let us write the Bernstein's conditions which says :

A potential hazard exists between instruction i and a subsequent instruction j when at least one of the following conditions fails  :

For RAW  :   W(i)  ∩  R(j)  =   Φ

For WAR :    R(i)   ∩  W(j) =   Φ 

For WAW :    W(i)   ∩  W(j) =   Φ 

So considering the above mentioned points , we now find number of each type of possible hazards :

A) RAW :

The hazards of this type will be :

a)  I1  -   I2    b)   I1 -  I4  

c)  I2 - I3       d)   I2 -  I5

e)  I2 - I4       f)    I4 - I5

B) WAR :

a)   I4 - I2

e)   I4 - I3     

C) WAW :

a)  I4 - I2

Hence ,

Number of RAW hazard   =   6

Number of WAR hazard   =   2

Number of WAW hazard   =  1

by Veteran (102k points)
selected by
0
Yes, it is.
0
Till now , in entire subjects that I have studied , I have found this problem the most debatable and conjectural one..:)
0
Sir, for all the gate questions, they just ask hazards and nothing about pipeline is given, i.e how is it working or out of order instructions, etc. So, for all of them, do we need to assume dependencies and hazards the same thing, otherwise its a one way ?
0
The question that came in 2006 - IT 78 was using the word "dependency" but they have given the options in light of the "hazards"..

That is why I referred this problem as "conjectural" one..
+1
Yes. Suppose there is a RAW dependency between $I_1$ and $I_{10}$. This is not a hazard if the pipeline stages are less than 10. But can still be a hazard if we consider out of order execution. For problems unless clearly stated or hinted otherwise, you can take them both same.
0
That is why I meant to say in my answer..Should I formalise my answer more so that it can be more useful??
+2
@Arjun Sir, Can you please generalize all these details as an answer ? It will make the concepts crystal clear.
0
Yes that would be good. But regarding "WAR", we need not consider this separately for out of order execution - even if they are executed out of order, the original "RAW" dependence will take care of them. So, we just need to consider them in the "sequence" of instructions given.
0
Sir can u plz elaborate this point..I m not able to get it..
+4

B) WAR :

a)  I2 - I1      b)   I3 - I2

c)  I4 - I1      d)   I4 - I2

e)  I5 - I2      f)    I5 - I4

Here, we need to consider only I3->I4, and I2-> I4

That is the source instruction (R) should happen before the (W). And this is with respect to the original order of instructions. We do not need to consider the dependence after instructions are reordered -- as that is why we first the dependence in the first place; meaning dependence and hazards are always with respect to the original sequence of instructions (not after they are reordered).

+1
@arjun Sir , like @kapil said could u pls generalise all the points from discussion  as answer ? It would be really helpful .
+1

Data hazards occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen by sequentially executing instructions on the unpipelined machine.

https://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/dataHaz.html

We can't change the execution of the statements. The hazards arises because the way we have developed the pipleine. So I think your assumption for the out of order execution is wrong. Plus  this is also wrong

the WAR and WAW hazards do not occur always ; they are possible if out of order execution.

Assume a Load followed by an airthmatic operation. 

LW R1, 0(R2) IF ID EX MEM1 MEM2 WB
ADD R1, R2, R3   IF ID EX WB  

Isn't It right. ?

+1
^The example you gave is not valid. In I2, WB wont be executed until WB of preious instruction is completed- this has nothing to do with dependency- because otherwise pipeline design would be really complex.
0
Sir , I am not saying this the PDF link I have posted have the example. So sir is PDF wrong ?
Sir can you plz post a clarified answer for the same. There is a bit of confussion in this.
+1
If dependencies are asked then

RAW 3 as i1 -i2 ,  i2-i3 and i4-i5

Ans WAR and WAW same as hazard?
–1

A potential hazard exists between instruction i and a subsequent instruction j when at least one of the following conditions fails  :

For RAW  :   W(i)  ∩  R(j)  =   Φ

For WAR :    R(i)   ∩  W(j) =   Φ 

For WAW :    W(i)   ∩  W(j) =   Φ

Now for I1 and I2 ,I1 is the i instruction and I2 is the j instruction i.e subsequent instruction.And R(i)   ∩  W(j) =   Φ  ,so why is it still considered as WAR dependency.?

0
@Arjun sir why there is RAW between I2 and I5? I4 has updated ACC already. Isn't it?
0
@Arjun Sir-Sir, here WAR dependencies are 2 and WAW are 1. Since, this pipeline is simple 3 stage, WAR and WAR hazards must be 0 assuming all instructions take 1 clock cycle each. Am I correct?
0
Why isn't this answer updated? RAW dependencies are only 5 but not 6. As there wont be any I2 - I5 RAW dependency.
0
I'm getting only 3 RAW hazards - I1-I2, I2-I3, I4-I5. I1-I4 dependecy doesn't cause hazard because the OF phase of I4 is executed after E/WB phase of I1. Same is the reason for I2-I4 dependency. Can someone tell me if this is correct?
0 votes

RAW-4,WAW-1,WAR-1

RAW:

  1. I1-I2
  2. I1-I4
  3. I2-I3
  4. I4-I5

WAW:

  1. I2-I4

WAR:

  1. I3-I4

https://gateoverflow.in/3622/gate2006-it-78

We are allowed to find the dependencies in the adjacent instructions only , unless  we are told to do so . If it is instruction Reordering it will be given explicity in the question beause whenever the question is ambiguous we should always consider the bestcase  and reduce the problem complexity as low as possible . 

Moreover In RAW type dependencies when one instruction update the value and reused in the following instruction we would consider oly the last update . (ie here I2-I4 I2-I5 are not taken into consideration for RAW ).

by Boss (21.5k points)
0
So in this question what about I2 and I5(ACC)?
0
It is a RAW dependency..
+1
No, it is not. I2-I5 is not any dependence here.
0
Yes I4 update ACC so I5 depeneds on I4.
0
It is not due to I4?
0
But it is true according to Bernsteins conditions right sir according to the sources that I have mentioned??
0
SO this case could be in WAR also?

If 3 instructions having variables defining WAR but 1st will not depend on 3rd due to 2nd instruction.
0
@Habib do not know of those conditions and not getting a standard resource to refer either. But as shown in the examples given by you and any standard resource, for RAW dependence the source WRITE must be the LAST WRITE to the location and not any before it.

@Vaishali No, for WAR this is not the case. Because here we do a Read after a Write. Even if multiple instructions follow and each does a Write, any of this can cause a hazard in an out-of-order machine. But for the RAW case, only the last Write matter.
0
r1 <- r2+r4

r2 <- r3+r4

r2 <- r4+r6

Arjun sir...please explain through this example ....i am not getting why not in WAR.
0
@Arjun Sir, there are many gate questions regarding hazards and all of them just ask how many hazards are there. No explicit pipeline working is given , so we need to assume them as dependency same as hazards are also in the same sequence and give the answer, rt ?

I saw almost all questions and also assume this only and simply count the hazards . No conditions are given explicitly.
+1
Here, WAR exists between I1->I2 and I1->I3.

Can we put I2 above I1?
Can we put I3 above I1?

r2 <- r5+r4

r2 <- r3+r4

r3 <- r2+r6

Can we put I1 after I3?
Can we put I2 above I3?
0
Vaishali there is no RAW.

and 2 WAR i.e. i1 to i3 for r2 and i1 to i3 for r2.
+1
@Kapil yes, possible hazards in pipeline means dependence.
+1
@Arjun sir, In gate questions, they ask simply to count the hazards and not even possible hazards.

At last, simply can I put it as 5 raw, 1 waw and 2 war ?
+2
yes, in GATE that will be it. This question is creating confusion by giving the pipleine details - because in such a case we have to assume sequential execution - meaning #WAR hazards = #WAW hazards = 0. Given 0 as a choice for this question one has to go for it.
+1
@arjun sir , why dont you give a proper answer to this question ? this actually kills much time reading all comments and answers :(
+6

@Arjun Sir :yes, in GATE that will be it. This question is creating confusion by giving the pipleine details - because in such a case we have to assume sequential execution - meaning #WAR hazards = #WAW hazards = 0. Given 0 as a choice for this question one has to go for it.

This is not true. WAW and WAR hazards are bcoz of two reasons:- 

1. Reordering

2. Check this link below .    

http://archive.is/7383#selection-9.9543-9.10079 this link says:

Although WAR and  WAW hazards cannot happen in a simple 5-stage pipeline that we have discussed,
it is possible in more realistic pipelines where complex instructions
such as FP divide take a longer time (e.g., 32 cycles) and
a simple FP  add takes only 4 cycles. In these cases, an earlier FP 
divide operate may complete at a later time time than a later FP add 
operation, causing WAW hazard!  In such a case the pipeline hardware
must ensure that the later instruction (FP Add) must be stalled
until the earlier FP Divide completes.

In Below diagram, pipelining is implemented in such a way that without any reordering we have chance for WAW. (Source: http://people.engr.ncsu.edu/efg/521/s06/common/lectures/notes/lec18.pdf)

(if load instruction is taking 2 mem cycle and Add is not taking any)

http://people.engr.ncsu.edu/efg/521/s06/common/lectures/notes/lec18.pdf

(in case if one argue that every instruction has to go through every stage then think this example as load is taking 3 Mem and Add taking 1, then also WAW)

(the only thing i am saying is, until we are given exact pipeline details we can never say 0.)

I also found out one assignment solution of udacity, https://www.udacity.com/wiki/hpca/problem-set-solutions/pipelining/problem01

and i suppose what ever solution is there, it is correct. We can trust udacity :)

0
@Sachin Mittal I also think the same. I have seen the pdf and pointed out that we can't always count war dependency. Have you found the solution yet for the problem?
0
I understood the concept. Just one more small doubt is that hazard can occur due to reordering of instructions as opposed to dependency where we don't reorder instructions . So, if hazards are asked in GATE, should we consider reordering of instructions or not?
0
in the video solution of madeeasy ... its given 3,1,2 as raw,waw,war. as they say for raw hazard only consecutive instructions did should be checked.

what's going on...
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,262 comments
104,976 users