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

good to read - https://www.geeksforgeeks.org/computer-organization-and-architecture-pipelining-set-2-dependencies-and-data-hazard/

---

Thanks for giving answer in a very short manner. There was always confusion,but now all clear.

---

1. Flow Dependency (Read After Write):

   • Correct. Flow dependency, also known as true dependency or read-after-write dependency, occurs when an instruction depends on the result of a previous instruction. The data "flows" from the write of one instruction to the read of another.

2. Anti Dependency (Write After Read):

   • Incorrect. Anti dependency, also known as output dependency, occurs when the write of one instruction depends on the read of another instruction. It is related to the ordering of instructions that write to a register and instructions that read from the same register. It is sometimes called write-after-read (WAR) dependency.

3. Output Dependency (Write After Write):

   • Incorrect. Output dependency, also known as write-after-write dependency, occurs when two instructions write to the same destination. It is a situation where the order of write operations matters. In a pipeline, for example, if the second instruction writes to a location before the first instruction completes its write, the final result might be incorrect.

To summarize:

• Flow Dependency (Read After Write): Data flows from a write to a subsequent read.
• Anti Dependency (Write After Read): Ordering issue where a write depends on a prior read.
• Output Dependency (Write After Write): Ordering issue where two writes compete for the same destination.

It's important to note that dependencies can lead to hazards in pipelined processors, affecting the performance and correctness of the execution.

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

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

---

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.

---

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

 

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