GATE CS 2017 Set 1 Q.50 (CS Q.50): Instruction Pipelining and Hazards

Instruction execution in a processor is divided into 5 stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX), and Write Back (WB). These stages take 5, 4, 20, 10, and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementations of the processor are contemplated:

(i) a naive pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage is divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.

The speedup (correct to two decimal places) achieved by EP over NP in executing 20 independent instructions with no hazards is ______.

Your answer

Official answer and solution

Accepted answers: 1.49 to 1.52
From: Official GATE 2017 answer key

Solution

Compute the cycle time and total execution time for 20 instructions in both naive (NP) and efficient (EP) pipelines to determine speedup.

Naive Pipeline (NP):

Stages: IF (5 ns), ID (4 ns), OF (20 ns), EX (10 ns), WB (3 ns).
Number of stages $k_1 = 5$ .
Buffer delay $d = 2\text{ ns}$ .
Clock cycle time $\tau_{\text{NP}} = \max(5, 4, 20, 10, 3) + 2 = 20 + 2 = 22\text{ ns}$ .
Execution time for $N = 20$ instructions: $T_{\text{NP}} = (k_1 + N - 1) \times \tau_{\text{NP}} = (5 + 20 - 1) \times 22 = 24 \times 22 = 528\text{ ns}$

Efficient Pipeline (EP):

The OF stage is split into OF1 (12 ns) and OF2 (8 ns).
Stages: IF (5 ns), ID (4 ns), OF1 (12 ns), OF2 (8 ns), EX (10 ns), WB (3 ns).
Number of stages $k_2 = 6$ .
Clock cycle time $\tau_{\text{EP}} = \max(5, 4, 12, 8, 10, 3) + 2 = 12 + 2 = 14\text{ ns}$ .
Execution time for $N = 20$ instructions: $T_{\text{EP}} = (k_2 + N - 1) \times \tau_{\text{EP}} = (6 + 20 - 1) \times 14 = 25 \times 14 = 350\text{ ns}$

Speedup achieved by EP over NP:

\text{Speedup} = \frac{T_{\text{NP}}}{T_{\text{EP}}} = \frac{528}{350} \approx 1.5086 \approx 1.51

Final answer

1.51

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 50 of 65, printed as CS Q.50
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