Changes:
\begin{tabular}{rl}
-27-Aug
-& \color{red} Note that decision to requeue is based on value of OLC {\it before} execution\\
+20-Sep
+& Update hatch description to match \href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50} \\
+28-Aug
+& Note that decision to requeue is based on value of OLC {\it before} execution\\
+& Note that decision to open the hatch is based on value of {\tt OS} bit\\
10-Jul
& Added {\tt OLC=0} predicate \\
& Eliminated {\tt TAPL} (made possible by previous change) \\
{\it an input dock}
\end{center}
-Note the mux on the path between {\tt EF} (epilogue fifo) and {\tt IF}
-(instruction fifo); this is known as ``the hatch''. The hatch has two
-states: sealed and unsealed. When the machine powers up, the hatch is
-unsealed; it is sealed by the {\tt tail} instruction and unsealed
-whenever the outer loop counter is set to zero (for any
-reason\footnote{this includes {\tt OLC} being decremented to zero, a
- {\tt set} instruction, or the occurrence
- of a torpedo}).
-
-When an instruction arrives at the epilogue fifo ({\tt EF}), it waits
-there until the hatch is in the unsealed state; the instruction then
-enters the instruction fifo. When an instruction emerges from the
-instruction fifo, it arrives at the ``on deck'' ({\tt OD}) stage,
-where it may execute.
+%\subsection{The Hatch}
+%
+%\color{red}
+%
+%Note the mux on the path between {\tt EF} (epilogue fifo) and {\tt IF}
+%(instruction fifo); this is known as ``the hatch''. The exact
+%behavior of the hatch is documented in
+%\href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50};
+%a summary of its behavior is included below.
+%
+%When an instruction arrives at the epilogue fifo ({\tt EF}), it waits
+%there until the hatch is in the unsealed state; the instruction then
+%enters the instruction fifo. When an instruction emerges from the
+%instruction fifo, it arrives at the ``on deck'' ({\tt OD}) stage,
+%where it may execute.
+\color{black}
\begin{center}
\epsfig{file=out,width=4in}\\
\end{center}
\pagebreak
+\subsection{The Hatch}
+
+What follows is a conservative approximation of the actual behavior of
+the hatch.
+For complete details on the behavior of the hatch, see
+\href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50}.
+
+For the purposes of this section, instructions will be
+classified into three categories: one-shot instructions ({\tt OS=1}),
+requeueable instructions ({\tt OS=0}), and {\tt tail} instructions.
+
+To avoid deadlock, the programmer must ensure that:
+
+\begin{itemize}
+
+\item A requeueable instruction is never followed immediately by a
+ one-shot.
+
+\item A one-shot instruction is never followed immediately by a {\tt
+ tail}.
+
+\item No contiguous sequence of requeueable instructions is longer
+ than the length of the instruction fifo.
+
+\item If a requeueable instruction is preceded by a one-shot
+ instruction or a {\tt tail}, then it must be the case that {\tt
+ OLC>0} both before and after the first time that instruction
+ executes.
+
+\item If {\tt OLC=0}, only a one-shot instruction may set it to a
+ nonzero value.
+
+\end{itemize}
+
+The dock guarantees that:
+
+\begin{itemize}
+
+\item If a requeueable instruction is preceded by a one-shot
+ instruction or a {\tt tail}, then the {\it following}
+ instruction will not execute until a {\tt tail} has reached the
+ hatch.
+
+\item Once a {\tt tail} instruction reaches the hatch, no further
+ instructions will be enqueued until a requeueable instruction
+ reaches the execution stage and {\tt OLC=0}.
+
+\end{itemize}
+
+
+\color{black}
\subsection{On Deck}
When an instruction arrives on deck, two concurrent processes are
-started. No subsequent instruction may come on deck until both
-processes have completed:
-
+started:
\begin{enumerate}
-
\item Requeueing:
\begin{itemize}
- \item If the outer loop counter is zero ({\tt OLC=0})
- \color{red}{\it before executing the
- instruction}\color{black}\ or the instruction on deck is a
- one-shot instruction ({\tt OS=1}), do nothing.
- \item {\it Otherwise} wait for the hatch to be sealed and
- enqueue a copy of the instruction currently on deck.
+ \item If the instruction on deck is a requeueable instruction
+ ({\tt OS=1}) and the outer loop counter is nonzero ({\tt
+ OLC>0}), a copy of the instruction is requeued.
\end{itemize}
\item Execution:
-
\begin{itemize}
\item
If the instruction's predicate condition is not met (see
section on predicates), do nothing.
\item
- {\it Otherwise} if the instruction is interruptible ({\tt I=0})
+ {\it Otherwise} if the instruction is interruptible ({\tt I=1})
and a torpedo is present in the waiting area: consume the
- torpedo, set the outer loop counter to zero ({\tt OLC=0}),
- set the inner loop counter to one ({\tt ILC=1}),
- unseal the hatch.
+ torpedo, set the outer loop counter to zero ({\tt OLC=0}) and
+ set the inner loop counter to one ({\tt ILC=1}).
\item
{\it Otherwise} if {\tt ILC$\neq$0} or the instruction is {\it
\color{black}
-\subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
+\subsection{{\tt move}}
\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
\end{bytefield}}}
\bitsTail
-When a {\tt tail} instruction reaches the hatch, it seals the hatch.
-The {\tt tail} instruction does not enter the instruction fifo.
+When a {\tt tail} instruction reaches the hatch and the hatch is open,
+it seals the hatch. The {\tt tail} instruction does not enter the
+instruction fifo.
\color{black}
%\pagebreak
projects / fleet.git / commitdiff