The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 votes

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
asked in CO & Architecture by Active (3.7k points)
retagged by | 4.8k views

4 Answers

+37 votes
Best answer
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$
answered by Veteran (369k points)
edited by
thank you 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
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 * 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.

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..
+22 votes
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$
answered by Junior (855 points)

(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

+17 votes

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$

answered by Boss (17.2k points)
edited by
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
+6 votes
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 ?
answered by Loyal (10k points)
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,457 questions
49,914 answers
65,897 users