GATE CS 2014 Set 3 Q.53 (CS Q.43): Instruction Pipelining and Hazards

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is _____.

Your answer

Official answer and solution

Accepted answers: 1.5 to 1.6
From: Official GATE 2014 answer key

Solution

Calculate clock cycle time and CPI for both designs, accounting for branch penalty stalls, and find the ratio of execution times.

Old Pipeline Design (5 stages):
- Stage latencies: IF ( $1$ ns), ID/RF ( $2.2$ ns), EX ( $2$ ns), MEM ( $1$ ns), WB ( $0.75$ ns).
- Clock cycle time: $\tau_{\text{old}} = \max(1, 2.2, 2, 1, 0.75) = 2.2$ ns.
- Branch instructions ( $20\%$ of instructions) produce the next instruction pointer at the end of the EX stage.
- Stages before target instruction fetch: IF (cycle 1), ID/RF (cycle 2), EX (cycle 3).
- Target instruction is fetched in cycle 4, incurring $3 - 1 = 2$ stall cycles per branch.
- $\text{CPI}_{\text{old}} = 1 + 0.20 \times 2 = 1.40$ .
- Execution time: $P = N \times \text{CPI}_{\text{old}} \times \tau_{\text{old}} = N \times 1.40 \times 2.2 = 3.08 N$ ns.
New Pipeline Design (8 stages):
- ID/RF is split into 3 stages: ID, RF1, RF2, each with latency $2.2 / 3 \approx 0.733$ ns.
- EX is split into 2 stages: EX1, EX2, each with latency $1$ ns.
- Stages: IF ( $1$ ns), ID ( $0.733$ ns), RF1 ( $0.733$ ns), RF2 ( $0.733$ ns), EX1 ( $1$ ns), EX2 ( $1$ ns), MEM ( $1$ ns), WB ( $0.75$ ns).
- Clock cycle time: $\tau_{\text{new}} = \max(1, 0.733, 0.733, 0.733, 1, 1, 1, 0.75) = 1$ ns.
- Branch target is produced at the end of EX2 (end of stage 6).
- Stall cycles per branch = $6 - 1 = 5$ stall cycles.
- $\text{CPI}_{\text{new}} = 1 + 0.20 \times 5 = 1 + 1.0 = 2.0$ .
- Execution time: $Q = N \times \text{CPI}_{\text{new}} \times \tau_{\text{new}} = N \times 2.0 \times 1.0 = 2.0 N$ ns.
Ratio $P / Q$ :
$\frac{P}{Q} = \frac{3.08 N}{2.0 N} = 1.54.$

This value lies within the official range $[1.50, 1.60]$ .

Final answer

1.54

Common trap

Counting total stage index instead of stall cycles (stage index minus 1) when computing branch penalties.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 53 of 65, printed as CS Q.43
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source