X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=doc%2Farchman.tex;h=7019dd8f94f1ce4d5aeef1b8dc0e9b0614431249;hb=b78b1fc6bf752e42b1a8d675cd6a3d4ce992688c;hp=5f669bab7a539337d4afa721fe24c8be0f9841c8;hpb=20e2056f1af4e3a1c10eb1e95a0bc8ee4e870159;p=fleet.git diff --git a/doc/archman.tex b/doc/archman.tex index 5f669ba..7019dd8 100644 --- a/doc/archman.tex +++ b/doc/archman.tex @@ -2,8 +2,17 @@ \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 @@ -20,7 +29,7 @@ \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 @@ -156,7 +165,7 @@ payload is a data item, it includes one machine word of data. 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} @@ -166,19 +175,19 @@ destinations which can send and recieve only tokens -- not data items \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 @@ -236,7 +245,7 @@ the instruction. {\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} @@ -260,7 +269,7 @@ instruction. {\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} @@ -307,7 +316,7 @@ successor of the execution point. \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 @@ -316,7 +325,7 @@ 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. 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} @@ -331,10 +340,11 @@ is assured that a kill instruction with a count of $n$ will kill $n$ \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} @@ -348,7 +358,7 @@ instructions will be executed until an {\tt unclog} is performed. \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 @@ -391,27 +401,28 @@ in the data latch. \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 @@ -437,12 +448,12 @@ if (Count==0) { 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 @@ -492,13 +503,13 @@ encompass will overlap. \subsection{Dispatching Code Bags} -A codebag is ``dispatched'' by causing its constitutent words to +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 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 @@ -517,16 +528,16 @@ 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 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 @@ -550,7 +561,7 @@ other types of instructions. This would have a few advantages: \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 @@ -597,9 +608,9 @@ would have similar advantages. \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}. @@ -624,13 +635,13 @@ 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, 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''