archman updates

[fleet.git] / doc / archman.tex

\documentclass[10pt,oneside]{article}
\reversemarginpar 
\usepackage{palatino}
\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}
\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})}

In \cite{ies02}, Sutherland writes:

{\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}{K} 
  \bitbox{1}{L} 
  \bitbox{1}{Ti} 
  \bitbox{1}{Di} 
  \bitbox{1}{Dc} 
  \bitbox{1}{Do} 
  \bitbox{1}{To} 
  \bitbox{1}{Rq} 
  \bitbox{7}{Count} 
  \bitbox{11}{Data/Token Path}
\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}{K} 
  \bitbox{1}{L} 
  \bitbox{1}{Ti} 
  \bitbox{1}{Di} 
  \bitbox{1}{Dc} 
  \bitbox{1}{Do} 
  \bitbox{1}{To} 
  \bitbox{1}{Rq} 
  \bitbox{7}{Count} 
  \bitbox{11}{Data/Token Path}
\end{bytefield}
}


\pagebreak

\section*{Instruction Formats}

Instructions can be grouped into two categories: {\it killing}
instructions, which are acted upon as soon as they leave the
instruction horn, and {\it executing} instructions, which pass through
the instruction queue before being acted upon.

Blank fields below are reserved for future use and must be set to
zero.

Note that the arbiter is requested whenever {\it any of the first
  three bits is {\tt 1}}.  If the arbiter is not requested, 



\setlength{\bitwidth}{5mm}

\subsection*{Killing Instructions}

Kill (kill anything other than a Clog)

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

UnClog (kill a Clog)

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

\subsection*{Executing Instructions}
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}}

Literal (sign extended, implicit {\tt Rq=1})

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


Normal

{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,6,7,17-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}}




\pagebreak
\subsection*{Field Descriptions}
{\tt
\begin{bytefield}{26}
  \bitheader[b]{0,6,7,16-25}\\
  \bitbox{1}{0} 
  \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*{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}

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 (FIXME).
\end{itemize}

\begin{verbatim}
essence of the pump:

ti
di

dc (data capture)
dl (data literal, take from instruction bits)

di
doi (data output, destination taken from instruction)
dod (data output, destination taken from Data register)

set count
decrement count

requeue if count>0
requeue unconditionally
repeat  if count>0
repeat  unconditionally

\end{verbatim}