Consider the following reservation table for a pipeline having three stages $S_1, S_2$ and $S_3$. The minimum average latency (MAL) is _______.

To determine the Minimum Average Latency (MAL) from the reservation table:

1. Identify Forbidden Latencies ($F$):

   • Stage $S_1$ is used at time steps 1 and 5: latency $5 - 1 = 4$.

   • Stage $S_2$ is used at time steps 2 and 4: latency $4 - 2 = 2$.

   • Stage $S_3$ is used only at time step 3: no collision.

   • Set of forbidden latencies: $F = \{2, 4\}$.

2. Initial Collision Vector ($C$):

   • Since the maximum forbidden latency is 4:

   $$C = (c_4, c_3, c_2, c_1) = (1, 0, 1, 0)$$

3. State Transition Diagram / Simple Cycles:

   • From state $(1010)_2$:

     • Allowed latency 1: $((1010) \gg 1) \lor (1010) = (0101) \lor (1010) = (1111)_2$.

       • From $(1111)_2$, only latencies $\ge 5$ are allowed, leading back to $(1010)_2$. Cycle: $(1, 5)$ with average latency $\frac{1 + 5}{2} = 3$.

     • Allowed latency 3: $((1010) \gg 3) \lor (1010) = (0001) \lor (1010) = (1011)_2$.

       • From $(1011)_2$, latency 3 gives $((1011) \gg 3) \lor (1010) = (1011)_2$. Constant cycle: $(3)$ with average latency $3$.

4. Minimum Average Latency (MAL):

   • Both simple cycles $(3)$ and $(1, 5)$ yield an average latency of $3$.

   • Hence, $\text{MAL} = 3$.