10,164 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.

edited by

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)

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

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

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 "

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

### Subscribe to GO Classes for GATE CSE 2022

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

by

Sir does it means presence of Hazard in a Pipeline structure is necessary but not sufficient condition for stall ??
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 :)
even I2 and I4 has WAR ,dependency..Plz correct m if m wrong!!!!
I2 I4 has WAR on r3
edited

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

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?

@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?
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.
How WB of I2 and ID of I4 is overlapped without operand forwarding value of r4 is availabe after WB of I2 right?
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.
> 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.

@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 ?

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

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

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

Is it true that RAW Hazards are to be considered  btw adjacent instructions??

@Arjun sir, in the second table (the stall table), we have a split phase applied for the ID and WB stages as you explained further above. If we follow the convention given in the question, $I_4$'s ID stage reads register $R_4$ before $I_2$'s WB stage can write to the register file. Shouldn't there be a stall in cycle 8 for $I_4$, and then the ID stage should occur?
Or have you followed the opposite convention in the second table (I have seen this in Prof Jacob's lectures), i.e. register reads happen in second phase of clock and register writes happen in the first?

@arjun sir ID of i3 should be done at t5 cycle ?bcz after WB it is available, and if operand forwarding is done between I1 and I3 to get r2 then how ??
so there are 4 or 7 hazards?
edited by

can you please tell the difference between WAR hazard and WAR dependency? As mentioned by you in the above statement.

Is it that data dependency is specific to code but data hazard is property of that code's pipeline. And therefore if there is no stall for that data dependency then it is not a data hazard.

At first, I couldn’t understand why Ex & WB are placed on same timeline since there is data dependency between I1 & I3. Now it clears more.

Dependency causes hazards but not all dependency cause a hazard.

Only if dependency cause a stall in pipeline, then we get a hazard.

can anybody explain how r2 is forwarded from i1 to i3 using operand forwarding ??
@Arjun Sir,

I1<----I3 wont cause a hazard right?
@ Gaurav you just cleared my major buffer register overwrite doubt in operand forwarding. Thank you
How I3 with I1 is causing a hazard? Even if there is no dependency between I3 and I1, still I3 will start with clock cycle t5 and continue till t9 without stall.

If we are fixing the hazard(RAW) between I2 with I1 then, I3 is automatically fixed, we are not having any stall specifically because of (I3,I1) RAW dependency.

Then why are we considering it as hazard?

4 RAW

3 WAR

With operand forwarding:

Without it:
(both tables represent the same pipeline)

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

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

edited by

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

"All (memory or register) reads take place in the second phase of a clock cycle and all writes occur in the first phase"

Does this statement also mean that memory write and read can happen in same clock cycle, in first half write and in second half read?

@sushmita

Here instruction I3 is decoding and fetching operand from registers in 4th clock cycle
There is an RAW dependency between I3 and I1 for R2. But correct value of R2 is available in register at end of I1 WB phase How I3 is gettng correct value of R2 in clock 4 ??

It is getting the correct value because of operand forwarding from memory stage of I1 to execution stage of I4.

Is it clear now?
i am talking about I3 dependency on I1 for R2
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.
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

@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 ??

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

@Shubhgupta

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

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

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

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

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?

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.
Do in any case war dependency produces war hazard i.e produces stall in pipelining

thanks  ,

the first table in 'without it' part ,the coloring of yellow and blue helped me understand the answer.Your effort helped me.