From 0ff42a9dafaac26353613ba5c8af0041cd660ec6 Mon Sep 17 00:00:00 2001 From: adam Date: Tue, 17 Feb 2009 11:09:20 -0800 Subject: [PATCH] update to 17-Feb darcs-hash:20090217190920-5007d-cfb034191bdc994c89346f2c9a25f0998928af2e.gz --- am33.tex | 456 +++++++++++++++++++++++++++++++++----------------------------- 1 file changed, 240 insertions(+), 216 deletions(-) diff --git a/am33.tex b/am33.tex index 632aefe..1c8eed3 100644 --- a/am33.tex +++ b/am33.tex @@ -37,7 +37,7 @@ %\pdfpagewidth 8.5in %\pdfpageheight 11in %\topmargin 0in -\textheight 7.9in +\textheight 8.2in %\textwidth 6.0in %\oddsidemargin 0.25in %\evensidemargin 0.25in @@ -66,11 +66,20 @@ Adam Megacz Changes: \begin{tabular}{rl} -\color{red} +\color{red}17-Feb\color{black} +& \color{red} Clarified setting of the {\tt C}-flag\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 -& \color{red} Updated diagram in section 3 to put dispatch path near MSB\\ -& \color{red} Changed DP[37:25] to DP[37:27]\\ -& \color{red} Added note on page 4 regarding previous\\ +& 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 \\ @@ -84,24 +93,24 @@ Changes: 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\\ +%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 \\ @@ -226,13 +235,19 @@ may differ. \end{center} 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. The dock also includes a {\it path latch}, which -stores the path along which outgoing packets will be sent.\color{black} - -Note that the pump in each dock has a destination of its own; this is -the {\it instruction destination} mentioned in the previous section. +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.\color{black} + +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 @@ -249,8 +264,8 @@ 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 port} of the dock at which it is to -execute. +sending it to the {\it instruction destination} of the dock at which +it is to execute. 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. @@ -259,7 +274,6 @@ This path is the path from the {\it dispatching} dock to the {\it \vspace{0.5cm} -\color{red} \setlength{\bitwidth}{3.5mm} {\tt \footnotesize \begin{bytefield}{37} @@ -269,7 +283,6 @@ This path is the path from the {\it dispatching} dock to the {\it \end{bytefield}} \color{black} -\color{red} Note that the 11 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 @@ -277,7 +290,7 @@ the switch fabric. The algorithm for expanding a path to a wider width is specific to the switch fabric implementation, and is not specified by this -document.\footnote{\color{red}for the Marina experiment, the correct +document.\footnote{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 all vacant bits of the latch} In particular, because the {\tt dispatch path} field is always used to @@ -286,79 +299,49 @@ data destination), and because instruction destinations ignore the signal bit, certain optimizations may be possible. \color{black} -\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} - -\subsubsection{Torpedoes} - -A token sent to an instruction destination is called a {\it torpedo}. -When a torpedo arrives at the tail of {\tt EF}, it is deposited in a -waiting area (not shown) rather than being enqueued into {\tt EF}. - -\subsection{Format of an Instruction} - -All instruction words have the following format: +%\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{1}{} \bitbox{3}{P} } \newcommand{\bitsHeaderNoI}{ - \bitbox{1}{} - \bitbox{1}{OS} + \bitbox{2}{} \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,31,32,34-36}\\ -\color{black} - \bitsHeader -\color{light} - \bitbox[tbr]{21}{} - \bitbox{11}{dispatch path} -\color{black} -\end{bytefield}} - -\begin{itemize} - -\item The {\tt I} bit stands for {\tt Immune}, - and indicates if an instruction is - immune to torpedoes. This bit only appears - in {\tt move} instructions. - -\item The {\tt OS} (``One Shot'') bit indicates whether or not this - instruction can pass through the pump more than once. If set to - {\tt 1}, then the instruction is a ``one-shot'' instruction, and - does not pass through the instruction fifo more than once. - -\item 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. -\end{itemize} -\pagebreak \subsection{Loop Counters} -A programmer can perform two types of loops: {\it inner} loops of only -one instruction and {\it outer} loops of multiple instructions. Inner -loops may be nested within an outer loop, but no other nesting of -loops is allowed. +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. The dock has two loop counters, one for each kind of loop: @@ -379,10 +362,10 @@ instruction the {\tt ILC} is reset to {\tt 1} (note that it is reset to {\tt 1}, {\it not to 0}). \color{black} -\subsection{Flags and Predication} +\subsection{Flags} -The pump has four flags: {\tt A}, {\tt B}, -{\tt C}, and {\tt Z}. +The dock has four flags: {\tt A}, {\tt B}, +{\tt C}, and {\tt D}. \begin{itemize} \item The {\tt A} and {\tt B} flags are general-purpose flags which @@ -404,116 +387,113 @@ The pump has four flags: {\tt A}, {\tt B}, ship or from an inbound packet. See the {\tt move} instruction for further details. -\item The {\tt Z} flag is known as the {\it zero} flag; it is set - whenever the {\tt OLC} is zero, and is cleared whenever the {\tt - OLC} is nonzero. +\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. \color{black} \end{itemize} -The {\tt P} field specifies a three-bit {\it predicate}. The -predicate determines which conditions must be true in order for the -instruction to execute; if it is not executed, it is simply {\it +\subsection{Predication} + +All instructions except for {\tt head} and {\tt tail} have a three-bit +field marked {\tt P}, which specifies a {\it predicate}. + +\begin{center} +\setlength{\bitwidth}{5mm} +{\tt{\footnotesize{ +\begin{bytefield}{26} + \bitheader[b]{0,20,21,23-25}\\ + \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 Code & Execute if \\\hline -{\tt 000:} & {\tt Z=0}\ and {\tt A=0} \\ -{\tt 001:} & {\tt Z=0}\ and {\tt A=1} \\ -{\tt 010:} & {\tt Z=0}\ and {\tt B=0} \\ -{\tt 011:} & {\tt Z=0}\ and {\tt B=1} \\ +{\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 Z=1}\ \\ -{\tt 110:} & {\tt Z=0}\ \\ +{\tt 101:} & {\tt D=1}\ \\ +{\tt 110:} & {\tt D=0}\ \\ {\tt 111:} & always \\ \hline\end{tabular} \end{center} \pagebreak -\subsection{The Hatch} - -What follows is a conservative approximation of the actual behavior of -the hatch. -For complete details on the behavior of the hatch, see -\href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50}. - -For the purposes of this section, instructions will be -classified into three categories: one-shot instructions ({\tt OS=1}), -requeueable instructions ({\tt OS=0}), and {\tt tail} instructions. - -To avoid deadlock, the programmer must ensure that: - -\begin{itemize} - -\item A requeueable instruction is never followed immediately by a - one-shot. -\item A one-shot instruction is never followed immediately by a {\tt - tail}. +\begin{wrapfigure}{r}{40mm} + \begin{center} +\epsfig{file=requeue,height=1.5in}\\ + \end{center} + \caption{{\it the requeue stage}} +\end{wrapfigure} -\item No contiguous sequence of requeueable instructions is longer - than the length of the instruction fifo. +\subsection{The Requeue Stage} -\item If a requeueable instruction is preceded by a one-shot - instruction or a {\tt tail}, then it must be the case that - {\tt Z=0} both before and after the first - time that instruction executes. +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. -\item If {\tt Z=1}, only a one-shot instruction may set it to a - nonzero value. - -\end{itemize} +The requeue stage has two states: {\sc Updating} and {\sc + Circulating}. -The dock guarantees that: +\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} -\item If a requeueable instruction is preceded by a one-shot - instruction or a {\tt tail}, then the {\it following} - instruction will not execute until a {\tt tail} has reached the - hatch. +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. -\item Once a {\tt tail} instruction reaches the hatch, no further - instructions will be enqueued until a requeueable instruction - reaches the execution stage and {\tt Z=1}. +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. -\end{itemize} +\subsubsection{The {\sc Circulating} State} +In the {\sc Circulating} state, the dock repeatedly executes the set +of instructions that are in the instruction fifo. -\color{black} -\subsection{On Deck} - -When an instruction arrives on deck, two concurrent processes are -started: -\begin{enumerate} -\item Requeueing: - \begin{itemize} - \item If the instruction on deck is a requeueable instruction - ({\tt OS=0}) and {\tt Z=0}, a copy of - the instruction is requeued. - \end{itemize} - -\item Execution: - \begin{itemize} - \item - If the instruction's predicate condition is not met (see - section on predicates), do nothing. - - \item - {\it Otherwise} if the instruction is interruptible ({\tt I=0}) - and a torpedo is present in the waiting area: consume the - torpedo, set {\tt OLC=0}, {\tt Z=1} and - set the inner loop counter to one ({\tt ILC=1}). - - \item - {\it Otherwise} if {\tt ILC$\neq$0} or the instruction is {\it - not} a {\tt move}: execute the instruction. - \end{itemize} -\end{enumerate} +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. +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. \color{black} @@ -558,7 +538,7 @@ started: \begin{bytefield}{26} \bitheader[b]{11,12,13}\\ - \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\footnotesize {\tt DataPredecessor[37:\color{red}27\color{black}]\to Path}})\ \ } + \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\footnotesize {\tt DataPredecessor[37:27\color{black}]\to Path}})\ \ } \bitbox[r]{1}{} \bitbox{1}{\tt 0} \bitbox{1}{\tt 1} @@ -590,23 +570,24 @@ started: The data successor and token successor must both be empty in order for a {\tt move} instruction to attempt execution. +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 may be set: +\color{red} \begin{itemize} \item At an {\it input} dock the {\tt C} flag is set to the signal bit - of the incoming packet if {\tt Di} or {\tt Ti} is - set otherwise it takes on an unknown - value. + of the incoming packet if {\tt Dc} bit is set. If the {\tt Dc} + bit is not set the {\tt C} flag takes an unknown value. \item At an {\it output} dock the {\tt C} flag is set to a value - provided by the ship if the {\tt Dc} bit is set. If - the {\tt Dc} bit is not set and the {\tt Ti} bit is set, it is - set to the signal bit of the incoming packet. If the {\tt Dc} - bit and {\tt Ti} bits are both cleared, it takes on an unknown - value.\color{black} - + provided by the ship if the {\tt Dc} bit is set. If the {\tt + Dc} bit is not set, the {\tt C} flag is set to the signal bit of + the incoming packet. \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 @@ -648,7 +629,6 @@ 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]{19-25}\\ @@ -656,8 +636,9 @@ counter, outer loop counter, and data latch. \bitbox{1}{1} \bitbox{1}{0} \color{light} - \bitbox{5}{Dest} - \bitbox{14}{} + \bitbox{4}{Dest} + \bitbox{3}{Src} + \bitbox{12}{} \color{black} \end{bytefield}} @@ -744,10 +725,7 @@ counter, outer loop counter, and data latch. \bitbox{6}{\tt nextA} \bitbox{6}{\tt nextB} \end{bytefield} - - \color{black} - } \bitsSet @@ -828,26 +806,68 @@ the instruction executes. \color{black} -\subsection{{\tt tail}} +\subsection{{\tt abort}} +\newcommand{\bitsAbort}{\setlength{\bitwidth}{5mm} +{\tt +\begin{bytefield}{26} + \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}{26} + \bitheader[b]{17-20}\\ +\color{light} + \bitbox{5}{} +\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}\\ + \bitheader[b]{17-20}\\ \color{light} \bitbox{5}{} \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 the hatch and the hatch is open, -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 @@ -999,33 +1019,37 @@ instruction fifo. \pagebreak \section*{Instruction Encoding Map\color{black}} -\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 move}\\ +\vspace{3mm}\hspace{-1cm}{\tt move}\hspace{1cm}\vspace{-6mm}\\ \bitsMove \bitsFlush -\color{black} -\hspace{-1cm}{\tt tail}\\ -\bitsTail +\vspace{3mm}\hspace{-1cm}{\tt abort}\hspace{1cm}\vspace{-6mm}\\ +\bitsAbort +\vspace{3mm}\hspace{-1cm}{\tt head}\hspace{1cm}\vspace{-6mm}\\ +\bitsHead -\color{black} +\vspace{3mm}\hspace{-1cm}{\tt tail}\hspace{1cm}\vspace{-6mm}\\ +\bitsTail -\pagebreak -\epsfig{file=all,height=5in,angle=90} -\pagebreak -\subsection*{Input Dock} -\epsfig{file=in,width=8in,angle=90} +%\pagebreak +%\epsfig{file=all,height=5in,angle=90} -\pagebreak -\subsection*{Output Dock} -\epsfig{file=out,width=8in,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 -- 1.7.10.4