\documentclass[10pt]{article}
\usepackage{palatino}
\usepackage{amsmath}
+\usepackage{pdflscape}
+\usepackage[figureright]{rotating}
\usepackage{epsfig}
\usepackage{color}
\usepackage{bytefield1}
%\pdfpagewidth 8.5in
%\pdfpageheight 11in
%\topmargin 0in
-%\textheight 7.5in
+\textheight 8.2in
%\textwidth 6.0in
%\oddsidemargin 0.25in
%\evensidemargin 0.25in
\end{tabular}}
}
-\title{\vspace{-1cm}The FleetTwo Dock}
+\title{\vspace{-1cm}AM33: The Marina Docks
+\\
+{\normalsize
+Adam Megacz
+}}
\begin{document}
\maketitle
\begin{abstract}
-Changes:
-
-\begin{tabular}{rl}
-\color{red}
-23-Apr
-& added epilogue fifo to diagrams \\
-& indicated that a token sent to the instruction port is treated as a torpedo \\
-18-Apr
-& replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
-& replaced {\tt literal} with {\tt shift} instruction \\
-\color{black}
-17-Apr
-& Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
-& Removed ability to manually set the {\tt C} flag \\
-& Expanded predicate field to three bits \\
-& New literals scheme (via shifting) \\
-& Instruction encoding changes made at Ivan's request (for layout purposes) \\
-& Added summary of instruction encodings on last page \\
-07-Apr
-& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
-06-Apr
-& extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
-& update table 3.1.2 \\
-& rename {\tt S} flag to {\tt C} \\
-& noted that {\tt setFlags} can be used as {\tt nop} \\
-29-Mar
-& removed the {\tt L} flag (epilogues can now do this) \\
-& removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
-& renamed {\tt data} instruction to {\tt literal} \\
-& renamed {\tt send} instruction to {\tt move} \\
+
+This document describes the Docks on the Marina test chip.
+
+%Changes:
+%
+%\begin{tabular}{rl}
+%29-Aug
+%& Final version \\
+%25-May
+%& Added errata for Kessels counter on Marina test chip \\
+%18-May
+%& Added errata for Marina test chip \\
+%17-Feb
+%& Clarified setting of the {\tt C}-flag\color{black}\\
+%& Removed {\tt OS} bit\color{black}\\
+%& Changed instruction length from 26 bits to 25\color{black}\\
+%& Updated which bits are used when the {\tt Path} latch captures from the data predecessor\color{black}\\
+%05-Jan
+%& Fixed a one-word typo \\
+%02-Jan
+%& Added {\tt head} instruction \\
+%& Lengthened external encoding of {\tt tail} instruction by one bit \\
+%& Added {\tt abort} instruction \\
+%& Removed {\tt OS} field from instructions \\
+%& Renamed the {\tt Z}-flag (olc {\bf Z}ero) to the {\tt D}-flag (loop {\bf D}one)\\
+%19-Dec
+%& Updated diagram in section 3 to put dispatch path near MSB\\
+%& Changed DP[37:25] to DP[37:27]\\
+%& Added note on page 4 regarding previous\\
+%14-Nov
+%& Roll back ``Distinguish {\tt Z}-flag from OLC=0'' \\
+%& Clarify what ``{\tt X-Extended}'' means \\
+%& Change C-bit source selector from {\tt Di} to {\tt Dc} \\
+%07-Nov
+%& Distinguish {\tt Z}-flag from OLC=0\\
+%& Add {\tt flush} instruction\\
+%& Change {\t I} bit from ``Interruptable'' to ``Immune''\\
+%20-Sep
+%& Update hatch description to match \href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50} \\
+%28-Aug
+%& Note that decision to requeue is based on value of OLC {\it before} execution\\
+%& Note that decision to open the hatch is based on value of {\tt OS} bit\\
+%10-Jul
+%& Added {\tt OLC=0} predicate \\
+%& Eliminated {\tt TAPL} (made possible by previous change) \\
+%& Expanded {\tt set} {\tt Immediate} field from 13 bits to 14 bits (made possible by previous change)\\
+%09-Jul
+%& Fixed a few typos \\
+%& Added {\tt DataLatch}\to{\tt TAPL} (Amir's request) \\
+%& Eliminate ability to predicate directly on {\tt C}-flag (Ivan's request) \\
+%16-Jun
+%& When a torpedo strikes, {\tt ILC} is set to {\tt 1} \\
+%& Only {\tt move} can be torpedoed (removed {\tt I}-bit from {\tt set}/{\tt shift}) \\
+%11-Jun
+%& Changed all uses of ``Payload'' to ``Immediate'' \color{black} (not in red) \\
+%& Reworked encoding of {\tt set} instruction \\
+%\color{black}
+%06-Jun
+%& Factored in Russell Kao's comments (thanks!)\\
+%& Added mechanism for setting C-flag from fabric even on outboxes\\
+%05-Jun
+%& Made {\tt OLC} test a predicate-controlled condition\\
+%& Rewrote ``on deck'' section \\
+%& Added ``{\tt unset}'' value for {\tt ILC}\\
+%& Changed {\tt DP} to {\tt DataPredecessor} for clarity\\
+%\color{black}
+%30-Apr
+%& added comment about address-to-path ship \\
+%& changed {\tt DST} field of {\tt set} instruction from 2 bits to 3 \\
+%& changed the order of instructions in the encoding map \\
+%23-Apr
+%& added epilogue fifo to diagrams \\
+%& indicated that a token sent to the instruction port is treated as a torpedo \\
+%18-Apr
+%& replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
+%& replaced {\tt literal} with {\tt shift} instruction \\
+%17-Apr
+%& Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
+%& Removed ability to manually set the {\tt C} flag \\
+%& Expanded predicate field to three bits \\
+%& New literals scheme (via shifting) \\
+%& Instruction encoding changes made at Ivan's request (for layout purposes) \\
+%& Added summary of instruction encodings on last page \\
+%07-Apr
+%& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
+%06-Apr
+%& extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
+%& update table 3.1.2 \\
+%& rename {\tt S} flag to {\tt C} \\
+%& noted that {\tt setFlags} can be used as {\tt nop} \\
+%29-Mar
+%& removed the {\tt L} flag (epilogues can now do this) \\
+%& removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
+%& renamed {\tt data} instruction to {\tt literal} \\
+%& renamed {\tt send} instruction to {\tt move} \\
%23-Mar
%& added ``if its predicate is true'' to repeat count \\
%& added note that red wires do not contact ships \\
%& Created the {\tt Hold} field \\
%& Changed how ReLooping works \\
%& Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
-\end{tabular}
+%\end{tabular}
\end{abstract}
\vfill
\begin{center}
-\epsfig{file=overview,width=1.5in}
-\epsfig{file=indock,width=3in}
+\epsfig{file=all,height=1.5in}
+\epsfig{file=overview-new,height=1.5in}
\end{center}
\pagebreak
\section{Overview of Fleet}
-A Fleet processor consists of a {\it switch fabric} with several
-functional units called {\it ships} connected to it. At each
-connection between a ship and the switch fabric lies a programmable
-element known as the {\it dock}.
+A Fleet processor is organized around a {\it switch fabric}, which is
+a packet-switched network with reliable in-order delivery. The switch
+fabric is used to carry data between different functional units,
+called {\it ships}. Each ship is connected to the switch fabric by
+one or more programmable elements known as {\it docks}.
A {\it path} specifies a route through the switch fabric from a
particular {\it source} to a particular {\it destination}. The
-combination of a path and a single word {\it payload} is called a {\it packet}. The
-switch fabric carries packets from their sources to their
-destinations. Each dock has two destinations: one for {\it
+combination of a path and a single word to be delivered is called a
+{\it packet}. The switch fabric carries packets from their sources to
+their destinations. Each dock has two destinations: one for {\it
instructions} and one for {\it data}. A Fleet is programmed by
-depositing packets into the switch fabric; these packets' paths lead
-them to the instruction destinations of the docks.
+depositing instruction packets into the switch fabric with paths that
+will lead them to the instruction destinations of the docks at which they
+are to execute.
When a packet arrives at the instruction destination of a dock, it is
enqueued for execution. Before the instruction executes, it may cause
the dock to wait for a packet to arrive at the dock's data destination
-or for a value to be presented by the ship. It may present a data
-value to the ship or transmit it for transmission to some other
-destination.
+or for a value to be presented by the ship. When an instruction
+executes it may consume this data and may present a data value to the
+ship or transmit a packet.
When an instruction sends a packet into the switch fabric, it may
specify that the payload of the packet is irrelevant. Such packets
are known as {\it tokens}, and consume less energy than data packets.
-From a programmer's perspective, a token packet is indistinguishable
-from a data packet with a unknown payload.
-In the diagram below, the red wires carry instructions and the blue
-wires carry data; the switch fabric (gray area) carries both. Notice
-that the red (instruction) wires do not contact the ships. This is an
-advantage: ships are designed without any consideration for the
-instructions used to program their docks.
\begin{center}
-\epsfig{file=overview,width=2.5in}\\
-{\it Overview of a Fleet processor; gray shading represents a
- packet-switched network fabric; blue lines carry data, red lines
- carry instructions.}
+\epsfig{file=overview-new,width=2.5in}\\
+{\it Overview of a Fleet processor; dark gray shading represents the
+ switch fabric, ships are shown in light gray, and docks are shown in blue.}
\end{center}
\color{black}
\pagebreak
-\section{The FleetTwo Pump}
+\section{The Marina Dock}
-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 that can send and receive only tokens -- not data items
--- are drawn as dashed lines.
+The diagram below represents a conceptual view of the interface
+between ships and the switch fabric; actual implementation circuitry
+may differ.
\begin{center}
-\epsfig{file=indock,width=3.5in}\\
-{\it an ``input'' dock}
-
-\epsfig{file=outdock,width=3.5in}\\
-{\it an ``output'' dock}
+\epsfig{file=all,width=3.5in}\\
+{\it An ``input'' dock and ``output'' dock connected to a ship. Solid
+ blue lines carry either tokens or data words, red lines carry either
+ instructions or torpedoes, and dashed lines carry only tokens.}
\end{center}
-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 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 pump control the data
-latch.
-
-Note that the pump in each dock has a destination of its own; this is
-the {\it instruction destination} mentioned in the previous section.
-Note that unlike all other destinations, there is no buffering fifo
-guarding this one. The size of these fifos are exposed to the
-software programmer so he can avoid deadlock.
+machine word and a circular {\it instruction fifo} of
+instruction-width latches. The values in the instruction fifo control
+the data latch. The dock also includes a {\it path latch}, which
+stores the path along which outgoing packets will be
+sent.
+
+Note that the instruction fifo in each dock has a destination of its
+own; this is the {\it instruction destination} mentioned in the
+previous section. A token sent to an instruction destination is
+called a {\it torpedo}; it does not enter the instruction fifo, but
+rather is held in a waiting area where it may interrupt certain
+instructions (see the section on the {\tt move} instruction for further
+details).
+
+From any source to any dock's data destination there are
+two distinct paths which differ by a single bit. This bit is known as
+the ``signal'' bit, and the routing of a packet is not affected by it;
+the signal bit is used to pass control values between docks. Note that paths
+terminating at an {\it instruction} destination need not have a signal
+bit.
\pagebreak
\section{Instructions}
In order to cause an instruction to execute, the programmer must first
-cause that instruction word to arrive in the data latch of some output
-dock. For example, this might be the ``data read'' output dock of the
-memory access ship or the output of a fifo ship. Once an instruction
-has arrived at this output dock, it is {\it dispatched} by sending it
-to the {\it instruction port} of the dock at which it is to execute.
+arrange for that instruction word to arrive in the data latch of some
+output dock. For example, this might be the ``data read'' output dock
+of the memory access ship or the output of a fifo ship. Once an
+instruction has arrived at this output dock, it is {\it dispatched} by
+sending it to the {\it instruction destination} of the dock at which
+it is to execute.
+
+There are two instruction formats, an {\it external format} described
+in this section and an {\it internal format} described in the last
+section of this memo.
-Each instruction is 26 bits long, which makes it possible for an
-instruction and an 11-bit path to fit in a single word of memory.
-This path is the path from the {\it dispatching} dock to the {\it
- executing} dock.
+Each instruction is 25\color{black}\ bits long, which makes it
+possible for an instruction and an 12\color{black}-bit path to fit in
+a single word of memory. This path is the path from the {\it
+ dispatching} dock to the {\it executing} dock.
+
+\vspace{0.5cm}
\setlength{\bitwidth}{3.5mm}
{\tt \footnotesize
\begin{bytefield}{37}
- \bitheader[b]{0,10,11,36}\\
- \bitbox{26}{instruction}
- \bitbox{11}{dispatch path}
+ \bitheader[b]{0,24,25,36}\\
+ \bitbox{12}{dispatch path}
+ \bitbox{25}{instruction (external format)}
\end{bytefield}}
+\color{black}
-{\bf Note:} the instruction encodings below are simply ``something to
-shoot at'' and a sanity check to make sure we haven't overrun our bit
-budget. The final instruction encodings will probably be
-different.
-
-All instruction words have the following format:
+Note that the 12\color{black}\ bit {\tt dispatch path} field is not
+the same width as the 13 bit {\tt Immediate} path field in the {\tt
+ move} instruction, which in turn may not be the same width as the
+actual path latches in the switch fabric. The algorithm for expanding
+a path to a wider width is specific to the switch fabric
+implementation, and may vary from Fleet to Fleet. For the Marina
+experiment, the correct algorithm is to sign-extend the path; the most
+significant bit of the given path is used to fill the vacant bit of
+the latch. Because the {\tt dispatch path} field is always used to
+specify a path which terminates at an instruction destination (never a
+data destination), and because instruction destinations ignore the
+signal bit, certain optimizations may be possible.
+
+%\subsection{Life Cycle of an Instruction}
+%
+%The diagram below shows an input dock for purposes of illustration:
+%
+%\begin{center}
+%\epsfig{file=in,width=4in}\\
+%{\it an input dock}
+%\end{center}
+%
+%\color{black}
+%
+%\begin{center}
+%\epsfig{file=out,width=4in}\\
+%{\it an output dock}
+%\end{center}
+%\subsection{Format of an Instruction}
+%
+%All instruction words have the following format:
+%
\newcommand{\bitsHeader}{
\bitbox{1}{I}
- \bitbox{1}{OS}
\bitbox{3}{P}
}
+\newcommand{\bitsHeaderNoI}{
+ \bitbox{1}{}
+ \bitbox{3}{P}
+}
+%
+%
+%The {\tt P} bits are a {\it predicate}; this holds a code which
+%indicates if the instruction should be executed or ignored depending
+%on the state of flags in the dock. Note that {\tt head} and {\tt
+%tail} instructions do not have {\tt P} fields.
-\setlength{\bitwidth}{3.5mm}
-{\tt \footnotesize
-\begin{bytefield}{37}
- \bitheader[b]{0,10,11,36}\\
-\color{black}
- \bitsHeader
-\color{light}
- \bitbox[tbr]{21}{}
- \bitbox{11}{dispatch path}
-\color{black}
-\end{bytefield}}
-Each instruction word is called a {\it micro instruction}.
-Collections of one or more micro instruction are known as {\it
- composite instructions}.
+\subsection{Loop Counters}
-The {\tt I} bit stands for {\tt Interruptible}. The {\tt OS} (``One
-Shot'') bit indicates whether or not this instruction is part of an
-outer loop. Both of the preceding bits are explained in the next
-section.
+A programmer can perform two types of loops: {\it inner} loops
+consisting of only one {\tt move} instruction and {\it outer} loops of
+multiple instructions of any type. Inner loops may be nested within
+an outer loop, but no other nesting of loops is allowed.
-\color{black}
+The dock has two loop counters, one for each kind of loop:
-The abbreviation {\tt P} stands for {\it predicate}; this is a two-bit
-code that indicates if the instruction should be executed or ignored.
+\begin{itemize}
+\item {\tt OLC} is the Outer Loop Counter
+\item {\tt ILC} is the Inner Loop Counter
+\end{itemize}
+The {\tt OLC} applies to all instructions and can hold integers {\tt
+ 0..MAX_OLC} (63).
+The {\tt ILC} applies only to {\tt move} instructions and can hold
+integers {\tt 0..MAX_ILC} (63) as well as a special value: $\infty$. When
+{\tt ILC=0} the next {\tt move} instruction executes zero times (ie is
+ignored). When {\tt ILC=$\infty$} the next {\tt move} instruction
+executes until interrupted by a torpedo. After every {\tt move}
+instruction the {\tt ILC} is reset to {\tt 1} (note that it is reset
+to {\tt 1}, {\it not to 0}).
-\pagebreak
-\subsection{Life Cycle of an Instruction}
+\color{black}
+\subsection{Flags}
-The diagram below shows an input dock for purposes of illustration
-(behavior at an output dock is identical).
+The dock has four flags: {\tt A}, {\tt B},
+{\tt C}, and {\tt D}.
-\begin{center}
-\epsfig{file=indock,width=3in}\\
-{\it an input dock}
-\end{center}
+\begin{itemize}
+\item The {\tt A} and {\tt B} flags are general-purpose flags which
+ may be set and cleared by the programmer.
-Note the circle on the path between ``instr horn'' and ``instr fifo'';
-this is known as ``the hatch''. The hatch has two states: sealed and
-unsealed. When the machine powers up, the hatch is unsealed; it is
-sealed by the {\tt tail} instruction and unsealed whenever the outer
-loop counter is set to zero (for any reason\footnote{this
- includes {\tt OLC} being decremented to zero, a {\tt setOuter} with
- a literal field of zero, a {\tt setOuter} which copies a zero from
- the data register to {\tt OLC}, or the occurrence of a
- torpedo}).
-
-When an instruction arrives at the instruction horn, it waits there
-until the hatch is in the unsealed state. The instruction then enters
-the instruction fifo. When an instruction emerges from the
-instruction fifo, it arrives at the ``on deck'' stage, where it may
-execute.
-
-\subsubsection{Inner and Outer Loops}
-
-A programmer can perform two types of loops: {\it inner} loops of only
-one micro-instruction and {\it outer} loops of multiple
-micro-instructions. Inner loops may be nested within an outer loop,
-but no other nesting of loops is allowed. The paths used by inner
-loops and outer loops are shown below:
+%\item
+%
+% The {\tt L} flag, known as the {\it last} flag, is set whenever
+% the value in the outer counter ({\tt OLC}) is one,
+\color{black}
+% indicating
+% that the dock is in the midst of the last iteration of an
+% outer loop. This flag can be used to perform certain
+% operations (such as sending a completion token) only on the last
+% iteration of an outer loop.
-\begin{center}
-\begin{minipage}{2in}
-\begin{center}
-\epsfig{file=inner-loop,width=2in}\\
-{\it inner loop (in red)}
-\end{center}
-\end{minipage}
-\begin{minipage}{2in}
-\begin{center}
-\epsfig{file=outer-loop,width=2in}\\
-{\it outer loop (in red)}
-\end{center}
-\end{minipage}
-\end{center}
+\item The {\tt C} flag is known as the {\it control} flag, and may be
+ set by the {\tt move} instruction based on information from the
+ ship or from an inbound packet. See the {\tt move} instruction
+ for further details.
-Each type of loop has a counter associated with it: the {\tt ILC}
-counter for inner loops and the {\tt OLC} counter for outer loops.
-The inner loop counter applies only to certain ``inner-looping''
-instructions (see the table below for details). When such an
-instruction reaches On Deck, if its predicate is true it will execute
-a number of times equal to {\tt ILC+1}, and leave {\tt ILC=0} after
-executing. Non-inner-looping instructions and instructions whose
-predicate is false do not decrement {\tt ILC}.
+\item The {\tt D} flag is known as the {\it done} flag. The {\tt D}
+ flag is {\it set} when the {\tt OLC} is zero immediately after
+ execution of a {\tt set olc} or {\tt decrement olc} instruction,
+ or when a torpedo strikes. The {\tt D} flag is {\it cleared}
+ when a {\tt set olc} instruction causes the {\tt OLC} to be
+ loaded with a nonzero value.
-The outer loop counter applies to all instructions {\it except} the
-instruction {\tt setOuter} with {\tt OS=1}, because such instructions
-are needed to reset the outer loop counter after it becomes zero.
-However, predicated {\tt setOuter} with {\tt OS=0} is useful for
-resetting the loop counter in the middle of the execution of a loop.
+\color{black}
-\subsubsection{On Deck}
+\end{itemize}
+
+\subsection{Predication}
-The table below lists the actions which may be taken when an
-instruction arrives on deck:
+All instructions except for {\tt head} and {\tt tail} have a three-bit
+field marked {\tt P}, which specifies a {\it predicate}.
\begin{center}
-\def\side#1{\begin{sideways}\parbox{15mm}{#1}\end{sideways}}
-\begin{tabular}{|r|ccccc|cccccc|}\hline
-%&\multicolumn{10}{c}{Predicate}&\\
-%&\multicolumn{10}{c}{True}&\\\hline
-&\multicolumn{5}{c}{Outer-Looping} &\multicolumn{5}{c}{One-Shot}&\\
-&\multicolumn{5}{c}{{\tt (OS=0)}} &\multicolumn{5}{c}{{\tt (OS=1)}}&\\
-&\side{{\tt move}}
-&\side{{\tt literal}}
-&\side{{\tt setFlags}}
-&\side{{\tt setInner}}
-&\side{{\tt setOuter}}
-&\side{{\tt move}}
-&\side{{\tt literal}}
-&\side{{\tt setFlags}}
-&\side{{\tt setInner}}
-&\side{{\tt setOuter}}
-&
-\\\hline
-Wait for hatch sealed, & + & + & + & + & + & - & - & - & - & - & \\
-then IF0 w/ copy of self & & & & & & & & & & & \\\hline
-Potentially torpedoable & P+I & P+I & P+I & P+I & P+I & P+I & P+I & P+I & P+I & PI & \\
-Execute & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P & \\
-Inner-looping & P+ & - & - & - & - & P & - & - & - & - & \\
-\hline
-\end{tabular}
+\setlength{\bitwidth}{5mm}
+{\tt{\footnotesize{
+\begin{bytefield}{25}
+ \bitheader[b]{0,20,21,23-24}\\
+ \bitsHeaderNoI
+ \bitbox[tbr]{21}{}
+\color{black}
+\end{bytefield}}}}
+\end{center}
+The predicate determines which conditions must be true in order for
+the instruction to execute; if it is not executed, it is simply {\it
+ ignored}. The table below shows what conditions must be true in
+order for an instruction to execute:
+
+\begin{center}
\begin{tabular}{|r|l|}\hline
-+ & Only if {\tt OLC>0} (ie {\tt OLC} is positive) \\
-P & Only if predicate is true \\
-P+ & Only if predicate is true and {\tt OLC>0} \\
-PI & Only if predicate is true and {\tt I=1}. \\
-P+I & Only if predicate is true and {\tt OLC>0} and {\tt I=1}. \\\hline
-\end{tabular}
+Code & Execute if \\\hline
+{\tt 000:} & {\tt D=0}\ and {\tt A=0} \\
+{\tt 001:} & {\tt D=0}\ and {\tt A=1} \\
+{\tt 010:} & {\tt D=0}\ and {\tt B=0} \\
+{\tt 011:} & {\tt D=0}\ and {\tt B=1} \\
+{\tt 100:} & Unused \\
+{\tt 101:} & {\tt D=1}\ \\
+{\tt 110:} & {\tt D=0}\ \\
+{\tt 111:} & always \\
+\hline\end{tabular}
\end{center}
-{\bf Note:} a non-one-shot instruction may {\it execute} before the
-hatch is sealed, but may not {\it fill IF0} before the hatch is
-sealed. The instruction will not vacate On Deck until both of these
-tasks are complete, so the second non-one-shot instruction in a loop
-will not execute until the hatch is sealed, {\it but the first
- instruction will}.
\pagebreak
-\color{black}
-\subsubsection{Torpedo}
+\begin{wrapfigure}{r}{40mm}
+ \begin{center}
+\epsfig{file=requeue,height=1.5in}\\
+ \end{center}
+ \caption{{\it the requeue stage}}
+\end{wrapfigure}
-\color{red}
-There is a small fifo marked ``Epilogue'' just beyond the instruction
-destination; after the {\tt tail} instruction seals the hatch, any
-subsequent instructions will queue up in this fifo until the hatch is
-unsealed. This is typically used as storage for a ``loop epilogue''
--- a sequence of instructions to be executed after a torpedo arrives
-or the outer loop counter expires.
+\subsection{The Requeue Stage}
-A {\it token} sent to a ship's instruction destination is treated as a
-torpedo; the check for a torpedo is performed {\it before} the head of
-the Epilogue fifo. Note that because the check for a token is
-performed ``upstream'' of the epilogue fifo, torpedos will still be
-effective even when the Epilogue fifo is nearly full.
-\color{black}
+The requeue stage has two inputs, which will be referred to as the
+{\it enqueueing} input and the {\it recirculating} input. It has a
+single output which feeds into the instruction fifo.
-The dock also has a {\it torpedo acknowledgment path latch},
-which stores the path along which a token should be sent when a
-torpedo strikes.
-
-When a data item or token arrives at the torpedo destination, it lies
-there in wait until On Deck holds a potentially torpedoable
-instruction (see previous table). Once this is the case, the torpedo
-causes the inner and outer loop counters to be set to zero (and
-therefore also unseals the hatch)\footnote{it is unspecified whether
- the torpedoed instruction is requeued or not; this may or may not
- occur, nondeterministically. It is the programmer's responsibility
- to ensure that the program behaves the same whether this happens or
- not. We think that this will not matter in most situations.} and
-sends a token along the path stored in the torpedo acknowledgment path
-latch.
+The requeue stage has two states: {\sc Updating} and {\sc
+ Circulating}.
+\subsubsection{The {\sc Updating} State}
+On initialization, the dock is in the {\sc Updating} state. In this
+state the requeue stage is performing three tasks:
+\begin{itemize}
+\item it is draining the
+previous loop's instructions (if any) from the fifo
+\item it is executing any ``one
+shot'' instructions which come between the previous loop's {\tt tail}
+and the next loop's {\tt head}
+\item it is loading the instructions of
+the next loop into the fifo.
+\end{itemize}
-\subsection{Flags}
+In the {\sc Updating} state, the requeue stage will accept any
+instruction other than a {\tt tail} which arrives at its {\it
+ enqueueing} input, and pass this instruction to its output. Any
+instruction other than a {\tt head} which arrives at the {\it
+ recirculating} input will be discarded.
-The pump has three flags: {\tt A}, {\tt B}, and {\tt C}.
+Note that when a {\tt tail} instruction arrives at the {\it
+ enqueueing} input, it ``gets stuck'' there. Likewise, when a {\tt
+ head} instruction arrives at the {\it recirculating} input, it also
+``gets stuck''. When the requeue stage finds {\it both} a {\tt tail}
+instruction stuck at the {\it enqueueing} input and a {\tt head}
+instruction stuck at the {\it recirculating} input, the requeue stage
+discards both the {\tt head} and {\tt tail} and transitions to the
+{\sc Circulating} state.
-\begin{itemize}
-\item The {\tt A} and {\tt B} flags are general-purpose flags which
- may be set and cleared by the programmer.
+\subsubsection{The {\sc Circulating} State}
-%\item
-%
-% The {\tt L} flag, known as the {\it last} flag, is set whenever
-% the value in the outer counter ({\tt OLC}) is one,
-\color{black}
-% indicating
-% that the dock is in the midst of the last iteration of an
-% outer loop. This flag can be used to perform certain
-% operations (such as sending a completion token) only on the last
-% iteration of an outer loop.
+In the {\sc Circulating} state, the dock repeatedly executes the set
+of instructions that are in the instruction fifo.
-\item The {\tt C} flag is known as the {\it control} flag, and it is
- set every time the data latch takes on a new value. At outboxes
- its value is determined by the ship; at inboxes its value is
- copied from an unused address bit in the destination to which
- the received value was sent.
-\end{itemize}
+In the {\sc Circulating} state, the requeue stage will not accept
+items from its {\it enqueueing} input. Any item presented at the {\it
+ recirculating} input will be passed through to the requeue stage's
+output.
-Many instruction fields are specified as
-three-bit {\it predicates}. These fields
-contain one of eight values, indicating if an action should be taken
-unconditionally or conditionally on one of the {\tt A}, {\tt B}, or
-{\tt C} flags:
+When an {\tt abort} instruction is executed, the requeue stage
+transitions back to the {\sc Updating} state. Note that {\tt abort}
+instructions include a predicate; an {\tt abort} instruction whose
+predicate is not met will not cause this transition.
-\begin{multicols}{2}
-\begin{itemize}
-\item {\tt 000:} if {\tt A} is set
-\item {\tt 001:} if {\tt A} is cleared
-\item {\tt 010:} if {\tt B} is set
-\item {\tt 011:} if {\tt B} is cleared
-\end{itemize}
-\begin{itemize}
-\item {\tt 100:} if {\tt C} is set
-\item {\tt 101:} if {\tt C} is cleared
-\item {\tt 110:} unused
-\item {\tt 111:} always
-\end{itemize}
-\end{multicols}
\color{black}
\pagebreak
\section{Instructions}
-Here is a list of the instructions supported by the dock:
-
-\begin{center}
-\begin{tabular}{|l|}\hline
-{\tt move} (variants: {\tt moveto}, {\tt dispatch}) \\
-{\tt literal}\\
-{\tt setFlags} \\
-{\tt setInner} \\
-{\tt setOuter} \\
-%{\tt torpedo} \\
-{\tt tail} \\\hline
-\end{tabular}
-\end{center}
-
-\color{black}
+%The dock supports four instructions:
+%{\tt move} (variants: {\tt moveto}, {\tt dispatch}),
+%{\tt shift},
+%{\tt set}, and
+%{\tt tail}.
+%\color{black}
-\subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
+\subsection{{\tt move}}
\newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
{\tt
-\begin{bytefield}{26}
+\begin{bytefield}{25}
\bitheader[b]{14-20}\\
\color{light}
\bitsHeader
\bitbox[l]{19}{}
\end{bytefield}}
-\begin{bytefield}{26}
+\begin{bytefield}{25}
\bitheader[b]{0,12,13}\\
- \bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt LiteralPath\to Path})}
+ \bitbox[1]{10}{\raggedleft {\tt moveto} ({\tt Immediate\to Path})}
\bitbox[r]{1}{}
\bitbox{1}{\tt 1}
- \bitbox{13}{\tt LiteralPath}
+ \bitbox{13}{\tt Immediate}
\end{bytefield}
-\begin{bytefield}{26}
+\begin{bytefield}{25}
\bitheader[b]{11,12,13}\\
- \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\tt DP[37:25]\to Path})\ \ }
+ \bitbox[1]{10}{\raggedleft {\tt dispatch} ({\footnotesize {\tt DataPredecessor[37:26\color{black}]\to Path}})\ \ }
\bitbox[r]{1}{}
\bitbox{1}{\tt 0}
\bitbox{1}{\tt 1}
- \bitbox{1}{\tt 0}
\color{light}
- \bitbox[trb]{11}{}
+ \bitbox[trb]{12}{}
\color{black}
\end{bytefield}
-\begin{bytefield}{26}
+\begin{bytefield}{25}
\bitheader[b]{11,12,13}\\
- \bitbox[1]{11}{\raggedleft {\tt move} ({\tt Path} unchanged):}
+ \bitbox[1]{10}{\raggedleft {\tt move} ({\tt Path} unchanged):}
\bitbox[r]{1}{}
\bitbox{1}{\tt 0}
\bitbox{1}{\tt 0}
- \bitbox{1}{\tt 1}
\color{light}
- \bitbox[trb]{11}{}
+ \bitbox[trb]{12}{}
\color{black}
\end{bytefield}}
\bitsMove
The data successor and token successor must both be empty in order for
a {\tt move} instruction to attempt execution.
-The inner loop counter can hold a number {\tt 0..MAX} or a special
-value $\infty$. If {\tt ILC} is nonzero after execution of a {\tt
- move} instruction, the instruction will execute again, and {\tt ILC}
-will be latched with {\tt (ILC==$\infty$?$\infty$:max(ILC-1, 0))}. When
-the inner loop counter reaches zero, the instruction ceases executing.
+The {\tt I} bit stands for {\tt Immune}, and indicates if the
+instruction is immune to torpedoes.
+Every time the {\tt move} instruction executes, the {\tt C} flag is
+be set:
+
+\begin{itemize}
+\item If the dock is an {\it output} and the instruction has the {\tt
+ Dc} bit set, the {\tt C} flag is set to a value provided by the
+ ship.
+
+\item Otherwise, if {\tt Ti=1} at any kind of dock or {\tt Di=1} at an
+ input dock, the {\tt C} flag is set to the signal bit of the
+ incoming packet.
+
+\item Otherwise, the signal bit is set to an undefined value.
+
+\end{itemize}
+\color{black}
+
+The {\tt flush} instruction is a variant of {\tt move} which is valid
+only at input docks. It has the same effect as {\tt deliver}, except
+that it sets a special ``flushing'' indicator along with the data
+being delivered.
+
+\newcommand{\bitsFlush}{\setlength{\bitwidth}{5mm}
+{\tt
+\begin{bytefield}{25}
+ \bitheader[b]{14-18}\\
+ \bitbox[r]{6}{\raggedleft{\tt flush\ \ }}
+ \bitbox{1}{\tt 0}
+\color{black}
+ \bitbox{1}{\tt 0}
+ \bitbox{1}{\tt 1}
+\color{light}
+ \bitbox{1}{\tt 0}
+ \bitbox{1}{\tt 0}
+ \bitbox{14}{}
+\end{bytefield}}}
+\bitsFlush
+
+When a ship fires, it must examine the ``flushing'' indicators on the
+input docks whose fullness was part of the firing condition. If all
+of the input docks' flushing indicators are set, the ship must drain
+all of their data successors and take no action. If some, but not
+all, of the indicators are set, the ship must drain {\it only the data
+ successors of the docks whose indicators were {\bf not} set}, and
+take no action. If none of the flushing indicators was set, the ship
+fires normally.
+
+\color{black}
\pagebreak
\subsection{{\tt set}}
-\color{red}
-
The {\tt set} command is used to set or decrement the inner loop
counter, outer loop counter, and data latch.
\newcommand{\bitsSet}{
-\setlength{\bitwidth}{5mm}
{\tt
-\begin{bytefield}{26}
- \bitheader[b]{0,14-15,16-20}\\
-\color{light}
- \bitsHeader
-\color{black}
+\begin{bytefield}{25}
+ \bitheader[b]{19-24}\\
+ \bitsHeaderNoI
\bitbox{1}{1}
\bitbox{1}{0}
- \bitbox{2}{SRC}
- \bitbox{2}{DST}
+\color{light}
+ \bitbox{4}{Dest}
+ \bitbox{3}{Src}
+ \bitbox{12}{}
\color{black}
- \bitbox{15}{Payload}
\end{bytefield}}
-}
-\bitsSet
-\begin{center}{\tt
-\begin{tabular}{|r|r|l|l|}\hline
-Source & SRC & DST & Destination \\\hline
-\hline
-Payload & 00 & 00 & OLC \\
-Data Latch & 01 & 00 & OLC \\
-OLC-1 & 10 & 00 & OLC \\
-Payload & 00 & 01 & ILC \\
-Data Latch & 01 & 01 & ILC \\
-$\infty$ & 10 & 01 & ILC \\
-Payload & 00 & 10 & Torpedo Ack Path \\
-Payload, 0-extend & 01 & 10 & Data Latch \\
-Payload, 1-extend & 10 & 10 & Data Latch \\
- see below & & 11 & Flags \\
-\hline
-\end{tabular}
-}\end{center}
+\begin{bytefield}{25}
+ \bitheader[b]{0,5,12-18}\\
+ \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt OLC}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 1000\color{black}}
+ \bitbox{3}{\tt 100}
+ \bitbox{6}{}
+ \bitbox{6}{\tt Immediate}
+\end{bytefield}
-The FleetTwo implementation is likely to have an unarchitected
-``literal latch'' at the OD stage, which is loaded with the
-possibly-extended literal {\it at the time that the {\tt set}
- instruction comes on deck}. This latch is then copied into the data
-latch when the instruction executes.
+\begin{bytefield}{25}
+ \bitheader[b]{12-18}\\
+ \bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt OLC}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 1000\color{black}}
+ \bitbox{3}{\tt 010}
+ \bitbox{12}{}
+\end{bytefield}
+
+\begin{bytefield}{25}
+ \bitheader[b]{12-18}\\
+ \bitbox[1]{6}{\raggedleft {\tt OLC-1}\to{\tt OLC}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 1000\color{black}}
+ \bitbox{3}{\tt 001}
+ \bitbox{12}{}
+\end{bytefield}
-If the {\tt Dest} field is flags, the {\tt Payload} field is
-interpreted as two fields, each giving the truth table for the new
-value of one of the two user-settable flags:
+\begin{bytefield}{25}
+ \bitheader[b]{0,5,6,12-18}\\
+ \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt ILC}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 0100\color{black}}
+ \bitbox{3}{\tt 100}
+ \bitbox{5}{}
+ \bitbox{1}{\tt 0}
+ \bitbox{6}{\tt Immediate}
+\end{bytefield}
+
+\begin{bytefield}{25}
+ \bitheader[b]{6,12-18}\\
+ \bitbox[1]{6}{\raggedleft $\infty$\to{\tt ILC}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 0100\color{black}}
+ \bitbox{3}{\tt 100}
+ \bitbox{5}{}
+ \bitbox{1}{\tt 1}
+ \bitbox{6}{}
+\end{bytefield}
+\begin{bytefield}{25}
+ \bitheader[b]{12-18}\\
+ \bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt ILC}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 0100\color{black}}
+ \bitbox{3}{\tt 010}
+ \bitbox{12}{}
+\end{bytefield}
+
+\begin{bytefield}{25}
+ \bitheader[b]{0,13-18}\\
+ \bitbox[1]{6}{\raggedleft \footnotesize {\tt Sign-Extended Immediate}\to{\tt Data Latch}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 0010\color{black}}
+ \bitbox{1}{\begin{minipage}{0.5cm}{
\begin{center}
-\setlength{\bitwidth}{5mm}
-{\tt
-\begin{bytefield}{26}
- \bitheader[b]{0,5,6,11}\\
-\color{light}
- \bitsHeader
- \bitbox{1}{1}
- \bitbox{1}{0}
-\color{light}
- \bitbox{2}{}
-\color{black}
- \bitbox{2}{11}
-\color{light}
+\tt{\footnotesize{Si
+
+\vspace{-2mm}gn}}
+\end{center}}
+\end{minipage}}
+ \bitbox{14}{\tt Immediate}
+\end{bytefield}
+
+\begin{bytefield}{25}
+ \bitheader[b]{0,5,6,11,15-18}\\
+ \bitbox[1]{6}{\raggedleft {\tt Update Flags}}
+ \bitbox[r]{1}{}
+ \bitbox{4}{\tt 0001\color{black}}
\bitbox{3}{}
+ \bitbox{6}{\tt nextA}
+ \bitbox{6}{\tt nextB}
+\end{bytefield}
\color{black}
- \bitbox{6}{nextA}
- \bitbox{6}{nextB}
-\end{bytefield}}
-\end{center}
+}
+\bitsSet
+
+The Marina implementation has an unarchitected
+``literal latch'' at the on deck ({\tt OD}) stage, which is loaded
+with the possibly-extended literal {\it at the time that the {\tt set}
+ instruction comes on deck}. This latch is then copied into the data
+latch when a {\tt set Data Latch} instruction
+executes.
+
+The {\tt Sign-Extended Immediate} instruction copies the {\tt
+Immediate} field into the least significant bits of the data latch.
+All other bits of the data latch are filled with a copy of the
+bit marked ``{\tt Sign}.''
\color{black}
-Each field has the following structure, and indicates which old flag
-values should be logically {\tt OR}ed together to produce the new flag
-value:
+
+Each of the {\tt nextA} and {\tt nextB} fields has the following
+structure, and indicates which old flag values should be logically
+{\tt OR}ed together to produce the new flag value:
\begin{center}
{\tt
\pagebreak
\subsection{{\tt shift}}
-\color{red}
-
-\newcommand{\shiftPayloadSize}{19}
+\newcommand{\shiftImmediateSize}{19}
-Each {\tt shift} instruction carries a payload of \shiftPayloadSize\
-bits. When a {\tt shift} instruction is executed, this payload is copied
-into the least significant \shiftPayloadSize\ bits of the data latch,
+Each {\tt shift} instruction carries an immediate of \shiftImmediateSize\
+bits. When a {\tt shift} instruction is executed, this immediate is copied
+into the least significant \shiftImmediateSize\ bits of the data latch,
and the remaining most significant bits of the data latch are loaded
with the value formerly in the least significant bits of the data latch.
In this manner, large literals can be built up by ``shifting'' them
-into the data latch \shiftPayloadSize\ bits at a time.
+into the data latch \shiftImmediateSize\ bits at a time.
\newcommand{\bitsShift}{
\setlength{\bitwidth}{5mm}
{\tt
-\begin{bytefield}{26}
+\begin{bytefield}{25}
\bitheader[b]{0,18-20}\\
\color{light}
- \bitsHeader
+ \bitsHeaderNoI
\color{black}
\bitbox{1}{0}
\bitbox{1}{0}
\color{black}
- \bitbox{\shiftPayloadSize}{Payload}
+ \bitbox{\shiftImmediateSize}{Immediate}
\end{bytefield}}
}
\bitsShift
-The FleetTwo implementation is likely to have an unarchitected
-``literal latch'' at the OD stage, which is loaded with the literal
-{\it at the time that the {\tt shift} instruction comes on deck}.
-This latch is then copied into the data latch when the instruction
-executes.
+The Marina implementation has an unarchitected
+``literal latch'' at the on deck ({\tt OD}) stage, which is loaded
+with the literal {\it at the time that the {\tt shift} instruction
+ comes on deck}. This latch is then copied into the data latch when
+the instruction executes.
\color{black}
-\subsection{{\tt tail}}
+\subsection{{\tt abort}}
+\newcommand{\bitsAbort}{\setlength{\bitwidth}{5mm}
+{\tt
+\begin{bytefield}{25}
+ \bitheader[b]{17-20}\\
+\color{light}
+ \bitsHeaderNoI
+\color{black}
+ \bitbox{1}{1}
+ \bitbox{1}{1}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox[tbr]{17}{}
+\end{bytefield}}}
+\bitsAbort
+
+An {\tt abort} instruction causes a loop to exit; see the section on
+the Requeue Stage for further details.
+
+\subsection{{\tt head}}
+\newcommand{\bitsHead}{
+\setlength{\bitwidth}{5mm}
+{\tt
+\begin{bytefield}{25}
+ \bitheader[b]{17-20}\\
+\color{light}
+ \bitbox{4}{}
+\color{black}
+ \bitbox{1}{1}
+ \bitbox{1}{1}
+ \bitbox{1}{1}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox[tbr]{17}{}
+\end{bytefield}}}
+\bitsHead
+
+A {\tt head} instruction marks the start of a loop; see the section on
+the Requeue Stage for further details.
+\color{black}
+\subsection{{\tt tail}}
\newcommand{\bitsTail}{
\setlength{\bitwidth}{5mm}
{\tt
-\begin{bytefield}{26}
- \bitheader[b]{19-20}\\
+\begin{bytefield}{25}
+ \bitheader[b]{17-20}\\
\color{light}
- \bitbox{5}{}
+ \bitbox{4}{}
\color{black}
\bitbox{1}{1}
\bitbox{1}{1}
+ \bitbox{1}{1}
+ \bitbox{1}{1}
\color{light}
- \bitbox[tbr]{19}{}
+ \bitbox[tbr]{17}{}
\end{bytefield}}}
\bitsTail
-When a {\tt tail} instruction reaches {\tt IH}, it seals the hatch.
-The {\tt tail} instruction does not enter the instruction fifo.
+A {\tt tail} instruction marks the end of a loop; see the section on
+the Requeue Stage for further details.
\color{black}
%\pagebreak
%
%\setlength{\bitwidth}{5mm}
%{\tt
-%\begin{bytefield}{26}
+%\begin{bytefield}{25}
% \bitheader[b]{16-19,21}\\
%\color{light}
% \bitbox{1}{A}
%
%\setlength{\bitwidth}{5mm}
%{\tt
-%\begin{bytefield}{26}
+%\begin{bytefield}{25}
% \bitheader[b]{16-19,21}\\
%\color{light}
% \bitbox{1}{A}
%%
%%\setlength{\bitwidth}{5mm}
%{\tt
-%\begin{bytefield}{26}
+%\begin{bytefield}{25}
% \bitheader[b]{0,5,16-19,21}\\
%\color{light}
% \bitbox{4}{}
%
%\setlength{\bitwidth}{5mm}
%{\tt
-%\begin{bytefield}{26}
+%\begin{bytefield}{25}
% \bitheader[b]{16-19,21}\\
%\color{light}
% \bitbox{4}{}
%
%\setlength{\bitwidth}{5mm}
%{\tt
-%\begin{bytefield}{26}
+%\begin{bytefield}{25}
% \bitheader[b]{16-19,21}\\
%\color{light}
% \bitbox{4}{}
%
%\setlength{\bitwidth}{5mm}
%{\tt
-%\begin{bytefield}{26}
+%\begin{bytefield}{25}
% \bitheader[b]{16-19,21}\\
%\color{light}
% \bitbox{4}{}
%clogged and whose instruction fifo contains no {\tt clog} instructions
%will cause the dock to deadlock.
+\pagebreak
+\section*{Errata}
+
+The following additional restrictions have been imposed on the dock in
+the Marina test chip:
+\subsection*{Both Docks}
+
+\begin{enumerate}
+
+\item
+A Marina dock initializes with the {\tt ILC}, {\tt OLC}, and flags in
+an indeterminate state.
+
+\item
+The instruction immediately after a {\tt move} instruction must not be
+a {\tt set flags} instruction which utilizes the {\tt C}-flag (the
+value of the {\tt C}-flag is not stable for a brief time after a {\tt
+ move}).
+
+\item
+If a {\tt move} instruction is torpedoable (ie it has the {\tt I} bit
+set to {\tt 0}), it {\it must} have either the {\tt Ti} bit or {\tt
+ Di} bit set (or both). It is not permitted for a torpedoable {\tt
+ move} to have both bits cleared.
+
+\end{enumerate}
+
+
+\subsection*{Dock with Ivan's Counter (non-stretch)}
+
+\begin{enumerate}
+
+\item
+
+A torpedoable {\tt move} instruction must not be followed immediately
+by a {\tt set olc} instruction or another torpedoable {\tt move}.
+
+\item
+
+This document specifies that when a torpedoable {\tt move} instruction
+executes successfully, the {\tt D} flag is unchanged. In Marina, when
+a torpedoable {\tt move} instruction executes successfully, it causes
+the {\tt D} flag to be set if the {\tt OLC} was zero and causes it to
+be cleared if the {\tt OLC} was nonzero. Thus, in the following
+instruction sequence:
+
+ \begin{verbatim}
+ head;
+ [*] set olc=1;
+ send token to self:i;
+ [T] recv token;
+ [*] send token to self;
+ [T] recv token;
+ [*] abort;
+ tail;
+ \end{verbatim}
+
+Will leave the {\tt D} flag {\it set} on Marina, whereas a strict
+implementation of this document would leave it cleared.
+
+In practice, this distinction rarely matters.
+
+\end{enumerate}
+
+\subsection*{Dock with Kessels Counter (``stretch'')}
+
+With the Kessels counter, the {\tt D}-flag {\it is exactly equal to}
+the zeroness of the {\tt OLC}; it cannot be ``out of sync'' with it.
+
+\begin{enumerate}
+
+\item
+Every ``load OLC'' instruction must be predicated on the {\tt D}-flag
+being {\it set}. This is a sneaky way of forcing the programmer to
+``run down'' the counter before loading it, because Kessels' counter
+does not support ``unloading.''
+
+\item
+Every ``decrement OLC'' instruction must be predicated on the {\tt
+ D}-flag being {\it cleared}. This way we never have to check if the
+counter is already empty before decrementing.
+
+\item
+The instruction after a torpedoable {\tt move} must not be predicated
+on the {\tt D}-flag being {\it set} (it may be predicated on the {\tt
+ D}-flag being {\it cleared}. This is because, while the move
+instruction is waiting to execute, the {\tt D}-flag will be cleared,
+and the predicate stage believes that it can skip the instruction even
+though {\tt do[ins]} is still high (I think this is dumb).
+
+
+\end{enumerate}
+
+\color{black}
\pagebreak
-\section*{\color{red}Instruction Encoding Map\color{black}}
+\section*{External Instruction Encoding Map\color{black}}
-\hspace{-1cm}{\tt move}\\
-\bitsMove
-\hspace{-1cm}{\tt shift}\\
+\vspace{3mm}\hspace{-1cm}{\tt shift}\hspace{1cm}\vspace{-6mm}\\
\bitsShift
-\hspace{-1cm}{\tt set}\\
+\vspace{3mm}\hspace{-1cm}{\tt set}\hspace{1cm}\vspace{-6mm}\\
\bitsSet
-\hspace{-1cm}{\tt tail}\\
-\bitsTail
+\vspace{3mm}\hspace{-1cm}{\tt move}\hspace{1cm}\vspace{-6mm}\\
+\bitsMove
+\bitsFlush
+\vspace{3mm}\hspace{-1cm}{\tt abort}\hspace{1cm}\vspace{-6mm}\\
+\bitsAbort
-\color{black}
+\vspace{3mm}\hspace{-1cm}{\tt head}\hspace{1cm}\vspace{-6mm}\\
+\bitsHead
-\pagebreak
-\epsfig{file=overview,height=5in,angle=90}
+\vspace{3mm}\hspace{-1cm}{\tt tail}\hspace{1cm}\vspace{-6mm}\\
+\bitsTail
-\pagebreak
-\subsection*{Input Dock}
-\epsfig{file=indock,width=7in,angle=90}
-\pagebreak
-\subsection*{Output Dock}
-\epsfig{file=outdock,width=6.5in,angle=90}
+%\pagebreak
+%\epsfig{file=all,height=5in,angle=90}
+
+%\pagebreak
+%\subsection*{Input Dock}
+%\epsfig{file=in,width=8in,angle=90}
+
+%\pagebreak
+%\subsection*{Output Dock}
+%\epsfig{file=out,width=8in,angle=90}
%\pagebreak
%\pagebreak
%\epsfig{file=best,height=5in,angle=90}
+\pagebreak
+\section*{Internal Instruction Encoding Map\color{black}}
+
+Marina Instructions in main memory occupy 37 bits. Of this, 11 bits
+give the path to the dock which is to execute the instruction; thus,
+only 26 of these bits are interpreted by the dock.
+
+It is easiest to design the OD and EX stages of the dock if the
+control bits supplied there are mostly one-hot encoded. Moreover, due
+to layout considerations there is very little cost associated with
+making the instruction fifo 36 bits wide rather than 26 bits wide.
+
+Due to these two considerations, all 26-bit instructions
+binary-coded-control instructions are expanded into 36-bit
+unary-coded-control instructions upon entry to the instruction fifo.
+This section documents the 36-bit unary-coded-control format.
+
+\subsection*{Predicate Field}
+
+The {\tt Predicate} field, common to many instructions, consists of a
+six-bit wide, one-hot encoded field. The instruction will be {\bf
+ skipped} (not executed) if {\bf any} condition corresponding to a
+bit whose value is one is met.
+
+\setlength{\bitwidth}{3.5mm}
+{\footnotesize\tt\begin{bytefield}{36}
+ \bitheader[b]{0,29-35}\\
+\color{black}
+ \bitbox{1}{D}
+ \bitbox{1}{!D}
+ \bitbox{1}{!B}
+ \bitbox{1}{B}
+ \bitbox{1}{!A}
+ \bitbox{1}{A}
+\color{light}
+ \bitbox{30}{}
+\end{bytefield}}
+
+For example, if bits 31 and 34 are set, the instruction will be
+skipped if either the {\tt B} flag is cleared or the {\tt A} flag is
+set. Equivalently, it will be executed iff the {\tt B} flag is set
+and the {\tt A} flag is cleared.
+
+\subsection*{Set Flags}
+
+Each of the {\tt FlagA} and {\tt FlagB} fields in the Set Flags
+instruction gives a truth table; the new value of the flag is the
+logical OR of the inputs whose bits are set to {\tt 1}.
+
+\setlength{\bitwidth}{5mm}
+{\tt\begin{bytefield}{6}
+ \bitheader[b]{0-5}\\
+\color{black}
+ \bitbox{1}{!C}
+ \bitbox{1}{C}
+ \bitbox{1}{!B}
+ \bitbox{1}{B}
+ \bitbox{1}{!A}
+ \bitbox{1}{A}
+\end{bytefield}}
+
+\newcommand{\common}{%
+\bitbox{6}{Predicate}%
+}
+
+\pagebreak
+\pagestyle{plain}
+\pdfpagewidth 8.5in
+\pdfpageheight 11in
+\textheight 7.9in
+\textwidth 7.0in
+\oddsidemargin 0.9in
+%\headwidth 6.0in
+
+\begin{sidewaysfigure}[h!]
+%\begin{landscape}
+
+\setlength{\bitwidth}{5mm}
+\begin{tabular}{lr}
+\\
+Shift &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,18,19,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+ \bitbox{19}{immediate}
+\end{bytefield}} \\
+Set Data Latch &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,13,14,15,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox{4}{}
+\color{black}
+ \bitbox{1}{+-}
+ \bitbox{14}{immediate to sign ext}
+\end{bytefield}} \\\hline
+\\
+Move, Immediate$\rightarrow$Path &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,13,14-20,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{Tp}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{rD}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{Ti}
+ \bitbox{1}{Di}
+ \bitbox{1}{Dc}
+ \bitbox{1}{Do}
+ \bitbox{1}{To}
+ \bitbox{1}{1}
+ \bitbox{13}{Immediate}
+\end{bytefield}} \\
+Move, DP[37:26]$\rightarrow$Path &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,12-13,14-20,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{Tp}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{rD}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{Ti}
+ \bitbox{1}{Di}
+ \bitbox{1}{Dc}
+ \bitbox{1}{Do}
+ \bitbox{1}{To}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox{12}{}
+\end{bytefield}} \\
+Move, Path unchanged &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,11-13,14-20,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{Tp}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{rD}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{Ti}
+ \bitbox{1}{Di}
+ \bitbox{1}{Dc}
+ \bitbox{1}{Do}
+ \bitbox{1}{To}
+ \bitbox{1}{0}
+ \bitbox{1}{1}
+ \bitbox{1}{F$\dagger$}
+\color{light}
+ \bitbox{11}{}
+\end{bytefield}} \\
+\hline
+\color{black}
+\\
+Set Flags &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,11,12,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{9}{}
+\color{black}
+ \bitbox{6}{FlagB}
+ \bitbox{6}{FlagA}
+\end{bytefield}} \\\hline
+\\
+Decrement OLC &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,20-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{20}{}
+\color{black}
+\end{bytefield}} \\
+Data Latch\to OLC &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,19-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{19}{}
+\color{black}
+\end{bytefield}} \\
+Immediate\to OLC &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,5,19-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+\color{black}
+ \bitbox{1}{{0}}
+\color{light}
+ \bitbox{13}{}
+\color{black}
+ \bitbox{6}{Immediate}
+\end{bytefield}} \\\hline
+\\
+Data Latch\to ILC &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,19,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{0}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{19}{}
+\color{black}
+\end{bytefield}} \\
+Immediate\to ILC &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,5,7,19,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox{10}{}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{0${}^\star$}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{6}{Immediate}
+\end{bytefield}} \\
+$\infty$\to ILC &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{0,7,21-30,35}\\
+\common
+\color{light}
+ \bitbox{3}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{0}
+\color{light}
+ \bitbox{11}{}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1${}^\star$}
+\color{light}
+ \bitbox{1}{}
+\color{light}
+ \bitbox{6}{}
+\end{bytefield}} \\\hline
+\\
+{\tt head} &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{29}\\
+\color{light}
+ \bitbox{6}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{2}{}
+\color{light}
+ \bitbox{27}{}
+\end{bytefield}} \\
+{\tt abort${}^1$} &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{28}\\
+\color{black}
+ \bitbox{6}{Predicate}
+\color{light}
+ \bitbox{1}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{6}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{9}{}
+\color{black}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{1}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{0}
+ \bitbox{1}{1}
+\end{bytefield}} \\
+{\tt tail} &
+{\tt\begin{bytefield}{36}
+ \bitheader[b]{27}\\
+\color{light}
+ \bitbox{6}{}
+\color{light}
+ \bitbox{2}{}
+\color{black}
+ \bitbox{1}{1}
+\color{light}
+ \bitbox{27}{}
+\end{bytefield}} \\
+\\
+\end{tabular}
+$\star$ -- Bit 8 is the ``infinity'' bit \\
+$\dagger$ -- When a ``Move, Path unchanged'' is performed, bit 12 is copied to the ``flushing latch''. \\
+.\hspace{0.5cm} When a ship fires, it examines the ``flushing latches'' of all of its inboxes as part of its decision about what to do. \\
+$1$ -- The encoding of the {\tt abort} instruction was chosen in order to make it look like a {\tt set flags} instruction which does not change the flags. \\
+Tp\ \ = Torpedoable (1=Torpedoable, 0=Not-Torpedoable) \\
+rD\ \ = recompute D-flag (1=recompute, 0=leave unchanged)
+%\end{landscape}
+\end{sidewaysfigure}
+
+\pagebreak
+\section*{Marina Dock Block Diagram}
+This diagram was produced by Ivan Sutherland.
+\\
+\epsfig{file=blockDiagram,width=8in,angle=90}
\end{document}
projects / fleet.git / blobdiff