\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{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
\vspace{0.3cm}
The term {\it port} refers to an interface to the ship, the {\it
- valve} connecting it to the switch fabric, and the corresponding
+ 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 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
{\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}
{\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}
\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
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. The programmer
-is assured that a kill instruction with a count of $n$ will kill $n$
+is assured that a kill instruction with a count of $n$ will kill $n+1$
{\it consecutive} instructions.
\vspace{0.3cm}
\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}
\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
\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\footnote{{\tt Ti}=1,{\tt Di}=1 is invalid on input port.}
+ \item [\tt Ti] ({\bf Token Input}) wait for a token and acknowledge 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 in the data latch. 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.}
+ 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 output port.}
+ \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
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
+ 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 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
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 the pump which ought to execute it.
+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
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 only be correctly dispatched from that particular
-source. However, it is a fairly simple matter two write a software
-program which can ``relocate'' a codebag by replacing the {\tt
- Instruction Path} fields as needed.
+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.
+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
\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
\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}.
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, and I choose this
-distinction as the basis for limiting the valves to linear control
+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''
grid_units="mm"
inkscape:grid-bbox="false"
inkscape:grid-points="true"
- inkscape:window-width="1462"
- inkscape:window-height="1079"
- inkscape:window-x="75"
- inkscape:window-y="52"
+ inkscape:window-width="1640"
+ inkscape:window-height="1006"
+ inkscape:window-x="0"
+ inkscape:window-y="22"
width="1052.3622px"
height="744.09448px"
showguides="true"
y="467.5433">Pump</tspan></text>
<path
style="fill:none;fill-rule:evenodd;stroke:#ff0000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 596.3622,506.06299 L 490.06299,433.19684"
+ d="M 581.10236,576.92917 L 474.80315,504.06302"
id="path3244"
sodipodi:nodetypes="cc" />
<path
<text
xml:space="preserve"
style="font-size:21.72095108px;font-style:normal;font-weight:normal;fill:#ff0000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
- x="614.59222"
- y="531.49603"
+ x="628.76544"
+ y="566.92914"
id="text4221"><tspan
sodipodi:role="line"
id="tspan4223"
- x="614.59222"
- y="531.49603"
+ x="628.76544"
+ y="566.92914"
style="text-align:center;text-anchor:middle;fill:#ff0000">Insertion</tspan><tspan
sodipodi:role="line"
- x="614.59223"
- y="558.64722"
+ x="628.76544"
+ y="594.08033"
id="tspan4225"
style="text-align:center;text-anchor:middle;fill:#ff0000">Point</tspan></text>
<path
- style="fill:none;fill-rule:evenodd;stroke:#ff0000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 687.40157,425.19685 L 488.97638,425.19685 C 488.97638,425.19685 481.21595,424.87154 481.88976,432.28347 L 481.88976,460.62992"
- id="path3417"
- sodipodi:nodetypes="cccc" />
+ style="fill:#999999;fill-rule:evenodd;stroke:#999999;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 481.88975,446.45669 L 481.88975,474.80314"
+ id="path3421"
+ sodipodi:nodetypes="cc" />
+ <text
+ xml:space="preserve"
+ style="font-size:18px;font-style:normal;font-weight:normal;text-align:center;text-anchor:middle;fill:#999999;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ x="568.98541"
+ y="489.13257"
+ id="text3495"
+ transform="scale(0.9999652,1.0000348)"><tspan
+ sodipodi:role="line"
+ id="tspan3497"
+ x="568.98541"
+ y="489.13257"
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#999999">Destination</tspan></text>
+ <path
+ style="fill:#999999;fill-rule:evenodd;stroke:#ff0000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 531.66928,496.49172 L 446.62992,496.49172"
+ id="path3221"
+ sodipodi:nodetypes="cc" />
<path
- style="fill:none;fill-rule:evenodd;stroke:#999999;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:none;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
- d="M 744.09449,425.19685 L 492.97638,425.19685"
- id="path3419"
+ style="fill:#999999;fill-rule:evenodd;stroke:#999999;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 732.09448,496.49171 L 480.97637,496.49171"
+ id="path3423"
sodipodi:nodetypes="cc" />
</g>
</svg>
objecttolerance="10"
inkscape:pageopacity="0.0"
inkscape:pageshadow="2"
- inkscape:zoom="1.5855365"
- inkscape:cx="510.02639"
- inkscape:cy="356.19542"
+ inkscape:zoom="1.1836462"
+ inkscape:cx="679.09752"
+ inkscape:cy="195.2233"
inkscape:document-units="px"
inkscape:current-layer="layer1"
showgrid="true"
inkscape:grid-bbox="false"
inkscape:grid-points="true"
inkscape:window-width="1454"
- inkscape:window-height="1163"
- inkscape:window-x="369"
+ inkscape:window-height="1050"
+ inkscape:window-x="137"
inkscape:window-y="22"
width="1052.3622px"
height="744.09448px" />
id="layer1">
<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 822.04724,581.10236 L 623.62205,581.10236 C 623.62205,581.10236 615.86162,580.77705 616.53543,588.18898 L 616.53543,616.53543"
- id="path3421"
- 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 878.74016,581.10236 L 627.62205,581.10236"
- id="path3423"
- 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 822.04724,262.20472 L 623.62205,262.20472 C 623.62205,262.20472 615.86162,261.87941 616.53543,269.29134 L 616.53543,297.63779"
- id="path3417"
- sodipodi:nodetypes="cccc" />
+ d="M 439.37009,581.10236 L 609.44883,581.10236 C 609.44883,581.10236 616.87235,580.77704 616.53544,588.18897 L 616.53544,644.53543 C 616.53544,644.53543 617.19767,651.62204 609.44883,651.62204 L 411.02363,651.62204 C 411.02363,651.62204 403.93701,652.95808 403.93701,644.53543 L 403.93701,588.18897 C 402.92629,579.76632 411.02363,581.10236 411.02363,581.10236 L 439.37009,581.10236 z "
+ id="path2172"
+ sodipodi:nodetypes="cccccccccc" />
<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 878.74016,262.20472 L 627.62205,262.20472"
- id="path3419"
+ style="fill:none;fill-rule:evenodd;stroke:#0000ff;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 616.53543,602.18898 L 616.53543,630.53543"
+ id="path3421"
sodipodi:nodetypes="cc" />
<path
style="fill:none;fill-rule:evenodd;stroke:#008080;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
d="M 566.92913,581.10237 L 566.92913,524.40945"
id="path3147" />
<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 439.37009,581.10236 L 609.44883,581.10236 C 609.44883,581.10236 616.87235,580.77704 616.53544,588.18897 L 616.53544,644.53543 C 616.53544,644.53543 617.19767,651.62204 609.44883,651.62204 L 411.02363,651.62204 C 411.02363,651.62204 403.93701,652.95808 403.93701,644.53543 L 403.93701,588.18897 C 402.92629,579.76632 411.02363,581.10236 411.02363,581.10236 L 439.37009,581.10236 z "
- id="path2172"
- sodipodi:nodetypes="cccccccccc" />
- <path
style="fill:#ffffff;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 425.19686,566.92914 L 425.19686,595.27559 L 460.62993,595.27559 L 474.80316,581.10237 L 460.62993,566.92914 L 425.19686,566.92914 z "
id="path2160" />
xml:space="preserve"
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="703.63574"
- y="256.02255"
- style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination</tspan></text>
- <text
- xml:space="preserve"
- 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
xml:space="preserve"
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"
+ y="644.85944"
id="text3495"
transform="scale(0.9999652,1.0000348)"><tspan
sodipodi:role="line"
id="tspan3497"
x="703.63574"
- y="575.99573"
+ y="644.85944"
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"
id="tspan3521"
x="541.69458"
y="722.83466"
- style="text-align:center;text-anchor:middle">Valves</tspan></text>
+ style="text-align:center;text-anchor:middle">Docks</tspan></text>
<text
xml:space="preserve"
style="font-size:21.32734108px;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"
style="text-align:center;text-anchor:middle"
id="tspan3539">Port</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 871.65354,389.76377 C 871.65354,389.76377 885.82677,389.85102 885.82677,403.937 L 885.82677,517.32283 C 885.82677,531.42335 900,531.49606 900,531.49606 C 900,531.49606 885.82677,532.86385 885.82677,545.66929 L 885.82677,637.79527 C 885.82677,652.52152 871.65354,651.9685 871.65354,651.9685"
+ style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.10158062;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 871.70433,389.81456 C 871.70433,389.81456 885.82677,389.91124 885.82677,405.52036 L 885.82677,531.16676 C 885.82677,546.79199 899.94921,546.87256 899.94921,546.87256 C 899.94921,546.87256 885.82677,548.38826 885.82677,562.57837 L 885.82677,664.66606 C 885.82677,680.98468 871.70433,680.37186 871.70433,680.37186"
id="path3527"
sodipodi:nodetypes="ccccccc" />
<path
id="tspan3569"
style="text-align:center;text-anchor:middle;fill:#008000">Latch</tspan></text>
<path
+ style="fill:none;fill-rule:evenodd;stroke:#0000ff;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 680.31496,652.22401 L 595.2756,652.22401"
+ id="path3221"
+ 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 878.74016,652.224 L 627.62205,652.224"
+ id="path3423"
+ 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 439.37008,262.55118 L 609.44882,262.55118 C 609.44882,262.55118 616.87234,262.22586 616.53543,269.63779 L 616.53543,325.98425 C 616.53543,325.98425 617.19766,333.07086 609.44882,333.07086 L 411.02362,333.07086 C 411.02362,333.07086 403.937,334.4069 403.937,325.98425 L 403.937,269.63779 C 402.92628,261.21514 411.02362,262.55118 411.02362,262.55118 L 439.37008,262.55118 z "
- id="path2247"
+ d="M 439.37013,276.37794 L 609.44887,276.37794 C 609.44887,276.37794 616.87239,276.05262 616.53548,283.46455 L 616.53548,339.81101 C 616.53548,339.81101 617.19771,346.89762 609.44887,346.89762 L 411.02367,346.89762 C 411.02367,346.89762 403.93705,348.23366 403.93705,339.81101 L 403.93705,283.46455 C 402.92633,275.0419 411.02367,276.37794 411.02367,276.37794 L 439.37013,276.37794 z "
+ id="path3223"
sodipodi:nodetypes="cccccccccc" />
<path
+ style="fill:none;fill-rule:evenodd;stroke:#0000ff;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 616.53547,297.46456 L 616.53547,325.81101"
+ id="path3225"
+ sodipodi:nodetypes="cc" />
+ <path
style="fill:#ffffff;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 425.02363,249.11811 L 425.02363,277.46456 L 460.4567,277.46456 L 474.62993,263.29134 L 460.4567,249.11811 L 425.02363,249.11811 z "
- id="path2249" />
+ d="M 425.1969,262.20472 L 425.1969,290.55117 L 460.62997,290.55117 L 474.8032,276.37795 L 460.62997,262.20472 L 425.1969,262.20472 z "
+ id="path3228" />
<path
style="fill:#ffffff;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 481.71654,249.11811 L 481.71654,277.46456 L 517.14961,277.46456 L 531.32284,263.29134 L 517.14961,249.11811 L 481.71654,249.11811 z "
- id="path2251" />
+ d="M 481.88981,262.20472 L 481.88981,290.55117 L 517.32288,290.55117 L 531.49611,276.37795 L 517.32288,262.20472 L 481.88981,262.20472 z "
+ id="path3230" />
<path
style="fill:#ffffff;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 588.01574,319.98424 L 588.01574,348.33069 L 552.58267,348.33069 L 538.40944,334.15747 L 552.58267,319.98424 L 588.01574,319.98424 z "
- id="path2253" />
+ d="M 588.18901,333.07085 L 588.18901,361.4173 L 552.75594,361.4173 L 538.58271,347.24408 L 552.75594,333.07085 L 588.18901,333.07085 z "
+ id="path3232" />
<path
style="fill:#ffffff;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 531.32283,319.98425 L 531.32283,348.3307 L 495.88976,348.3307 L 481.71653,334.15748 L 495.88976,319.98425 L 531.32283,319.98425 z "
- id="path2255" />
+ d="M 531.4961,333.07086 L 531.4961,361.41731 L 496.06303,361.41731 L 481.8898,347.24409 L 496.06303,333.07086 L 531.4961,333.07086 z "
+ id="path3234" />
<path
style="fill:#ffffff;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 474.62992,319.98424 L 474.62992,348.33069 L 439.19685,348.33069 L 425.02362,334.15747 L 439.19685,319.98424 L 474.62992,319.98424 z "
- id="path2257" />
+ d="M 474.80319,333.07085 L 474.80319,361.4173 L 439.37012,361.4173 L 425.19689,347.24408 L 439.37012,333.07085 L 474.80319,333.07085 z "
+ id="path3236" />
<path
style="fill:#ffffff;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 545.49607,249.11811 L 545.49607,277.46456 L 580.92914,277.46456 L 595.10237,263.29134 L 580.92914,249.11811 L 545.49607,249.11811 z "
- id="path2259" />
+ d="M 545.66934,262.20472 L 545.66934,290.55117 L 581.10241,290.55117 L 595.27564,276.37795 L 581.10241,262.20472 L 545.66934,262.20472 z "
+ id="path3238" />
<text
xml:space="preserve"
style="font-size:21.72095108px;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="483.88974"
- y="304.55118"
- id="text2261"><tspan
+ x="484.06305"
+ y="317.63776"
+ id="text3240"><tspan
sodipodi:role="line"
- id="tspan2263"
- x="483.88974"
- y="304.55118">Pump</tspan></text>
+ id="tspan3242"
+ x="484.06305"
+ y="317.63776">Pump</tspan></text>
+ <text
+ xml:space="preserve"
+ 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="340.14563"
+ id="text3244"
+ transform="scale(0.9999652,1.0000348)"><tspan
+ sodipodi:role="line"
+ id="tspan3246"
+ x="703.63574"
+ y="340.14563"
+ style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination</tspan></text>
+ <path
+ style="fill:none;fill-rule:evenodd;stroke:#0000ff;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ d="M 680.315,347.49959 L 595.27564,347.49959"
+ id="path3248"
+ 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 878.74016,347.49958 L 627.62209,347.49958"
+ id="path3250"
+ sodipodi:nodetypes="cc" />
</g>
</svg>
\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}
-Fleet compilers and tools work primarily with representations of two
-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.
+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
\pagebreak
\section{Introduction}
-Fleet compilers and tools work primarily with representations of two
-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.
+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 (such as
-the assembler and compiler) of what ships it contains and how they may
-be used. A library is provided for parsing the textual file format
-into the Java representation.
+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
programs into {\tt CodeBag}s of {\tt Instruction}s, and for writing
those objects back out as text.
-Finally, the FleetTwo Toolchain defines a very simple debugging
-interface, {\tt Device}, which lets a program dispatch a codebag to a
-running Fleet chip 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 minor
-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.
+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.
\pagebreak
-\section{Representing Ships}
+\section{Ships}
\subsection{Ship Description Files (FleetDoc)}
Inspired by JavaDoc, the Fleet software toolchain includes a tool
\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
\pagebreak
\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<ValveDescription> {
+ public String getName();
+ public Iterable<ConstantDescription> getConstantDescriptions();
+ public Iterable<ValveDescription> getValveDescriptions();
+}
+
+/** a description of a valve */
+public class ValveDescription {
+ public String getName();
+ public boolean isInbox();
+ public boolean isOutbox();
+ public ValveDescription 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{Representing Machine Code}
+\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 formal syntax is given below. The metagrammar used is that of the
+Scannerless Boolean Parser \cite{sbp}.
\verbatiminput{fleet.g}
CodeBagDef}.
A {\tt Fiber} is a set of {\tt Instruction}s which all share a common
-execution point ({\tt Pump}). Each instruction can be a {\tt unclog},
+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
notify}, or {\tt notifyLast}. These are compiled as shown below:
\begin{itemize}
-\item[\tt wait] is valid only on an inbox, and sets {\tt Ti=1}
\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 send] is valid only on an output port, and sets {\tt Do=1,To=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).
+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.
+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}
-#expect 3
-
#ship debug : Debug
#ship memory : Memory
\pagebreak
\subsection{Java API for Fleet Machine Code}
+\subsection{Ships}
+\begin{verbatim}
+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<Valve> getValves();
+ public Valve getValve(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{Valve}
+\begin{verbatim}
+public class Valve {
+
+ /** the descriptive name of this pump (relative to its ship) */
+ public abstract String getName();
+
+ /** return the Ship to which this Valve belongs */
+ public abstract Ship getShip();
+
+ /** the maximum number of instructions we can put in the Valve 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 Valve 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 / commitdiff
