IAE Academy

GATE 2024 CS2 Q.31: solution and answer

GATE 2024 · CS2Q.31 · 1 mark · MSQ

An instruction format has the following structure:

Instruction Number: Opcode destination reg, source reg-1, source reg-2

Consider the following sequence of instructions to be executed in a pipelined processor:

I1: DIV R3, R1, R2
I2: SUB R5, R3, R4
I3: ADD R3, R5, R6
I4: MUL R7, R3, R8

Which of the following statements is/are TRUE?

  1. (A)

    There is a RAW dependency on R3 between I1 and I2

  2. (B)

    There is a WAR dependency on R3 between I1 and I3

  3. (C)

    There is a RAW dependency on R3 between I2 and I3

  4. (D)

    There is a WAW dependency on R3 between I3 and I4

See the question in the paper
GATE 2024 CS2 question 31Tap to open full size

Answer and solution

ANSWER

The correct answer is Option A only — MSQ answer: A.

Official answer: ASource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

  1. List every access to R3 across the four instructions, in program order, marking each as a read or a write (destination = write, source = read):

    I1: DIV R3, R1, R2   ->  writes R3
I2: SUB R5, R3, R4   ->  reads  R3 (source reg-1)
I3: ADD R3, R5, R6   ->  writes R3
I4: MUL R7, R3, R8   ->  reads  R3 (source reg-1)

  2. I1 -> I2 (Statement A): I1 writes R3 and I2, which comes later in program order, reads that same R3 as an operand. A later read of a value an earlier instruction produces is exactly a RAW (read-after-write / true) dependency. So Statement A is TRUE.

  3. I1 -> I3 (Statement B): A WAR (write-after-read) dependency on a register requires an earlier instruction to read it and a later instruction to write it. I1 only writes R3 — it never reads R3 — so the I1-I3 pair cannot be WAR on R3 (it is in fact WAW, since both write R3). Statement B is FALSE.

  4. I2 -> I3 (Statement C): I2 reads R3 (as SUB's source reg-1) and I3, later in program order, writes R3. A later write following an earlier read of the same register is the definition of a WAR (anti-) dependency, not RAW. Statement C mislabels this as RAW, so it is FALSE.

  5. I3 -> I4 (Statement D): A WAW dependency on a register requires both instructions to write it. I3 writes R3, but I4 only reads R3 (as MUL's source reg-1) — I4's destination register is R7, not R3. Since I4 never writes R3, there is no WAW dependency on R3 between I3 and I4. Statement D is FALSE.

  6. Only Statement A correctly names a true dependency on R3. Since this is an MSQ, the final answer is exactly the option(s) verified true: A.

KEY IDEA

To classify a data hazard between two instructions sharing a register, first tag every access to that register, in program order, as a read (source) or a write (destination): earlier-write/later-read = RAW (true), earlier-read/later-write = WAR (anti), and earlier-write/later-write = WAW (output). Only a register that is genuinely written by BOTH instructions can be WAW, and only one genuinely read-then-written can be WAR — mislabeling one for the other is the entire trap in this question.

WATCH OUT FOR

Assuming that because two instructions both "touch" the same register in some order, any of RAW/WAR/WAW could apply interchangeably — e.g. calling the I2(reads R3)→I3(writes R3) pair a RAW dependency (as option C does) instead of correctly recognizing it as WAR, or calling I1(writes R3)→I3(writes R3) a WAR (as option B does) instead of WAW. The fix is to always ask two separate yes/no questions per pair — "does the earlier instruction read or write this register?" and "does the later instruction read or write it?" — rather than pattern-matching on which instructions appear first.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 12 Pipelining questions, with notes

More Pipelining questions