The Gateway to Computer Science Excellence
+29 votes
4.3k 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
in CO and Architecture by Veteran (105k points)
retagged by | 4.3k views
+24

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.

0
S1 : Output Dependency

2 Answers

+39 votes
Best answer

Answer should be (B).

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.

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

add R1,R2,R3 (R1<-R2+R3)

add R2,R4,R5

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?
+6
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
+10

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..
+6
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 ?
+8
what's issue there? WAW is not anti-dependence. It is output dependence.
0

I2I2: MUL R7, R1, R3

I4I4: ADD R3, R2, R4

 

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.???
+5
@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

+10

Very Nicely Explaned !

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

@jatin khachane 1

That is a good video.

Thanks.

0

@Arjun sir, please verified this 

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

+15 votes
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

      I4: ADD R3, R2, R4

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.
by Loyal (6.9k points)
edited by
0

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

0
@arjun

I1: Read r1

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.
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,644 questions
56,505 answers
195,555 comments
101,051 users