\begin{tabular}{rl}
\color{red}
+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 \\
+\color{black}
17-Apr
& Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
& Removed ability to manually set the {\tt C} flag \\
& New literals scheme (via shifting) \\
& Instruction encoding changes made at Ivan's request (for layout purposes) \\
& Added summary of instruction encodings on last page \\
-\color{black}
07-Apr
& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
06-Apr
\\\hline
Wait for hatch sealed, & + & + & + & + & + & - & - & - & - & - & \\
then IF0 w/ copy of self & & & & & & & & & & & \\\hline
-Potentially torpedoable & P+I & P+I & P+I & P+I & P+I & P\color{red}+\color{black}I & P\color{red}+\color{black}I & P\color{red}+\color{black}I & P\color{red}+\color{black}I & PI & \\
-Execute & P+ & P+ & P+ & P+ & P+ & P\color{red}+\color{black} & P\color{red}+\color{black} & P\color{red}+\color{black} & P\color{red}+\color{black} & P & \\
+Potentially torpedoable & P+I & P+I & P+I & P+I & P+I & P+I & P+I & P+I & P+I & PI & \\
+Execute & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P & \\
Inner-looping & P+ & - & - & - & - & P & - & - & - & - & \\
\hline
\end{tabular}
\color{black}
\subsubsection{Torpedo}
-There is a small fifo (not shown) before the latch marked
-``Instruction Horn''; after the {\tt tail} instruction seals the
-hatch, any subsequent instructions will queue up in this fifo until
-the hatch is unsealed. This is typically used as storage for a ``loop
-epilogue'' -- a sequence of instructions to be executed after a
-torpedo arrives or the outer loop counter expires.
-
-Each dock has a fourth connection to the switch fabric (not shown),
-called its {\it torpedo destination}. Anything (even a token) sent to
-this destination is treated as a torpedo. Note that because this is a
-distinct destination, instructions or data queued up in the other
-destination fifos will not prevent a torpedo from occurring.
-
\color{red}
+There is a small fifo marked ``Epilogue'' just beyond the instruction
+destination; after the {\tt tail} instruction seals the hatch, any
+subsequent instructions will queue up in this fifo until the hatch is
+unsealed. This is typically used as storage for a ``loop epilogue''
+-- a sequence of instructions to be executed after a torpedo arrives
+or the outer loop counter expires.
+
+A {\it token} sent to a ship's instruction destination is treated as a
+torpedo; the check for a torpedo is performed {\it before} the head of
+the Epilogue fifo. Note that because the check for a token is
+performed ``upstream'' of the epilogue fifo, torpedos will still be
+effective even when the Epilogue fifo is nearly full.
+\color{black}
+
The dock also has a {\it torpedo acknowledgment path latch},
which stores the path along which a token should be sent when a
-torpedo strikes. How this latch is set is yet to be determined.
-\color{black}
+torpedo strikes.
When a data item or token arrives at the torpedo destination, it lies
there in wait until On Deck holds a potentially torpedoable
the torpedoed instruction is requeued or not; this may or may not
occur, nondeterministically. It is the programmer's responsibility
to ensure that the program behaves the same whether this happens or
- not. We think that this will not matter in most situations.} \color{red}and
+ not. We think that this will not matter in most situations.} and
sends a token along the path stored in the torpedo acknowledgment path
-latch\color{black}.
+latch.
\end{itemize}
Many instruction fields are specified as
-\color{red}three-bit\color{black}\ {\it predicates}. These fields
+three-bit {\it predicates}. These fields
contain one of eight values, indicating if an action should be taken
unconditionally or conditionally on one of the {\tt A}, {\tt B}, or
{\tt C} flags:
-\color{red}
\begin{multicols}{2}
\begin{itemize}
\item {\tt 000:} if {\tt A} is set
\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{14-19,21}\\
+ \bitheader[b]{14-20}\\
\color{light}
\bitsHeader
\color{black}
- \bitbox{2}{01}
+ \bitbox{1}{0}
+ \bitbox{1}{1}
\bitbox{1}{\tt Ti}
\bitbox{1}{\tt Di}
\bitbox{1}{\tt Dc}
\bitbox[l]{19}{}
\end{bytefield}}
-%\begin{bytefield}{26}
-% \bitheader[b]{12-18}\\
-% \bitbox[]{8}{\raggedleft Input Dock:}
-% \bitbox[r]{2}{}
-% \bitbox{1}{\tt So}
-% \bitbox{1}{\tt Dc}
-% \bitbox[l]{15}{}
-%\end{bytefield}
-%
-%\begin{bytefield}{26}
-% \bitheader[b]{12-18}\\
-% \bitbox[]{8}{\raggedleft Output Dock:}
-% \bitbox[r]{2}{}
-% \bitbox{1}{\tt Si}
-% \bitbox{1}{\tt To}
-% \bitbox[l]{15}{}
-%\end{bytefield}
-
\begin{bytefield}{26}
\bitheader[b]{0,12,13}\\
\bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt LiteralPath\to Path})}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{12,13}\\
+ \bitheader[b]{11,12,13}\\
\bitbox[1]{11}{\raggedleft {\tt dispatch} ({\tt DP[37:25]\to Path})\ \ }
\bitbox[r]{1}{}
\bitbox{1}{\tt 0}
\bitbox{1}{\tt 1}
+ \bitbox{1}{\tt 0}
\color{light}
- \bitbox[trb]{12}{}
+ \bitbox[trb]{11}{}
\color{black}
\end{bytefield}
\begin{bytefield}{26}
- \bitheader[b]{12,13}\\
+ \bitheader[b]{11,12,13}\\
\bitbox[1]{11}{\raggedleft {\tt move} ({\tt Path} unchanged):}
\bitbox[r]{1}{}
\bitbox{1}{\tt 0}
\bitbox{1}{\tt 0}
+ \bitbox{1}{\tt 1}
\color{light}
- \bitbox[trb]{12}{}
+ \bitbox[trb]{11}{}
\color{black}
\end{bytefield}}
\bitsMove
\pagebreak
-\subsection{{\tt literal}}
-
-\color{red}
-\newcommand{\literalPayloadSize}{17}
+\subsection{{\tt set}}
-Each literal instruction carries a payload of \literalPayloadSize\
-bits. When a literal instruction is executed, this payload is copied
-into the least significant \literalPayloadSize\ bits of the data latch,
-and the remaining most significant bits of the data latch are loaded
-with either:
-
-\begin{itemize}
-\item All zeroes
-\item All ones
-\item The value formerly in the least significant bits of the data latch
-\end{itemize}
+\color{red}
-In this manner, large literals can be built up by ``shifting'' them
-into the data latch \literalPayloadSize\ bits at a time.
+The {\tt set} command is used to set or decrement the inner loop
+counter, outer loop counter, and data latch.
-\newcommand{\bitsLiteral}{
+\newcommand{\bitsSet}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{0,16-21}\\
+ \bitheader[b]{0,14-15,16-20}\\
\color{light}
\bitsHeader
\color{black}
- \bitbox{2}{00}
- \bitbox{2}{SEL}
+ \bitbox{1}{1}
+ \bitbox{1}{0}
+ \bitbox{2}{SRC}
+ \bitbox{2}{DST}
\color{black}
- \bitbox{\literalPayloadSize}{Payload}
+ \bitbox{15}{Payload}
\end{bytefield}}
}
-\bitsLiteral
+\bitsSet
-{\tt
-\begin{tabular}{|r|c|c|c|}\hline
-sel & D[37:18] & D[17:1] \\\hline
-00 & D[20:1] & Payload[17:1] \\
-01 & all 0 & Payload[17:1] \\
-10 & all 1 & Payload[17:1] \\
-11 & not used & not used \\
+\begin{center}{\tt
+\begin{tabular}{|r|r|l|l|}\hline
+Source & SRC & DST & Destination \\\hline
\hline
-\end{tabular}}
-
-\color{black}
-
+Payload & 00 & 00 & OLC \\
+Data Latch & 01 & 00 & OLC \\
+OLC-1 & 10 & 00 & OLC \\
+Payload & 00 & 01 & ILC \\
+Data Latch & 01 & 01 & ILC \\
+$\infty$ & 10 & 01 & ILC \\
+Payload & 00 & 10 & Torpedo Ack Path \\
+Payload, 0-extend & 01 & 10 & Data Latch \\
+Payload, 1-extend & 10 & 10 & Data Latch \\
+ see below & & 11 & Flags \\
+\hline
+\end{tabular}
+}\end{center}
+The FleetTwo implementation is likely to have an unarchitected
+``literal latch'' at the OD stage, which is loaded with the
+possibly-extended literal {\it at the time that the {\tt set}
+ instruction comes on deck}. This latch is then copied into the data
+latch when the instruction executes.
-\subsection{{\tt setFlags}}
+If the {\tt Dest} field is flags, the {\tt Payload} field is
+interpreted as two fields, each giving the truth table for the new
+value of one of the two user-settable flags:
-\newcommand{\bitsFlags}{\setlength{\bitwidth}{5mm}
+\begin{center}
+\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{0,5,6,11,12,16-20}\\
+ \bitheader[b]{0,5,6,11}\\
\color{light}
\bitsHeader
- \bitbox{2}{10}
- \bitbox{7}{}
-\color{red}
+ \bitbox{1}{1}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox{2}{}
+\color{black}
+ \bitbox{2}{11}
+\color{light}
+ \bitbox{3}{}
+\color{black}
\bitbox{6}{nextA}
\bitbox{6}{nextB}
+\end{bytefield}}
+\end{center}
\color{black}
-\end{bytefield}}}
-\bitsFlags
-
-When this instruction executes, the flags are updated according to the
-{\tt nextA} and {\tt nextB} fields; each specifies the new value as
-the logical {\tt OR} of zero or more inputs:
+Each field has the following structure, and indicates which old flag
+values should be logically {\tt OR}ed together to produce the new flag
+value:
\begin{center}
{\tt
set are {\tt OR}ed together, and the resulting value is assigned to
the flag. Note that if none of the bits are set, the value assigned
is zero. Note also that it is possible to produce a {\tt 1} by {\tt
- OR}ing any flag with its complement, and that {\tt setFlags} can
+ OR}ing any flag with its complement, and that {\tt set Flags} can
be used to create a {\tt nop} (no-op) by setting each flag to itself.
+\color{black}
\pagebreak
+\subsection{{\tt shift}}
-\subsection{{\tt setInner}}
+\color{red}
-This instruction loads the inner loop counter with either a literal
-number, the special value $\infty$, or the contents of the {\tt data}
-register.
+\newcommand{\shiftPayloadSize}{19}
+
+Each {\tt shift} instruction carries a payload of \shiftPayloadSize\
+bits. When a {\tt shift} instruction is executed, this payload is copied
+into the least significant \shiftPayloadSize\ bits of the data latch,
+and the remaining most significant bits of the data latch are loaded
+with the value formerly in the least significant bits of the data latch.
+In this manner, large literals can be built up by ``shifting'' them
+into the data latch \shiftPayloadSize\ bits at a time.
-\newcommand{\bitsSetInner}{
+\newcommand{\bitsShift}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{16-19,21}\\
+ \bitheader[b]{0,18-20}\\
\color{light}
\bitsHeader
\color{black}
- \bitbox{2}{11}
- \bitbox{2}{00}
-\color{light}
- \bitbox[tbr]{9}{}
- \bitbox[l]{8}{}
-\color{black}
-\end{bytefield}}\\
-
-\begin{bytefield}{26}
- \bitbox[r]{18}{\raggedleft from data latch:\hspace{0.2cm}\ }
- \bitbox{2}{\tt 00}
-\color{light}
- \bitbox[tbr]{6}{}
-\color{black}
-\end{bytefield}
-
-\begin{bytefield}{26}
- \bitheader[b]{0,5,6,7}\\
- \bitbox[r]{18}{\raggedleft from literal:\hspace{0.2cm}\ }
- \bitbox{2}{\tt 10}
- \bitbox{6}{\tt Literal}
-\end{bytefield}
-
-\begin{bytefield}{26}
- \bitheader[b]{0,5,6,7}\\
- \bitbox[r]{18}{\raggedleft with $\infty$\ \ }
- \bitbox{2}{\tt 11}
-\color{light}
- \bitbox[tbr]{6}{}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
\color{black}
+ \bitbox{\shiftPayloadSize}{Payload}
\end{bytefield}}
-\bitsSetInner
-
-
-\subsection{{\tt setOuter}}
+}
+\bitsShift
-This instruction loads the outer loop counter {\tt OLC} with either
-{\tt max(0,OLC-1)}, a literal or the contents of the {\tt data}
-register.
+The FleetTwo implementation is likely to have an unarchitected
+``literal latch'' at the OD stage, which is loaded with the literal
+{\it at the time that the {\tt shift} instruction comes on deck}.
+This latch is then copied into the data latch when the instruction
+executes.
-\newcommand{\bitsSetOuter}{\setlength{\bitwidth}{5mm}
-{\tt
-\begin{bytefield}{26}
- \bitheader[b]{16-19,21,24}\\
-\color{light}
- \bitsHeader
-\color{black}
- \bitbox{2}{11}
- \bitbox{2}{01}
-\color{light}
- \bitbox[tbr]{10}{}
- \bitbox[l]{7}{}
\color{black}
-\end{bytefield}}\\
-
-\begin{bytefield}{26}
- \bitbox[r]{19}{\raggedleft {\tt max(0,OLC-1)}:\hspace{0.2cm}\ }
- \bitbox{2}{\tt 00}
-%\color{light}
- \bitbox[tbr]{5}{}
-%\color{black}
-\color{black}
-\end{bytefield}
-
-\begin{bytefield}{26}
- \bitbox[r]{19}{\raggedleft from data latch:\hspace{0.2cm}\ }
- \bitbox{2}{\tt 01}
-\color{light}
- \bitbox[tbr]{5}{}
-\color{black}
-\end{bytefield}
-
-\begin{bytefield}{26}
- \bitheader[b]{0,5,6}\\
- \bitbox[r]{19}{\raggedleft from literal:\hspace{0.2cm}\ }
- \bitbox{1}{\tt 1}
- \bitbox{6}{\tt Literal}
-\end{bytefield}}
-\bitsSetOuter
-
-%\subsection{{\tt torpedo}}
-%
-%\setlength{\bitwidth}{5mm}
-%{\tt
-%\begin{bytefield}{26}
-% \bitheader[b]{0,5,16-19,21}\\
-%\color{light}
-% \bitbox{4}{}
-%\color{black}
-% \bitbox{3}{000}
-% \bitbox{1}{1}
-% \bitbox{2}{00}
-%\color{light}
-% \bitbox[tbr]{16}{}
-%\end{bytefield}}
-%
-%
-%When a {\tt torpedo} instruction reaches the instruction horn, it will
-%wait there until an instruction is on deck whose {\tt A}rmor bit is
-%not set. The {\tt torpedo} will then cause ``Process \#2'' of the on
-%deck instruction to terminate and will set the outer loop counter to zero.
\subsection{{\tt tail}}
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{0,5,16-19,21}\\
+ \bitheader[b]{19-20}\\
\color{light}
\bitbox{5}{}
\color{black}
- \bitbox{2}{11}
- \bitbox{2}{11}
+ \bitbox{1}{1}
+ \bitbox{1}{1}
\color{light}
- \bitbox[tbr]{17}{}
+ \bitbox[tbr]{19}{}
\end{bytefield}}}
\bitsTail
\pagebreak
\section*{\color{red}Instruction Encoding Map\color{black}}
-\bitsLiteral
-
+\hspace{-1cm}{\tt move}\\
\bitsMove
-\bitsFlags
-
-\bitsSetInner
+\hspace{-1cm}{\tt shift}\\
+\bitsShift
-\bitsSetOuter
+\hspace{-1cm}{\tt set}\\
+\bitsSet
+\hspace{-1cm}{\tt tail}\\
\bitsTail
projects / fleet.git / commitdiff