From 25cc5d4e56f230027a465c0cb195af740ec3a87d Mon Sep 17 00:00:00 2001 From: adam Date: Fri, 7 Nov 2008 14:41:20 -0800 Subject: [PATCH] 20-sep darcs-hash:20081107224120-5007d-4211a3a0c2d3d029bad391b322a2e74437b874df.gz --- am33.tex | 117 ++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 83 insertions(+), 34 deletions(-) diff --git a/am33.tex b/am33.tex index 0486704..ab6960d 100644 --- a/am33.tex +++ b/am33.tex @@ -66,8 +66,11 @@ Adam Megacz Changes: \begin{tabular}{rl} -27-Aug -& \color{red} Note that decision to requeue is based on value of OLC {\it before} execution\\ +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) \\ @@ -261,20 +264,22 @@ The diagram below shows an input dock for purposes of illustration: {\it an input dock} \end{center} -Note the mux on the path between {\tt EF} (epilogue fifo) and {\tt IF} -(instruction 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 set} instruction, or the occurrence - of a torpedo}). - -When an instruction arrives at the epilogue fifo ({\tt EF}), 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'' ({\tt OD}) stage, -where it may execute. +%\subsection{The Hatch} +% +%\color{red} +% +%Note the mux on the path between {\tt EF} (epilogue fifo) and {\tt IF} +%(instruction fifo); this is known as ``the hatch''. The exact +%behavior of the hatch is documented in +%\href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50}; +%a summary of its behavior is included below. +% +%When an instruction arrives at the epilogue fifo ({\tt EF}), 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'' ({\tt OD}) stage, +%where it may execute. +\color{black} \begin{center} \epsfig{file=out,width=4in}\\ @@ -403,37 +408,80 @@ Code & Execute & if \\\hline \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}. + +\item No contiguous sequence of requeueable instructions is longer + than the length of the instruction fifo. + +\item If a requeueable instruction is preceded by a one-shot + instruction or a {\tt tail}, then it must be the case that {\tt + OLC>0} both before and after the first time that instruction + executes. + +\item If {\tt OLC=0}, only a one-shot instruction may set it to a + nonzero value. + +\end{itemize} + +The dock guarantees that: + +\begin{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. + +\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 OLC=0}. + +\end{itemize} + + +\color{black} \subsection{On Deck} When an instruction arrives on deck, two concurrent processes are -started. No subsequent instruction may come on deck until both -processes have completed: - +started: \begin{enumerate} - \item Requeueing: \begin{itemize} - \item If the outer loop counter is zero ({\tt OLC=0}) - \color{red}{\it before executing the - instruction}\color{black}\ or the instruction on deck is a - one-shot instruction ({\tt OS=1}), do nothing. - \item {\it Otherwise} wait for the hatch to be sealed and - enqueue a copy of the instruction currently on deck. + \item If the instruction on deck is a requeueable instruction + ({\tt OS=1}) and the outer loop counter is nonzero ({\tt + OLC>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}) + {\it Otherwise} if the instruction is interruptible ({\tt I=1}) and a torpedo is present in the waiting area: consume the - torpedo, set the outer loop counter to zero ({\tt OLC=0}), - set the inner loop counter to one ({\tt ILC=1}), - unseal the hatch. + torpedo, set the outer loop counter to zero ({\tt OLC=0}) and + set the inner loop counter to one ({\tt ILC=1}). \item {\it Otherwise} if {\tt ILC$\neq$0} or the instruction is {\it @@ -456,7 +504,7 @@ The dock supports four instructions: \color{black} -\subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})} +\subsection{{\tt move}} \newcommand{\bitsMove}{\setlength{\bitwidth}{5mm} {\tt @@ -734,8 +782,9 @@ the instruction executes. \end{bytefield}}} \bitsTail -When a {\tt tail} instruction reaches the hatch, it seals the hatch. -The {\tt tail} instruction does not enter the instruction fifo. +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. \color{black} %\pagebreak -- 1.7.10.4