GATE IT 2007 | Question: 39

Question

Data forwarding techniques can be used to speed up the operation in presence of data dependencies. Consider the following replacements of LHS with RHS.

1.  $R1→ Loc, Loc→ R2 \quad ≡  R1→ R2, R1 → Loc$
2.  $R1→ Loc, Loc→ R2 \quad ≡ R1→ R2$
3.  $R1→ Loc, R2 → Loc \quad ≡ R1→ Loc$
4.  $R1→ Loc, R2 → Loc \quad ≡  R2→ Loc$

In which of the following options, will the result of executing the RHS be the same as executing the LHS irrespective of the instructions that follow ?

• A. i and iii
• B. i and iv
• C. ii and iii
• D. ii and iv

Comments

What does it mean by "irrespective of the instructions that follows"?

Acc to me it mean either we follow lhs or rhs instructions result should be same.

---

@Chhotu data forwarding or operand forwarding/bypassing/short circuiting is a hardware mechanism techniques used to minimize data hazard when data dependency present in program instructions.
according to this technique we can use buffers between the stages to hold intermediate results.
 

---

Just see whose value is in who like for LHS to be equal to RHS we need all R1,R2,Loc in each of the sides to be equal to the corresponding ones of the other side

Answer 1

1. is true. Both $LOC$ and $R2$ are getting the value of $R1$ in $LHS$ and $RHS$.
2. false, because $R2$ gets the correct data in both $LHS$ and $RHS$, but $LOC$ is not updated in $RHS$.
3. is wrong because $R2$ is writing last, not $R1$ in $LHS$, but not in $RHS$.
4. is true. The first write to $LOC$ in $LHS$ is useless as it is overwritten by the next write.

So, answer is (B).

Comments

@vijaycs07,

See , Ex--> (i) R1 has value 5 ,and transfer(store) that value to some memory address(Loc = 3000) 

Now, at some time, suppose a new program or same program only wants that value to load in some register say R2.

This time we didn't load it into R1, because data of R1 will be needed in future .Now, R1 = R2 = 5 = LOC (3000)

RHS is also doing the same thing.

(ii) LHS is saying load 5 in all  , but RHS says, no need of LOC .

So, we are not sure about what LOC contains. IN this statement, there is no role of LOC. so, how can we say LOC contains 5 or any other garbage value.

---

got it thanks :)

---

Gr8 Explanation :)

Answer 2

		Reason
i	✅ Yes	R2 and Loc both get value of R1
ii	❌ No	Loc not updated in RHS
iii	❌ No	Missing second update to Loc
iv	✅ Yes	Loc ends with R2’s value

Correct replacements are i and iv.
Ans: Option B

 

Answer 3

\textbf{Answer: (i) and (iv)}

\section*{Explanation}

The notation is interpreted as follows:

\[
R_1 \rightarrow Loc : \text{Store the contents of register } R_1 \text{ into memory location } Loc
\]

\[
Loc \rightarrow R_2 : \text{Load the contents of memory location } Loc \text{ into register } R_2
\]

\[
R_1 \rightarrow R_2 : \text{Copy the contents of } R_1 \text{ directly into } R_2
\]

The replacements are examined below.

\subsection*{Option (i)}

\[
R_1 \rightarrow Loc,\; Loc \rightarrow R_2
\equiv
R_1 \rightarrow R_2,\; R_1 \rightarrow Loc
\]

LHS:
\[
\begin{aligned}
&Loc \leftarrow R_1,\\
&R_2 \leftarrow Loc
\end{aligned}
\]

After execution,
\[
Loc = R_1,\qquad R_2 = R_1.
\]

RHS:
\[
\begin{aligned}
&R_2 \leftarrow R_1,\\
&Loc \leftarrow R_1
\end{aligned}
\]

Again,
\[
Loc = R_1,\qquad R_2 = R_1.
\]

Both the register and memory contents are identical after execution.

\[
\boxed{\text{Option (i) is correct.}}
\]

\subsection*{Option (ii)}

\[
R_1 \rightarrow Loc,\; Loc \rightarrow R_2
\equiv
R_1 \rightarrow R_2
\]

LHS:
\[
Loc = R_1,\qquad R_2 = R_1.
\]

RHS:
\[
R_2 = R_1,\qquad Loc \text{ remains unchanged.}
\]

If a later instruction accesses memory location \(Loc\), the two executions produce different results.

\[
\boxed{\text{Option (ii) is incorrect.}}
\]

\subsection*{Option (iii)}

\[
R_1 \rightarrow Loc,\; R_2 \rightarrow Loc
\equiv
R_1 \rightarrow Loc
\]

LHS:
\[
Loc \leftarrow R_1,\qquad
Loc \leftarrow R_2.
\]

The second store overwrites the first, so

\[
Loc = R_2.
\]

RHS:

\[
Loc = R_1.
\]

Unless \(R_1 = R_2\), the final memory contents differ.

\[
\boxed{\text{Option (iii) is incorrect.}}
\]

\subsection*{Option (iv)}

\[
R_1 \rightarrow Loc,\; R_2 \rightarrow Loc
\equiv
R_2 \rightarrow Loc
\]

LHS:
\[
Loc \leftarrow R_1,\qquad
Loc \leftarrow R_2.
\]

Final value:
\[
Loc = R_2.
\]

RHS:
\[
Loc \leftarrow R_2.
\]

Again,
\[
Loc = R_2.
\]

The first store is completely overwritten by the second and has no observable effect.

\[
\boxed{\text{Option (iv) is correct.}}
\]

\section*{Final Answer}

The replacements that always preserve the program behavior, irrespective of the instructions that follow, are

\[
\boxed{\text{(i) and (iv)}}
\]