GATE CSE 2006 | Question: 42

Question

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: 

• A. $\text{1.0 second}$
• B. $\text{1.2 seconds}$
• C. $\text{1.4 seconds}$
• D. $\text{1.6 seconds}$

Comments

Each instruction will run 1 cycle anyway in ideal case so 10^9 cycles will run for sure but there will also be stall cycles we should add ,

Now for the stall cycles 20% that is 0.2 x 10^9 are the required no of branch insutructions and each branch instruction will have 2 stalls because each of the instruction the target/branch condition evaluation is done at the third stage hence 3-1 (kth stage done so k-1 stalls) = 2 stalls will be there.

Now, as we can see 10^9 + 0.2x(10^9)x2 = total no of clock cyles for all instructions

Now for time we multiply clock cyles with time for one which is, multiply by 1/(10^9) as time = 1/f

So, final answer will be 1.4 s

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

---

Intuitive way to solve: 

 

Answer 1

 

1. System Specifications

Clock Frequency: 1 GHz
This corresponds to 10^9 cycles per second.
Cycle Time: 1 / (10^9 Hz) = 10^-9 seconds = 1 ns.

2. Pipeline Structure and Branch Penalty

The processor uses a 5-stage pipeline:
1. IF (Instruction Fetch)
2. ID (Instruction Decode)
3. EX (Execute)
4. MA (Memory Access)
5. WB (Write Back)

It is assumed that the branch target address is determined at the end of the EX stage. This leads to a 2-cycle delay for every branch instruction.

3. Performance Calculation

Given: 20% of all instructions are branch instructions.

Average Cycles Per Instruction (CPI):
Avg CPI = Ideal CPI + (Branch Frequency x Stall Cycles)
Avg CPI = 1 + (0.2 x 2)
Avg CPI = 1 + 0.4
Avg CPI = 1.4

Conclusion: On average, each instruction takes 1.4 cycles to execute.

4. Total Execution Time

Average Instruction Execution Time:
Avg Instruction Time = Avg CPI x Cycle Time
= 1.4 x 1 ns = 1.4 ns

Total Time for 10^9 Instructions:
Total Execution Time = (Number of Instructions) x (Avg Instruction Time)
= 10^9 x (1.4 x 10^-9 seconds)
= 1.4 seconds

Answer 2

Ans

Answer 3

Each instruction will run 1 cycle anyway in ideal case so 10^9 cycles will run for sure but there will also be stall cycles we should add ,

Now for the stall cycles 20% that is 0.2 x 10^9 are the required no of branch insutructions and each branch instruction will have 2 stalls because each of the instruction the target/branch condition evaluation is done at the third stage hence 3-1 (kth stage done so k-1 stalls) = 2 stalls will be there.

Now, as we can see 10^9 + 0.2x(10^9)x2 = total no of clock cyles for all instructions

Now for time we multiply clock cyles with time for one which is, multiply by 1/(10^9) as time = 1/f

So, final answer will be 1.4 s