The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3k 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:

$$\begin{array}{|l|l|} \hline \text{I1:} & \text{sub $r 2,r 3,r 4$} & \text{/*}\quad  r2 \leftarrow r3 - r4 \quad\text{*/} \\\hline \text{I2:} & \text{sub $r 4,r 2,r 3$} & \text{/*}\quad r4 \leftarrow r2 - r3 \quad\text{*/} \\\hline \text{I3:} &  \text{sw $r2,100(r1)$} & \text{/*}\quad\text{$M[r1 + 100]$} \leftarrow \text{r2}  \quad\text{*/}\\\hline \text{I4:} &  \text{sub $r 3,r 4,r 2$} & \text{/*}\quad r3 \leftarrow  r4 - r2 \quad\text{*/} \\\hline\end{array}$$

  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 ago by | 3k 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

+21 votes
Best answer

RAW dependencies:

  1. $I_1 \leftarrow I_2$
  2. $I_1 \leftarrow I_3$
  3. $I_1 \leftarrow I_4$
  4. $I_2 \leftarrow I_4$

WAR dependencies:

  1. $I_2 \leftarrow I_1$
  2. $I_4 \leftarrow I_1$
  3. $I_4 \leftarrow I_2$

Consider a normal pipeline execution:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline
&\bf{t_1}&\bf{t_2}&\bf{t_3}&\bf{t_4}&\bf{t_5}&\bf{t_6}&\bf{t_7}&\bf{t_8}\\\hline
\bf{I_1}& \text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_2}&&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_3}&&&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_4}&&&&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\end{array}$$

So, there are RAW hazards for $I_2$ and $I_3$ with $I_1$ and for $I_4$ with $I_2.$ (Not all dependencies cause a hazard. Only if a dependency causes a stall in the given pipeline structure, we get a hazard) These hazards causes the following stalls in the pipeline:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline
&\bf{t_1}&\bf{t_2}&\bf{t_3}&\bf{t_4}&\bf{t_5}&\bf{t_6}&\bf{t_7}&\bf{t_8}&\bf{t_9}&\bf{t_{10}}&\bf{t_{11}}\\\hline
\bf{I_1}& \text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_2}&&\text{IF}&-&-&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_3}&&&-&-&\text{IF}&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\bf{I_4}&&&&-&-&\text{IF}&-&\text{ID}&\text{EX}&\text{MEM}&\text{WB} \\ \hline
\end{array}$$

Now, with operand forwarding from $\text{EX} - \text{EX}$ stage we can do as follows: 

$$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline
&\bf{t_1}&\bf{t_2}&\bf{t_3}&\bf{t_4}&\bf{t_5}&\bf{t_6}&\bf{t_7}&\bf{t_8}\\\hline
\bf{I_1}& \text{IF}&\text{ID}&\underset{1}{\boxed{\text{EX}}}&\text{MEM}&\text{WB} \\ \hline
\bf{I_2}&&\text{IF}&\text{ID}&\underset{1}{\boxed{\text{EX}}}&\text{MEM}&\text{WB} \\ \hline
\bf{I_3}&&&\text{IF}&\text{ID}&\underset{3}{\boxed{\underset{1}{\boxed{\text{EX}}}}}&\text{MEM}&\text{WB} \\ \hline
\bf{I_4}&&&&\text{IF}&\text{ID}&\underset{3}{\boxed{\text{EX}}}&\text{MEM}&\text{WB} \\ \hline
\end{array}$$

Thus all hazards are eliminated. 

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

answered by Veteran (395k points)
edited ago by
+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.

+32 votes

4 RAW

3 WAR 

With operand forwarding:

Without it:
(both tables represent the same pipeline)


 

answered by Boss (30.9k points)
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?

+1
I think the only hazards are I1-I2(R2) and I2-I4(R4), because without forwarding, they need stalls to execute correctly.

Data Dependency is a property of the code.Hazards is the property of the pipeline.

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
50,049 questions
53,194 answers
184,531 comments
70,402 users