GATE CSE 2008 | Question: 77

Question

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 \leftarrow R7 + R8$

I2: Sub $R4 \leftarrow R5 – R6$

I3: ADD $R1 \leftarrow R2 + R3$

I4: STORE Memory $[R4] \leftarrow R1$

     BRANCH to Label if $R1 == 0$

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

• A. I1
• B. I2
• C. I3
• D. I4

Comments

#plz give a link?

---

Delayed Branching- this technique says that execute some meaningful instruction which is independent of other instructions before taking the branch to avoid stall cycle in the pipeline
Here I4 instruction says that "move the content of the register R1 into some main memory location whose address is stored in the register R4.
Here instruction I2 cannot be move after branch otherwise memory location stored in register R4 will get change for the instruction i4 and may throw some error while executing I4.

---

No re arrangement no mop substitute so I4 instruction occupy delay

---

Delay bracndhing explained

https://gateoverflow.in/43487/gate-cse-2008-question-77?show=409507#a409507

Answer 1

Answer is (D) I4. The STORE instruction can be moved below the conditional branch instruction. Whether the branch is taken or not, STORE will be executed as the next instruction after conditional branch instruction, due to delayed branching.

Here, I3 is not the answer because the branch conditional variable R1 is dependent on it. Same for I1. Similarly, I4 has a dependency on I2 and hence I2 must be executed before I4.

Answer 2

Delay  Branching in simple terms

imagine you're following a set of instructions in a recipe. Sometimes, the recipe might give you a choice like "If the vegetables are fresh, do this step. If not, skip to the next step." Now, let's relate this to a computer's way of working..

In a computer, there's something called a pipeline that helps it process tasks faster. It's like an assembly line in a factory, where different steps are done one after another to make something. But sometimes, the computer encounters a step where it's not sure what to do because it depends on something else, like our recipe example.

To make things efficient, the computer can sometimes find steps that are safe to do no matter what the uncertain part is. It's like finding an instruction in the recipe that you can always follow regardless of whether the veggies are fresh or not.

Now, when the computer comes across a point where it's not sure because of a "choice" (like our fresh veggies decision), it starts working on the step that comes right after that uncertain point. This is like you starting to do the next recipe step without waiting to see if the veggies are fresh or not.

And here's the cool part: the computer doesn't need to worry about the choice anymore. Whether the veggies are fresh or not, it already started the next step which is safe to do anyway. So, it keeps working smoothly without having to stop and think too much about the uncertain choice, just like you keep going with the recipe without worrying about the veggies.

This way, the computer can keep its pipeline busy and be more efficient, just like you can keep making progress in your recipe by doing the steps that don't depend on the uncertain part.

if it is helpfull upvote it !

Answer 3

In the I2 instruction, register R4 takes the value as R5-R6. Instruction I4 stores the R1 register value in the address stored in R4(which we calculate from I2). If the flow is I1 > I3 > I4 > branch > I2, when executing I4 we won’t have the address so error. The only possible flow is I1 > I2 > I3 > branch > I4,
 

This can be pictorially represented as a 5 stage pipeline. Here, I am assuming there is also a follow-up instruction I5 for generality

I1	I1	I1	I1	I1	I1
	I2	I2	I2	I2	I2	I2
		I3	I3	I3	I3	I3	I3
			B	B	B	B	B	B
				I4	I4	I4	I4	I4	I4
					I5	I5	I5	I5	I5	I5

 

I1	I1	I1	I1	I1	I1
	I2	I2	I2	I2	I2	I2
		I3	I3	I3	I3	I3	I3
			I4	I4	I4	I4	I4	I4
				B	B	B	B	B	B
						NOP	I5	I5	I5	I5	I5

Comparing both the images, in the first image we observe that by placing I4 in the slot after the branch instruction(depicted as B) we are utilizing what would otherwise be filled with NOP(as in the second image). Clearly, one extra cycle is required in the second image as branch decision is taken usually after the 3^rd stage.