The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.8k views

Consider a 5-stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (memory), and WB (Write Back). All (memory or register) reads take place in the second phase of a clock cycle and all writes occur in the first phase. Consider the execution of the following instruction sequence:

I1: sub r2, r3, r4; /* $r2 \leftarrow r3 - r4$ */
I2: sub r4, r2, r3; /* $r4 \leftarrow r2 - r3$ */
I3: sw r2, 100(r1) /* $M[r1+100] \leftarrow r2$ */
I4: sub r3, r4, r2 /* $r3 \leftarrow r4 -r2$ */
  1. Show all data dependencies between the four instructions.
  2. Identify the data hazards.
  3. Can all hazards be avoided by forwarding in this case.

 

asked in CO & Architecture by Veteran (59.4k points)
retagged by | 1.8k views
+5

Just additional information

Forwarding can(because not always)avoid RAW hazards (because even before writing we are sending output via forwarding so read could be performed even before write).

Renaming can avoid WAR and WAW (Here Forwarding does not make sense because we want to delay write  it could be achieved via instruction shuffling or register renaming)

Sometimes "do nothing" also work because there is enough separation between two dependent instructions.

 

Notice -> Here we are reading register in ID phase itself. But in some cases it happens in OF stage (https://gateoverflow.in/1388/gate2005-65)

0

yes..me too have same opinion so on the basis of this can we say NO for the answer of part (c) ..?

2 Answers

+24 votes
Best answer

4 RAW

3 WAR 

With operand forwarding:

 

Without it:
(both tables represent the same pipeline)


 

answered by Boss (30.6k points)
selected by
0
Yes, Thank you. :)
0

@reena_kandari

When we execute them with space time diagram,then we always execute them in sequential order.So,there will never be any WAW,WAR when we execute them on space time diagram.THere will only RAW,which may or may not be eliminated by pipeline

0
yes, What I mentioned is RAW hazards.but you always can't say that in sequential execution WAW or WAR cann't happen.If preceding process takes less number of clock cycles than the successor one..then there is a possibility of WAW.
0
WAW WAR happens only in out of order.These can not happen inorder. IF there is a WAW between I1 and I2 ,assume,Now only when I2 will release the Write back stage,then next I2 will be able to take.
0

 

yes, if we allow out of order execution then WAW/WAR hazards are possible.

0
There are no WAR hazards .. there are only WAR dependencies ... A dependency if it causes a pipeline to stall then that dependency is called as a hazard ... Here though we have 3 WAR dependencies ... none of them produces stall cycles ... so 0 WAR hazards ...
0

 @Vicky rix @reena_kandari @rahul @chottu ji

The final conclusions : (Comment if something wrong)

1)  Operand forwarding is used to avoid RAW hazards but it is not necessary that it will always avoid them.

2)  Register renaming can be used to avoid WAR and WAW hazards (I think this is NOT always successful)

https://cs.stackexchange.com/questions/30108/does-register-renaming-remove-all-kinds-of-war-hazard

From a computer architecture point of view, an additional problem for write-after-read hazards is dealing with load and store operations to main memory. Register renaming won't help with this problem

3)  Now,Only out of order execution can produce WAR and WAW hazards --> This statement is false.

here, we are executing the two instructions inorder but, still write by I2 is performed first and then write by I1(This is wrong,first I1 should write R1 and then I2).

3)  There are no WAR hazards .. there are only WAR dependencies ... A dependency if it causes a pipeline to stall then that dependency is called as a hazard ... Here though we have 3 WAR dependencies ... none of them produces stall cycles ... so 0 WAR hazards ...

4)  Keeping in mind point (3) above, the answer to (c) part is Yes because after using operand forwarding in this case we are successful in eliminating all hazards.

 

 

0

@VS, for your statement 2) plz see my comment over here bcz what I think is register renaming is not always successful. Please Do comment over there if you have any good points.

0

https://gateoverflow.in/52/gate2012-20-isro2016-23 look in comments there they use word eliminate.

+1

@ VS ji, 

1)  Operand forwarding is used to avoid RAW hazards but it is not necessary that it will always avoid them.

Yes. Because If data is available in earlier stage of the pipe line then it could be moved to any stage. But sometimes if data itself is not available then what will be forwarded (like in LOAD instruction data come in MA stage).

2)  Register renaming can be used to avoid WAR and WAW hazards (I think this is always successful)

Not very sure. @reena_kandari ji point(as mentioned on https://gateoverflow.in/447/gate2008-36#c174683) looks good to me. So waiting for other users reply. 

3)  Now,Only out of order execution can produce WAR and WAW hazards --> This statement is false.

This is correct. 

+13 votes

RAW dependencies:

I1 <- I2
I1 <- I3
I1 <- I4
I2 <- I4

WAR
I2 <- I1
I4 <- I1
I4 <- I2

Consider a normal pipeline execution. 

  t1 t2 t3 t4 t5 t6 t7 t8
I1 IF ID EX MEM WB      
I2   IF ID EX MEM WB    
I3     IF ID EX MEM WB  
I4       IF ID EX MEM WB

So, here are RAW hazards for I2  and I3 with I1 and for I4 with I2. These can be eliminated with pipeline stalls as follows:

 

  t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11
I1 IF ID EX MEM WB            
I2   IF - - ID EX MEM WB      
I3     - - IF ID EX MEM WB    
I4       - - IF - ID EX MEM WB

 

Now, with operand forwarding from EX - EX stage we can do as follows: 

  t1 t2 t3 t4 t5 t6 t7 t8
I1 IF ID EX MEM WB      
I2   IF ID EX MEM WB    
I3     IF ID EX MEM WB  
I4       IF ID EX MEM WB

Thus all hazards are eliminated. 

Ref: http://cseweb.ucsd.edu/classes/wi05/cse240a/pipe2.pdf

 

answered by Veteran (339k points)
+2
Sir does it means presence of Hazard in a Pipeline structure is necessary but not sufficient condition for stall ??
+2
Yes. Many hazards can do without a stall. And hazard is not a sufficient condition for a stall. We can simply have a stall also :)
0
even I2 and I4 has WAR ,dependency..Plz correct m if m wrong!!!!
0
I2 I4 has WAR on r3
0

@Arjun sir, I think everything alright except , WAR Hazards, 

               - plz check WAR Hazards by Amar (only WAR Hazards..)


& in Pipeline Execution without Operand Forwarding - 

             I4 can do IF in stage tonly , not before as the IF hardware is occupied by Itill  t6.

0

Refer to table number 2, i.e. without operand forwarding.

Why is that at instruction I2 pipeline : ID takes place at t5 but not at t3, and similarly for other instructions too?

0
@arjun without operand forwarding can we do IF at T3 for I3 and also how can we perform ID of I3 at at T8 which should be done after WB of I2.Can you please explain?
0
I3 is not dependent on I2. IF of I3 can start at T3 provided multiple stage buffers are there. Even if we do this here, answer remains the same.
0
How WB of I2 and ID of I4 is overlapped without operand forwarding value of r4 is availabe after WB of I2 right?
+1
WB and ID can happen in same cycle using positive edge/negative edge and this is called split phase technique. You can see the accepted answer where this is shown clearly.
0
> Can all hazards be avoided by forwarding in this case.

Although answer is very informative, but why it is assumed that stages of pipeline are taking one clock cycle. Because if some stage is taking more cycle then even forwarding can not eliminate all Data Hazard.
0

@Arjun sir  Actually here there is no WAR hazard right ? 

Because we do register-read only in the ID phase and register-write only in the WB stage and here WB of an instruction Ii will happen only after the ID of Ij where j<i right ?

0
Sir How we can say WAR hazards are also removed as WAR needs renaming basically
0
@Arjun sir? IS it possible to have stalls without hazard?
+4
@rahul "IS it possible to have stalls without hazard?"

Yes, it is possible. A simple example will be when we have a cache miss.

Related questions



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

34,770 questions
41,729 answers
118,874 comments
41,381 users