The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 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. $\text{1.0 second}$
  2. $\text{1.2 seconds}$
  3. $\text{1.4 seconds}$
  4. $\text{1.6 seconds}$
  • ๐Ÿšฉ Edit necessary | ๐Ÿ‘ฎ Hirak | ๐Ÿ’ฌ โ€œ$10^9$ should be the number of instructionsโ€
asked in CO & Architecture by Active (3.3k points) 1 flag
edited by | 5.7k views
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).


5 Answers

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

Correct Answer: $C$
answered by Veteran (406k 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..
+26 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 (757 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

+7 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 (9.6k 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
+1 vote

There are 2 methods to solve this type of question.

answered by Active (1.8k points)
0 votes
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
answered by Junior (729 points)

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
49,540 questions
54,099 answers
71,007 users