[fleet.git] / chips / f2 / doc / am42 / am42.tex

\documentclass[10pt]{article}
\usepackage{palatino}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{color}
\usepackage{bytefield1}
\usepackage{comment}
\usepackage{fancyhdr}
\include{megacz}
\bibliographystyle{alpha}
\pagestyle{fancyplain}

\definecolor{light}{gray}{0.7}

\title{\vspace{-1cm}AM42: The F2 Dock
\\
{\normalsize
Adam Megacz
}}

\begin{document}

\maketitle

\begin{abstract}

To Do:
\\

\begin{verbatim}

    - tokenhood as address bit
    - signal/path boundary/etc
  - Rename EPI and OD to something more meaningful
  - Get rid of OD?
  - get rid of shadow latch
  - single counter
  - figure out C-flag / signal bit situation
    - single "predicate" flag
  - Suggestion that there should be a "T" flag
  - Get rid of "shadow latch" for literals?
  - unify flags and signal bit by saying that the dock can
    see the upper X bits of a word?
    - should have a way to set just the upper X bits of the word
    - flags are actually part of the data latch!
    - the signal bit(s) belong to the Destination (or is it the Path?)
  - flushing situation
  - How do you get a runtime count value to an input dock?
  - Simplify the whole c-flag/signal-bit situation
  - tokenhood should be LITERALLY an address bit!

\end{verbatim}

\begin{tabular}{rl}

29-Aug
&  Initial Version \\
\end{tabular}
\end{abstract}

\vfill

\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 four\ 
destinations: one each for {\it instructions}, {\it
  torpedoes}, {\it tokens},\ and {\it words}.  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.

Packets sent to token and torpedo destinations carry no payload.  Such
packets consume less energy than instruction packets or word packets.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.

X

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

Note that the instruction fifo in each dock has a destination of its
own; this is the {\it instruction destination} mentioned in the
previous section.  A token sent to an instruction destination is
called a {\it torpedo}; it does not enter the instruction fifo, but
rather is held in a waiting area where it may interrupt certain
instructions (see the section on the {\tt move} instruction for further
details).

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.


Source-sequence guarantee.  Shared across instruction/torpedo (?) and
token/word destinations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 destination} of the dock at which
it is to execute.

Each instruction is 25\ bits long, which makes
it possible for an instruction and an 12-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.

\vspace{0.5cm}

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


Note that the 12\ bit {\tt dispatch path}
field is not the same width as the 13 bit {\tt Immediate} path field
in the {\tt move} instruction, which in turn may not be the same width
as the actual path latches in the switch fabric.

The algorithm for expanding a path to a wider width is specific to the
switch fabric implementation, and is not specified by this
document.\footnote{for the Marina experiment, the correct
  algorithm is to sign-extend the path; the most significant bit of
  the given path is used to fill the vacant bit of the latch} In
particular, because the {\tt dispatch path} field is always used to
specify a path which terminates at an instruction destination (never a
data destination), and because instruction destinations ignore the
signal bit, certain optimizations may be possible.


\subsection{Loop Counter}

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

The dock has one loop counter, called {\tt LC}.  It is the
same width as a word carried through the switch fabric (37 bits).

\subsection{Flags}

The dock has four flags: {\tt A}, {\tt B}, {\tt C}, and {\tt Z}.

\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 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.

\item The {\tt Z}\ flag is known as the
      {\it zero}\ flag.  The {\tt
      Z}\ flag is {\it set} whenever the {\tt LC} is zero.
      In an actual implementation the {\tt Z}\ 
      flag might require an actual latch; it might simply be derived
      from the ``zeroness'' of the {\tt LC}.

\end{itemize}

\subsection{Predication}

All instructions except for {\tt head} and {\tt tail} have a three-bit
field marked {\tt P}, which specifies a {\it predicate}.

\begin{center}
\setlength{\bitwidth}{5mm}
{\tt{\footnotesize{
\begin{bytefield}{25}
  \bitheader[b]{0,21,22,24}\\
  \bitbox{3}{P} 
  \bitbox[tbr]{22}{} 

\end{bytefield}}}}
\end{center}

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|l|}\hline
Code       & Execute if \\\hline
{\tt 000:} & {\tt Z=0}\   and {\tt A=0} \\
{\tt 001:} & {\tt Z=0}\   and {\tt A=1} \\
{\tt 010:} & {\tt Z=0}\   and {\tt B=0} \\
{\tt 011:} & {\tt Z=0}\   and {\tt B=1} \\
{\tt 100:} & Unused  \\
{\tt 101:} & {\tt Z=1}\   \\
{\tt 110:} & {\tt Z=0}\   \\
{\tt 111:} & always  \\
\hline\end{tabular}
\end{center}

\pagebreak

\subsection{The Requeue Stage}

The requeue stage has two inputs, which will be referred to as the
{\it enqueueing} input and the {\it recirculating} input.  It has a
single output which feeds into the instruction fifo.

The requeue stage has two states: {\sc Updating} and {\sc
  Circulating}.

\subsubsection{The {\sc Updating} State}

On initialization, the dock is in the {\sc Updating} state.  In this
state the requeue stage is performing three tasks:
\begin{itemize}
\item it is draining the
previous loop's instructions (if any) from the fifo
\item it is executing any ``one
shot'' instructions which come between the previous loop's {\tt tail}
and the next loop's {\tt head}
\item it is loading the instructions of
the next loop into the fifo.
\end{itemize}

In the {\sc Updating} state, the requeue stage will accept any
instruction other than a {\tt tail} which arrives at its {\it
  enqueueing} input, and pass this instruction to its output.  Any
instruction other than a {\tt head} which arrives at the {\it
  recirculating} input will be discarded.

Note that when a {\tt tail} instruction arrives at the {\it
  enqueueing} input, it ``gets stuck'' there.  Likewise, when a {\tt
  head} instruction arrives at the {\it recirculating} input, it also
``gets stuck''.  When the requeue stage finds {\it both} a {\tt tail}
instruction stuck at the {\it enqueueing} input and a {\tt head}
instruction stuck at the {\it recirculating} input, the requeue stage
discards both the {\tt head} and {\tt tail} and transitions to the
{\sc Circulating} state.

\subsubsection{The {\sc Circulating} State}

In the {\sc Circulating} state, the dock repeatedly executes the set
of instructions that are in the instruction fifo.

In the {\sc Circulating} state, the requeue stage will not accept
items from its {\it enqueueing} input.  Any item presented at the {\it
  recirculating} input will be passed through to the requeue stage's
output.

When an {\tt abort} instruction is executed, the requeue stage
transitions back to the {\sc Updating} state.  Note that {\tt abort}
instructions include a predicate; an {\tt abort} instruction whose
predicate is not met will not cause this transition.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Instructions}

\subsection{{\tt move}}

\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{25}
  \bitheader[b]{14-21}\\
\color{light}
  \bitbox{3}{P} 


  \bitbox{1}{0} 
  \bitbox{1}{R} 
  \bitbox{1}{I} 

  \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}{25}
  \bitheader[b]{0,12,13}\\
  \bitbox[1]{10}{\raggedleft {\tt moveto} ({\tt Immediate$\to$ Path})}
  \bitbox[r]{1}{}
  \bitbox{1}{\tt 1}
  \bitbox{13}{\tt Immediate}
\end{bytefield}

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

\begin{bytefield}{25}
  \bitheader[b]{11,12,13}\\
  \bitbox[1]{10}{\raggedleft {\tt move} ({\tt Path} unchanged):}
  \bitbox[r]{1}{}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 0}
\color{light}
  \bitbox[trb]{11}{}
\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.


If the {\tt S} bit is set (not shown -- there is no space left!), the
{\tt move} instruction will subtract one from the {\tt LC} counter
each time it executes.
NOTE: the flavor of {\tt set} instruction which decrements the counter
is now unnecessary; we can simply use a ``do-nothing {\tt move}'' with
the {\tt S}-bit set for that.

If the {\tt R} bit is set, the {\tt move} instruction will execute
repeatedly until its predicate no longer holds (or a torpedo strikes).
An ``infinite'' or ``standing'' move can be achieved by setting the
{\tt R} bit and clearing the {\tt S} bit.


\subsection*{Torpedoes}

The {\tt I} bit stands for {\tt Immune}, and indicates if the
instruction is immune to torpedoes.  If a {\tt move} instruction which
is not immune is waiting to execute and a torpedo is lying in wait,
the torpedo {\it strikes}.  When a torpedo strikes, the
{\tt move} instruction and the torpedo are both consumed and the {\tt
  LC} is set to zero.

\subsection*{The C Flag}

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.

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


\subsection*{Flushing}

The {\tt flush} instruction is a variant of {\tt move} which is valid
only at input docks.  It has the same effect as {\tt deliver}, except
that it sets a special ``flushing'' indicator along with the data
being delivered.

\newcommand{\bitsFlush}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{25}
  \bitheader[b]{14-18}\\
  \bitbox[r]{6}{\raggedleft{\tt flush\ \ }}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 1}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 0}

  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 0}
  \bitbox{1}{\tt 1}

  \bitbox{11}{}
\end{bytefield}}}
\bitsFlush

When a ship fires, it must examine the ``flushing'' indicators on the
input docks whose fullness was part of the firing condition.  If all
of the input docks' flushing indicators are set, the ship must drain
all of their data successors and take no action.  If some, but not
all, of the indicators are set, the ship must drain {\it only the data
  successors of the docks whose indicators were {\bf not} set}, and
take no action.  If none of the flushing indicators was set, the ship
fires normally.



\pagebreak
\subsection{{\tt set}}

The {\tt set} command is used to set the data latch, the flags, or the
loop counter.

\newcommand{\bitsSet}{
{\tt\begin{bytefield}{25}
  \bitheader[b]{19-21}\\
\color{light}
  \bitbox{3}{P} 
  \bitbox{1}{1}
  \bitbox{1}{0} 
  \bitbox{1}{1} 
\color{light}
  \bitbox{4}{Dest} 
  \bitbox{3}{Src} 
  \bitbox{12}{} 
\end{bytefield}}

\begin{bytefield}{25}
  \bitheader[b]{0,11-18}\\
  \bitbox[1]{5}{\raggedleft {\tt Immediate}$\to${\tt LC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 1000}
  \bitbox{3}{\tt 100}
  \bitbox{12}{\tt Immediate}
\end{bytefield}

\begin{bytefield}{25}
  \bitheader[b]{12-18}\\
  \bitbox[1]{5}{\raggedleft {\tt Data Latch}$\to${\tt LC}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 1000}
  \bitbox{3}{\tt 010}
  \bitbox{12}{}
\end{bytefield}

\begin{bytefield}{25}
  \bitheader[b]{0,13-18}\\
  \bitbox[1]{5}{\raggedleft \footnotesize {\tt Sign-Extended Immediate}$\to${\tt Data Latch}}
  \bitbox[r]{1}{}
  \bitbox{4}{\tt 0010}
  \bitbox{1}{\begin{minipage}{0.5cm}{
\begin{center}
\tt{\footnotesize{Si

\vspace{-2mm}gn}}
\end{center}}
\end{minipage}}
  \bitbox{14}{\tt Immediate}
\end{bytefield}

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

}
\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.

The {\tt Sign-Extended Immediate} instruction copies the {\tt
Immediate} field into the least significant bits of the data latch.
All other bits of the data latch are filled with a copy of the
bit marked ``{\tt Sign}.''


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.




\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}{25}
  \bitheader[b]{0,18-21}\\
\color{light}
  \bitbox{3}{P} 


  \bitbox{1}{1} 
  \bitbox{1}{0} 
  \bitbox{1}{0} 

  \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.



\subsection{{\tt abort}}
\newcommand{\bitsAbort}{\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{25}
  \bitheader[b]{18-21}\\
\color{light}
  \bitbox{3}{P} 


  \bitbox{1}{1} 
  \bitbox{1}{1} 
  \bitbox{1}{0} 

  \bitbox{1}{0} 
\color{light}
  \bitbox[tbr]{18}{}
\end{bytefield}}}
\bitsAbort

An {\tt abort} instruction causes a loop to exit; see the section on
the Requeue Stage for further details.

\subsection{{\tt head}}
\newcommand{\bitsHead}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{25}
  \bitheader[b]{18-21}\\
\color{light}
  \bitbox{3}{} 


  \bitbox{1}{1}
  \bitbox{1}{1}
  \bitbox{1}{1}

  \bitbox{1}{0}
\color{light}
  \bitbox[tbr]{18}{} 
\end{bytefield}}}
\bitsHead

A {\tt head} instruction marks the start of a loop; see the section on
the Requeue Stage for further details.


\subsection{{\tt tail}}
\newcommand{\bitsTail}{
\setlength{\bitwidth}{5mm}
{\tt
\begin{bytefield}{25}
  \bitheader[b]{18-21}\\
\color{light}
  \bitbox{3}{} 


  \bitbox{1}{1}
  \bitbox{1}{1}
  \bitbox{1}{1}

  \bitbox{1}{1}
\color{light}
  \bitbox[tbr]{18}{} 
\end{bytefield}}}
\bitsTail

A {\tt tail} instruction marks the end of a loop; see the section on
the Requeue Stage for further details.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section*{Instruction Encoding Map}


\vspace{3mm}\hspace{-1cm}{\tt move}\hspace{1cm}\vspace{-6mm}\\
%\bitsMove
\bitsFlush

\vspace{3mm}\hspace{-1cm}{\tt shift}\hspace{1cm}\vspace{-6mm}\\
\bitsShift

\vspace{3mm}\hspace{-1cm}{\tt set}\hspace{1cm}\vspace{-6mm}\\
%\bitsSet

\vspace{3mm}\hspace{-1cm}{\tt abort}\hspace{1cm}\vspace{-6mm}\\
\bitsAbort

\vspace{3mm}\hspace{-1cm}{\tt head}\hspace{1cm}\vspace{-6mm}\\
\bitsHead

\vspace{3mm}\hspace{-1cm}{\tt tail}\hspace{1cm}\vspace{-6mm}\\
\bitsTail


\end{document}