edited by
20,877 views
50 votes
50 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 $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: 

  1. $\text{1.0 second}$
  2. $\text{1.2 seconds}$
  3. $\text{1.4 seconds}$
  4. $\text{1.6 seconds}$
edited by

9 Answers

Best answer
68 votes
68 votes
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$
edited by
41 votes
41 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$
10 votes
10 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 ?
Answer:

Related questions