A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction fetch…
2006
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:
- A.
1.0 second
- B.
1.2 seconds
- C.
1.4 seconds
- D.
1.6 seconds
Attempted by 61 students.
Show answer & explanation
Correct answer: C
Answer: 1.4 seconds
Total instructions = 10^9. Fraction of conditional branches = 20% → number of branches = 0.2 × 10^9 = 2 × 10^8.
Fetch happens in pipeline stage 1 and the branch outcome is known in stage 3. After a branch is fetched, fetching is stopped until the outcome is known, which takes two cycles (stage 1 → stage 3). So each conditional branch causes a 2-cycle fetch stall.
Extra cycles due to branches = 2 cycles/branch × 2 × 10^8 branches = 4 × 10^8 cycles.
Base cycles (one cycle per instruction on average) = 10^9 cycles. Total cycles = 10^9 + 4 × 10^8 = 1.4 × 10^9 cycles.
CPU frequency = 1 GHz, so execution time = total cycles / 10^9 = 1.4 seconds.