20-sep

[fleet.git] / am33.tex

\documentclass[10pt]{article}
\usepackage{palatino}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{color}
\usepackage{bytefield1}
\usepackage{wrapfig}
\usepackage{stmaryrd}
\usepackage{subfigure}
\usepackage{syntax}
\usepackage{comment}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{rotating}
\include{megacz}
\bibliographystyle{alpha}
\pagestyle{fancyplain}

\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}
  \setcounter{#1}{\value{footnote}}
} \newcommand{\footnoterecall}[1]{
  \footnotemark[\value{#1}]
}

%\pdfpagewidth 8.5in
%\pdfpageheight 11in 
%\topmargin 0in
\textheight 7.9in
%\textwidth 6.0in
%\oddsidemargin 0.25in
%\evensidemargin 0.25in
%\headwidth 6.0in
\def\to{\ $\rightarrow$\ }

\def\docnum{AM33}

\author{
\normalsize{
\begin{tabular}{c}
\end{tabular}}
}

\title{\vspace{-1cm}AM33: The FleetTwo Dock
\\
{\normalsize
Adam Megacz
}}

\begin{document}

\maketitle

\begin{abstract}
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
& 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 \\
\color{black} 
06-Jun
& Factored in Russell Kao's comments (thanks!)\\
& Added mechanism for setting C-flag from fabric even on outboxes\\
05-Jun
& Made {\tt OLC} test a predicate-controlled condition\\
& Rewrote ``on deck'' section \\
& Added ``{\tt unset}'' value for {\tt ILC}\\
& Changed {\tt DP} to {\tt DataPredecessor} for clarity\\
\color{black}
30-Apr
& added comment about address-to-path ship \\
& changed {\tt DST} field of {\tt set} instruction from 2 bits to 3 \\
& changed the order of instructions in the encoding map \\
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 \\
%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}  \\
%& 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} \\
\end{tabular}
\end{abstract}

\vfill

\begin{center}
\epsfig{file=all,height=1.5in}
\epsfig{file=overview-new,height=1.5in}
\end{center}

\pagebreak

\section{Overview of Fleet}

A Fleet processor is organized around a {\it switch fabric}, which is
a packet-switched network with reliable in-order delivery.  The switch
fabric is used to carry data between different functional units,
called {\it ships}.  Each ship is connected to the switch fabric by
one or more programmable elements known as {\it docks}.

A {\it path} specifies a route through the switch fabric from a
particular {\it source} to a particular {\it destination}.  The
combination of a path and a single word to be delivered is called a
{\it packet}.  The switch fabric carries packets from their sources to
their destinations.  Each dock has two destinations: one for {\it
  instructions} and one for {\it data}.  A Fleet is programmed by
depositing instruction packets into the switch fabric with paths that
will lead them to instruction destinations of the docks at which they
are to execute.

When a packet arrives at the instruction destination of a dock, it is
enqueued for execution.  Before the instruction executes, it may cause
the dock to wait for a packet to arrive at the dock's data destination
or for a value to be presented by the ship.  When an instruction
executes it may consume this data and may present a data value to the
ship or transmit a packet.

When an instruction sends a packet into the switch fabric, it may
specify that the payload of the packet is irrelevant.  Such packets
are known as {\it tokens}, and consume less energy than data packets.


\begin{center}
\epsfig{file=overview-new,width=2.5in}\\
{\it Overview of a Fleet processor; dark gray shading represents the
  switch fabric, ships are shown in light gray, and docks are shown in blue.}
\end{center}
\color{black}

\pagebreak

\section{The FleetTwo Dock}

The diagram below represents a conceptual view of the interface
between ships and the switch fabric; actual implementation circuitry
may differ.

\begin{center}
\epsfig{file=all,width=3.5in}\\
{\it An ``input'' dock and ``output'' dock connected to a ship.  Solid
  blue lines carry either tokens or data words, red lines carry either
  instructions or torpedoes, and dashed lines carry only tokens.}
\end{center}

Each dock consists of a {\it data latch}, which is as wide as a single
machine word and a {\it pump}, which is a circular fifo of
instruction-width latches.  The values in the pump control the data
latch.  The dock also includes a {\it path latch}, which
stores the path along which outgoing packets will be sent.\color{black}

Note that the pump in each dock has a destination of its own; this is
the {\it instruction destination} mentioned in the previous section.

From any source to any dock's data destination there are
two distinct paths which differ by a single bit.  This bit is known as
the ``signal'' bit, and the routing of a packet is not affected by it;
the signal bit is used to pass control values between docks.  Note that paths
terminating at an {\it instruction} destination need not have a signal
bit.  \color{black}

\pagebreak
\section{Instructions}

In order to cause an instruction to execute, the programmer must first
arrange for that instruction word to arrive in the data latch of some
output dock.  For example, this might be the ``data read'' output dock
of the memory access ship or the output of a fifo ship.  Once an
instruction has arrived at this output dock, it is {\it dispatched} by
sending it to the {\it instruction port} of the dock at which it is to
execute.

Each instruction is 26 bits long, which makes it possible for an
instruction and an 11-bit path to fit in a single word of memory.
This path is the path from the {\it dispatching} dock to the {\it
  executing} dock.

\setlength{\bitwidth}{3.5mm}
{\tt \footnotesize
\begin{bytefield}{37}
  \bitheader[b]{0,10,11,36}\\
  \bitbox{26}{instruction} 
  \bitbox{11}{dispatch path} 
\end{bytefield}}




\subsection{Life Cycle of an Instruction}

The diagram below shows an input dock for purposes of illustration:

\begin{center}
\epsfig{file=in,width=4in}\\
{\it an input dock}
\end{center}

%\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}\\
{\it an output dock}
\end{center}

\subsubsection{Torpedoes}

A token sent to an instruction destination is called a {\it torpedo}.
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}.

\subsection{Format of an Instruction}

All instruction words have the following format:

\newcommand{\bitsHeader}{
  \bitbox{1}{I} 
  \bitbox{1}{OS}
  \bitbox{3}{P} 
}
\newcommand{\bitsHeaderNoI}{
  \bitbox{1}{} 
  \bitbox{1}{OS}
  \bitbox{3}{P} 
}

\setlength{\bitwidth}{3.5mm}
{\tt \footnotesize
\begin{bytefield}{37}
  \bitheader[b]{0,10,11,31,32,34-36}\\
\color{black}
  \bitsHeader
\color{light}
  \bitbox[tbr]{21}{} 
  \bitbox{11}{dispatch path} 
\color{black}
\end{bytefield}}

\begin{itemize}
\item The {\tt I} bit stands for {\tt Interruptible}, and indicates if an
instruction is vulnerable to torpedoes.  This bit only appears in {\tt move} instructions.

\item The {\tt OS} (``One Shot'') bit indicates whether or not this
  instruction can pass through the pump more than once.  If set to
  {\tt 1}, then the instruction is a ``one-shot'' instruction, and
  does not pass through the instruction fifo more than once.

\item  The {\tt P} bits are a {\it predicate}; this
holds a code which indicates if the instruction should be executed or
ignored depending on the state of flags in the dock.
\end{itemize}

\pagebreak
\subsection{Loop Counters}

A programmer can perform two types of loops: {\it inner} loops of only
one instruction and {\it outer} loops of multiple instructions.  Inner
loops may be nested within an outer loop, but no other nesting of
loops is allowed.

The dock has two loop counters, one for each kind of loop:

\begin{itemize}
\item {\tt OLC} is the Outer Loop Counter
\item {\tt ILC} is the Inner Loop Counter
\end{itemize}

The {\tt OLC} applies to all instructions and can hold integers {\tt
  0..MAX_OLC}.

The {\tt ILC} applies only to {\tt move} instructions and can hold
integers {\tt 0..MAX_ILC} as well as a special value: $\infty$.  When
{\tt ILC=0} the next {\tt move} instruction executes zero times (ie is
ignored).  When {\tt ILC=$\infty$} the next {\tt move} instruction
executes until interrupted by a torpedo.  After every {\tt move}
instruction the {\tt ILC} is reset to {\tt 1} (note that it is reset
to {\tt 1}, {\it not to 0}).

\color{black}
\subsection{Flags and Predication}

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
      may be set and cleared by the programmer.

%\item
%
% The {\tt L} flag, known as the {\it last} flag, is set whenever
%      the value in the outer counter ({\tt OLC}) is one,
\color{black}
% indicating
%      that the dock is in the midst of the last iteration of an
%      outer loop.  This flag can be used to perform certain
%      operations (such as sending a completion token) only on the last
%      iteration of an outer loop.

\item The {\tt C} flag is known as the {\it control} flag, and may be
      set by the {\tt move} instruction based on information from the
      ship or from an inbound packet.  See the {\tt move} instruction
      for further details.
\color{black}

\end{itemize}

The {\tt P} field specifies a three-bit {\it predicate}.  The
predicate determines which conditions must be true in order for the
instruction to execute; if it is not executed, it is simply {\it
  ignored}.  The table below shows what conditions must be true in
order for an instruction to execute:

\begin{center}
\begin{tabular}{|r|ll|}\hline
Code       & Execute & if \\\hline
{\tt 000:} & {\tt OLC$\neq$0} & and {\tt A=0} \\
{\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:} & 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:
\begin{enumerate}
\item Requeueing:
      \begin{itemize}
      \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=1})
      and a torpedo is present in the waiting area: consume the
      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
      not} a {\tt move}: execute the instruction.
      \end{itemize}
\end{enumerate}


\color{black}


\pagebreak
\section{Instructions}

The dock supports four instructions:
{\tt move} (variants: {\tt moveto}, {\tt dispatch}),
{\tt shift},
{\tt set}, and
{\tt tail}.
\color{black}


\subsection{{\tt move}}

\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
  \bitheader[b]{14-20}\\
\color{light}
  \bitsHeader
\color{black}
  \bitbox{1}{0} 
  \bitbox{1}{1} 
  \bitbox{1}{\tt Ti}
  \bitbox{1}{\tt Di}
  \bitbox{1}{\tt Dc}
  \bitbox{1}{\tt Do}
  \bitbox{1}{\tt To}
  \bitbox[l]{19}{}
\end{bytefield}}

\begin{bytefield}{26}
  \bitheader[b]{0,12,13}\\
  \bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt Immediate\to Path})}
  \bitbox[r]{1}{}
  \bitbox{1}{\tt 1}
  \bitbox{13}{\tt Immediate}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{11,12,13}\\
  \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\footnotesize {\tt DataPredecessor[37:25]\to Path}})\ \ }
  \bitbox[r]{1}{}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 1}
\color{light}
  \bitbox[trb]{12}{}
\color{black}
\end{bytefield}

\begin{bytefield}{26}
  \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}
\color{light}
  \bitbox[trb]{12}{}
\color{black}
\end{bytefield}}
\bitsMove

\begin{itemize}
\item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
\item {\tt Di} - Data Input: wait for the data predecessor to be full and drain it.
\item {\tt Dc} - Data Capture: pulse the data latch.
\item {\tt Do} - Data Output: fill the data successor.
\item {\tt To} - Token Output: fill the token successor.
\end{itemize}

The data successor and token successor must both be empty in order for
a {\tt move} instruction to attempt execution.

Every time the {\tt move} instruction executes, the {\tt C} flag may
be set:

\begin{itemize}
\item At an {\it input} dock the {\tt C} flag is set to the signal bit
      of the incoming packet if {\tt Di} or {\tt Ti} is set.

\item At an {\it output} dock the {\tt C} flag is set to a value
      provided by the ship if the {\tt Di} bit is set, and to the
      signal bit of the incoming packet if {\tt Di} is clear and {\tt
      Ti} is set.
\end{itemize}

\color{black}

\pagebreak

\subsection{{\tt set}}

The {\tt set} command is used to set or decrement the inner loop
counter, outer loop counter, and data latch.

\newcommand{\bitsSet}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
  \bitheader[b]{19-25}\\
  \bitsHeaderNoI
  \bitbox{1}{1}
  \bitbox{1}{0} 
\color{light}
  \bitbox{5}{Dest} 
  \bitbox{14}{} 
\color{black}
\end{bytefield}}

\begin{bytefield}{26}
  \bitheader[b]{0,5,12-18}\\
  \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt OLC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 1000\color{black}}
  \bitbox{3}{\tt 100}
  \bitbox{6}{}
  \bitbox{6}{\tt Immediate}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{12-18}\\
  \bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt OLC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 1000\color{black}}
  \bitbox{3}{\tt 010}
  \bitbox{12}{}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{12-18}\\
  \bitbox[1]{6}{\raggedleft {\tt OLC-1}\to{\tt OLC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 1000\color{black}}
  \bitbox{3}{\tt 001}
  \bitbox{12}{}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{0,5,6,12-18}\\
  \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt ILC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0100\color{black}}
  \bitbox{3}{\tt 100}
  \bitbox{5}{}
  \bitbox{1}{\tt 0}
  \bitbox{6}{\tt Immediate}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{6,12-18}\\
  \bitbox[1]{6}{\raggedleft $\infty$\to{\tt ILC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0100\color{black}}
  \bitbox{3}{\tt 100}
  \bitbox{5}{}
  \bitbox{1}{\tt 1}
  \bitbox{6}{}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{12-18}\\
  \bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt ILC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0100\color{black}}
  \bitbox{3}{\tt 010}
  \bitbox{12}{}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{0,13-18}\\
  \bitbox[1]{6}{\raggedleft \footnotesize {\tt 0-Extended Immediate}\to{\tt Data Latch}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0010\color{black}}
  \bitbox{1}{\tt 0}
  \bitbox{14}{\tt Immediate}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{0,13-18}\\
  \bitbox[1]{6}{\raggedleft \footnotesize {\tt 1-Extended Immediate}\to{\tt Data Latch}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0010\color{black}}
  \bitbox{1}{\tt 1}
  \bitbox{14}{\tt Immediate}
\end{bytefield}

\begin{bytefield}{26}
  \bitheader[b]{0,5,6,11,15-18}\\
  \bitbox[1]{6}{\raggedleft {\tt Update Flags}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0001\color{black}}
  \bitbox{3}{}
  \bitbox{6}{\tt nextA}
  \bitbox{6}{\tt nextB}
\end{bytefield}


\color{black}

}
\bitsSet

The FleetTwo implementation is likely to have an unarchitected
``literal latch'' at the on deck ({\tt 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 a {\tt set Data Latch} instruction
executes\color{black}.

Each of the {\tt nextA} and {\tt nextB} fields 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
\begin{bytefield}{6}
  \bitheader[b]{0-5}\\
  \bitbox{1}{${\text{\tt A}}$}
  \bitbox{1}{$\overline{\text{\tt A}}$}
  \bitbox{1}{${\text{\tt B}}$}
  \bitbox{1}{$\overline{\text{\tt B}}$}
  \bitbox{1}{${\text{{\tt C}\ }}$}
  \bitbox{1}{$\overline{\text{{\tt C}\ }}$}
\end{bytefield}}
\end{center}

Each bit corresponds to one possible input; all inputs whose bits are
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 set Flags} can
be used to create a {\tt nop} (no-op) by setting each flag to itself.


\color{black}

\pagebreak
\subsection{{\tt shift}}

\newcommand{\shiftImmediateSize}{19}

Each {\tt shift} instruction carries an immediate of \shiftImmediateSize\ 
bits.  When a {\tt shift} instruction is executed, this immediate is copied
into the least significant \shiftImmediateSize\  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 \shiftImmediateSize\ bits at a time.

\newcommand{\bitsShift}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,18-20}\\
\color{light}
  \bitsHeaderNoI
\color{black}
  \bitbox{1}{0} 
  \bitbox{1}{0} 
\color{black}
  \bitbox{\shiftImmediateSize}{Immediate} 
\end{bytefield}}
}
\bitsShift

The FleetTwo implementation is likely to have an unarchitected
``literal latch'' at the on deck ({\tt 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.

\color{black}

\subsection{{\tt tail}}

\newcommand{\bitsTail}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{26}
  \bitheader[b]{19-20}\\
\color{light}
  \bitbox{5}{} 
\color{black}
  \bitbox{1}{1}
  \bitbox{1}{1}
\color{light}
  \bitbox[tbr]{19}{} 
\end{bytefield}}}
\bitsTail

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
%\subsection{{\tt takeOuterLoopCounter}}
%
%\setlength{\bitwidth}{5mm}
%{\tt
%\begin{bytefield}{26}
%  \bitheader[b]{16-19,21}\\
%\color{light}
%  \bitbox{1}{A}
%  \bitbox{1}{OS} 
%  \bitbox{2}{P}
%\color{black}
%  \bitbox{3}{000}
%  \bitbox{1}{0}
%  \bitbox{2}{11}
%\color{light}
%  \bitbox[tbr]{16}{} 
%\color{black}
%\end{bytefield}}
%
%This instruction copies the value in the outer loop counter {\tt OLC}
%into the least significant bits of the data latch and leaves all other
%bits of the data latch unchanged.
%
%\subsection{{\tt takeInnerLoopCounter}}
%
%\setlength{\bitwidth}{5mm}
%{\tt
%\begin{bytefield}{26}
%  \bitheader[b]{16-19,21}\\
%\color{light}
%  \bitbox{1}{A}
%  \bitbox{1}{OS} 
%  \bitbox{2}{P}
%\color{black}
%  \bitbox{3}{???}
%  \bitbox{1}{?}
%  \bitbox{2}{??}
%\color{light}
%  \bitbox[tbr]{16}{} 
%\color{black}
%\end{bytefield}}
%
%This instruction copies the value in the inner loop counter {\tt ILC}
%into the least significant bits of the data latch and leaves all other
%bits of the data latch unchanged.
%
%
%
%%\pagebreak
%%\subsection{{\tt interrupt}}
%%
%%\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 an {\tt interrupt} instruction reaches {\tt IH}, it will wait
%there for the {\tt OD} stage to be full with an instruction that has
%the {\tt IM} bit set.  When this occurs, the instruction at {\tt OD}
%{\it will not execute}, but {\it may reloop} if the conditions for
%relooping are met.
%\footnote{The ability to interrupt an instruction yet have it reloop is very
%useful for processing chunks of data with a fixed size header and/or
%footer and a variable length body.}
%
%
%\subsection{{\tt massacre}}
%
%\setlength{\bitwidth}{5mm}
%{\tt
%\begin{bytefield}{26}
%  \bitheader[b]{16-19,21}\\
%\color{light}
%  \bitbox{4}{} 
%\color{black}
%  \bitbox{3}{000} 
%  \bitbox{1}{1}
%  \bitbox{2}{01}
%\color{light}
%  \bitbox[tbr]{16}{} 
%\color{black}
%\end{bytefield}}
%
%When a {\tt massacre} instruction reaches {\tt IH}, it will wait there
%for the {\tt OD} stage to be full with an instruction that has the
%{\tt IM} bit set.  When this occurs, all instructions in the
%instruction fifo (including {\tt OD}) are retired.
%
%\subsection{{\tt clog}}
%
%\setlength{\bitwidth}{5mm}
%{\tt
%\begin{bytefield}{26}
%  \bitheader[b]{16-19,21}\\
%\color{light}
%  \bitbox{4}{} 
%\color{black}
%  \bitbox{3}{000} 
%  \bitbox{1}{1}
%  \bitbox{2}{10}
%\color{light}
%  \bitbox[tbr]{16}{} 
%\color{black}
%\end{bytefield}}
%
%When a {\tt clog} instruction reaches {\tt OD}, it remains there and
%no more instructions will be executed until an {\tt unclog} is
%performed.
%
%\subsection{{\tt unclog}}
%
%\setlength{\bitwidth}{5mm}
%{\tt
%\begin{bytefield}{26}
%  \bitheader[b]{16-19,21}\\
%\color{light}
%  \bitbox{4}{} 
%\color{black}
%  \bitbox{3}{000} 
%  \bitbox{1}{1}
%  \bitbox[lrtb]{2}{11}
%\color{light}
%  \bitbox[tbr]{16}{} 
%\color{black}
%\end{bytefield}}
%
%When an {\tt unclog} instruction reaches {\tt IH}, it will wait there
%until a {\tt clog} instruction is at {\tt OD}.  When this occurs, both
%instructions retire.
%
%Note that issuing an {\tt unclog} instruction to a dock which is not
%clogged and whose instruction fifo contains no {\tt clog} instructions
%will cause the dock to deadlock.



\pagebreak
\section*{Instruction Encoding Map\color{black}}

\hspace{-1cm}{\tt shift}\\
\bitsShift

\hspace{-1cm}{\tt set}\\
\bitsSet

\hspace{-1cm}{\tt move}\\
\bitsMove

\hspace{-1cm}{\tt tail}\\
\bitsTail


\color{black}

\pagebreak
\epsfig{file=all,height=5in,angle=90}

\pagebreak
\subsection*{Input Dock}
\epsfig{file=in,width=8in,angle=90}

\pagebreak
\subsection*{Output Dock}
\epsfig{file=out,width=8in,angle=90}


%\pagebreak
%\epsfig{file=ports,height=5in,angle=90}

%\pagebreak
%\epsfig{file=best,height=5in,angle=90}


\end{document}