GATE CSE 2008 | Question: 76

Question

Delayed branching can help in the handling of control hazards

For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false,

• A. The instruction following the conditional branch instruction in memory is executed

• B. The first instruction in the fall through path is executed

• C. The first instruction in the taken path is executed

• D. The branch takes longer to execute than any other instruction

Comments

You can have a read

https://www.cs.uaf.edu/2000/fall/cs301/notes/notes/node113.html

---

@Arjun sir what is the difference between option 1 and option 2 as both will excute the instruction just after the branch instruction..

---

Fall through path depends on the condition to be evaluated whereas chosen delayed instruction will be independent of the condition i.e it must be executed. Delayed instructions are used for just filling the stalls.

Answer 1

Answer is A. In order to avoid the pipeline delay due to conditional branch instruction, a suitable instruction is placed below the conditional branch instruction such that the instruction will be executed irrespective of whether branch is taken or not and won't affect the program behaviour.

Comments

sir , i am not getting the meaning of " one branch delay slot" plz help..

---

Usually after a branch instruction nothing can be put in a pipeline as branch can be either "yes" or "no" and correspondingly the next instruction can change. So, branch delay slot is a technique where we put an instruction which have no dependence on the branch condition to be executed just after the branch instruction. In this way "pipeline" would be used more efficiently.

Currently architectures use branch prediction where either "yes" or "no" is predicted by hardware mechanism and correspondingly instructions are pipelined. If prediction goes wrong, the pipeline is flushed and whole thing re-executed.  

---

Sir,

Please explain option B and C in question 76. I want to know what is the meaning or difference between 'fall through path' and 'taken path'.

This diagram http://cellperformance.beyond3d.com/articles/2006/04/background-on-branching.html depicts the two path created by branch instruction.

---

On a conditional jump, the path on condition success path is the taken path and the condition failed path (not a jump) is the fall through path.

---

@Arjun sir  could u plz tell me why i2 wont be the answer .because it is also independent instruction.Any independent instruction which is not affected by branch is put in that place. right? assume the qstn says 2 branch delay slot is there. what will be the ans then?  i2 &i4 ?

---

I2 is not... I2 is dependent on I4.... I2 is writing value of R4,which is used by I4

---

What is the meaning of option a in ques 76?

---

@Pyuri So, I4 is dependent on I2.

@Khush Even though that instruction is below a branch instruction, it will be executed (completely) unlike a normal case where only when the branch target is known further instructions are executed.

---

Sir, meaning of fall through path written in the link provided by ram sharma1 is different frm ur explanation.

Which one is true??

---

what is different?

---

But u said condition failed path is fall through path...and as shown in pic (in if part) when condition is true fall through path address. 

Fall through path is if branch is failed the ins. Address processor takes is fall through path address.right??

 

---

well, see the change in condition on the right side. The condition is complemented there- this is needed to avoid one more JMP instruction. I was referring to condition in assembly code (right side one).

---

I couldn't understand the right side of tht protion.

I dnt evn knw wht beq n cr0 is.

---

in if we were doing != condition.

In assembly it became beq- branch on equal. So, NOT EQUAL became EQUAL here with a JUMP. The semantics of the code remains the same though the condition is reversed.

---

@Arjun, could you plz explain the difference between option(1) and option(2) ?

---

@arjun sir could you plz explain why option(b) is nt true ?
can we place instructions executed by true condition just after conditional branch instruction that is in taken path just  after conditional branch instruction.

---

I am not able to get any of the options. What i have read id that we exacute an instruction that would be anyways executed, independent of the branch condition .For eg in quest no. 77) , I4 would be anyways expected , so this is the instruction we execute after branch (not in order) to avoid branch penalty.

as for this question,
a) if we execute instruction following conditional branch, it would be same a snormal flow of thw program and may case branch penalty if branch condition evaluates to false

b) as per the suggested article, i ma not able to understand the concept of fall through path. in first case it says condition on evaluation of if as true as fall through  and its different for the other one.

c)  first instruction in taken path is same as option a)
 
d) its wrong because branching will take same time to execute

please help me clear the concept.

---

@aayushi plzz see my ans i think it ll definetly helps u and after that if u have any doubt then  can tell me.

---

fall through path depend on instruction.If condition is false it is in fall through path
But here question said, irrespective of condition is true or false
that is why A) is answer

See, it is called delayed conditional branch because it first execute instruction after the following that delayed branch and then condition is evaluated.Condition is evaluated lately, that is why it is called delayed branching

---

Example to Understand what is fall through path:-

Branch instructions divide the execution path in two paths, the target path and the fall-through path. The address of the first instruction on each path is referred to as target address and fall-through address

Here 102 is fall through address and 500 is target address(target address is the address we want to branch).

If the condition evaluates to true then we go to target address i.e 500 otherwise we go to fall through address

   101       JZ 500

   102       Next Instruction

        .

        .

        .

 500     HLT

---

@arjun sir according to you -branch delay slot is a technique where we put an instruction which have no dependence on the branch condition to be executed just after the branch instruction.

so why I2 cannot be the ans as it is not dependent on the branch condition???

Plz clear my doubt.

---

que. 76.  but even if condition is true or false the next instruction after the condition will definitely going to be executed if iam right?? the first instruction of fall through path will execute??

---

Let's consider a program sequence such that there is no instruction that can be put after the branch instruction.

What happens then?

---

@Vishal Things will happen just like given in this question-> GATE CSE 2006 | Question: 42 - GATE Overflow

It will fetch new instructions only after the branch outcome is known.

---

From the image uploaded by @khushtak

It states “ The address of the first instruction on fall through path is referred to as fall-through address. The fall-through address represents the instruction just after the branch.”

Isn’t the following address of branch instruction is fall-through address?

Then Option B is also correct.

Please correct me where am I going wrong.

---

mani312

NO!

the main difference in Option A and Option B is that.

fall through path is that path which will be executed only when the condition fails!  but in the question it is clearly asking that , what will surely happen irrespective of the condition check. so the only correct answer is  option A.

---

@Arjun sir

But what if any suitable instruction is not present in the program ,
then no instruction will be executed till the deciding stage/phase of condition (stalling),
and then if the branch occurs the next instruction will not execute.

 

Answer 2

reference pattrerson book "the hardware software interface" 3^rd edition page no 382 

Answer 3

Delayed branching is a solution to handle the control hazards. 

Delayed Branching Idea: Just give him something to execute…

Detailed Video Explanation: Delayed Branch Solution for Control Hazards

One way to maximize the use of the pipeline, is to find an instruction that can be safely exeucted 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. How do we know? The compiler promised it would be safe.

When the program was compiled, the compiler looked at each branch instruction, and tried to find something that could be safely executed, whether we take the branch or not.

https://www.cs.umd.edu/users/meesh/cmsc411/website/projects/branches/delay.html 

Delayed Branching - define the branch such that one (or two) instruction(s) after the branch will always be executed.

Compiler automatically rearranges code to fill the delayed-branch slot(s) with instructions that can always be executed. Instructions in the delayed-branch slot(s) do not need to be flushed after branching. If no instruction can be found to fill the delayed-branch slot(s), the a NOOP instruction is inserted.

https://www.cs.uni.edu/~fienup/cs240f03/lectures/lec21_11-4-03_control_hazards.htm 

Branch delay slots. The ISA is constructed such that one or more instructions sequentially following a conditional branch instruction are executed whether or not the branch is taken. The compiler or assembly language writer must fill these branch delay slots with useful instructions or NOPs (no-operation opcodes). This solution doesn't extend well to deeper pipelines, and becomes architectural baggage that the ISA must carry into future implementations. 

https://people.engr.tamu.edu/djimenez/taco/utsa-www/cs5513-fall07/lecture4.html 

https://www.cs.umd.edu/~meesh/411/CA-online/chapter/handling-control-hazards/index.html