GATE CS 2015 Set 3 Q.57 (CS Q.47): Instruction Pipelining and Hazards

Consider the following code sequence having five instructions $I_1$ 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_1$ and $I_5$
S2: There is an anti-dependence between instructions $I_2$ and $I_4$
S3: Within an instruction pipeline an anti-dependence always creates one or more stalls

Which one of above statements is/are correct?

Only S1 is true

Only S2 is true

Only S1 and S3 are true

Only S2 and S3 are true

Official answer and solution

Official answer: B
From: Official GATE 2015 answer key

Solution

Identify Read-After-Write, Write-After-Read, and Write-After-Write dependencies across the instruction sequence.

Instructions format: OP Destination, Source1, Source2

$I_1$ : ADD R1, R2, R3 (reads R2, R3; writes R1)
$I_2$ : MUL R7, R1, R3 (reads R1, R3; writes R7)
$I_3$ : SUB R4, R1, R5 (reads R1, R5; writes R4)
$I_4$ : ADD R3, R2, R4 (reads R2, R4; writes R3)
$I_5$ : MUL R7, R8, R9 (reads R8, R9; writes R7)

An anti-dependence (Write-After-Read, WAR) occurs between instruction $I_j$ and subsequent instruction $I_k$ ( $j < k$ ) if $I_j$ reads a register that $I_k$ writes.

Evaluate statements:

S1: Anti-dependence between $I_1$ and $I_5$ . $I_1$ reads R2, R3; $I_5$ writes R7. No register conflict exists. Statement S1 is False.
S2: Anti-dependence between $I_2$ and $I_4$ . $I_2$ reads R3; $I_4$ writes R3. Since $I_2$ reads R3 before $I_4$ writes to R3, there is a WAR anti-dependence on R3. Statement S2 is True.
S3: In standard in-order pipelined processors, operands are read in the ID stage while results are written in the later WB stage; hence reads naturally complete before later instructions write back, so anti-dependencies do not cause stalls in an in-order pipeline. Statement S3 is False.

Thus, only statement S2 is true (Option B).

Final answer

Common trap

Confusing true data dependencies (RAW, which can cause stalls) with anti-dependencies (WAR, which are hazards only in out-of-order execution).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 57 of 65, printed as CS Q.47
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source