Delayed branching can help in the handling of control hazards The following…

2008

Delayed branching can help in the handling of control hazards The following code is to run on a pipelined processor with one branch delay slot: 

I1: ADD R2←R7+R8
I2 : SUB R4← R5-R6
I3 : ADD R1← R2+R3
I4 : STORE Memory [R4]←[R1]
BRANCH to Label if R1== 0

Which of the instructions I1, I2, I3 or I4 can legitimately occupy the delay slot without any other program modification?

Answer: D. I4 — An instruction placed in a branch delay slot always executes exactly once, regardless of whether the branch is taken, but it is relocated to run immediately…

  1. A.

    I1

  2. B.

    I2

  3. C.

    I3

  4. D.

    I4

Attempted by 28 students.

Show answer & explanation

Correct answer: D

An instruction placed in a branch delay slot always executes exactly once, regardless of whether the branch is taken, but it is relocated to run immediately after the branch instruction rather than at its original position before the branch -- which may shift it several instruction-slots later in program order, depending on how far before the branch it originally sat. Moving an instruction into that slot without inserting a NOP or duplicating code is legitimate only if (a) no instruction that now runs ahead of the branch depends on a register the moved instruction produces, and (b) the moved instruction does not itself produce the register the branch condition tests -- otherwise the branch would evaluate on a stale value.

Application: Check each candidate against that rule.

Candidate

Still executes before the branch after the move

Conflict introduced

I1 (produces R2)

I2, I3, I4

I3 (ADD R1<-R2+R3) still runs ahead of the branch and needs R2 at that point, but I1 has not run yet -- R2 is stale.

I2 (produces R4)

I1, I3, I4

I4 (STORE Memory[R4]<-[R1]) still runs ahead of the branch and needs R4 at that point, but I2 has not run yet -- R4 is stale.

I3 (produces R1)

I1, I2, I4

The BRANCH itself tests R1, and R1 is exactly what I3 produces. Delaying I3 past the branch makes the branch evaluate its own condition on a value that has not been recomputed yet.

I4 (consumes R4, R1; writes only to memory)

I1, I2, I3

Both R4 (from I2) and R1 (from I3) are already produced by the instructions still ahead of the branch, and I4 writes to memory only, never to a register anything else reads. No conflict.

Cross-check: the only candidate that (i) is not itself a dependency for any instruction still scheduled ahead of the branch and (ii) has both of its own operands already produced by the time it runs in the delay slot is the one that reads R4 and R1 and writes only to memory. That is the unique instruction satisfying both conditions of the rule stated above.

Every other candidate is disqualified because some instruction still ahead of the branch (or the branch's own condition test) needs a register value that the moved instruction alone was responsible for producing.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…