GATE2006-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⁹ 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. 1.0 second
• B. 1.2 seconds
• C. 1.4 seconds
• D. 1.6 seconds

Comments

program execute at 10^9

frequency =1/10^9

instruction fetch in first stage and conditional branch at third stage,so 2 stall cycle.

20% conditional branch and remaining 80%.non conditional branch

CPI of conditional branch=3*1/10^9

CPI of non conditional branch=1*1/10^9

conditional branch(10^9*20/100)(3*1/10^9)+non conditional branch(10^9*80/100)(1*1/10^9).

0.6+0.8=1.4ns

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$

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

 

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

(1+stall frequency* stall cycle)* tc

NOW , stall freq is 20% and stall cycle is 2 bcz we have to wait  upto 2 stage and in 3rd stage we are getiing the evaluation. 

So taccesstime=(1+0.20*2)*1/10^9)  for 1 instuction then for 10^9 instruction will be (1+0.20*2)*1/10^9* 10^9= 1.4 sec 

---

I branch instruction should take 2 cycles why have u taken 3

---

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

Avg instruction execution time = ( Ideal CPI + Branch Frequency*Branch Penalty)*Cycle Time}

Avg instruction execution time = ( 1 + .2*2)*1ns = 1.4ns

There are total $10^9$ instructions, so total program execution time = $1.4*10^-9*10^9 = 1.4 sec$

Comments

giga is 10^9 and there are 10^9 instructions.

---

@kaushik.p.e  bro plz clear my doubt if i compute avg cpi  then it will be equal to 1.4 means to execute one instruction it will take 1.4 cycle and given that time of 1 cycle is 1*10^-9 sec then answer will be 1.4 ns   but given 1.4s where i m wrong

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

Answer 5

There are 2 methods to solve this type of question.

Answer 6

So for branch instructions CPI will be 3 , as no of stalls are 2 , and there are 2*10^8 branch instructions , therefore total machine cycles used =2*10^8*3 and for remaining 8*10^8 instructions CPI will be 1 as they are non branch instructions , and total machine cycles taken =8*10^8*1,now total machine cycles used = 8*10^8*1+3*2*10^8 = 14*10^8 , now cpu frequency is 1Ghz Therefore memory cycle time =1/(10^9), finally total execution time = total no of machine cycles used *cycle time=(14*10^8)/10^9= 1.4 sec