GATE IT 2006 | Question: 78

Question

A pipelined processor uses a $4-$stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement $X = (S - R * (P + Q))/T$ is given below. The values of variables $P, Q, R, S$ and $T$ are available in the registers $R0, R1, R2, R3$ and $R4$ respectively, before the execution of the instruction sequence.
$$\begin{array}{ll} \text{ADD} & \text{R5, R0, R1} && \text{; R5 ← R0 + R1} \\  \text{MUL} & \text{R6, R2, R5} && \text{; R6 ← R2 * R5} \\   \text{SUB} & \text{R5, R3, R6} && \text{; R5 ← R3 - R6} \\  \text{DIV} & \text{R6, R5, R4} && \text{; R6 ← R5/R4} \\ \text{STORE} & \text{R6, X} && \text{; X  ← R6} \\ \end{array}$$
The number of Read-After-Write (RAW) dependencies, Write-After-Read( WAR) dependencies, and Write-After-Write (WAW) dependencies in the sequence of instructions are, respectively,

• A. $2, 2, 4$
• B. $3, 2, 3$
• C. $4, 2, 2$
• D. $3, 3, 2$

Comments

IT ONLY TALKS ABOUT DEPENDANCY SO PIPELINE INFORMATION DOES NOT MATTER IE., THE FIRST PARAGRAPH MAKES NO DIFFERENCE ONLY SEE THE INSTRUCTIONS AND THE QUESTION BELOW IT

---

Visual 

---

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

Watch Detailed Video Solution   

Answer 1

(C) is the correct option for this question:

RAW

1. I1 - I2 (R5)
2. I2 - I3 (R6)
3. I3 - I4 (R5)
4. I4 - I5 (R6)

WAR 

1. I2 - I3 (R5)
2. I3 - I4 (R6)

WAW

1. I1 - I3 (R5)
2. I2 - I4 (R6)

Comments

consider, instead of 4 stage , 5 stage pipeline is used then

RAW will be 6,

The 4 which are mentioned and

I1- I4

I2- I5

 

Correct me, if i am wrong

---

Is there any difference between dependency and hazard? If I remember correctly, dependency is what‘s been calculated in this question, but hazards will not be the same. They will be only those dependencies that are actually affecting our pipeline (i.e those dependencies which are causing stalls).

Are my concepts wrong? Can anyone please clarify?

---

Yes you are right

Answer 2

C : as RAW dependency is 4.

Answer 3

Ans

Answer 4

Instruction sequence (rewrite clearly)

Instr	Instruction	Registers READ	Registers WRITTEN
I1	ADD R5, R0, R1	R0, R1	R5
I2	MUL R6, R2, R5	R2, R5	R6
I3	SUB R5, R3, R6	R3, R6	R5
I4	DIV R6, R5, R4	R5, R4	R6
I5	STORE R6, X	R6	X (memory)

• I1 → I2 :

  • I1 writes R5, I2 reads R5 → ✅ RAW

• I2 → I3 :

  • I2 writes R6, I3 reads R6 → ✅ RAW

• I3 → I4 :

  • I3 writes R5, I4 reads R5 → ✅ RAW

• I4 → I5 :

  • I4 writes R6, I5 reads R6 → ✅ RAW

✅ Total RAW = 4 

 

 

• I2 reads R5, I3 writes R5 → ✅ WAR

• I3 reads R6, I4 writes R6 → ✅ WAR

✅ Total WAR = 2

 

 

• I1 writes R5, I3 writes R5 → ✅ WAW

• I2 writes R6, I4 writes R6 → ✅ WAW

✅ Total WAW = 2