\documentclass[10pt,oneside]{article}
\reversemarginpar
+\usepackage[titles]{tocloft}
\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 Toolchain Manual\\{\normalsize A Compiler Writer's View of Fleet}}
+\title{The FleetTwo Toolchain Manual\\{\normalsize A Compiler Writer's View of FleetTwo}}
+\author{Adam Megacz}
\begin{document}
\maketitle
\begin{thebibliography}{[GDG01]}
\bibitem[ArchMan]{ArchMan}
{\it The FleetTwo Architecture Manual}
+\bibitem[Meg06]{SBP}
+ Megacz, Adam, {\it Scannerless Boolean Parsing}. Electronic Notes in
+ Theoretical Computer Science 1368, (Volume 164, Issue 2):
+ Proceedings of the Sixth Workshop on Language Descriptions, Tools,
+ and Applications (LDTA 2006)
\end{thebibliography}
+
\vspace{3cm}
\begin{abstract}
-FIXME
+Fleet compilers and tools work primarily with three entities: Ships,
+Instructions, and Test Cases. In order to promote greater
+interoperability, the FleetTwo Toolchain defines both a Java API and a
+text file format for each of these.
\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
-\section*{Fleet Assembly Language}
+\tableofcontents
-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:
+\pagebreak
+\section{Introduction}
+
+Fleet compilers and tools work primarily with three entities: Ships,
+Instructions, and Test Cases. In order to promote greater
+interoperability, the FleetTwo Toolchain defines both a Java API and a
+textual file format for each of these.
+
+In the case of ships, this takes the form of the {\tt .ship} file
+format for describing ships and the {\tt ShipDescription} Java class
+which an implementation of Fleet uses to inform the toolchain of what
+ships it contains and how they may be used. The toolchain includes a
+library for parsing the textual file format into the Java
+representation.
+
+In the case of instructions, and more generally programs, this takes
+the form of the {\tt .fleet} assembly language file format for
+representing Fleet programs and the {\tt Instruction} and {\tt
+ CodeBag} Java classes for representing programs and manipulating
+them. A library is provided for parsing Fleet assembly language
+programs into {\tt CodeBag}s of {\tt Instruction}s, and for writing
+those objects back out as text.
+
+In the case of Test Cases, the FleetTwo Toolchain defines a very
+simple debugging interface, {\tt Device}, which lets a program
+dispatch a codebag to a running Fleet implementation or emulator and
+read back the words which arrive at its {\tt Debug} port. A test
+harness has been written which makes no assumptions about the device
+under test other than that it supports this debugging interface and
+that it is capable of describing itself via the {\tt ShipDescription}
+API. By meeting these relatively modest requirements, a new Fleet
+implementation can immediately take advantage of a great deal of
+prebuilt testing infrastructure. This API has been implemented and is
+fully functional for both the software interpreter implementation of
+Fleet and the FPGA simulation of Fleet.
-\verbatiminput{fleet.g}
\pagebreak
-\section*{FleetDoc}
+\section{Ships}
+\subsection{Ship Description Files (FleetDoc)}
Inspired by JavaDoc, the Fleet software toolchain includes a tool
called {\tt FleetDoc}, which processes {\it ship description files}
\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
+\item A list of the people who contributed to all of the above
\end{itemize}
Keeping all of this information in a single file ensures that changes
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
+details of ship ports without the risk
inherent in manual synchronization.
The latter half of the architecture manual \cite{ArchMan} -- including
the {\tt .ship} files.
\pagebreak
-\subsection*{An Example FleetDoc File}
+\subsubsection{An Example FleetDoc File}
\begin{verbatim}
ship: BitFifo
\pagebreak
-\section*{Java APIs}
-\subsection*{Representing Code}
-\subsection*{Representing Ships}
+\subsection{Java API for Ship Descriptions}
+
+The FleetTwo toolchain includes a utility for parsing a {\tt .ship}
+file into a {\tt ShipDescription}. There is one {\tt ShipDescription}
+for each {\it kind} of ship. This distinction will become important
+later, when we introduce classes to represent {\it instances} of ship
+types.
+
+\begin{verbatim}
+/** a description of a ship */
+public class ShipDescription implements Iterable<DockDescription> {
+ public String getName();
+ public Iterable<ConstantDescription> getConstantDescriptions();
+ public Iterable<DockDescription> getDockDescriptions();
+}
+
+/** a description of a valve */
+public class DockDescription {
+ public String getName();
+ public boolean isInbox();
+ public boolean isOutbox();
+ public DockDescription getShortcut();
+}
+
+/** a constant declared by a ship */
+public class ConstantDescription {
+ public final long setbits;
+ public final long clearbits;
+ public final boolean signExtend;
+ public final int numberOffset;
+ public final int numberWidth;
+}
+\end{verbatim}
+
+
+\pagebreak
+\section{Instructions}
+\subsection{Fleet Assembly Language}
+
+The Fleet Assembly language is designed to be a human-readable
+depiction of the bits which comprise a Fleet program.
+
+\subsubsection{Formal Grammar}
+
+The formal syntax is given below. The metagrammar used is that of the
+Scannerless Boolean Parser \cite{sbp}.
+
+\verbatiminput{fleet.g}
+
+\subsubsection{Translation To Machine Code}
+
+Please refer to \cite{ArchMan} for the details of the Fleet
+instruction encoding.
+
+As shown in the grammar above, the start symbol for the grammar ({\tt
+ s}) yields a {\tt Program} surrounded by optional whitespace. A
+program is a sequence of {\tt Directive}s followed by a {\tt
+ CodeBagBody}. A {\tt CodeBagBody} consists of zero or more
+elements, each of which is either a {\tt Fiber} or a (nested) {\tt
+ CodeBagDef}.
+
+A {\tt Fiber} is a set of {\tt Instruction}s which all share a common
+execution point ({\tt Pump}). Each instruction can be {\tt unclog},
+{\tt clog}, {\tt kill}, {\tt literal}, or a set of {\tt Command}s. It
+should be fairly clear how to translate all but the last sort of
+instruction into machine code, based on the encodings in
+\cite{ArchMan}. Take particular note of the fact that {\tt literal}s
+may have a {\tt RequeueCount} but not a {\tt RepeatCount}.
+
+The repetition count for an instruction is placed in square brackets
+and prefixes the instruction. The requeueing count for an instruction
+is placed at the end of the instruction because, {\it conceptually},
+requeueing takes place after the instruction executes.
+
+A {\tt Command} is either {\tt wait}, {\tt nop}, {\tt discard}, {\tt
+ recieve}, {\tt take}, {\tt deliver}, {\tt send}, {\tt sendto}, {\tt
+ notify}, or {\tt notifyLast}. These are compiled as shown below:
+
+\begin{itemize}
+\item[\tt nop] is not valid in combination with any other command; it sets all control bits to {\tt 0}
+\item[\tt wait] is valid only on an output port, and sets {\tt Ti=1}
+\item[\tt discard] sets {\tt Di=1,Dc=0}
+\item[\tt recieve] is valid only on an input port, and sets {\tt Di=1,Dc=1}
+\item[\tt take] is valid only on an output port, and sets {\tt Di=1,Dc=1}
+\item[\tt deliver] is valid only on an input port, and sets {\tt Do=1}
+\item[\tt sendto] is valid only on an output port, and sets {\tt Do=1}
+\item[\tt send] is valid only on an output port, and sets {\tt Do=1,To=1}\footnote{see \cite{ArchMan} for the special meaning this bit combination has}
+\item[\tt notify] sets {\tt To=1} and is not valid in combination with {\tt send} or {\tt sendto}
+\item[\tt notifyLast] sets {\tt To=1,Ig=1} and is not valid in combination with {\tt send} or {\tt sendto}
+\end{itemize}
+
+It is an error to specify two commands within a single instruction if
+both of the commands attempt to set the same bit, even if they attempt
+to set it to the same value.
+
+Note that un-named ``anonymous'' codebags may appear as literals.
+This means that it is possible to write interesting programs such as
+the one below:
+
+\begin{verbatim}
+#ship debug : Debug
+#ship memory : Memory
+
+memory.inCBD: literal {
+ memory.inCBD: literal {
+ memory.inCBD: literal {
+ debug.in:
+ literal 3;
+ deliver;
+ }; deliver;
+ }; deliver;
+ }; deliver;
+\end{verbatim}
+
+
+
\pagebreak
-\section*{Misc}
+\subsection{Java API for Fleet Machine Code}
+\subsection{Ships}
\begin{verbatim}
-- sequencing guarantees
-- codebag format
-- behavior when token arrives at data port, vice versa
-- overlapping codebags
+public abstract class Ship {
+
+ /** return the description for this ship */
+ public ShipDescription getShipDescription();
+
+ /** return all pumps which feed this ship; order is NOT significant */
+ public Iterable<Dock> getDocks();
+ public Dock getDock(String s);
+
+ /** if this is the 4th fifo ship, this method returns 4 */
+ public int getOrdinal();
+
+ /** return the Fleet that this Ship belongs to, if any */
+ public Device getDevice();
+}
+\end{verbatim}
+
+\subsection{Dock}
+\begin{verbatim}
+public class Dock {
+
+ /** the descriptive name of this pump (relative to its ship) */
+ public abstract String getName();
+
+ /** return the Ship to which this Dock belongs */
+ public abstract Ship getShip();
+
+ /** the maximum number of instructions we can put in the Dock instruction fifo,
+ * or Integer.MAX_VALUE if unbounded */
+ public abstract int getInstructionFifoLength();
+
+ /** returns true if this is an inbox */
+ public abstract boolean isInbox();
+
+ /** returns true if this is an outbox */
+ public abstract boolean isOutbox();
+
+ /** return the Dock which is the destination of this Box's shortcut (if any) */
+ public Destination getShortcut() { return null; }
+}
+\end{verbatim}
+
+\subsection{Instructions}
+\begin{verbatim}
+public abstract class Instruction {
+ public final Pump pump;
+
+ public static class UnClog extends Instruction {
+ }
+
+ public static class Clog extends Instruction {
+ }
+
+ public static abstract class CountingInstruction extends Instruction {
+ public final int count;
+ public CountingInstruction decrementCount();
+ }
+
+ public static class Kill extends CountingInstruction {
+ }
+
+ public static class Executable extends CountingInstruction {
+
+ public final Destination dest;
+
+ public final boolean tokenIn;
+ public final boolean dataIn;
+ public final boolean latch;
+ public final boolean send;
+ public final boolean sendTo;
+ public final boolean tokenOut;
+ public final boolean requeue;
+ public final boolean ignoreUntilLast;
+
+ public boolean isStanding();
+ }
+
+ public static class Literal extends CountingInstruction {
+ public final long literal;
+ }
+}
+\end{verbatim}
+
+\pagebreak
+\section{Test Cases}
+
+\subsection{Test Case File Format}
+
+The test case file format is quite simple -- it is nothing more than a
+regular Fleet assembly language program with {\tt \#expect} statements
+to indicate the values which should arrive at the {\tt Debug.in} port
+if the test runs correctly.
+
+\subsection{Java API for Controlling Device Under Test}
+
+\subsection{The Device}
+\begin{verbatim}
+public abstract class Device implements Iterable<Ship> {
+
+ /** read a machine-formatted instruction from a file (into a Java object) */
+ public abstract Instruction
+ readInstruction(DataInputStream is) throws IOException;
+
+ /** write a machine-formatted instruction to a file (from a Java object) */
+ public abstract void
+ writeInstruction(DataOutputStream os, Instruction instr) throws IOException;
+
+ public abstract Iterator<Ship> iterator();
+
+ /** if possible, run the given code and create a FleetProcess */
+ public FleetProcess run(byte[] code);
+}
+\end{verbatim}
+
+\subsection{A Running Test}
+
+\begin{verbatim}
+/** represents a <i>running</i> "slave" fleet with a debug connection */
+public abstract class FleetProcess {
+
+ /** dumps an instruction into the fetch unit */
+ public abstract void invokeInstruction(Instruction i);
+
+ /** reads a word back from the debug port */
+ public abstract long readWord();
+
+ public final synchronized void terminate();
+
+ public final boolean isTerminated();
+}
\end{verbatim}
\end{document}
projects / fleet.git / blobdiff