5.5k views

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 109 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:

1. 1.0 second
2. 1.2 seconds
3. 1.4 seconds
4. 1.6 seconds
retagged | 5.5k views
+1
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

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$
edited
0
thank you sir :)
+4
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
0
Thanks for the correction :)
+3

@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 * Tclock    as the number of cycles on an average required for the instruction is given.

In this case the answer could be 1.0 sec.

+1
Which formula is being used to calculate the execution time??
0
Execution time in Seconds or Nano-Seconds?

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

@Arjun sir

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 .

0

@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.

0
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..

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$
+24

(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

+1
I branch instruction should take 2 cycles why have u taken 3
+1
bcz in the question itsself given i.e conditional instructions evaluate in the  3rd stage , so there will be 2 stall cycle.
0
Why you have added 4*10^8 ?
+1
total no of cycles for execution=[ [80%(0+1)+20%(2+1)] *10^-9] 10^9

=1.4ns

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$

edited
0
giga is 10^9 and there are 10^9 instructions.
0
@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
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 ?
0
Yes, thats also correct :)
0

0
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
+1 vote

There are 2 methods to solve this type of question.

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

1
2