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

in delayed branching solution it is the responsiblilty of the compiler to find the suitable independent instruction to fill the delayed slot so that it wont affect the normal execution. if compiler is unable to find any it will put NOP instruction once the branch is resolved fall through path first instruction or taken path first instructution is executed ..

---

The compiler just gives SOME INDEPENDENT INSTRUCTION TO EXECUTE for more read Deepak Poonia SIr's answer below

---

References : Carl Hamcher 

In the delayed branch technique, the instruction located immediately after the branch instruction is executed whether the branch condition is satisfied or not.

==>The compiler fills the Branch Delay Slot  with a useful instruction that needs to be executed regardless of the branch outcome.

==> If no independent instruction can be scheduled by the compiler, a NOP (No-Operation) instruction is placed in that slot.

==> Because fetching continues sequentially into the delay slot before the branch target address can update the Program Counter ($PC$), the instruction following the conditional branch in memory is executed in all cases (whether the branch evaluates to true or false).

Reference : Wikipedia 

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

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.

 

---

@JAINchiNMay if no such instruction is found a NOOP instruction is inserted.

https://www.techtarget.com/whatis/definition/no-op-no-operation

Answer 2

Delayed branching is a solution to handle the control hazards. 

Delayed Branching Idea: Just give the CPU 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 

Comments

WOWW

 

---

goku4199

 Why Option B is not correct :

==> Because "fall-through path" refers to the entire sequential sequence of instructions executed if the branch condition is false . If the branch is true (taken) , control jumps to the target address, so subsequent instructions in the fall-through path are not executed—only the single instruction in the delay slot immediately following the branch is executed.

---

And for Option C ) it is not true because if the condition evaluates to false not taken, the taken-path target instruction is skipped entirely and never executed.

Answer 3

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

Answer 4

I found some useful resource, but yeah, it's confusing. Deepak Sir's answer is much helpful.

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

Answer 5

img source: carl hamacher

a technique to reduce the penalty for branch instructions is Delayed branching

The location that follows a branch instruction is called the branch delay slot, the compiler attempts to find a suitable instruction to occupy the delay slot (for eg add is inserted below the branch instruction), one that needs to be executed even when the branch is taken.

Instruction Ij+1 is fetched only if the branch is not taken.

branching takes place one instruction later than where the branch instruction appears in the instruction sequence. This technique is called delayed branching.

therefore in the question as said  irrespective of whether the condition evaluates to true or false,

the instruction following the conditional branch instruction in memory is executed.

Option A