-\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
inkscape:pageshadow="2"
inkscape:zoom="1.5855365"
inkscape:cx="510.02639"
- inkscape:cy="102.56622"
+ inkscape:cy="356.19542"
inkscape:document-units="px"
inkscape:current-layer="layer1"
showgrid="true"
sodipodi:nodetypes="cccc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#800080;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 850.3937,581.10236 L 627.62205,581.10236"
+ d="M 878.74016,581.10236 L 627.62205,581.10236"
id="path3423"
sodipodi:nodetypes="cc" />
<path
sodipodi:nodetypes="cccc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#800080;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 850.3937,262.20472 L 627.62205,262.20472"
+ d="M 878.74016,262.20472 L 627.62205,262.20472"
id="path3419"
sodipodi:nodetypes="cc" />
<path
sodipodi:nodetypes="cc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#800080;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 850.3937,191.33858 L 627.62205,191.33858"
+ d="M 878.74016,191.33858 L 627.62205,191.33858"
id="path3413"
sodipodi:nodetypes="cc" />
<path
sodipodi:nodetypes="cc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 385.76378,496.06299 L 484.97638,496.06299"
- id="path3195" />
+ d="M 347.24409,496.06299 L 484.97638,496.06299"
+ id="path3195"
+ sodipodi:nodetypes="cc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 450.45669,177.16535 L 393.76378,177.16535"
- id="path3193" />
+ d="M 450.45669,177.16535 L 357.41732,177.16535"
+ id="path3193"
+ sodipodi:nodetypes="cc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#0000ff;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
d="M 566.92913,581.10237 L 566.92913,524.40945"
id="rect3191"
width="177.16536"
height="552.75592"
- x="212.59842"
+ x="177.16536"
y="106.29921" />
<g
id="g3407"
- transform="translate(299.46456,106.75592)"
+ transform="translate(325.32331,106.75592)"
style="stroke:#800080">
<rect
y="74.409424"
</g>
<path
style="fill:none;fill-rule:evenodd;stroke:#800080;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:3, 3;stroke-dashoffset:0;stroke-opacity:1"
- d="M 850.04724,533.49606 L 635.62205,533.49606"
+ d="M 876.04724,533.49606 L 635.62205,533.49606"
id="path3445"
sodipodi:nodetypes="cc" />
<g
id="g3447"
- transform="translate(299.46456,448.91341)"
+ transform="translate(325.98424,448.91341)"
style="stroke:#800080">
<rect
y="74.409424"
<text
xml:space="preserve"
style="font-size:52.43335342px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="240.94489"
+ x="205.51183"
y="396.8504"
id="text3459"><tspan
sodipodi:role="line"
id="tspan3461"
- x="240.94489"
+ x="205.51183"
y="396.8504">Ship</tspan></text>
<text
xml:space="preserve"
y="622.36218">Pump</tspan></text>
<text
xml:space="preserve"
- style="font-size:12.39046097px;font-style:normal;font-weight:normal;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="646.73108"
+ style="font-size:18px;font-style:normal;font-weight:normal;text-align:center;text-anchor:middle;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="703.63574"
y="256.02255"
id="text3475"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3477"
- x="646.73108"
+ x="703.63574"
y="256.02255"
- style="fill:#800080">Destination</tspan></text>
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination</tspan></text>
<text
xml:space="preserve"
- style="font-size:12.39046097px;font-style:normal;font-weight:normal;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="644.90436"
+ style="font-size:18px;font-style:normal;font-weight:normal;text-align:center;text-anchor:middle;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="703.63574"
y="184.24554"
id="text3479"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3481"
- x="644.90436"
+ x="703.63574"
y="184.24554"
- style="fill:#800080">Destination</tspan></text>
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination</tspan></text>
<text
xml:space="preserve"
- style="font-size:12.39046097px;font-style:normal;font-weight:normal;fill:#0000ff;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="644.90436"
+ style="font-size:18px;font-style:normal;font-weight:normal;text-align:center;text-anchor:middle;fill:#0000ff;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="703.61377"
y="134.64098"
id="text3483"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3485"
- x="644.90436"
+ x="703.61377"
y="134.64098"
- style="fill:#008080">Source</tspan></text>
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#008080">Source</tspan></text>
<text
xml:space="preserve"
- style="font-size:12.39046097px;font-style:normal;font-weight:normal;fill:#0000ff;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="666.16492"
+ style="font-size:18px;font-style:normal;font-weight:normal;text-align:center;text-anchor:middle;fill:#0000ff;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="703.61377"
y="455.52747"
id="text3487"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3489"
- x="666.16492"
+ x="703.61377"
y="455.52747"
- style="fill:#008080">Source</tspan></text>
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#008080">Source</tspan></text>
<text
xml:space="preserve"
- style="font-size:12.39046097px;font-style:normal;font-weight:normal;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="653.99127"
+ style="font-size:18px;font-style:normal;font-weight:normal;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="651.99121"
y="528.39105"
id="text3491"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3493"
- x="653.99127"
+ x="651.99121"
y="528.39105"
- style="fill:#800080">Destination</tspan></text>
+ style="font-size:18px;fill:#800080">Destination</tspan></text>
<text
xml:space="preserve"
- style="font-size:12.39046097px;font-style:normal;font-weight:normal;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="653.99127"
+ style="font-size:18px;font-style:normal;font-weight:normal;text-align:center;text-anchor:middle;fill:#800080;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="703.63574"
y="575.99573"
id="text3495"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3497"
- x="653.99127"
+ x="703.63574"
y="575.99573"
- style="fill:#800080">Destination</tspan></text>
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination</tspan></text>
<path
style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:none"
d="M 389.76378,680.31495 L 389.76378,708.66141"
projects / fleet.git / commitdiff
