GATE CSE 2015 | Set 3 | Question: 47

Question

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?

• A. Only S1 is true
• B. Only S2 is true
• C. Only S1 and S3 are true
• D. Only S2 and S3 are true

Comments

Question is not even asking for finding no of clock cycles for all instructions to complete,so why do you even need to know how many stages does this pipeline have?

---

Since an anti-dependence never causes stalls in an in-order pipeline, and is completely bypassed without stalls in an OoO pipeline using renaming, the word "always" in S3 makes it undeniably false

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

Answer 1

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.

Comments

Lakshman Patel RJIT

in you example...how there is RAW dependency between

I1-I4 and I2-I4 ??

Both R1 and R7 are not read by i4..

 

I1: ADD R1, R2, R3

I2: MUL R7, R1, R3

I4: ADD R3, R2, R4

 

---

there are the following dependencies please correct me if wrong 
therefore total = 5 dependencies 

---

@Sarang_Gajare

just 1 missed; $WAR:$ $I1 \rightarrow I4$

Answer 2

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.

Comments

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

---

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

Answer 3

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.

Answer – B

 

Answer 4

Alternative Name For Each Dependancy :-

1. RAW -> True Dependancy 

2. WAW, WAR }-> false Dependancy 

3. WAR -> Anti Depndancy 

4. WAW -> OutPut Dependancy 

Each of alternative Name have story behind it eigther You can Mug up or Watch Go Classes @deepak Poonia @GO Classes Lectures to really understand story

 

Answer 5

Ans

Answer 6

S1: Anti-dependence between I₂ and I₅

• I₂ reads R1 and R3, writes R7.

• I₅ writes R7, but I₂ does not read R7. → No WAR here. S1 is false.

S2: Anti-dependence between I₂ and I₄

• I₂ reads R3.

• I₄ writes R3. → Later instruction (I₄) writes to a register (R3) that earlier instruction (I₂) reads. → This is a WAR. S2 is true.

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

• Not always. Anti-dependence can often be eliminated by register renaming.

• So it does not always cause stalls. S3 is false.

✅ Final Answer

Only S2 is correct.