Skip to content
GATETECH
Official PYQ · 1999Q13Instruction PipeliningNAT1 mark

GATE CS 1999 Q13 — Instruction Pipelining

Explain with AI
An instruction pipeline consists of 44 stages – Fetch (F)(F), Decode field (D)(D), Execute (E)(E) and Result Write (W)(W). The 55 instructions in a certain instruction sequence need these stages for the different number of clock cycles as shown by the table below InstructionFDEW 1121121221321324132151212\begin{array}{|c|c|c|c|c|} \hline \textbf{Instruction} & \textbf{F} &\textbf{D} & \textbf{E} & \textbf{W } \\ \hline \textbf{1}& 1 & 2 & 1 & 1 \\ \hline \textbf{2} & 1 & 2 & 2 & 1\\ \hline \textbf{3}& 2 & 1 & 3 & 2 \\ \hline \textbf{4} & 1 & 3 & 2 & 1 \\ \hline \textbf{5} & 1 & 2 & 1 & 2 \\ \hline \end{array} Find the number of clock cycles needed to perform the 55 instructions.
View worked solution

Answer: 15

In an in-order instruction pipeline, an instruction ii can enter a stage SS only after:

  1. It has completed the previous stage S−1S-1.
  2. The preceding instruction i−1i-1 has cleared stage SS.

Thus, the start time for any stage is given by:
Start(S,i)=max⁡(End(S−1,i),End(S,i−1))\text{Start}(S, i) = \max\big(\text{End}(S-1, i), \text{End}(S, i-1)\big) and the end time is:
End(S,i)=Start(S,i)+Latency(S,i)\text{End}(S, i) = \text{Start}(S, i) + \text{Latency}(S, i)

Tracing the execution cycle-by-cycle for each instruction:

Inst. Fetch (F) Decode (D) Execute (E) Write (W)
I1 0 – 1 1 – 3 3 – 4 4 – 5
I2 1 – 2 3 – 5 5 – 7 7 – 8
I3 2 – 4 5 – 6 7 – 10 10 – 12
I4 4 – 5 6 – 9 10 – 12 12 – 13
I5 5 – 6 9 – 11 12 – 13 13 – 15

The final stage (Write) of the last instruction (Instruction 5) completes at clock cycle 15.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Instruction Pipelining questions