GATE CS 2015 Set 3 Q51 — Instruction Pipelining

To find the Minimum Average Latency (MAL), we first determine the forbidden latencies and construct the state transition diagram.

Step 1: Find the Forbidden Latencies
Forbidden latencies are the time differences between any two mark points ($X$) in the same row of the reservation table:

• For stage $S_1$: Mark points at times $1$ and $5$. Forbidden latency = $|5 - 1| = 4$.
• For stage $S_2$: Mark points at times $2$ and $4$. Forbidden latency = $|4 - 2| = 2$.
• For stage $S_3$: Only one mark point at time $3$. No forbidden latency.

Step 2: Determine the Collision Vector
The collision vector is $C = (c_4 c_3 c_2 c_1) = (1010)_2$, where $c_i = 1$ if $i \in F$, and $c_i = 0$ otherwise.

Step 3: Construct the State Transition Diagram
Starting with the initial state $S_0 = (1010)$:

• From $S_0 = (1010)$:
  • With latency $1$: New state = $\text{Shift}(1010, 1) \lor (1010) = (0101) \lor (1010) = (1111)$.
  • With latency $3$: New state = $\text{Shift}(1010, 3) \lor (1010) = (0001) \lor (1010) = (1011)$.
  • With latency $\ge 5$: Transitions back to $S_0$.
• From state $(1111)$:
  • No latencies $< 5$ are allowed. With latency $\ge 5$, it transitions back to $S_0$.
• From state $(1011)$:
  • With latency $3$: New state = $\text{Shift}(1011, 3) \lor (1010) = (0001) \lor (1010) = (1011)$ (self-loop).
  • With latency $\ge 5$: Transitions back to $S_0$.

Step 4: Identify Simple Cycles and Calculate Average Latencies

• Cycle $S_0 \xrightarrow{1} (1111) \xrightarrow{5} S_0$: Average latency = $\frac{1 + 5}{2} = 3$
• Cycle $(1011) \xrightarrow{3} (1011)$: Average latency = $3$
• Cycle $S_0 \xrightarrow{3} (1011) \xrightarrow{5} S_0$: Average latency = $\frac{3 + 5}{2} = 4$