-\documentclass[10pt,oneside]{book}
+\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}
+\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*{Glossary}
+\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...
-Port\\
-Inlet\\
-Outlet\\
-Pump\\
-Packet\\
-Data Item\\
-Opcode Port\\
-Bypass\\
+\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*{Programmer's View of The Ship-Fabric Interface}
+\section*{The Programmer's View of The Ship-Fabric Interface}
-The diagram below represents a {\it programmer's} conceptual view of
-the interface between ships and the switch fabric. Actual
-implementations may differ radically, as long as such differences are
-not visible to software programs.
+The role of the Fleet switch fabric is to carry {\it packets} from
+{\it sources} to {\it destinations}.
-%\begin{wrapfigure}{R}{2in}
-\epsfig{file=ports,width=6in}
-%\end{wrapfigure}
+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 term {\it port} refers to each interface to the ship (either
-inbound or outbound) and the machinery required to manage this
-interface. The machinery consists of a {\it latch}, which is as wide
-as a single machine word, a {\it pump}, which is a circular fifo of
-instruction-width latches, and a number of {\it sources} or {\it
- destinations}. Sources and destinations which can only send or
-recieve tokens (rather than data items) are drawn as dashed lines.
-Buffering fifos are drawn where they appear.
+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.
-Note in particular that every pump is a destination capable of
-recieving a data word. This is how instructions are dispatched to
-pumps -- they are inserted into the switch fabric as {\it packets}
-whose destination addresses
+\vspace{0.3cm}
+\begin{center}
+\epsfig{file=ports,width=4in}
+\end{center}
+\vspace{0.3cm}
-Note that addresses are actually paths.
+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.
-Define packets.
+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 Destination Address (12 bits)}
+\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
\begin{bytefield}{49}
\bitheader[b]{37,47,48}\\
\bitbox{1}{T}
- \bitbox{11}{Destination Address}
+ \bitbox{11}{Path}
\bitbox[l]{37}{}
\end{bytefield}
}
\subsection*{Data Word In Memory (37 bits)}
-A word of memory is 37 bits wide. For convenience, we assume that the
-memory word width is also the width of a pointer as well as the width
-of all on-chip data item registers.
+A word of data is 37 bits wide.
{\tt\footnotesize
\begin{bytefield}{49}
\end{bytefield}
}
-\subsection*{Data Packet In Flight (49 bits)}
-
-A {\it data packet} is a data item in the switch fabric, on its way to
-some destination.
+\subsection*{Packet In Flight (49 bits)}
{\tt\footnotesize
\begin{bytefield}{49}
\bitheader[b]{0,36,37,47,48}\\
\bitbox{1}{T}
- \bitbox{11}{Destination Address}
+ \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.
+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 Register Address}
+ \bitbox{11}{Instruction Path}
\bitbox{1}{K}
\bitbox{1}{L}
\bitbox{1}{Ti}
\bitbox{1}{To}
\bitbox{1}{Rq}
\bitbox{7}{Count}
- \bitbox{11}{Data/Token Destination}
+ \bitbox{11}{Data/Token Path}
\end{bytefield}
}
\subsection*{Instruction Packet In Flight (49 bits)}
-A {\it instruction packet} is an instruction in the instruction horn
-(which may or may not be the same thing as the data horn), on its way
-to some instruction register (Valve).
+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 Register Address}
- \bitbox[lr]{11}{}
+ \bitbox{11}{Instruction Path}
+ \bitbox{11}{Instruction Path}
\bitbox{1}{K}
\bitbox{1}{L}
\bitbox{1}{Ti}
\bitbox{1}{To}
\bitbox{1}{Rq}
\bitbox{7}{Count}
- \bitbox{11}{Data/Token Destination}
+ \bitbox{11}{Data/Token Path}
\end{bytefield}
}
\end{itemize}
\pagebreak
-\section{Future Directions}
+\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