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

@V_Sarath_Chandra

Yes that should work, but the question mentions that the "code is to be run on a pipelined processor with one branch delay slot". So only I4 is safe.

---

Wow! That's called perfect analysis.

you explained every Read After Write dependencies which matter's n causes hazards.

Keep up the good work buddy!!

 

Appreciate ur efforts!! @pm45420

---

Read Highlighted part :

Answer 1

What is Delayed Branching ?
One way to maximize the use of the pipeline, is to find an instruction that can be safely executed whether the branch is taken or not, and execute that instruction. So, when a branch instruction is encountered, the hardware puts the instruction following the branch into the pipe and begins executing it, just as in predict-not-taken. However, unlike in predict-not-taken, we do not need to worry about whether the branch is taken or not, we do not need to clear the pipe because no matter whether the branch is taken or not, we know the instruction is safe to execute.

Moving $I_1$ after branch

• $I1$ is updating the value of  $R2$
• $R2$ which is used to determine branch condition $R1$
• Value of $R2$ is available after branch
  $\Rightarrow$ Cannot be moved

Moving $I_3$ after branch

• value of $R1$ is computed in this instruction
• $R1$ is the branch condition
  $\Rightarrow$ Cannot be moved

Moving $I_4$ after branch

• $I4$ is simple store instruction used to store R1 in memory

• program execution will have no effect if this is placed after conditional branch
  $\Rightarrow$ Can be moved

Moving $I_2$ after branch

• It update the memory location to place the storing of conditional branch instruction $R1$
• If moved after branch , when compiler reaches $I4$ program execution will stop
  $\Rightarrow $ Cannot be moved

Hence, option D is answer.

Comments

I understood the answer ,Does this simply means we have to use RAW,WAR,WAW concepts? Or they are irrelevant here.

---

Replace the link with this https://web.archive.org/web/20150810190535/http://www.cs.umd.edu/class/fall2001/cmsc411/projects/branches/delay.html

---

I understand what is delayed branching, and that location(s) following a branch statement is(are) called branch delay slot(s). But, I can’t understand the logic behind using the word ‘delay’. Is there indeed any delay involved while executing an instruction, and/or a branch instruction when we use delayed branching, or, similar to the the naming convention of data hazards (i.e., naming the data hazard by the ordering in the program that must be preserved by the pipeline), we name it delayed branching because it might help remove the delay caused by branch statements in a normal pipeline without such facilities? Any help is highly appreciated.

Answer 2

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 3

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 4

You should know about Delayed Branching concept first for such type of problem. It is the concept where in delay slot(the instruction space following branch instruction) we insert that instruction which is always executed, whether branch is taken or not.

Hence, let's consider branch instruction as I_j and the instruction following branch instruction as I_j+1, so in delay slot, we can't place I_j+1 , as it may be discarded when branch is taken, hence we can place instruction preceding to branch instruction in delay slot, So as per above program I4 should be placed in Delay Slot.

So remember in Delayed branching, we are not logically changing order of instructions, only branch instruction is executed one instruction later(Delayed).

Comments

yes, good one. This answer will clear the doubt that why can’t we place $I_{2}$ in the delay slot. It is because it will change the logic of the program.

Answer 5

we have 5 inst. and let pipeline stages will be 5.so we can process all the inst. in (n+k-1)=(5+5-1)=9 clock cycle.

if in 9 clock cycle we are able to arrange in such a way that the dependancy will not violate.but the order may be different.  then it will be ok.

I1 CANT BE AFTER I3 (DUE TO DEPENDENCY ON R2)

I2 CANT BE AFTER I4 (COZ  I4 REQUIRE MEM[R4] OF I2)

I3 CANT BE AFTER I4 (DUE TO DEPENDENCY ON R1)

SO  I1 THEN I3

                      I2,I3 THEN I4

=>I4 CANT BE BEFORE I1,I2,I3.

=>LET I1 FIRST(5 CLOCK)

           I2(1 CLOCK)

           I3(1 CLOCK)

           BRANCH(1 CLOCK)

           I4 (1 CLOCK)

TOTAL 9 CLOCK AND THAT IS WHAT WE WANT

Answer 6

It can't be l1 or l3, because directly or indirectly they are taking part in the branching decision. Now we can have both l2 and l4 after the branching decision statement and  the order of I2 and I4 matters because in I2 we are getting the final value in register R4 and in instruction we are saving contents of R1 in memory whose address is stored in the register. So If we made I2 to be the instruction after branch then the value in the first loop itself the value stored in memory location whose address is stored in R4 would be wrong because it actually should have been updated first by R5-R6.So  I4 is correct. So (D) is correct option.