Reference: Page 24 http://www2.cs.siu.edu/~cs401/Textbook/ch3.pdf
$S_1$ is needed at time $1$ and $5,$ so its forbidden latency is $5-1=4.$
$S_2$ is needed at time $2$ and $4,$ so its forbidden latency is $4-2=2.$
So, forbidden latency $= (2,4,0)$ ( $0$ by default is forbidden)
Allowed latency $= (1,3,5)$ (any value more than $5$ also).
Collision vector $(4,3,2,1,0) = 10101$ which is the initial state as well.
From initial state we can have a transition after $\text{“1"}$ or $\text{“3"}$ cycles and we reach new states with collision vectors $(10101 >> 1 + 10101 = 11111)$ and $(10101 >> 3 + 10101 = 10111)$ respectively.
These $2$ becomes states $2$ and $3$ respectively. For $\text{“5"}$ cycles we come back to state $1$ itself.
From state $2\ (11111),$ the new collision vector is $11111.$ We can have a transition only when we see the first $0$ from the right. So, here it happens on $5^{th}$ cycle only which goes to the initial state. (Any transition after $5$ or more cycles goes to initial state as we have $5$ time slices).
From state $3\ (10111),$ the new collision vector is $10111.$ So, we can have a transition on $3,$ which will give $(10111 >> 3 + 10101 = 10111)$ third state itself. For $5,$ we get the initial state. Thus all the transitions are complete.
$$\begin{array}{|c|c|c|} \hline \textbf {State\Time} & \textbf {1} & \textbf {3} & \textbf{5 } \\\hline \textbf{1(10101)} & \text{2}& \text{3} & \text{1} \\\hline \textbf{2(11111)} & \text{-} & \text{-}& \text{1}\\\hline \textbf{3(10111)}& \text{-}&\text{3} & \text{1}\\\hline \end{array}$$
So, minimum length cycle is of length 3 either from $\text{3-3}$ or from $\text{1-3,3-1}$.
Not asked in the question, still.
Pipeline throughput is the number of instructions initiated per unit time.
So, with $MAL = 3,$ we have $2$ initiations in $1+3 = 4$ units of time (one at time unit $1$ and another at time unit $4$ ). So, throughput $=\dfrac{2}{4}=0.5$.
Pipeline efficiency is the $\%$ of time every stage of the pipeline is being used.
For the given question we can extend the reservation table and taking $MAL = 3,$ we can initiate new tasks after every $3$ cycles. So, we can consider the time interval from $\text{4-6}$ in the below figure. (The red color shows a stage not being used- affects efficiency).$$\begin{array}{|ccccc|} \hline \textbf{Time} \rightarrow \\\hline & \text{$1$}& \text{$2$} & \text{$3$} & \text{$4$} & \text{$5$} & \text{$6$} & \text{$7$} & \text{$8$} & \text{$9$} & \text{$10$} & \text{$11$} \\\hline \textbf{$S _{1}$} & \text{$X$} & & & \text{$Y$} & \text{$X$} & \times & \text{$Z$} & \text{$Y$} & \times & \text{$A$} & \text{$Z$} \\\hline \textbf{$S _{2}$} & & \text{$X$} & & \text{$X$} & \text{$Y$} & \times & \text{$Y$} & \text{$Z$} & & \text{$Z$} & \text{$A$} \\\hline \textbf{$S _{3}$} & & & \text{$X$} & \times & \times & \text{$Y$} & & & \text{$Z$} & & & \\\hline \end{array}$$
Here (during cycles $4-6$ ), $\text{stage 1}$ is used $\dfrac{2}{3},$ $\text{stage 2}$ is used $\dfrac{2}{3}$ and stage $3$ is used $\dfrac{1}{3}.$
So, total stage utilization $=\dfrac{(2+2+1)}{9}=\dfrac{5}{9}$ and efficiency $=\dfrac{500}{9} \%=55.55\ %$.
For simulation, Reference: http://www.ecs.umass.edu/ece/koren/architecture/ResTable/SimpRes/
Similar Question