3.2k views

no of RAW,WAR and WAW ?

retagged | 3.2k views
0
RAW- 5, WAW-1,WAR-2?
0
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
0
@saurabh why?
0
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

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
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
0
Correct according to me.

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
0
Nice Explanation... But How ACC be in Write set of I0  ? Can u explain that part ?
+1
Typo..:)  Correcting..
0

@habibkhan correct me if wrong

RAW

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

WAR

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

WAW

1. I2 - I4

Im getting 6, 5 , 1

----edit---
I missed I2-I1 in WAR

+1
In WAR , I2-I1 will also come (or I1 - I2 the way u have written) as

R(I2)  =  {ACC,R0}

W(I1)  = {R0}

So intersection result is not phi and hence possibility of WAR hazard if I2 occurs before I1..

Hope this clears..
+1
I missed I2-I1 in WAR . Corrected . Now, Im also getting 6,6,1 :)
0
Can you explain when do we need to consider like instructions sufflled manner ? Like I2 comes before I1 ?
Do I have to consider this situation always while checking number of RAR RAW WAW ?
0

@habibkhan

hazard resolution in each stage

What is the significance of this in the question ? Will it affect calculation of hazards ? Im confused with this word

0
It is required to do instruction scheduling solution to avoid hazard..But in that process what we do is instructions may get rearranged and hence we are referring as out of order execution done in instruction scheduling leads to WAR and WAW hazards .

But given no such rearrangement then no need to bother about WAR and WAW hazards..In such a scenario , only RAW hazards are applicable..
+1
That is what is referred to as instruction scheduling according to detection of hazards..Nothing else significance is there..
0
So, should we always need to rearrange when the question is asked to find the number of WAW and  WAR
0
U need not rearrange code manually..Just keep in mind the conditions that I have mentioned..
+2
@Habib Good formal way. But I do not think unless stated in question we need to consider "out-of-order" execution as this cannot happen inside a pipeline but should be done by the Instruction scheduler.

Also, whatever be the order - there should not be a RAW dependence between $I_2$ and $I_5$.
0

But sir since nothing is mentioned whether out of order execution will occur or not..We should explore all the possible scenarios..

Moreover the Bernsteins conditions strictly specify that 2 statements will be done in parallel meaning that they will not be affected by any of the 3 hazard iff they satisfy Bernsteins conditions which is mentioned earlier..So from this it follows that possible hazard occurs if there is something in common in any of the 3 mentioned conditions ..

Also verified from : https://en.wikipedia.org/wiki/Data_dependency#Flow_dependency..Plz check sir..

+1

@arjun Sir, why dont there be any RAW betwen $I_{2}$ and $_{5}$ ?.  ACC ?

0
@Habib @Arjun

I dont agree with you. You need to consider out of order executions only when there is no dependency otherwise it may create inconsistency.

Consider why do we create a graph for conflict serializability considering the sequnce of oprations in the schedule? Same here. I think we shouldnt disturb the sequnce.
0
So once we have dependency graph, onlythen we change the sequnce of instructions.
0
The dependency graph is I1 ==> I2 ==> I3

and  I1 ==> I2 ==> I4  ==> I5

So, topological sorting can be

I1, I2, I3,I4, I5

I1, I2, I4, I5,I3

I1, I2, I4,I3, I5
0
So, now from all the 3 sequences, we get following hazards,

WAW:
I2-I4

WAR:
I3-I4,I2-I4

Berstein's is in all situations irrespective of dependencies..
0
@Sushant Gokhale ,there is a possibility of instruction scheduling..U have to consider that..Hence u cannot neglect those cases..
0
@but dependencies cant be neglected.
0
@Habib

We want to do minimum number of hazards.

Why we do maximum hazards, though it is not mentioned "out of order" execution?
+1
+1
@srestha if we don't consider out of order execution then no WAR and WAW hazards are possible here.
0
@Habib I really appriciate u to put this approach.

But , I believe hazard must be minimized. Otherwise we donot putting register renaming or other stuff to overcome hazards.

@saurabh

In GATE they consider general answer I think. Do u seen such exception question in GATE?
0
@vijaycs @Manoj see it
0
ys. this is what i was also asking.. When do we need to consider this out of order case ? In question it should be mentioned , right ?
0
@srestha i m not considering anything explicitly i m just following the concept
Every time when we are finding WAR and WAW dependency and hazard we r assuming reordering as a possible case  there may b other cause for WAR and WAW hazard but it is most common case and smtimes  there is no WAR and WAW hazard in pipeline like MIPS bcoz of no reordering . so why these r also nt called True data dependency like RAW.
0
But @srestha here they are asking simply the 3 types of hazards possible..

And register renaming etc solutions to be considered if mentioned in question explicitly..

Hence we have to take general approach..

Hence we are considering all out of order execution hazards possible which is given clearly by Bernstein's conditions.

IT is rather mathematical and general method to solve such questions..

And I have given reference also regarding this..
+1
but @habibkhan that reference is n't any standard one i guess. for gate we must look for references from standard text books or any nptel one . Let see if we can find out  something like that to confirm . what I think for now is if reordering it should be explicitly mentioned .
0
@saurabh. WAR and WAW hazards need to be considered for in sequnce execution of instructions considering that stalls may occur for previous instructions.
+1
No WAR and WAW hazards are meaningless for inorder execution of instructions..I dont understand why u all r complicating this question..

And @Anjana Babu , dont u consider the wikipedia as an authentic resource??

And also the instance of original Bernsteins conditions that I have also mentioned..
0
For e.g

ID IF   stall   stall   stall  EX   MA   WB

IF     ID      EX      MA    WB

Now, here we need to do sequncing for the 2nd instruction i.e create stalls as well as take care that WB of 2nd instruction comes after  WB of first
0
@Habib. You are not recognising that instructions are fed to processor only after all optimizations have been done.

SO, there cant be any out of order execution
0

@habib

### Anti-dependency

An anti-dependency, also known as write-after-read (WAR), occurs when an instruction requires a value that is later updated. In the following example, instruction 2 anti-depends on instruction 3 — the ordering of these instructions cannot be changed, nor can they be executed in parallel (possibly changing the instruction ordering), as this would affect the final value of A.

Souce : https://en.wikipedia.org/wiki/Data_dependency#Anti-dependency

What do you say with this ?

0
But why r u going for optimisation ..Have they asked for minimum no of hazards possible??

Simply the hazards are being asked..

Ok dont mind do it as u wish..

I have given a clear cut explanation to it.
0
Oops. I just wanted to make sure what is right :(
0
@Habib. Dont take it personally. We are just discusssing what can be right.
0
No bro..I have not taken it personally..:)..
+1
you are correct @habib. (y)
0
Did u verify from anywhere by the way..:)
+1
still working on it :) :)
+1
0
Anyways nice discussion in this question..:)
+1
I bet it is not coming in xm :p :P :)
0
If at all it comes in exam , everything should be mentioned clearly..
+2

In fact , a similar question has come earlier on this..And my approach gives correct result ..This is the question :

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

+1
@habib
Oh yeah.. After seing all the notification I was searching for this question from today moring onwards :D
0

@habib WAR between ? $I_1$ and $I_2$​ in ​​​​​​https://gateoverflow.in/3622/gate2006-it-78 ?

0

@Habib, for https://gateoverflow.in/3622/gate2006-it-78

its giving me 6,6,2 with your approach. Is it correct?

0
Should I give answer to that link by my approach to make my point clear??
0
0
0
@Sushant Gokhale, can u plz look at my comment that I have posted to pC's answer??
It would be helpful of me..
+1

Hi @Sushant Gokhale , plz have a look at the following :

https://www.udacity.com/wiki/hpca/problem-set-solutions/pipelining/problem01

https://en.wikipedia.org/wiki/Data_dependency

By virtue of these 2 references , I m getting correct answer as well for the given question..

+1
After all the healthy discussion i feel this seems to be correct answer .
@habibkhan why not updating this answer with all the references , gate question .  difference between dependency and hazard . what is potential hazard and how they relate with each other (with the given instruction set ) will definitely make this solution supercool :)
0
@Habib.

With the definiion given on wiki, the answer to 2006 question is correct.
0
0
Sir can u plz elaborate??
+1

Copying from here:

Consider following assembly-language program:

 1: MOV R3, R7

2: LD R8, (R3)

5: BNE R8, R9, L3

a) This program includes WAW, RAW, and WAR dependencies. Show these.

b) What is the difference between a dependency and hazard?

c) What is the difference between a name dependency and a true dependency?

e) Which of WAW, RAW, WAR are true dependencies and which are name dependencies?

Solution

WAW: L1-L3;

RAW: L1-L2,L1-L3, L3-L4,L2-L5,L4-L5

WAR: L2-L3;

In RAW, L1-L4 is not there.

+2

But in wikipedia (https://en.wikipedia.org/wiki/Data_dependency), it is mentioned  :

### Flow dependency

A Flow dependency, also known as a data dependency or true dependency or read-after-write (RAW), occurs when an instruction depends on the result of a previous instruction:

1. A = 3
2. B = A
3. C = B


Instruction 3 is truly dependent on instruction 2, as the final value of C depends on the instruction updating B. Instruction 2 is truly dependent on instruction 1, as the final value of B depends on the instruction updating A. Since instruction 3 is truly dependent upon instruction 2 and instruction 2 is truly dependent on instruction 1, instruction 3 is also truly dependent on instruction 1.

So from this it follows I- I4 for the above question should also hold..

0
@Arjun Sir, I2 - I5 is having true dependency but not a hazard here as ACC has been updated,rt?
+2
Yes, But the issue is $L_3$. Since $L_3$ writes to $R_3$, now $L_4$ depends on $L_3$ and not $L_1$ - like a local variable hiding a global variable in programming. This is so obvious (no example from any standard resource will be against this) but I'll try getting a proper definition which clearly includes this.

Also I see some people saying about "adjacent instructions" for hazards. This is like saying more than one comparison makes a language non CFL without considering what those comparisons are.

Is there anywhere a question is asked for "hazard" in the sense that only those which causes a stall cycle in pipeline are considered as answer?
+1
@Kapil No. That is not even a dependence for the same reason. Whatever $I_2$ writes is of no importance to $I_5$ meaning no dependence.
0
okk  !! So, that makes bi-implication between dependency and hazard ?
+1
Almost, but they can ask for "hazard" in the sense of a given pipeline meaning only those instructions causing a stall which also requires instructions not to be executed out of order. But this should never happen for GATE.
0

Isnt it true that all hazards are dependencies but all dependencies are not hazards..??Sir plz have a look at the part D) of the following :

According to it the statement made by me is correct and hence it should be a one way implication..

+2
Yes, that definition is correct. It is clearly a one way implication. But when the exact working of the pipeline is not given - all dependences become "possible hazards".
0
So we should also consider I1 - I4 right as a dependency according to the definition given in the link that I gave just before??
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

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?

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 .

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)

(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...