The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
2.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.8k points)
edited by | 2.8k views
+10

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) ..?

+1

Chhotu please clear my confusion

(I1 and I4) has RAW dependence on r2 but does not cause RAW hazard, right?

0
3rd part of question is related to the basic concept of pipelining which states that : "whether a particular hazard leads to stall is property of pipelining architecture for example in 5 stage MIPS pipelining there is no hazard due to WAR AND WAW dependency "
0

@MiNiPanda there will be no RAW as well as WAW,WAR. bcz  when I4 required I1 at EXE stage ...I1 already completed it execution.

2 Answers

+32 votes
Best answer

4 RAW

3 WAR 

With operand forwarding:

Without it:
(both tables represent the same pipeline)


 

answered by Boss (31.1k points)
selected by
0
I3 calculates r1+100 in EX stage and r1 does not depend on any previous instruction and when it loads the value of r2 in 6th cycle, r2 is already written to register file in 5th clock cycle, so no problem.
0
Sorry but m not getting

when I3 will read value of R2 ..in ID phase ..it will write it to M[r1+100] in MEM phase

But In ID phase that is 3rd clock will I3 get correct value of R2 ??..isn't there dependency between I1 and I3 RAW
0

@Arjun sir

 In I3, while doing memory access in 6th state, we are having the value of R2 because its written back by I1 during 5th stage so it can get the value from register file ??

0

@Arjun please clear this doubt 

0

ye @sushmita, I3 can get the value of r2 because it is already written by I1.

+1

@Shubhgupta

But ID of I3 where I3 have fetched wrong R2 is happened before ..I1 write to register file.

0
But it's not written at the RD stage then how can I3 read the correct value?
0

, we are using operand forwarding EX to EX so after EX phase of I1 correct value of r2 will be available in register. So that's why I3 will read the correct value fo r2.

0

so after EX phase of I1 correct value of r2 will be available in register

No operand forwarding from EX to EX phase means after EX phase output is provided back to input of EX phase that is EX of next instruction..final computation is written to register only in WB phase from where ID phase read

0

check this https://gateoverflow.in/1391/gate2005-68

  1. Why there is a stall I2 in T4 ? 
    Data is being forwarded from MA of I1 EX of I2 .MA operation of I1 must complete so that correct data will be available in register .

so in our question correct value of r2 will be available in register after EX phase. Isn't it?

+21 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 (379k points)
+4
Sir does it means presence of Hazard in a Pipeline structure is necessary but not sufficient condition for stall ??
+5
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?
+6
@rahul "IS it possible to have stalls without hazard?"

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


first thing here no WAR hazards is present. it's WAR dependency.

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

47,241 questions
51,468 answers
178,538 comments
66,754 users