Changes:
\begin{tabular}{rl}
+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) \\
+& Expanded {\tt set} {\tt Immediate} field from 13 bits to 14 bits (made possible by previous change)\\
+09-Jul
+& Fixed a few typos \\
+& Added {\tt DataLatch}\to{\tt TAPL} (Amir's request) \\
+& Eliminate ability to predicate directly on {\tt C}-flag (Ivan's request) \\
16-Jun
-& \color{red} When a torpedo strikes, {\tt ILC} is set to {\tt 1} \\
-& \color{red} Only {\tt move} can be torpedoed (removed {\tt I}-bit from {\tt set}/{\tt shift}) \\
+& When a torpedo strikes, {\tt ILC} is set to {\tt 1} \\
+& Only {\tt move} can be torpedoed (removed {\tt I}-bit from {\tt set}/{\tt shift}) \\
11-Jun
& Changed all uses of ``Payload'' to ``Immediate'' \color{black} (not in red) \\
& Reworked encoding of {\tt set} instruction \\
23-Apr
& added epilogue fifo to diagrams \\
& indicated that a token sent to the instruction port is treated as a torpedo \\
-18-Apr
-& replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
-& replaced {\tt literal} with {\tt shift} instruction \\
-17-Apr
-& Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
-& Removed ability to manually set the {\tt C} flag \\
-& Expanded predicate field to three bits \\
-& New literals scheme (via shifting) \\
-& Instruction encoding changes made at Ivan's request (for layout purposes) \\
-& Added summary of instruction encodings on last page \\
+%18-Apr
+%& replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
+%& replaced {\tt literal} with {\tt shift} instruction \\
+%17-Apr
+%& Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
+%& Removed ability to manually set the {\tt C} flag \\
+%& Expanded predicate field to three bits \\
+%& New literals scheme (via shifting) \\
+%& Instruction encoding changes made at Ivan's request (for layout purposes) \\
+%& Added summary of instruction encodings on last page \\
%07-Apr
%& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
%06-Apr
{\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}\\
When a torpedo arrives at the tail of {\tt EF}, it is deposited in a
waiting area (not shown) rather than being enqueued into {\tt EF}.
-There is a latch (not shown) called the {\it torpedo acknowledgment path
- latch} ({\tt TAPL}) which stores a path. When a torpedo is consumed
-(see section ``On Deck''), a token is sent along the path held in this
-latch.
-
\subsection{Format of an Instruction}
All instruction words have the following format:
{\tt 001:} & {\tt OLC$\neq$0} & and {\tt A=1} \\
{\tt 010:} & {\tt OLC$\neq$0} & and {\tt B=0} \\
{\tt 011:} & {\tt OLC$\neq$0} & and {\tt B=1} \\
-{\tt 100:} & {\tt OLC$\neq$0} & and {\tt C=0} \\
-{\tt 101:} & {\tt OLC$\neq$0} & and {\tt C=1} \\
+{\tt 100:} & Unused & \\
+{\tt 101:} & {\tt OLC=0} & \\
{\tt 110:} & {\tt OLC$\neq$0} & \\
{\tt 111:} & always & \\
\hline\end{tabular}
\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}) 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}),
- \color{red}set the inner loop counter to one ({\tt ILC=1}),\color{black}\
- unseal the hatch, and transmit a token along in the
- {\it torpedo acknowledgment path latch} ({\tt TAPL}).
+ 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
\pagebreak
\section{Instructions}
-The dock supports for instructions:
+The dock supports four instructions:
{\tt move} (variants: {\tt moveto}, {\tt dispatch}),
{\tt shift},
{\tt set}, and
\color{black}
-\subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
+\subsection{{\tt move}}
\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
\end{bytefield}}
\begin{bytefield}{26}
- \bitheader[b]{0,5,11-18}\\
+ \bitheader[b]{0,5,12-18}\\
\bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt OLC}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 10000}
+ \bitbox{4}{\tt 1000\color{black}}
\bitbox{3}{\tt 100}
- \bitbox{5}{}
+ \bitbox{6}{}
\bitbox{6}{\tt Immediate}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{11-18}\\
+ \bitheader[b]{12-18}\\
\bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt OLC}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 10000}
+ \bitbox{4}{\tt 1000\color{black}}
\bitbox{3}{\tt 010}
- \bitbox{11}{}
+ \bitbox{12}{}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{11-18}\\
+ \bitheader[b]{12-18}\\
\bitbox[1]{6}{\raggedleft {\tt OLC-1}\to{\tt OLC}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 10000}
+ \bitbox{4}{\tt 1000\color{black}}
\bitbox{3}{\tt 001}
- \bitbox{11}{}
+ \bitbox{12}{}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{0,5,6,11-18}\\
+ \bitheader[b]{0,5,6,12-18}\\
\bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt ILC}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 01000}
+ \bitbox{4}{\tt 0100\color{black}}
\bitbox{3}{\tt 100}
- \bitbox{4}{}
+ \bitbox{5}{}
\bitbox{1}{\tt 0}
\bitbox{6}{\tt Immediate}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{6,11-18}\\
+ \bitheader[b]{6,12-18}\\
\bitbox[1]{6}{\raggedleft $\infty$\to{\tt ILC}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 01000}
+ \bitbox{4}{\tt 0100\color{black}}
\bitbox{3}{\tt 100}
- \bitbox{4}{}
+ \bitbox{5}{}
\bitbox{1}{\tt 1}
\bitbox{6}{}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{11-18}\\
+ \bitheader[b]{12-18}\\
\bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt ILC}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 01000}
+ \bitbox{4}{\tt 0100\color{black}}
\bitbox{3}{\tt 010}
- \bitbox{11}{}
+ \bitbox{12}{}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{0,12,13-18}\\
+ \bitheader[b]{0,13-18}\\
\bitbox[1]{6}{\raggedleft \footnotesize {\tt 0-Extended Immediate}\to{\tt Data Latch}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 00100}
+ \bitbox{4}{\tt 0010\color{black}}
\bitbox{1}{\tt 0}
- \bitbox{13}{\tt Immediate}
+ \bitbox{14}{\tt Immediate}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{0,12,13-18}\\
+ \bitheader[b]{0,13-18}\\
\bitbox[1]{6}{\raggedleft \footnotesize {\tt 1-Extended Immediate}\to{\tt Data Latch}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 00100}
+ \bitbox{4}{\tt 0010\color{black}}
\bitbox{1}{\tt 1}
- \bitbox{13}{\tt Immediate}
+ \bitbox{14}{\tt Immediate}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{0,5,6,11,14-18}\\
+ \bitheader[b]{0,5,6,11,15-18}\\
\bitbox[1]{6}{\raggedleft {\tt Update Flags}}
\bitbox[r]{1}{}
- \bitbox{5}{\tt 00010}
- \bitbox{2}{}
+ \bitbox{4}{\tt 0001\color{black}}
+ \bitbox{3}{}
\bitbox{6}{\tt nextA}
\bitbox{6}{\tt nextB}
\end{bytefield}
-\begin{bytefield}{26}
- \bitheader[b]{0,12,14-18}\\
- \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt TAPL}}
- \bitbox[r]{1}{}
- \bitbox{5}{\tt 00001}
- \bitbox{1}{}
- \bitbox{13}{\tt Immediate}
-\end{bytefield}
\color{black}
\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 / blobdiff