retagged by
21,807 views
46 votes
46 votes

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 by

3 Answers

Best answer
62 votes
62 votes

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.

edited by
18 votes
18 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.
edited by
0 votes
0 votes

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

 

edited by
Answer:

Related questions

70 votes
70 votes
5 answers
1
go_editor asked Feb 16, 2015
40,747 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...
0 votes
0 votes
1 answer
3
Deepak9000 asked Nov 5, 2023
242 views
I have a Self doubt question on Operand Forwarding . The data forwarded should be done in EX-EX stage or Mem-EX ? Which one to follow and when ?Using EX-EX we require les...