GATE CSE 2006 | Question: 42

Question

A CPU has a five-stage pipeline and runs at $1$ GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes $10^9$ instructions out of which $20\%$ are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is: 

• A. $\text{1.0 second}$
• B. $\text{1.2 seconds}$
• C. $\text{1.4 seconds}$
• D. $\text{1.6 seconds}$

Comments

Sir, please correct GO pdf it says 109 instructions instead of 10^9 instructions.

---

Can’t Fetch instruction for the next instruction start at the same clock where branch condition is getting executed at means in 3rd clock branch will execute in first half and in second half next instruction’s fetch will run? Why is it not possible?

---

Shouldn’t we be accounting for 1’st instruction which is going to take 5 stage to execute , and then calculate time taken by rest of the instructions.  

Why have we ignored first execution in this question. ?

Answer 1

Delay slots in the pipeline caused due to a branch instruction is $2$ as after the $3^{rd}$
stage of current instruction (during $4^{th}$ stage) IF of next begins.
Ideally, this should be during $2\text{nd}$ stage.

So, for total no. of instructions = $10^9$ and $20\%$ branch,
we have $0.2 \times 2 \times 10^9 = 4 \times 10^8$ cycle penalty.

Since clock speed is $1\text{ GHz}$ and each instruction on average takes $1$ cycle,
total execution time in seconds will be

$=\dfrac{10^9}{10^9}+4 \times \dfrac{10^8}{10^9}$

$= 1.4$

Correct Answer: $C$

Comments

thank you sir :)

---

Sir,

number of stalls per branch instruction=2

we have 20% branch instructions=$2\times 10^{8}$

therefore stall cycles caused by 20% of instructions=$2\times 2\times 10^{8}$

Execution time=$10^{9}/10^{9}+4\times 10^{8}/10^{9}$=1.4

https://gateoverflow.in/1818/gate2006_42

---

Thanks for the correction :)

---

@Arjun sir I have a silly doubt here 

If each instruction takes one cycle to complete on average 

Does this not imply that we can simply do this ---   No. of instructions * clock cycle/instruction * T_clock    as the number of cycles on an average required for the instruction is given.

In this case the answer could be 1.0 sec.

---

Which formula is being used to calculate the execution time??

---

Execution time in Seconds or Nano-Seconds?

I think options must be in Nano-seconds for value 1.4 to be correct.

---

@Arjun sir

@Ayush Upadhyaya

Here are we considering that branch is always NOT TAKEN.. hence we have to execute all $10^{9}$ instructions

Else if branch would have been taken instructions to execute will be less hence time also

correct me if wrong .

---

@jatin khachane 1-Here the concern is not the branch is taken or not.The concern is the stalls caused when the conditional instructions are fetched.

---

Yes but anyway both cases branch taken or not we stalls happen..but if branch taken then we may skip some instructions hence time will be less..

https://gateoverflow.in/330/gate2013-45

 

---

In this question we have control hazard.right?
because we are having stalls

---

In the GOPDF for 2020, the value is given as $109$ instead of $10^9$. Please fix when you can.

---

Same error for me

---

@arjun sir here one instruction takes takes one cycle so one stage should take 0.2 cycles so why are you considering stall cycles to be 2 it should be 0.4 stall cycles please help me here

---

@Arjun What would have been the stalls and the final answer if it was an unconditional branch ?

---

We have to assume here that branch is always NOT TAKEN, right?? Because, if branch is taken at least once, then all 10^9 wouldn’t be executed, right??

---

@Arjun Sir, what is the significance of this line

The processor stops fetching new instructions following a conditional branch until the branch outcome is known

---

@Gaurav I also have the same doubt

---

@Codered03

because of this line only we will know that how many stall cycles are caused due to the branch.

---

Same doubt why they all take it one clock cycle

That is 0.2 clock cycle

@Gaurav Chaudhari @yashpaneliya

Answer 2

No. of non branch instructions $= 8 \times 10^8$

No. of branch instructions $= 2 \times 10^8$

When the branch condition is evaluated in third stage- first and second stage of pipeline are empty. So,
no. of stalls created by control hazard(branch instruction) $= 2 \times 2 \times 10^8 = 4 \times 10^8$

Then,   total no of cycle for execution $= 8 \times 10^8 + 2 \times 10^8 + 4 \times 10^8 ns \\= 14 \times 10^8ns = 1.4s$

Comments

bcz in the question itsself given i.e conditional instructions evaluate in the  3rd stage , so there will be 2 stall cycle.

---

Why you have added 4*10^8 ?

---

total no of cycles for execution=[ [80%(0+1)+20%(2+1)] *10^-9] 10^9

                                                =1.4ns

Answer 3

There are 2 methods to solve this type of question.

Comments

BEST answer.

Answer 4

Total excution time is :{(3*2*10^8)+(8*10^1)}*10^-9=1.4 sec

where first term in addition is no of cycle taken by branch instruction to excute ( 2 stall + 1 for its fetch )

and next every instruction is complete in 1

It it correct way of thinking ?

Comments

Yes, thats also correct :)

---

Please elaborate a bit 

ThanThanks in advance 

---

a conditional branch instruction  compute target address and evaluate in the third stage it means no of stalls =2

and clock per instruction(cpi)=1+no of stalls      =1+2=3

20% are branch instruction and 80% are non branch