\definecolor{light}{gray}{0.7}
+\setlength{\marginparwidth}{1.2in}
+\let\oldmarginpar\marginpar
+\renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize #1]%
+{\raggedright\footnotesize #1}}
+
+
\newcommand{\footnoteremember}[2]{
\footnote{#2}
\newcounter{#1}
\begin{tabular}{rl}
\color{red}
+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 \\
+\color{black}
07-Apr
& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
06-Apr
& extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
& update table 3.1.2 \\
& rename {\tt S} flag to {\tt C} \\
-\color{black}
& noted that {\tt setFlags} can be used as {\tt nop} \\
29-Mar
& removed the {\tt L} flag (epilogues can now do this) \\
& removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
& renamed {\tt data} instruction to {\tt literal} \\
& renamed {\tt send} instruction to {\tt move} \\
-23-Mar
-& added ``if its predicate is true'' to repeat count \\
-& added note that red wires do not contact ships \\
-& changed name of {\tt flags} instruction to {\tt setFlags} \\
-& removed black dot from diagrams \\
-& changed {\tt OL} (Outer Loop participant) to {\tt OS} (One Shot) and inverted polarity \\
-& indicated that the death of the {\tt tail} instruction is what causes the hatch to be unsealed \\
-& indicated that only {\tt send} instructions which wait for data are torpedoable \\
-& added section ``Torpedo Details'' \\
-& removed {\tt torpedo} instruction \\
-12-Mar
-\color{black}
-& renamed loop+repeat to outer+inner (not in red) \\
-& renamed {\tt Z} flag to {\tt L} flag (not in red) \\
-& rewrote ``inner and outer loops'' section \\
-& updated all diagrams \\
-\color{black}
-7-Mar
-& Moved address bits to the LSB-side of a 37-bit instruction \\
-& Added {\it micro-instruction} and {\it composite instruction} terms \\
-& Removed the {\tt DL} field, added {\tt decrement} mode to {\tt loop} \\
-& Created the {\tt Hold} field \\
-& Changed how ReLooping works \\
-& Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
+%23-Mar
+%& added ``if its predicate is true'' to repeat count \\
+%& added note that red wires do not contact ships \\
+%& changed name of {\tt flags} instruction to {\tt setFlags} \\
+%& removed black dot from diagrams \\
+%& changed {\tt OL} (Outer Loop participant) to {\tt OS} (One Shot) and inverted polarity \\
+%& indicated that the death of the {\tt tail} instruction is what causes the hatch to be unsealed \\
+%& indicated that only {\tt send} instructions which wait for data are torpedoable \\
+%& added section ``Torpedo Details'' \\
+%& removed {\tt torpedo} instruction \\
+%12-Mar
+%\color{black}
+%& renamed loop+repeat to outer+inner (not in red) \\
+%& renamed {\tt Z} flag to {\tt L} flag (not in red) \\
+%& rewrote ``inner and outer loops'' section \\
+%& updated all diagrams \\
+%\color{black}
+%7-Mar
+%& Moved address bits to the LSB-side of a 37-bit instruction \\
+%& Added {\it micro-instruction} and {\it composite instruction} terms \\
+%& Removed the {\tt DL} field, added {\tt decrement} mode to {\tt loop} \\
+%& Created the {\tt Hold} field \\
+%& Changed how ReLooping works \\
+%& Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
\end{tabular}
\end{abstract}
All instruction words have the following format:
+\newcommand{\bitsHeader}{
+ \bitbox{1}{I}
+ \bitbox{1}{OS}
+ \bitbox{3}{P}
+}
+
\setlength{\bitwidth}{3.5mm}
{\tt \footnotesize
\begin{bytefield}{37}
\bitheader[b]{0,10,11,36}\\
\color{black}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
+ \bitsHeader
\color{light}
- \bitbox[tbr]{22}{}
+ \bitbox[tbr]{21}{}
\bitbox{11}{dispatch path}
\color{black}
\end{bytefield}}
The table below lists the actions which may be taken when an
instruction arrives on deck:
-\color{red}
\begin{center}
\def\side#1{\begin{sideways}\parbox{15mm}{#1}\end{sideways}}
\begin{tabular}{|r|ccccc|cccccc|}\hline
\\\hline
Wait for hatch sealed, & + & + & + & + & + & - & - & - & - & - & \\
then IF0 w/ copy of self & & & & & & & & & & & \\\hline
-Potentially torpedoable & P+I & P+I & P+I & P+I & P+I & PI & PI & PI & PI & PI & \\
-Execute & P+ & P+ & P+ & P+ & P+ & P & P & P & P & P & \\
+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 & \\
Inner-looping & P+ & - & - & - & - & P & - & - & - & - & \\
\hline
\end{tabular}
P+I & Only if predicate is true and {\tt OLC>0} and {\tt I=1}. \\\hline
\end{tabular}
\end{center}
-\color{black}
-\color{red}
{\bf Note:} a non-one-shot instruction may {\it execute} before the
hatch is sealed, but may not {\it fill IF0} before the hatch is
sealed. The instruction will not vacate On Deck until both of these
tasks are complete, so the second non-one-shot instruction in a loop
will not execute until the hatch is sealed, {\it but the first
instruction will}.
-\color{black}
+\pagebreak
+\color{black}
\subsubsection{Torpedo}
There is a small fifo (not shown) before the latch marked
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 occuring.
+destination fifos will not prevent a torpedo from occurring.
+
+\color{red}
+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}
When a data item or token arrives at the torpedo destination, it lies
there in wait until On Deck holds a potentially torpedoable
instruction (see previous table). Once this is the case, the torpedo
causes the inner and outer loop counters to be set to zero (and
-therefore also unseals the hatch).\footnote{it is unspecified whether
+therefore also unseals the hatch)\footnote{it is unspecified whether
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.}
+ not. We think that this will not matter in most situations.} \color{red}and
+sends a token along the path stored in the torpedo acknowledgment path
+latch\color{black}.
-\color{black}
\subsection{Flags}
-The pump has three flags: {\tt A}, {\tt B}, and {\color{red}{\tt C}\color{black}\ }.
+The pump has three flags: {\tt A}, {\tt B}, and {\tt C}.
\begin{itemize}
\item The {\tt A} and {\tt B} flags are general-purpose flags which
% operations (such as sending a completion token) only on the last
% iteration of an outer loop.
-\item The {\color{red}{\tt C}\color{black}\ } flag, known as the {\it control} flag.
- \color{red}At outboxes its value is determined by the ship; at
- inboxes its value is copied from an unused address bit in the
- destination to which the received value was sent.
- \color{black}
+\item The {\tt C} flag is known as the {\it control} flag, and it is
+ set every time the data latch takes on a new value. At outboxes
+ its value is determined by the ship; at inboxes its value is
+ copied from an unused address bit in the destination to which
+ the received value was sent.
\end{itemize}
-Many instruction fields are specified as two-bit {\it predicates}.
-These fields contain one of four values, indicating if an action
-should be taken unconditionally or conditionally on one of the {\tt A}
-or {\tt B} flags:
+Many instruction fields are specified as
+\color{red}three-bit\color{black}\ {\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
+\item {\tt 001:} if {\tt A} is cleared
+\item {\tt 010:} if {\tt B} is set
+\item {\tt 011:} if {\tt B} is cleared
+\end{itemize}
\begin{itemize}
-\item {\tt 00:} if {\tt A} is set
-\item {\tt 10:} if {\tt B} is set
-\item {\tt 01:} \color{red}if {\color{red}{\tt C}\color{black}\ } is set\color{black}
-\item {\tt 11:} always
+\item {\tt 100:} if {\tt C} is set
+\item {\tt 101:} if {\tt C} is cleared
+\item {\tt 110:} unused
+\item {\tt 111:} always
\end{itemize}
+\end{multicols}
+\color{black}
\pagebreak
\begin{center}
\begin{tabular}{|l|}\hline
{\tt move} (variants: {\tt moveto}, {\tt dispatch}) \\
-{\tt literal} (variants: {\tt literalhi}, {\tt literallo})\\
+{\tt literal}\\
{\tt setFlags} \\
{\tt setInner} \\
{\tt setOuter} \\
\subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
-\setlength{\bitwidth}{5mm}
+\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
\bitheader[b]{14-19,21}\\
\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
+ \bitsHeader
\color{black}
- \bitbox{3}{001}
+ \bitbox{2}{01}
\bitbox{1}{\tt Ti}
\bitbox{1}{\tt Di}
\bitbox{1}{\tt Dc}
\color{light}
\bitbox[trb]{12}{}
\color{black}
-\end{bytefield}
+\end{bytefield}}
+\bitsMove
\begin{itemize}
\item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
\pagebreak
-\subsection{{\tt literal}, {\tt literalhi}, {\tt literallo}}
+\subsection{{\tt literal}}
-These instructions load part or all of the data latch ({\tt D}).
-
-{\tt literalhi: Literal[18:1]\to D[37:20]} (and {\tt Literal[18]\to S})
+\color{red}
-\setlength{\bitwidth}{5mm}
-{\tt
-\begin{bytefield}{26}
- \bitheader[b]{0,18,19,21}\\
-\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
-\color{black}
- \bitbox{1}{0}
- \bitbox{2}{11}
-\color{light}
- \bitbox[trb]{1}{}
-\color{black}
- \bitbox{18}{Literal}
-\end{bytefield}}
+\newcommand{\literalPayloadSize}{17}
-{\tt literallo: Literal[19:1]\to D[19:1]}
+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:
-\setlength{\bitwidth}{5mm}
-{\tt
-\begin{bytefield}{26}
- \bitheader[b]{0,18,19,21}\\
-\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
-\color{black}
- \bitbox{1}{0}
- \bitbox{2}{10}
- \bitbox{19}{Literal}
-\end{bytefield}}
+\begin{itemize}
+\item All zeroes
+\item All ones
+\item The value formerly in the least significant bits of the data latch
+\end{itemize}
-{\tt literal:}
+In this manner, large literals can be built up by ``shifting'' them
+into the data latch \literalPayloadSize\ bits at a time.
+\newcommand{\bitsLiteral}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{0,18,19,21}\\
+ \bitheader[b]{0,16-21}\\
\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
+ \bitsHeader
\color{black}
- \bitbox{1}{1}
+ \bitbox{2}{00}
\bitbox{2}{SEL}
- \bitbox{19}{Literal}
+\color{black}
+ \bitbox{\literalPayloadSize}{Payload}
\end{bytefield}}
+}
+\bitsLiteral
{\tt
\begin{tabular}{|r|c|c|c|}\hline
-sel & D[37:20] & D[19:1] \\\hline
-00 & Literal[18:1] & all 0 \\
-01 & Literal[18:1] & all 1 \\
-10 & all 0 & Literal[19:1] \\
-11 & all 1 & Literal[19:1] \\
+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 \\
\hline
\end{tabular}}
+\color{black}
\subsection{{\tt setFlags}}
-\setlength{\bitwidth}{5mm}
+\newcommand{\bitsFlags}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
- \bitheader[b]{0,5,6,11,12,17-19,21}\\
+ \bitheader[b]{0,5,6,11,12,16-20}\\
\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
-\color{black}
- \bitbox{3}{000}
- \bitbox{1}{0}
+ \bitsHeader
+ \bitbox{2}{10}
+ \bitbox{7}{}
+\color{red}
\bitbox{6}{nextA}
\bitbox{6}{nextB}
- \bitbox{6}{nextC}
-\end{bytefield}}
+\color{black}
+\end{bytefield}}}
+\bitsFlags
-The {\tt P} field is a predicate; if it does not hold, the instruction
-is ignored. Otherwise the flags are updated according to the {\tt
- nextA}, {\tt nextB}, and {\tt nextC} fields; each specifies the new
-value as the logical {\tt OR} of zero or more inputs:
+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:
\begin{center}
{\tt
\bitbox{1}{$\overline{\text{\tt A}}$}
\bitbox{1}{${\text{\tt B}}$}
\bitbox{1}{$\overline{\text{\tt B}}$}
- \bitbox{1}{${\text{\color{red}{\tt C}\color{black}\ }}$}
- \bitbox{1}{$\overline{\text{\color{red}{\tt C}\color{black}\ }}$}
+ \bitbox{1}{${\text{{\tt C}\ }}$}
+ \bitbox{1}{$\overline{\text{{\tt C}\ }}$}
\end{bytefield}}
\end{center}
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. Note that {\tt setFlags} can
+ OR}ing any flag with its complement, and that {\tt setFlags} can
be used to create a {\tt nop} (no-op) by setting each flag to itself.
number, the special value $\infty$, or the contents of the {\tt data}
register.
+\newcommand{\bitsSetInner}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
\bitheader[b]{16-19,21}\\
\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
- \bitbox{2}{P}
+ \bitsHeader
\color{black}
- \bitbox{3}{000}
- \bitbox{1}{1}
- \bitbox{2}{01}
+ \bitbox{2}{11}
+ \bitbox{2}{00}
\color{light}
- \bitbox[tbr]{8}{}
+ \bitbox[tbr]{9}{}
\bitbox[l]{8}{}
\color{black}
\end{bytefield}}\\
\color{light}
\bitbox[tbr]{6}{}
\color{black}
-\end{bytefield}
+\end{bytefield}}
+\bitsSetInner
\subsection{{\tt setOuter}}
{\tt max(0,OLC-1)}, a literal or the contents of the {\tt data}
register.
-\setlength{\bitwidth}{5mm}
+\newcommand{\bitsSetOuter}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
\bitheader[b]{16-19,21,24}\\
\color{light}
- \bitbox{1}{I}
- \bitbox{1}{OS}
-\color{light}
- \bitbox[tbr]{2}{P}
+ \bitsHeader
\color{black}
- \bitbox{3}{000}
- \bitbox{1}{1}
- \bitbox{2}{10}
+ \bitbox{2}{11}
+ \bitbox{2}{01}
\color{light}
- \bitbox[tbr]{9}{}
+ \bitbox[tbr]{10}{}
\bitbox[l]{7}{}
\color{black}
\end{bytefield}}\\
\bitbox[r]{19}{\raggedleft from literal:\hspace{0.2cm}\ }
\bitbox{1}{\tt 1}
\bitbox{6}{\tt Literal}
-\end{bytefield}
-
+\end{bytefield}}
+\bitsSetOuter
%\subsection{{\tt torpedo}}
%
\subsection{{\tt tail}}
+\newcommand{\bitsTail}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
\bitheader[b]{0,5,16-19,21}\\
\color{light}
- \bitbox{4}{}
+ \bitbox{5}{}
\color{black}
- \bitbox{3}{000}
- \bitbox{1}{1}
- \bitbox{2}{01}
+ \bitbox{2}{11}
+ \bitbox{2}{11}
\color{light}
- \bitbox[tbr]{16}{}
-\end{bytefield}}
+ \bitbox[tbr]{17}{}
+\end{bytefield}}}
+\bitsTail
When a {\tt tail} instruction reaches {\tt IH}, it seals the hatch.
The {\tt tail} instruction does not enter the instruction fifo.
\pagebreak
+\section*{\color{red}Instruction Encoding Map\color{black}}
+
+\bitsLiteral
+
+\bitsMove
+
+\bitsFlags
+
+\bitsSetInner
+
+\bitsSetOuter
+
+\bitsTail
+
+
+\color{black}
+
+\pagebreak
\epsfig{file=overview,height=5in,angle=90}
\pagebreak
projects / fleet.git / commitdiff