\documentclass[10pt,oneside]{article}
\reversemarginpar
+\usepackage[titles]{tocloft}
+\usepackage{emp}
+\usepackage{amsmath}
+\DeclareGraphicsRule{*}{mps}{*}{}
+
+\newcommand{\footnoteremember}[2]{
+ \footnote{#2}
+ \newcounter{#1}
+ \setcounter{#1}{\value{footnote}}
+} \newcommand{\footnoterecall}[1]{
+ \footnotemark[\value{#1}]
+}
+
+\ifx\pdftexversion\undefined
+\usepackage[dvips]{graphicx}
+\DeclareGraphicsExtensions{.eps}\else
+\usepackage[pdftex]{graphicx}
+\DeclareGraphicsExtensions{.pdf,.png,.mps,.mp}
+\usepackage{epstopdf}
+\fi
\usepackage{palatino}
\usepackage{wrapfig}
\usepackage{epsfig}
\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}}
+\title{The FleetTwo Architecture Manual\\{\normalsize A Programmer's View of FleetTwo}}
\begin{document}
\maketitle
\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[AM17]{am17}
+ Megacz, Adam,
+ \href{http://research.cs.berkeley.edu/class/fleet/docs/people/adam.megacz/am17-The.Choice.Ship.pdf}{\it UCB-AM17: The Choice Ship}
\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[AM25]{am25}
+ Megacz, Adam,
+ \href{http://research.cs.berkeley.edu/class/fleet/docs/people/adam.megacz/am25.pdf}{\it UCB-AM25: Opcode Ports}
+\bibitem[AM27]{am27}
+ Megacz, Adam,
+ \href{http://research.cs.berkeley.edu/class/fleet/docs/people/adam.megacz/am27.pdf}{\it UCB-AM27: Bypass Paths}
+\bibitem[IES31]{ies31}
+ Sutherland, Ivan,
+ \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies31-Some.SHIPs.pdf}{\it UCB-IES31: Some Ships}
\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}
+\vspace{1cm}
\begin{abstract}
This manual attempts to detail all those aspects of Fleet which are
visible to a software programmer or compiler backend.
\end{abstract}
+%\vfill
+%\fbox{\parbox{5in}{\footnotesize
+%\begin{center}
+%The software described in this memo may be obtained using
+%\href{http://www.darcs.net/}{\tt darcs}, with the command:
+%
+%{\tt darcs get http://research.cs.berkeley.edu/class/fleet/repos/fleet/}
+%\end{center}
+%}}
+
+\pagebreak
+\tableofcontents
+
\pagebreak
-\section*{Introduction (from \cite{ies02})}
+\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},
+through massive changes and improvements. Nonetheless, the
+fundamental vision 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
\pagebreak
-\section*{The Programmer's View of The Ship-Fabric Interface}
+\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}.
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
+destinations which can send and receive only tokens -- not data items
-- are drawn as dashed lines.
\vspace{0.3cm}
\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
+The term {\it port} refers to an interface to the ship, the {\it
+ dock} 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
+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 contents of the instruction fifo
+instruction-width latches. The values in 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
+Note that the pump in each dock 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.
+this fifo is exposed to the software programmer so she can avoid
+deadlock.
\pagebreak
-\section*{Data Formats}
+\section{Data Formats}
-\subsection*{Path (12 bits)}
+\subsection{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.
+These bits appear physically within the switch fabric. \footnote{In
+ the Sun Labs implementation, these bits have ``address bit
+ timing.''} The {\tt T} bit is the ``tokenhood'' bit; if set, this
+packet represents a token\footnote{In the Sun Labs
+ implementation, this bit inhibits the switch fabric data latches
+ from firing.}
{\tt\footnotesize
\begin{bytefield}{49}
\end{bytefield}
}
-\subsection*{Data Word In Memory (37 bits)}
+\subsection{Data Word In Memory (37 bits)}
A word of data is 37 bits wide.
\end{bytefield}
}
-\subsection*{Packet In Flight (49 bits)}
+\subsection{Packet In Flight (49 bits)}
{\tt\footnotesize
\begin{bytefield}{49}
\end{bytefield}
}
-\subsection*{Instruction In Memory (37 bits)}
+\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
{\tt\tiny
\begin{bytefield}{49}
- \bitheader[b]{0,10,11,17,18-26,36}\\
+ \bitheader[b]{0,6,7,17,18-26,36}\\
\bitbox[r]{12}{}
\bitbox{11}{Instruction Path}
\bitbox{1}{1}
\end{bytefield}
}
-\subsection*{Instruction Packet In Flight (49 bits)}
+\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
{\tt\tiny
\begin{bytefield}{49}
- \bitheader[b]{0,10,11,17,18-25,37,47,48}\\
+ \bitheader[b]{0,6,7,17,18-25,37,47,48}\\
\bitbox[r]{1}{0}
\bitbox{11}{Instruction Path}
\bitbox{11}{Instruction Path}
\setlength{\bitwidth}{5mm}
\pagebreak
-\section*{Instruction Formats}
+\section{Instruction Formats}
\begin{wrapfigure}{R}{2in}
\epsfig{file=locations,width=2in}
\vspace{-0.4in}
\vspace{0.3cm}
{\bf Kill}
+\addcontentsline{toc}{subsection}{Kill}
{\tt
\begin{bytefield}{26}
\bitbox{1}{1}
\bitbox{1}{0}
\bitbox{1}{1}
- \bitbox{14}{}
+ \bitbox{14}{don't care}
\bitbox{7}{Count}
\end{bytefield}}
When a {\tt kill} instruction reaches the insertion point, it will
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.
+decrementing, the {\tt kill} instruction is retired. The programmer
+is assured that a kill instruction with a count of $n$ will kill $n+1$
+{\it consecutive} instructions.
\vspace{0.3cm}
{\bf Clog}
+\addcontentsline{toc}{subsection}{Clog}
{\tt
\begin{bytefield}{26}
\bitbox{1}{1}
\bitbox{1}{0}
\bitbox{1}{0}
- \bitbox{21}{}
+ \bitbox{21}{don't care}
\end{bytefield}}
-When a {\tt clog} instruction reaches the execution point, no more
-instructions will be executed until an {\tt unclog} is performed.
+When a {\tt clog} instruction reaches the execution point, it remains
+there and no more instructions will be executed until an {\tt unclog}
+is performed.
\vspace{0.3cm}
{\bf UnClog}
+\addcontentsline{toc}{subsection}{UnClog}
{\tt
\begin{bytefield}{26}
\bitbox{1}{0}
\bitbox{1}{1}
\bitbox{1}{0}
- \bitbox{21}{}
+ \bitbox{21}{don't care}
\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 blocked.
+this occurs, both instructions retire.
\vspace{0.3cm}
{\bf Literal}
+\addcontentsline{toc}{subsection}{Literal}
{\tt
\begin{bytefield}{26}
\pagebreak
-{\bf Normal Instruction (at Execution Point)}
+{\bf Normal Instruction}
+\addcontentsline{toc}{subsection}{Normal Instruction}
{\tt
\begin{bytefield}{26}
\end{bytefield}
}
+\footnoteremember{tidi}{{\tt Ti}=1,{\tt Di}=1 is invalid on input port.}
+\footnoteremember{didc}{Note that {\tt Di}=0,{\tt Dc}=1
+ is meaningless and therefore reserved for other
+ uses.}
+\footnoteremember{todo}{ {\tt To}=1,{\tt Do}=1 have special meaning on an output port.}
+\footnoteremember{toig}{{\tt To}=0,{\tt Ig}=1 is invalid}
\begin{itemize}
+ \item [\tt Ti] ({\bf Token Input}) wait for a token and acknowledge it.
- \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 Di] ({\bf Data Input}) wait for a datum and acknowledge it.
+ \footnoterecall{tidi}\footnoterecall{didc}
\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.}
+ datum in the data latch. This bit is ignored if the incoming packet is
+ a token. \footnoterecall{didc}
- \item [\tt Do] ({\bf Data Output}) emit a datum.
+ \item [\tt Do] ({\bf Data Output}) emit a datum.\footnoterecall{todo}
- \item [\tt To] ({\bf Token Output}) emit a token.\footnote{ {\tt To}=1,{\tt
- Do}=1 have special meaning on an outbox.}
+ \item [\tt To] ({\bf Token Output}) emit a token.\footnoterecall{todo}\footnoterecall{toig}
\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}
+ the {\tt To} bit unless {\tt Count=0}\footnoterecall{toig}
\item [\tt Rq] ({\bf ReQueue}) if set, instructions having nonzero
count are ``Re-Queued'' rather than RePeated. See
}
}
\end{verbatim}
-Note how a ``standing'' instruction is encoded as {\tt Count=1111111}
+Note how a ``standing'' instruction is encoded as {\tt Count=MAX\_COUNT}
\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}).
+ Normally, this field is copied into the path portion of any
+ outgoing packet ({\tt Do} on an output port or {\tt To} on either).
- However, in the special case of an outbox, if {\tt Do=1,To=1}, then
+ However, in the special case of an output port, 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.
+ data register} are used as a destination path 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
\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}
+\section{Opcodes}
+
+Opcodes, as specified in \cite{am25}, are not yet implemented, but
+should be.
+
+\section{Bypasses}
+
+Bypasses, as specified in \cite{am27}, are not yet implemented, but
+should be.
+
+\section{Sequencing Guarantees}
+
+\addcontentsline{toc}{subsection}{Source Sequence Guarantee}
+If two packets leave the same source and have the same path, they will
+arrive at their common destination {\it in the same order in which
+ they left the source}. This assurance is referred to as the {\it
+ source sequence guarantee}.
+
+\addcontentsline{toc}{subsection}{Instruction Sequence Guarantee}
+CodeBags in memory consist of an unordered set of {\it fibers}. A
+fiber is an ordered set of instructions which all share the same
+instruction path, and therefore will be executed by the same pump.
+Any code which dispatches a codebag {\it must} ensure that the
+instructions within a fiber reach their pump in the order in which
+they appear in the fiber. This is known as the {\it instruction
+ sequence guarantee}. Typically the software dispatching a codebag
+will take advantage of the source sequence guarantee in order to
+fulfill the instruction sequence guarantee.
+
+\section{Code Bags}
+
+Code bags may overlap in memory. If the assembler determines that two
+code bags share a set of fibers, it may feel free to re-order those
+fibers in such a way that the code bags overlap, sharing memory words
+for these fibers. The codebag descriptors for the two bags will then
+have different addresses and/or sizes, but the ranges which they
+encompass will overlap.
+
+\subsection{Dispatching Code Bags}
+
+A codebag is ``dispatched'' by causing its constituent words to
+arrive at the data latch of some output port, and then causing that
+output port's pump to execute a {\tt send} (not {\tt sendto})
+instruction, which is encoded as {\tt Do=1,To=1}. Because
+instructions are encoded in such a way that their {\tt Instruction
+ Path} appears in the upper 11 bits, the {\tt send} mechanism will
+correctly route the instruction to a pump will execute it.
+
+Currently the {\tt inCBD} port of the {\tt Memory} ship is ideally
+suited for this purpose, although a similar effect can easily be
+achieved using the {\tt BitFifo} ship in conjunction with the {\tt
+ Memory} ship. The only disadvantage to this arrangement is that the
+{\tt out} port must execute {\tt send} a certain number of times, and
+that number of times is determined by the {\tt size} field of the
+codebag descriptor. Unfortunately this value is not known at compile
+time, so it cannot be encoded as a repeat count on the instruction at
+the {\tt out} port. The typical solution is to place a standing ({\tt
+ count=$\infty$}) {\tt send} instruction at the {\tt out} port of one
+{\tt Memory} ship, and reserve that ship exclusively for dispatching
+code bags.
+
+Note that instructions are encoded relative to a particular dispatch
+output port. That is, the {\tt Instruction Path} field of the
+instruction specifies a path to the desired execution pump -- but this
+path is also specified with respect to some source. Therefore the
+instruction can be correctly dispatched only from that particular
+source. However, it is fairly simple to write software which can
+``relocate'' a codebag by replacing the {\tt Instruction Path} fields
+as needed.
+
+\subsection{Tokens and Data Items}
+
+When a data item is sent to a destination which expects a token, such
+as an output port destination, the effect will be the same as if a token
+had been sent to that destination, and the data value will be lost.
+
+When a token is sent to a destination which expects a data item, such
+as a pump destination or an input port destination, the effect will be
+the same as if a data item {\it having an undefined value} were sent
+to that destination. In other words, the programmer has no completely
+reliable mechanism for distinguishing between tokens and data items.
+
+
+\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
\item It would be possible to have finitely-repeating,
infinitely-requeueing instructions. Various implementation
- details\footnote{in many implementations, the count field of an
+ 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
\begin{itemize}
\item await and acknowledge a token
\item await and acknowledge a datum
+\item load the awaited datum into the path latch (top 11 bits)
\item load the awaited datum into the data latch
-\item load the a literal into the data latch
-\item load a value indicated by the instruction into the path latch
-\item load the top 11 bits of the data latch into the path latch
-\item treat the values in the path latch and data latch as a packet and transmit it
-\item treat the value in the path latch as a token and transmit it
+\item load a literal into the data latch
+\item load a literal into the path latch
+\item send the value in the data latch along the path in the path latch
+\item send a token along the path in the path latch
\item set the count register to a literal value
\item decrement the count register
\item requeue this instruction if {\tt count>0}
latches from two distinct data items, allowing ships to create,
handle, and consume {\it packets} in the form of a pair of data items.
-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.
+At this point, the remaining decisions are simply 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...}
+\subsection{For Just a Little Bit More...}
-Compared to early revisions of the Fleet architecture, the valves of
+Compared to early revisions of the Fleet architecture, the docks 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
+additional power to the docks, 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}.
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.
+instruction stream has an optimal spatial mapping which is
+efficient: simply lay it out as a FIFO.
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
+unrestricted branching is logically a {\it tree} structure.
+Unfortunately, however, 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
+class than that of programs with linear control flow, and I choose this
+distinction as the basis for limiting the docks 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:
+the docks. This might take the form of:
\begin{itemize}
\item Instructions to unconditionally set some ``state flags''
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.
+unrestricted branching or nested looping) preserve the crucial
+property that they have an efficient spatial mapping. Any steps
+beyond this, however, cross a fairly fundamental line.
+
+\addcontentsline{toc}{section}{Ship Descriptions}
projects / fleet.git / blobdiff