# GATE2015-3-47

7.5k views

Consider the following code sequence having five instructions from $I_1 \text{ to } I_5$. Each of these instructions has the following format.

OP Ri, Rj, Rk

Where operation OP is performed on contents of registers Rj and Rk and the result is stored in register Ri.

$I_1$: ADD R1, R2, R3

$I_2$: MUL R7, R1, R3

$I_3$: SUB R4, R1, R5

$I_4$: ADD R3, R2, R4

$I_5$: MUL R7, R8, R9

Consider the following three statements.

S1: There is an anti-dependence between instructions $I_2 \text{ and } I_5$

S2: There is an anti-dependence between instructions $I_2 \text{ and } I_4$

S3: Within an instruction pipeline an anti-dependence always creates one or more stalls

Which one of the above statements is/are correct?

1. Only S1 is true
2. Only S2 is true
3. Only S1 and S3 are true
4. Only S2 and S3 are true

retagged
41

Dependency and Hazards are different.

Flow Dependency is same as Read After Write.

Anti Dependency is same as Write After Read.

Output Dependency is same as Write After Write.

1
S1 : Output Dependency
0
0
Thanks for giving answer in a very short manner. There was always confusion,but now all clear.

Anti-dependence can be overcome in pipeline using register renaming. So, "always" in S3 makes it false. Also, if $I2$ is completed before $I4$ (execution stage of MUL), then also there won't be any stall.

edited by
1
what do you think @Arjun Sir is option (B) correct ??
12
Yes. B is correct. Anti-dependence can be overcome in pipeline using register renaming. So, "always" in S3 makes it false.
14
@Arjun Sir, even if we consider this case

in this case it is not creating stall na even there's anti dependence (WAR).....

I also marked B....Just asking whether concept and explanation are right?
9
Yes. Because both are ADD instructions and before the write to R2 in the second instruction the Read for I1 would be completed. But this assumes I1 is not waiting for any other operand- no other data dependencies.
0
Arjun sir . We use register renaming to over come anti dependency. Anti dependency in a instruction itself always causes a stall. So in order to overcome that we use register renaming during the programming phase itself.

And the option has asked within a pipeline anti dependence always causes a stall. That means it wants to say that the instruction is already in the pipeline and we get an anti dependency. So there is not any possibility of register renaming here as it is done before the program is executed.

Please correct me if am wrong.

Thanks
14

Register renaming is not done during programming phase. It is done inside processor. See the organization tab in the below link.

http://www.d.umn.edu/~gshute/arch/register-renaming.xhtml

Now, even if we don't use register renaming anti-dependence won't "ALWAYS" cause a stall. Whether it causes a stall or not depends on the order of instructions and the number of cycles of instructions between them.

0
So is it the task of cpu whether or not to do the register renaming?..can you please state the difference between output dependencies and anti dependencies as given in the article of the link..
9
Yes. When we buy a CPU we pay for the register renaming technique :)
0
hi arjun,

just a doubt,

we accept there is an dependence between i2 and i5(waw) .

but isnt the same with i2 and i4 . i mean the war dependency ??

just a question, isnt answer none of above ?
9
what's issue there? WAW is not anti-dependence. It is output dependence.
0

I2I2: MUL R7, R1, R3

i mean , aren't we having a WAR dependence here ? how come an anti-dependence . that's what i cannot understand . sorry to pester much :P

0
can it sometimes cause stall if not always??
4
@Arjun sir, Does Register renaming remove WAR  and WAW dependence completely?
1
Yes....^
0
@ Arjun sir what if it was given that I2 can be completed before I4 fetch stage then should we say dependence is there???? Or we should consider that they can be exectued in different order and I4 can write first so it is war dependece.???
6
@Rahul For data dependence just consider read and write to same location. It is independent of execution order or pipeline structure - those are needed for "hazards".
0
Thank you @ Arjun sir. I was confused between hazards and dependence. What would be the answer jf WAR "hazards" were asked??? 2 WAR hazarads, is it correct???
1
2

There is a point in below discussion that "WAW hazards are present only in pipeline that allow an instruction to proceed when a previous instruction is stalled"

Is that mean WAW doesnot create stall, but it depend on stall?

https://gateoverflow.in/753/gate2001-12

https://gateoverflow.in/186494/self-doubt

https://gateoverflow.in/85255/pipeline_hazard?show=86814

https://gateoverflow.in/67293/%23co

18

Very Nicely Explaned !

1
Am I the only one who dont know what is anti-dependency??
0
0

@jatin khachane 1

That is a good video.

Thanks.

0

$I_1$: ADD R1, R2, R3

$I_2$: MUL R7, R1, R3

$I_3$: SUB R4, R1, R5

$I_4$: ADD R3, R2, R4

$I_5$: MUL R7, R8, R9

Write - After - Write (WAW): Output - dependence

$I_{2} - I_{5}$

Read - After - Write (RAW): Flow - dependence

$I_{1} - I_{4}$

$I_{1} - I_{2}$

$I_{2} - I_{4}$

$I_{1} - I_{3}$

$I_{3} - I_{4}$

Write - After - Read (WAR): Anti - dependence

$I_{1} - I_{2}$

$I_{1} - I_{3}$

$I_{3} - I_{4}$

$I_{4} - I_{1}$

$I_{4} - I_{2}$

Total dependencies $(WAW,RAW,WAR) = 1 + 5 + 5 = 11.$

0
In the S3 option, it asks if anti-dependency always creates the stalls and not if it can resolve the stalls as well using register renaming. If we focus only on the stalls creation, then anti-dependency always creates stalls.
Anti Dependence =============== Write After Read Dependencies

S1      I2: MUL R7, R1, R3

I5: MUL R7, R8, R9

in this there is Write After Write dependencies Also called Output Dependencies

So, s1 is false

S2  I2: MUL R7, R1, R3

there is case in which R3 is written First By I4

and  then after R3 is read by I2  which is wrong thats why it is Write after Read Dependencies

so, S2 is True

S3 is wrong Because  Anti-dependence can be overcome in pipeline using register renaming.

edited
0

So what is the answer for statement-3 I mean which dependancy always creates one or more stall cycles?

0
@arjun

I2 : Write r1

In WAR, there is a stall because if I2 finishes before I1 , I1 will read wrong value.

Now, I want to know when will this happen, even if I1 is large, it will occupy the stage and I2 can't get ahead of I1.

Please give any example where  second instruction finished before  1st instruction.

In S3 its asked : Within an instruction pipeline an anti-dependence always creates one or more stalls.

Here it is not asked wether can we avoid it or not ? So according to me its true but is heavily dependent on how the instruction cycle is designed for different instructions and what's the order of instructions (whether the re-ordering has been done or not) :

One reason : Different instructions having different instruction cycle.

For eg:

 1 2 3 4 5 6 SW r1,0(r2) IF ID EX MEM1 MEM2 WB ADD r2,r4,r3 IF ID EX WB

In this situation there’s a WAR data hazard, and for it to even happen we’re using different instruction cycle for different instructions, dividing memory phases into two cycles and then also we are using split register file. So WAR and WAW are dependent on how the pipeline is designed and different instructions have different cycle.

Another reason : Out of order execution :

Therefore, S3 is wrong because anti-dependence only creates stalls when different instructions have different instruction cycle or out of order execution is being applied and not ‘always’ .

S1 is output dependency .

S2 is anti dependency.

edited

## Related questions

1
19.1k views
Consider the following reservation table for a pipeline having three stages $S_1, S_2 \text{ and } S_3$. $\begin{array}{|ccccc|} \hline \textbf{Time} \rightarrow \\\hline & \text{1}& \text{2} & \text{$3$} & \text{$4$} & \text{$5$} \\\hline \textbf{$S _1$} & \text{$ ... $}\\\hline \textbf{$S _3$} & & & \text{$X$} & \\\hline \end{array}$ The minimum average latency (MAL) is ______
Consider a machine with a byte addressable main memory of $2^{20}$ bytes, block size of 16 bytes and a direct mapped cache having $2^{12}$ cache lines. Let the addresses of two consecutive bytes in main memory be $(E201F)_{16}$ and $(E2020)_{16}$. What are the tag and cache line addresses ( in hex) for main memory address $(E201F)_{16}$? $E, 201$ $F, 201$ $E, E20$ $2, 01F$