retagged by
9,895 views
18 votes
18 votes

no of RAW,WAR and WAW ?

retagged by

2 Answers

Best answer
22 votes
22 votes

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

selected by
0 votes
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 ).

Related questions

1 votes
1 votes
4 answers
2
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4
Vishnathan asked Nov 17, 2018
945 views
Find the data hazards(RAW,WAW,WAR) in the given instructions