edited by
20,879 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

2 votes
2 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
2 votes
2 votes

Following are my two approach - 

First Approach:

$10^{9}$ * 20% = 2 *$10^{8}$ will be executed in non-pipelined mode.

$10^{9}$ * 80% = 8 * $10^{8}$ will be executed in pipelined mode.

so according to formula, Total execution time = pipeline mode + non-pipeline mode

$(2 * 10^{8})$ * 3 * 1ns  +  $[5 + (8 * 10^{8}) - 1]$ * 1ns = 1.4 sec + 4ns

so I can neglect 4ns & hence ans is  1.4 sec

2nd Approach:

Total time = New CPI * cycle time * Instruction count

New CPI = ( Old CPI + stall-rate*stall-cycle)

so, total time = (1+ 0.2*2) * 1ns * 10^9 = 1.4 sec

1 votes
1 votes

I1 : F D E M W
I2 :    F D E M W

I3 :       F  _  _  F D E M W (Due to branch the EA calculations will be done again after the results obtained from last cycle)  So 3 cylces will be there in 20% of the instructions.

I4 :
I5 :
Execution time = 0.8 * 1* 1/10^9 * 10^9 + 0.2*3* 1/10^9 * 10^9 = 0.8 + 0.6 = 1.4ns

edited by
0 votes
0 votes

Since it is a conditional branch, so only some instructions may branch and not all.

Effective CPI of non-branched instructions = 1

Stalls = 3 -1 = 2

Thus, Total Time = Time taken by non-branch instructions + Time due to stalls( branch instructions)

                            = (0.8 * 1 * 10^9 + 0.2 * 1 * 10^9) / 10^9 + (0.2 * 10^9 * 2 ) / 10^9

                           = 0.8 + 0.2 + 0.4

                           = 1.4 sec (Answer)

edited by
Answer:

Related questions