major updates to manual

[fleet.git] / doc / archman.tex

\documentclass[10pt,oneside]{article}
\reversemarginpar 
\usepackage{palatino}
\usepackage{wrapfig}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{parskip}
\usepackage{register}
\usepackage{bytefield}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
\renewcommand{\ttdefault}{cmtt}
\title{The FleetTwo Architecture Manual\\{\normalsize A Programmer's View of Fleet}}
\begin{document}
\maketitle

\begin{thebibliography}{[GDG01]}
\bibitem[IES02]{ies02}
  Sutherland, Ivan,
  \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies02-FLEET-A.Once.Instruction.Computer.pdf}{\it UCB-IES02: Fleet -- A One Instruction Computer}
\bibitem[IES14]{ies14}
  Sutherland, Ivan,
  \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies14-Fleet.Definition.pdf}{\it UCB-IES14: The Fleet Definition}
\bibitem[IES44]{ies44}
  Sutherland, Ivan,
  \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies44-Fleet.Definition.pdf}{\it UCB-IES44: The Fleet Definition}
\bibitem[MS68]{WheelOfReincarnation}
  Myer, T. and Sutherland, Ivan, {\it On the Design of Display Processors}
  Communications of the ACM, Vol 11, No. 6, June 1968 .
\end{thebibliography}

\vspace{3cm}
\begin{abstract}
This manual attempts to detail all those aspects of Fleet which are
visible to a software programmer or compiler backend.

This document assumes that the reader is broadly familiar with the
Fleet architecture and the motivation behind it.  For a far better
introduction to these topics, the reader is referred to \cite{ies02}
\cite{ies14} and \cite{ies44}.  Please bear in mind that many of the
details in these documents have been changed, but they still serve as
the authoritative introduction to the architecture.  After reviewing
these introductory papers, the reader is invited to digest this
architecture manual for the latest information on the details
necessary to write software and compilers for Fleet.
\end{abstract}


\pagebreak
\section*{Introduction (from \cite{ies02})}

During the past two and a half years, the Fleet architecture has gone
through massive changes and improvements.  In spite of this, however,
the fundamental idea behind Fleet remains unchanged.  As Sutherland
writes in the original Berkeley Fleet description \cite{ies02},

{\it
When computers were new, logic and storage were expensive and wires
were relatively cheap.  Early computer designers avoided using logic
wherever possible but were not greatly concerned with communication.
They made design choices consistent with the costs of the day.  My
favorite example is the jump instruction.  Early designers put jump
instructions at the end of each block of code to avoid the expense of
storing the address of the next block while executing the present one.

Today's chip fabrication methods invert the older cost balance.  In
today's integrated circuits logic and memory are now almost free but
communication costs dominate chip area, energy consumption and delay.
In spite of these changes in the stuff from which we make computers,
vestiges of the past remain in many of today's common microprocessor
designs.  For example, jump instructions still appear at the end of
each basic block of code in spite of the need to pre-fetch the next
block while executing this one.  It seems better today to store a
pointer to the next block and the length of the current block early in
each block of code.

Instead of following the path of history, I'd like to listen carefully
to what modern chip structures have to teach about how one might build
a modern computer.  I see three major lessons.  First, simplicity can
reduce cost.  Second, moving data will consume most of the time,
energy and chip area of a modern computer. And third, the low cost of
logic makes concurrency available if we can figure out how to use it.

\begin{itemize}

\item {\bf Simplicity}: The Fleet architecture seeks simplicity by treating
      all processing devices alike...

\item {\bf Communication}: The Fleet architecture seeks to control the
      cost of communication by putting it under direct programmer
      control.  Thus Fleet avoids instructions like {\sc ADD} or {\sc STORE} that
      include concealed communication to and from a register file...

\item {\bf Concurrency}: The Fleet architecture assumes concurrency
      nearly everywhere...

\item {\bf Asynchrony}: This provides enormous flexibility for
      implementers to improve the performance or reduce the cost of
      the processing devices in a Fleet system.  -- Synchronous
      implementations both of ships and of the switch fabric are
      possible provided they use validity or occupancy bits to achieve
      the arbitrary delays required at sources and destinations...

\end{itemize}
}


\pagebreak
\section*{The Programmer's View of The Ship-Fabric Interface}

The role of the Fleet switch fabric is to carry {\it packets} from
{\it sources} to {\it destinations}.

A packet consists of a {\it path} and a {\it payload}.  The path is
some string of bits which tells the switch fabric how to route from
the desired source to the desired destination.  The distinction
between a {\it path} and a {\it destination} is extremely important!
The payload is either a {\it token} or a {\it data item}.  If the
payload is a data item, it includes one machine word of data.

The diagram below represents a {\it programmer's} conceptual view of
the interface between ships and the switch fabric.  Actual
implementation circuitry may differ substantially.  Sources and
destinations which can send and recieve only tokens -- not data items
-- are drawn as dashed lines.

\vspace{0.3cm}
\begin{center}
\epsfig{file=ports,width=4in}
\end{center}
\vspace{0.3cm}

The term {\it port} refers to each interface to the ship, the {\it
  valve} connecting it to the switch fabric, and the corresponding
sources and destinations on the switch fabric.

Each valve 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 contents of the instruction fifo
control the data latch, as future chapters will explain.

Note that the pump in each valve has a destination of its own, and
that there is no buffering fifo guarding this destination.  Note that
all other destinations are guarded by a buffering fifo; the size of
this fifo is exposed to the software programmer so she can ensure that
deadlock does not occur.


\pagebreak
\section*{Data Formats}

\subsection*{Packet Path (12 bits)}

These bits appear physically within the switch fabric, and have
``address bit timing.''  The {\tt T} bit is the ``tokenhood'' bit; if
set, this packet represents a token and it does not cause the switch
fabric data latches to fire.

{\tt\footnotesize
\begin{bytefield}{49}
  \bitheader[b]{37,47,48}\\
  \bitbox{1}{T} 
  \bitbox{11}{Path} 
  \bitbox[l]{37}{} 
\end{bytefield}
}

\subsection*{Data Word In Memory (37 bits)}

A word of data is 37 bits wide.

{\tt\footnotesize
\begin{bytefield}{49}
  \bitheader[b]{0,36}\\
  \bitbox[r]{12}{}
  \bitbox{37}{Data Word} 
\end{bytefield}
}

\subsection*{Packet In Flight (49 bits)}

{\tt\footnotesize
\begin{bytefield}{49}
  \bitheader[b]{0,36,37,47,48}\\
  \bitbox{1}{T} 
  \bitbox{11}{Packet Path} 
  \bitbox{37}{Data Word} 
\end{bytefield}
}

\subsection*{Instruction In Memory (37 bits)}

An instruction must be no wider than a memory word.  The next section
explains the bits in greater detail.  The {\tt Instruction Path} is
the path which the instruction itself will take in order to arrive at
the desired pump destination.  The {\it Data/Token Path} is placed on
any packet inserted into the switch fabric as a result of executing
the instruction.

{\tt\tiny
\begin{bytefield}{49}
  \bitheader[b]{0,10,11,17,18-26,36}\\
  \bitbox[r]{12}{}
  \bitbox{11}{Instruction Path}
  \bitbox{1}{1} 
  \bitbox{1}{Ti} 
  \bitbox{1}{Di} 
  \bitbox{1}{Dc} 
  \bitbox{1}{Do} 
  \bitbox{1}{To} 
  \bitbox{1}{Ig} 
  \bitbox{1}{Rq} 
  \bitbox{11}{Data/Token Path} 
  \bitbox{7}{Count} 
\end{bytefield}
}

\subsection*{Instruction Packet In Flight (49 bits)}

Note that Fleet simply copies the {\tt Instruction Path} field, bit
for bit, into the packet {\tt Path} field in order to ``dispatch'' an
instruction.

{\tt\tiny
\begin{bytefield}{49}
  \bitheader[b]{0,10,11,17,18-25,37,47,48}\\
  \bitbox[r]{1}{0} 
  \bitbox{11}{Instruction Path}
  \bitbox{11}{Instruction Path}
  \bitbox{1}{1} 
  \bitbox{1}{Ti} 
  \bitbox{1}{Di} 
  \bitbox{1}{Dc} 
  \bitbox{1}{Do} 
  \bitbox{1}{To} 
  \bitbox{1}{Ig} 
  \bitbox{1}{Rq} 
  \bitbox{11}{Data/Token Path} 
  \bitbox{7}{Count} 
\end{bytefield}
}

\setlength{\bitwidth}{5mm}
\pagebreak

\section*{Instruction Formats}
\begin{wrapfigure}{R}{2in}
\epsfig{file=locations,width=2in}
\vspace{-0.4in}
\end{wrapfigure}
Within the pump's instruction fifo, there are two points of particular
interest.  The first point is the {\it insertion point}, which is the
point in the ring where new instructions enter from the switch fabric.
The other point of interest is the {\it execution point}, which is the
point in the ring where instructions other than {\tt kill} and {\tt
  unclog} are performed.

The programmer may assume that the insertion point is the immediate
successor of the insertion point.

\vspace{0.3cm}
{\bf Kill}

{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,6,7,20-25}\\
  \bitbox{1}{0} 
  \bitbox{1}{0} 
  \bitbox{1}{1} 
  \bitbox{1}{0} 
  \bitbox{1}{1} 
  \bitbox{14}{}
  \bitbox{7}{Count} 
\end{bytefield}}
When a {\tt kill} instruction reaches the insertion point, it will
wait there for a non-{\tt clog} instruction to reach the execution
point.  When this occurs, the instruction at the execution point is
retired and the count field of the {\tt kill} instruction is
decremented.  If the {\tt kill} instruction's count was {\tt 0} before
decrementing, the {\tt kill} instruction is retired.

\vspace{0.3cm}
{\bf Clog}

{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,20-25}\\
  \bitbox{1}{0} 
  \bitbox{1}{0} 
  \bitbox{1}{1} 
  \bitbox{1}{0} 
  \bitbox{1}{0} 
  \bitbox{21}{}
\end{bytefield}}
When a {\tt clog} instruction reaches the execution point, no more
instructions will be executed until an {\tt unclog} is performed.

\vspace{0.3cm}
{\bf UnClog}

{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,20-25}\\
  \bitbox{1}{0} 
  \bitbox{1}{0} 
  \bitbox{1}{0} 
  \bitbox{1}{1} 
  \bitbox{1}{0} 
  \bitbox{21}{}
\end{bytefield}}
When an {\tt unclog} instruction reaches the insertion point, it will wait
there until a {\tt clog} instruction is at the execution point.  When
this occurs, both instructions retire. {\it Note:} this means
that if an {\tt unclog} instruction enters the instruction fifo
without a {\tt clog} ahead of it, the pump's insertion point will become
irretrievably jammed.

\vspace{0.3cm}
{\bf Literal}

{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,6,7,23-25}\\
  \bitbox{1}{0} 
  \bitbox{1}{1} 
  \bitbox{17}{Literal}
  \bitbox{7}{Count} 
\end{bytefield}}
When a literal instruction reaches the execution point, its {\tt
  Literal} field is sign-extended to a full word length and captured
in the data latch.


\pagebreak
{\bf Normal Instruction (at Execution Point)}

{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,6,7,16-25}\\
  \bitbox{1}{1} 
  \bitbox{1}{Ti} 
  \bitbox{1}{Di} 
  \bitbox{1}{Dc} 
  \bitbox{1}{Do} 
  \bitbox{1}{To} 
  \bitbox{1}{Ig} 
  \bitbox{1}{Rq} 
  \bitbox{11}{Dest} 
  \bitbox{7}{Count} 
\end{bytefield}
}

\begin{itemize}

  \item [\tt Ti] ({\bf Token Input}) wait for a token and accept
                 it\footnote{{\tt Ti}=1,{\tt Di}=1 is invalid on inbox.}

  \item [\tt Di] ({\bf Data Input}) wait for a datum and accept it.

  \item [\tt Dc] ({\bf Data Capture}) capture (latch) the accepted
                 datum.  This bit is ignored if the incoming packet is
                 a token. \footnote{ Note that {\tt Di}=0,{\tt Dc}=1
                 is meaningless and therefore reserved for other
                 uses.}

  \item [\tt Do] ({\bf Data Output}) emit a datum.

  \item [\tt To] ({\bf Token Output}) emit a token.\footnote{ {\tt To}=1,{\tt
                 Do}=1 have special meaning on an outbox.}

  \item [\tt Ig] ({\bf Ignore {\tt To} Until Last Iteration}) ignore
                 the {\tt To} bit unless {\tt Count=0} \footnote{{\tt
                 To}=0,{\tt Ig}=1 is invalid}

  \item [\tt Rq] ({\bf ReQueue}) if set, instructions having nonzero
                 count are ``Re-Queued'' rather than RePeated.  See
                 {\tt Count} for more detail. \footnote{ An
                 instruction {\it in memory} may not have {\tt
                 Rq=1,Count=0} (use {\tt Rq=0,Count=0})}

  \item  [\tt Count] ({\bf Count}) {\it After} executing:
\begin{verbatim}
if (Count==0) {
    discard this instruction
} else {
    if Count < MAX_COUNT {
      decrement count
    }
    if Rq=1 or Literal {
       put this instruction back into the instruction fifo
    } else {
       execute this instruction again
    }
}
\end{verbatim}
Note how a ``standing'' instruction is encoded as {\tt Count=1111111}       

\item [\tt Dest] ({\bf Data/Token Destination})
   Normally, this field is copied into the address portion of any
   outgoing packet ({\tt Do} on an outbox or {\tt To}).

   However, in the special case of an outbox, if {\tt Do=1,To=1}, then
   the {\it most significant} {\tt 11} bits of the value in the {\it
   data register} are used as a destination address instead.
   %\footnote{This
   %functionality eliminates the need for any sort of ``{\tt Execute}''
   %ship, and lets a {\tt Fifo} ship act as an extension of the
   %instruction queue in the pump.}

\end{itemize}


\pagebreak
\section*{Fleet Assembly Language}

The Fleet Assembly language is designed to be a human-readable
depiction of the bits which comprise a Fleet program.  The formal
syntax is given below:

\verbatiminput{fleet.g}

\pagebreak
\section*{FleetDoc}

Inspired by JavaDoc, the Fleet software toolchain includes a tool
called {\tt FleetDoc}, which processes {\it ship description files}
(with the extension {\tt .ship}).  These files contain sections for:

\begin{itemize}
\item The name of the ship
\item A list of its ports
\item A prose description of the ship
\item A list of the constants associated with a ship
\item Java source code for a software simulation of the ship
\item Verilog source code for an FPGA simulation of the ship
\item A test case for the ship
\item A list of the contributors to all of the above
\end{itemize}

Keeping all of this information in a single file ensures that changes
to one item (such as the list of ports) are propagated to the other
items (such as the verilog code for simulation purposes).

Keeping this information in {\it machine-readable} format makes it
possible to automatically generate tools which depend on the precise
details of ship ports (such as the Fleet assembler) without the risk
inherent in manual synchronization of the spec with the
implementation.

The latter half of this manual is generated automatically from the
contents of the {\tt .ship} files.

\pagebreak
\subsection*{An Example FleetDoc File}
\begin{verbatim}
ship: BitFifo

== Ports ===========================================================
in:   in
in:   inOp
  constant lsbFirst: ....................................1
  constant msbFirst: ....................................0
  constant drop:     .............................uuuuuu..
  constant take:     .......................uuuuuu........
...
  
== TeX ==============================================================
The BitFifo internally stores some number of bits in a fifo structure.
Its capacity is guaranteed to be at least two full machine words or
more.
...

== Fleeterpreter ====================================================
public void service() {
  if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
  ...

== FPGA ==============================================================
always @(posedge clk) begin
  if (!in_r    && in_a)     in_a    <= 0;
  if (!inOp_r  && inOp_a)   inOp_a  <= 0;
  ...

== Test ==============================================================
#expect 1
#expect 68719476736
#ship debug        : Debug
#ship bitfifo      : BitFifo

bitfifo.outOp:      literal BitFifo.outOp[take=37]; [*] deliver;
...

== Contributors =========================================================
Amir Kamil <kamil@cs.berkeley.edu>
Adam Megacz <megacz@cs.berkeley.edu>
\end{verbatim}


\pagebreak
\section*{Java APIs}
\subsection*{Representing Code}
\subsection*{Representing Ships}

\pagebreak
\section*{Misc}

\begin{verbatim}
- sequencing guarantees
- codebag format
- behavior when token arrives at data port, vice versa
- overlapping codebags
\end{verbatim}

\pagebreak
\section*{Future Directions}

\subsection*{The Role of the Count Field}

Looking back on the design of the pump, several things are now
apparent which were not initially.  In particular, it seems that it
could be useful to separate {\it loading the count register} from
other types of instructions.  This would have a few advantages:

\begin{itemize}
\item The size of the count field would not be a consideration in the
      ``instruction budget'' of normal execution instructions

\item It would be possible to have finitely-repeating,
      infinitely-requeueing instructions.  Various implementation
      details\footnote{in many implementations, the count field of an
      instruction is destroyed as it counts down; another register and
      mux would be needed to ``save'' this value so it could be
      restored prior to being requeued} make it awkward to support
      this unless the count register can be manipulated independently
      of instruction execution.
\end{itemize}

With this in mind, we can refactor the ``essence of the pump'' into
the following fields, which are basically orthogonal:

\begin{itemize}
\item wait for a token
\item wait for a datum
\item load the data latch from the awaited datum
\item load the data latch from a literal in the instruction
\item send a datum to a destination indicated by the instruction
\item send a datum to a destination indicated by the data latch value
\item send a token to a destination indicated by the instruction
\item send a token to a destination indicated by the data latch value
\item set the count register to a literal value
\item decrement the count register
\item requeue this instruction if {\tt count>0}
\item requeue this instruction unconditionally
\item repeat this instruction if {\tt count>0}
\item repeat this instruction unconditionally
\end{itemize}

The crucial change here is the decoupling of the act of {\it loading
  the count register} from the act of {\it loading the next
  instruction}.

At this point, it boils down to a question of instruction bit
budgeting.  Currently we have a separate instruction form for
literals, so that the literal can use bits which are not otherwise
relevant to literal instructions (for example, {\tt Di}).  Adding an
additional instruction form for loading the count register would have
similar advantages.


\subsection*{For Just a Little Bit More...}

Compared to early revisions of the Fleet architecture, the valves of
FleetTwo are substantially more powerful.  One might ask, why not add
additional power to the valves, perhaps up to the point of making them
tiny von Neumann machines in their own right?  Indeed, doing so would
risk reliving the {\it Wheel of Reincarnation}
\cite{WheelOfReincarnation}.

I believe, however, that there is a fundamental distinction to be
made between devices whose control flow {\it can branch} and those
whose control flow {\it cannot branch}, and that this distinction is
founded in the geometry of VLSI, and indeed, Euclidean space.
Ultimately, the instruction stream for any component of a processor
must exist in some physical incarnation -- some geometric extent.  If
the control flow of a program is linear, with no branching, then the
instruction stream has an optimal spatial mapping which is quite
efficient: it is simply laid out in FIFO fashion.

By contrast, however, a program whose instruction stream has
unrestricted branching is logically a {\it tree} structure.  Quite
unfortunately, general trees have no efficient mapping onto
two-dimensional surfaces.  By this, I mean that in every possible
mapping, there exists some pair of {\it logically adjacent}
instructions whose {\it physical distance} is proportional to the size
of the entire program, rather than some constant factor irrespective
of the program size.  Therefore I conclude that the spatial mapping of
a program with unrestricted branching is in an entirely different
class than that of programs with linear control flow.  I choose this
distinction as the basis for limiting our valves to linear control
flow sequences.  A similar argument can be made for looping constructs
in which two or more loops may be nested within a single parent loop.

With this distinction in mind, it would not be objectionable for
future incarnations of Fleet to have {\it predicated} instructions at
the valves.  This might take the form of:

\begin{itemize}
\item Instructions to unconditionally set some ``state flags''
\item Instructions to conditionally set some ``state flags'' based on the contents of the data latch
\item Bits which cause an instruction to be ignored or retired based on the state flags
\end{itemize}

I feel that this addition would not risk falling down the slippery
slope -- instruction streams with predicated instructions (but not
unrestricted branching) preserve the crucial property that they have
an efficient spatial mapping.  Any steps beyond this, however, cross a
fairly fundamental line.