1 \documentclass[10pt]{article}
5 \usepackage[figureright]{rotating}
8 \usepackage{bytefield1}
11 \usepackage{subfigure}
20 \bibliographystyle{alpha}
21 \pagestyle{fancyplain}
23 \definecolor{light}{gray}{0.7}
25 \setlength{\marginparwidth}{1.2in}
26 \let\oldmarginpar\marginpar
27 \renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize #1]%
28 {\raggedright\footnotesize #1}}
31 \newcommand{\footnoteremember}[2]{
34 \setcounter{#1}{\value{footnote}}
35 } \newcommand{\footnoterecall}[1]{
36 \footnotemark[\value{#1}]
44 %\oddsidemargin 0.25in
45 %\evensidemargin 0.25in
47 \def\to{\ $\rightarrow$\ }
57 \title{\vspace{-1cm}AM33: The Marina Docks
69 This document describes the Docks on the Marina test chip.
77 %& Added errata for Kessels counter on Marina test chip \\
79 %& Added errata for Marina test chip \\
81 %& Clarified setting of the {\tt C}-flag\color{black}\\
82 %& Removed {\tt OS} bit\color{black}\\
83 %& Changed instruction length from 26 bits to 25\color{black}\\
84 %& Updated which bits are used when the {\tt Path} latch captures from the data predecessor\color{black}\\
86 %& Fixed a one-word typo \\
88 %& Added {\tt head} instruction \\
89 %& Lengthened external encoding of {\tt tail} instruction by one bit \\
90 %& Added {\tt abort} instruction \\
91 %& Removed {\tt OS} field from instructions \\
92 %& Renamed the {\tt Z}-flag (olc {\bf Z}ero) to the {\tt D}-flag (loop {\bf D}one)\\
94 %& Updated diagram in section 3 to put dispatch path near MSB\\
95 %& Changed DP[37:25] to DP[37:27]\\
96 %& Added note on page 4 regarding previous\\
98 %& Roll back ``Distinguish {\tt Z}-flag from OLC=0'' \\
99 %& Clarify what ``{\tt X-Extended}'' means \\
100 %& Change C-bit source selector from {\tt Di} to {\tt Dc} \\
102 %& Distinguish {\tt Z}-flag from OLC=0\\
103 %& Add {\tt flush} instruction\\
104 %& Change {\t I} bit from ``Interruptable'' to ``Immune''\\
106 %& Update hatch description to match \href{http://fleet.cs.berkeley.edu/docs/people/ivan.e.sutherland/ies50-Requeue.State.Diagram.pdf}{IES50} \\
108 %& Note that decision to requeue is based on value of OLC {\it before} execution\\
109 %& Note that decision to open the hatch is based on value of {\tt OS} bit\\
111 %& Added {\tt OLC=0} predicate \\
112 %& Eliminated {\tt TAPL} (made possible by previous change) \\
113 %& Expanded {\tt set} {\tt Immediate} field from 13 bits to 14 bits (made possible by previous change)\\
115 %& Fixed a few typos \\
116 %& Added {\tt DataLatch}\to{\tt TAPL} (Amir's request) \\
117 %& Eliminate ability to predicate directly on {\tt C}-flag (Ivan's request) \\
119 %& When a torpedo strikes, {\tt ILC} is set to {\tt 1} \\
120 %& Only {\tt move} can be torpedoed (removed {\tt I}-bit from {\tt set}/{\tt shift}) \\
122 %& Changed all uses of ``Payload'' to ``Immediate'' \color{black} (not in red) \\
123 %& Reworked encoding of {\tt set} instruction \\
126 %& Factored in Russell Kao's comments (thanks!)\\
127 %& Added mechanism for setting C-flag from fabric even on outboxes\\
129 %& Made {\tt OLC} test a predicate-controlled condition\\
130 %& Rewrote ``on deck'' section \\
131 %& Added ``{\tt unset}'' value for {\tt ILC}\\
132 %& Changed {\tt DP} to {\tt DataPredecessor} for clarity\\
135 %& added comment about address-to-path ship \\
136 %& changed {\tt DST} field of {\tt set} instruction from 2 bits to 3 \\
137 %& changed the order of instructions in the encoding map \\
139 %& added epilogue fifo to diagrams \\
140 %& indicated that a token sent to the instruction port is treated as a torpedo \\
142 %& replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
143 %& replaced {\tt literal} with {\tt shift} instruction \\
145 %& Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
146 %& Removed ability to manually set the {\tt C} flag \\
147 %& Expanded predicate field to three bits \\
148 %& New literals scheme (via shifting) \\
149 %& Instruction encoding changes made at Ivan's request (for layout purposes) \\
150 %& Added summary of instruction encodings on last page \\
152 %& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
154 %& extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
155 %& update table 3.1.2 \\
156 %& rename {\tt S} flag to {\tt C} \\
157 %& noted that {\tt setFlags} can be used as {\tt nop} \\
159 %& removed the {\tt L} flag (epilogues can now do this) \\
160 %& removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
161 %& renamed {\tt data} instruction to {\tt literal} \\
162 %& renamed {\tt send} instruction to {\tt move} \\
164 %& added ``if its predicate is true'' to repeat count \\
165 %& added note that red wires do not contact ships \\
166 %& changed name of {\tt flags} instruction to {\tt setFlags} \\
167 %& removed black dot from diagrams \\
168 %& changed {\tt OL} (Outer Loop participant) to {\tt OS} (One Shot) and inverted polarity \\
169 %& indicated that the death of the {\tt tail} instruction is what causes the hatch to be unsealed \\
170 %& indicated that only {\tt send} instructions which wait for data are torpedoable \\
171 %& added section ``Torpedo Details'' \\
172 %& removed {\tt torpedo} instruction \\
175 %& renamed loop+repeat to outer+inner (not in red) \\
176 %& renamed {\tt Z} flag to {\tt L} flag (not in red) \\
177 %& rewrote ``inner and outer loops'' section \\
178 %& updated all diagrams \\
181 %& Moved address bits to the LSB-side of a 37-bit instruction \\
182 %& Added {\it micro-instruction} and {\it composite instruction} terms \\
183 %& Removed the {\tt DL} field, added {\tt decrement} mode to {\tt loop} \\
184 %& Created the {\tt Hold} field \\
185 %& Changed how ReLooping works \\
186 %& Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
193 \epsfig{file=all,height=1.5in}
194 \epsfig{file=overview-new,height=1.5in}
199 \section{Overview of Fleet}
201 A Fleet processor is organized around a {\it switch fabric}, which is
202 a packet-switched network with reliable in-order delivery. The switch
203 fabric is used to carry data between different functional units,
204 called {\it ships}. Each ship is connected to the switch fabric by
205 one or more programmable elements known as {\it docks}.
207 A {\it path} specifies a route through the switch fabric from a
208 particular {\it source} to a particular {\it destination}. The
209 combination of a path and a single word to be delivered is called a
210 {\it packet}. The switch fabric carries packets from their sources to
211 their destinations. Each dock has two destinations: one for {\it
212 instructions} and one for {\it data}. A Fleet is programmed by
213 depositing instruction packets into the switch fabric with paths that
214 will lead them to the instruction destinations of the docks at which they
217 When a packet arrives at the instruction destination of a dock, it is
218 enqueued for execution. Before the instruction executes, it may cause
219 the dock to wait for a packet to arrive at the dock's data destination
220 or for a value to be presented by the ship. When an instruction
221 executes it may consume this data and may present a data value to the
222 ship or transmit a packet.
224 When an instruction sends a packet into the switch fabric, it may
225 specify that the payload of the packet is irrelevant. Such packets
226 are known as {\it tokens}, and consume less energy than data packets.
230 \epsfig{file=overview-new,width=2.5in}\\
231 {\it Overview of a Fleet processor; dark gray shading represents the
232 switch fabric, ships are shown in light gray, and docks are shown in blue.}
238 \section{The Marina Dock}
240 The diagram below represents a conceptual view of the interface
241 between ships and the switch fabric; actual implementation circuitry
245 \epsfig{file=all,width=3.5in}\\
246 {\it An ``input'' dock and ``output'' dock connected to a ship. Solid
247 blue lines carry either tokens or data words, red lines carry either
248 instructions or torpedoes, and dashed lines carry only tokens.}
251 Each dock consists of a {\it data latch}, which is as wide as a single
252 machine word and a circular {\it instruction fifo} of
253 instruction-width latches. The values in the instruction fifo control
254 the data latch. The dock also includes a {\it path latch}, which
255 stores the path along which outgoing packets will be
258 Note that the instruction fifo in each dock has a destination of its
259 own; this is the {\it instruction destination} mentioned in the
260 previous section. A token sent to an instruction destination is
261 called a {\it torpedo}; it does not enter the instruction fifo, but
262 rather is held in a waiting area where it may interrupt certain
263 instructions (see the section on the {\tt move} instruction for further
266 From any source to any dock's data destination there are
267 two distinct paths which differ by a single bit. This bit is known as
268 the ``signal'' bit, and the routing of a packet is not affected by it;
269 the signal bit is used to pass control values between docks. Note that paths
270 terminating at an {\it instruction} destination need not have a signal
274 \section{Instructions}
276 In order to cause an instruction to execute, the programmer must first
277 arrange for that instruction word to arrive in the data latch of some
278 output dock. For example, this might be the ``data read'' output dock
279 of the memory access ship or the output of a fifo ship. Once an
280 instruction has arrived at this output dock, it is {\it dispatched} by
281 sending it to the {\it instruction destination} of the dock at which
284 There are two instruction formats, an {\it external format} described
285 in this section and an {\it internal format} described in the last
286 section of this memo.
288 Each instruction is 25\color{black}\ bits long, which makes it
289 possible for an instruction and an 12\color{black}-bit path to fit in
290 a single word of memory. This path is the path from the {\it
291 dispatching} dock to the {\it executing} dock.
295 \setlength{\bitwidth}{3.5mm}
297 \begin{bytefield}{37}
298 \bitheader[b]{0,24,25,36}\\
299 \bitbox{12}{dispatch path}
300 \bitbox{25}{instruction (external format)}
304 Note that the 12\color{black}\ bit {\tt dispatch path} field is not
305 the same width as the 13 bit {\tt Immediate} path field in the {\tt
306 move} instruction, which in turn may not be the same width as the
307 actual path latches in the switch fabric. The algorithm for expanding
308 a path to a wider width is specific to the switch fabric
309 implementation, and may vary from Fleet to Fleet. For the Marina
310 experiment, the correct algorithm is to sign-extend the path; the most
311 significant bit of the given path is used to fill the vacant bit of
312 the latch. Because the {\tt dispatch path} field is always used to
313 specify a path which terminates at an instruction destination (never a
314 data destination), and because instruction destinations ignore the
315 signal bit, certain optimizations may be possible.
317 %\subsection{Life Cycle of an Instruction}
319 %The diagram below shows an input dock for purposes of illustration:
322 %\epsfig{file=in,width=4in}\\
329 %\epsfig{file=out,width=4in}\\
330 %{\it an output dock}
333 %\subsection{Format of an Instruction}
335 %All instruction words have the following format:
337 \newcommand{\bitsHeader}{
341 \newcommand{\bitsHeaderNoI}{
347 %The {\tt P} bits are a {\it predicate}; this holds a code which
348 %indicates if the instruction should be executed or ignored depending
349 %on the state of flags in the dock. Note that {\tt head} and {\tt
350 %tail} instructions do not have {\tt P} fields.
353 \subsection{Loop Counters}
355 A programmer can perform two types of loops: {\it inner} loops
356 consisting of only one {\tt move} instruction and {\it outer} loops of
357 multiple instructions of any type. Inner loops may be nested within
358 an outer loop, but no other nesting of loops is allowed.
360 The dock has two loop counters, one for each kind of loop:
363 \item {\tt OLC} is the Outer Loop Counter
364 \item {\tt ILC} is the Inner Loop Counter
367 The {\tt OLC} applies to all instructions and can hold integers {\tt
370 The {\tt ILC} applies only to {\tt move} instructions and can hold
371 integers {\tt 0..MAX_ILC} (63) as well as a special value: $\infty$. When
372 {\tt ILC=0} the next {\tt move} instruction executes zero times (ie is
373 ignored). When {\tt ILC=$\infty$} the next {\tt move} instruction
374 executes until interrupted by a torpedo. After every {\tt move}
375 instruction the {\tt ILC} is reset to {\tt 1} (note that it is reset
376 to {\tt 1}, {\it not to 0}).
381 The dock has four flags: {\tt A}, {\tt B},
382 {\tt C}, and {\tt D}.
385 \item The {\tt A} and {\tt B} flags are general-purpose flags which
386 may be set and cleared by the programmer.
390 % The {\tt L} flag, known as the {\it last} flag, is set whenever
391 % the value in the outer counter ({\tt OLC}) is one,
394 % that the dock is in the midst of the last iteration of an
395 % outer loop. This flag can be used to perform certain
396 % operations (such as sending a completion token) only on the last
397 % iteration of an outer loop.
399 \item The {\tt C} flag is known as the {\it control} flag, and may be
400 set by the {\tt move} instruction based on information from the
401 ship or from an inbound packet. See the {\tt move} instruction
404 \item The {\tt D} flag is known as the {\it done} flag. The {\tt D}
405 flag is {\it set} when the {\tt OLC} is zero immediately after
406 execution of a {\tt set olc} or {\tt decrement olc} instruction,
407 or when a torpedo strikes. The {\tt D} flag is {\it cleared}
408 when a {\tt set olc} instruction causes the {\tt OLC} to be
409 loaded with a nonzero value.
415 \subsection{Predication}
417 All instructions except for {\tt head} and {\tt tail} have a three-bit
418 field marked {\tt P}, which specifies a {\it predicate}.
421 \setlength{\bitwidth}{5mm}
423 \begin{bytefield}{25}
424 \bitheader[b]{0,20,21,23-24}\\
431 The predicate determines which conditions must be true in order for
432 the instruction to execute; if it is not executed, it is simply {\it
433 ignored}. The table below shows what conditions must be true in
434 order for an instruction to execute:
437 \begin{tabular}{|r|l|}\hline
438 Code & Execute if \\\hline
439 {\tt 000:} & {\tt D=0}\ and {\tt A=0} \\
440 {\tt 001:} & {\tt D=0}\ and {\tt A=1} \\
441 {\tt 010:} & {\tt D=0}\ and {\tt B=0} \\
442 {\tt 011:} & {\tt D=0}\ and {\tt B=1} \\
443 {\tt 100:} & Unused \\
444 {\tt 101:} & {\tt D=1}\ \\
445 {\tt 110:} & {\tt D=0}\ \\
446 {\tt 111:} & always \\
452 \begin{wrapfigure}{r}{40mm}
454 \epsfig{file=requeue,height=1.5in}\\
456 \caption{{\it the requeue stage}}
459 \subsection{The Requeue Stage}
461 The requeue stage has two inputs, which will be referred to as the
462 {\it enqueueing} input and the {\it recirculating} input. It has a
463 single output which feeds into the instruction fifo.
465 The requeue stage has two states: {\sc Updating} and {\sc
468 \subsubsection{The {\sc Updating} State}
470 On initialization, the dock is in the {\sc Updating} state. In this
471 state the requeue stage is performing three tasks:
473 \item it is draining the
474 previous loop's instructions (if any) from the fifo
475 \item it is executing any ``one
476 shot'' instructions which come between the previous loop's {\tt tail}
477 and the next loop's {\tt head}
478 \item it is loading the instructions of
479 the next loop into the fifo.
482 In the {\sc Updating} state, the requeue stage will accept any
483 instruction other than a {\tt tail} which arrives at its {\it
484 enqueueing} input, and pass this instruction to its output. Any
485 instruction other than a {\tt head} which arrives at the {\it
486 recirculating} input will be discarded.
488 Note that when a {\tt tail} instruction arrives at the {\it
489 enqueueing} input, it ``gets stuck'' there. Likewise, when a {\tt
490 head} instruction arrives at the {\it recirculating} input, it also
491 ``gets stuck''. When the requeue stage finds {\it both} a {\tt tail}
492 instruction stuck at the {\it enqueueing} input and a {\tt head}
493 instruction stuck at the {\it recirculating} input, the requeue stage
494 discards both the {\tt head} and {\tt tail} and transitions to the
495 {\sc Circulating} state.
497 \subsubsection{The {\sc Circulating} State}
499 In the {\sc Circulating} state, the dock repeatedly executes the set
500 of instructions that are in the instruction fifo.
502 In the {\sc Circulating} state, the requeue stage will not accept
503 items from its {\it enqueueing} input. Any item presented at the {\it
504 recirculating} input will be passed through to the requeue stage's
507 When an {\tt abort} instruction is executed, the requeue stage
508 transitions back to the {\sc Updating} state. Note that {\tt abort}
509 instructions include a predicate; an {\tt abort} instruction whose
510 predicate is not met will not cause this transition.
516 \section{Instructions}
518 %The dock supports four instructions:
519 %{\tt move} (variants: {\tt moveto}, {\tt dispatch}),
526 \subsection{{\tt move}}
528 \newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
530 \begin{bytefield}{25}
531 \bitheader[b]{14-20}\\
545 \begin{bytefield}{25}
546 \bitheader[b]{0,12,13}\\
547 \bitbox[1]{10}{\raggedleft {\tt moveto} ({\tt Immediate\to Path})}
550 \bitbox{13}{\tt Immediate}
553 \begin{bytefield}{25}
554 \bitheader[b]{11,12,13}\\
555 \bitbox[1]{10}{\raggedleft {\tt dispatch} ({\footnotesize {\tt DataPredecessor[37:26\color{black}]\to Path}})\ \ }
564 \begin{bytefield}{25}
565 \bitheader[b]{11,12,13}\\
566 \bitbox[1]{10}{\raggedleft {\tt move} ({\tt Path} unchanged):}
577 \item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
578 \item {\tt Di} - Data Input: wait for the data predecessor to be full and drain it.
579 \item {\tt Dc} - Data Capture: pulse the data latch.
580 \item {\tt Do} - Data Output: fill the data successor.
581 \item {\tt To} - Token Output: fill the token successor.
584 The data successor and token successor must both be empty in order for
585 a {\tt move} instruction to attempt execution.
587 The {\tt I} bit stands for {\tt Immune}, and indicates if the
588 instruction is immune to torpedoes.
590 Every time the {\tt move} instruction executes, the {\tt C} flag is
594 \item If the dock is an {\it output} and the instruction has the {\tt
595 Dc} bit set, the {\tt C} flag is set to a value provided by the
598 \item Otherwise, if {\tt Ti=1} at any kind of dock or {\tt Di=1} at an
599 input dock, the {\tt C} flag is set to the signal bit of the
602 \item Otherwise, the signal bit is set to an undefined value.
607 The {\tt flush} instruction is a variant of {\tt move} which is valid
608 only at input docks. It has the same effect as {\tt deliver}, except
609 that it sets a special ``flushing'' indicator along with the data
612 \newcommand{\bitsFlush}{\setlength{\bitwidth}{5mm}
614 \begin{bytefield}{25}
615 \bitheader[b]{14-18}\\
616 \bitbox[r]{6}{\raggedleft{\tt flush\ \ }}
628 When a ship fires, it must examine the ``flushing'' indicators on the
629 input docks whose fullness was part of the firing condition. If all
630 of the input docks' flushing indicators are set, the ship must drain
631 all of their data successors and take no action. If some, but not
632 all, of the indicators are set, the ship must drain {\it only the data
633 successors of the docks whose indicators were {\bf not} set}, and
634 take no action. If none of the flushing indicators was set, the ship
641 \subsection{{\tt set}}
643 The {\tt set} command is used to set or decrement the inner loop
644 counter, outer loop counter, and data latch.
646 \newcommand{\bitsSet}{
648 \begin{bytefield}{25}
649 \bitheader[b]{19-24}\\
660 \begin{bytefield}{25}
661 \bitheader[b]{0,5,12-18}\\
662 \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt OLC}}
664 \bitbox{4}{\tt 1000\color{black}}
667 \bitbox{6}{\tt Immediate}
670 \begin{bytefield}{25}
671 \bitheader[b]{12-18}\\
672 \bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt OLC}}
674 \bitbox{4}{\tt 1000\color{black}}
679 \begin{bytefield}{25}
680 \bitheader[b]{12-18}\\
681 \bitbox[1]{6}{\raggedleft {\tt OLC-1}\to{\tt OLC}}
683 \bitbox{4}{\tt 1000\color{black}}
688 \begin{bytefield}{25}
689 \bitheader[b]{0,5,6,12-18}\\
690 \bitbox[1]{6}{\raggedleft {\tt Immediate}\to{\tt ILC}}
692 \bitbox{4}{\tt 0100\color{black}}
696 \bitbox{6}{\tt Immediate}
699 \begin{bytefield}{25}
700 \bitheader[b]{6,12-18}\\
701 \bitbox[1]{6}{\raggedleft $\infty$\to{\tt ILC}}
703 \bitbox{4}{\tt 0100\color{black}}
710 \begin{bytefield}{25}
711 \bitheader[b]{12-18}\\
712 \bitbox[1]{6}{\raggedleft {\tt Data Latch}\to{\tt ILC}}
714 \bitbox{4}{\tt 0100\color{black}}
719 \begin{bytefield}{25}
720 \bitheader[b]{0,13-18}\\
721 \bitbox[1]{6}{\raggedleft \footnotesize {\tt Sign-Extended Immediate}\to{\tt Data Latch}}
723 \bitbox{4}{\tt 0010\color{black}}
724 \bitbox{1}{\begin{minipage}{0.5cm}{
731 \bitbox{14}{\tt Immediate}
734 \begin{bytefield}{25}
735 \bitheader[b]{0,5,6,11,15-18}\\
736 \bitbox[1]{6}{\raggedleft {\tt Update Flags}}
738 \bitbox{4}{\tt 0001\color{black}}
740 \bitbox{6}{\tt nextA}
741 \bitbox{6}{\tt nextB}
747 The Marina implementation has an unarchitected
748 ``literal latch'' at the on deck ({\tt OD}) stage, which is loaded
749 with the possibly-extended literal {\it at the time that the {\tt set}
750 instruction comes on deck}. This latch is then copied into the data
751 latch when a {\tt set Data Latch} instruction
754 The {\tt Sign-Extended Immediate} instruction copies the {\tt
755 Immediate} field into the least significant bits of the data latch.
756 All other bits of the data latch are filled with a copy of the
757 bit marked ``{\tt Sign}.''
760 Each of the {\tt nextA} and {\tt nextB} fields has the following
761 structure, and indicates which old flag values should be logically
762 {\tt OR}ed together to produce the new flag value:
768 \bitbox{1}{${\text{\tt A}}$}
769 \bitbox{1}{$\overline{\text{\tt A}}$}
770 \bitbox{1}{${\text{\tt B}}$}
771 \bitbox{1}{$\overline{\text{\tt B}}$}
772 \bitbox{1}{${\text{{\tt C}\ }}$}
773 \bitbox{1}{$\overline{\text{{\tt C}\ }}$}
777 Each bit corresponds to one possible input; all inputs whose bits are
778 set are {\tt OR}ed together, and the resulting value is assigned to
779 the flag. Note that if none of the bits are set, the value assigned
780 is zero. Note also that it is possible to produce a {\tt 1} by {\tt
781 OR}ing any flag with its complement, and that {\tt set Flags} can
782 be used to create a {\tt nop} (no-op) by setting each flag to itself.
788 \subsection{{\tt shift}}
790 \newcommand{\shiftImmediateSize}{19}
792 Each {\tt shift} instruction carries an immediate of \shiftImmediateSize\
793 bits. When a {\tt shift} instruction is executed, this immediate is copied
794 into the least significant \shiftImmediateSize\ bits of the data latch,
795 and the remaining most significant bits of the data latch are loaded
796 with the value formerly in the least significant bits of the data latch.
797 In this manner, large literals can be built up by ``shifting'' them
798 into the data latch \shiftImmediateSize\ bits at a time.
800 \newcommand{\bitsShift}{
801 \setlength{\bitwidth}{5mm}
803 \begin{bytefield}{25}
804 \bitheader[b]{0,18-20}\\
811 \bitbox{\shiftImmediateSize}{Immediate}
816 The Marina implementation has an unarchitected
817 ``literal latch'' at the on deck ({\tt OD}) stage, which is loaded
818 with the literal {\it at the time that the {\tt shift} instruction
819 comes on deck}. This latch is then copied into the data latch when
820 the instruction executes.
824 \subsection{{\tt abort}}
825 \newcommand{\bitsAbort}{\setlength{\bitwidth}{5mm}
827 \begin{bytefield}{25}
828 \bitheader[b]{17-20}\\
841 An {\tt abort} instruction causes a loop to exit; see the section on
842 the Requeue Stage for further details.
844 \subsection{{\tt head}}
845 \newcommand{\bitsHead}{
846 \setlength{\bitwidth}{5mm}
848 \begin{bytefield}{25}
849 \bitheader[b]{17-20}\\
862 A {\tt head} instruction marks the start of a loop; see the section on
863 the Requeue Stage for further details.
866 \subsection{{\tt tail}}
867 \newcommand{\bitsTail}{
868 \setlength{\bitwidth}{5mm}
870 \begin{bytefield}{25}
871 \bitheader[b]{17-20}\\
884 A {\tt tail} instruction marks the end of a loop; see the section on
885 the Requeue Stage for further details.
889 %\subsection{{\tt takeOuterLoopCounter}}
891 %\setlength{\bitwidth}{5mm}
893 %\begin{bytefield}{25}
894 % \bitheader[b]{16-19,21}\\
908 %This instruction copies the value in the outer loop counter {\tt OLC}
909 %into the least significant bits of the data latch and leaves all other
910 %bits of the data latch unchanged.
912 %\subsection{{\tt takeInnerLoopCounter}}
914 %\setlength{\bitwidth}{5mm}
916 %\begin{bytefield}{25}
917 % \bitheader[b]{16-19,21}\\
931 %This instruction copies the value in the inner loop counter {\tt ILC}
932 %into the least significant bits of the data latch and leaves all other
933 %bits of the data latch unchanged.
938 %%\subsection{{\tt interrupt}}
940 %%\setlength{\bitwidth}{5mm}
942 %\begin{bytefield}{25}
943 % \bitheader[b]{0,5,16-19,21}\\
954 %When an {\tt interrupt} instruction reaches {\tt IH}, it will wait
955 %there for the {\tt OD} stage to be full with an instruction that has
956 %the {\tt IM} bit set. When this occurs, the instruction at {\tt OD}
957 %{\it will not execute}, but {\it may reloop} if the conditions for
959 %\footnote{The ability to interrupt an instruction yet have it reloop is very
960 %useful for processing chunks of data with a fixed size header and/or
961 %footer and a variable length body.}
964 %\subsection{{\tt massacre}}
966 %\setlength{\bitwidth}{5mm}
968 %\begin{bytefield}{25}
969 % \bitheader[b]{16-19,21}\\
981 %When a {\tt massacre} instruction reaches {\tt IH}, it will wait there
982 %for the {\tt OD} stage to be full with an instruction that has the
983 %{\tt IM} bit set. When this occurs, all instructions in the
984 %instruction fifo (including {\tt OD}) are retired.
986 %\subsection{{\tt clog}}
988 %\setlength{\bitwidth}{5mm}
990 %\begin{bytefield}{25}
991 % \bitheader[b]{16-19,21}\\
1003 %When a {\tt clog} instruction reaches {\tt OD}, it remains there and
1004 %no more instructions will be executed until an {\tt unclog} is
1007 %\subsection{{\tt unclog}}
1009 %\setlength{\bitwidth}{5mm}
1011 %\begin{bytefield}{25}
1012 % \bitheader[b]{16-19,21}\\
1018 % \bitbox[lrtb]{2}{11}
1020 % \bitbox[tbr]{16}{}
1024 %When an {\tt unclog} instruction reaches {\tt IH}, it will wait there
1025 %until a {\tt clog} instruction is at {\tt OD}. When this occurs, both
1026 %instructions retire.
1028 %Note that issuing an {\tt unclog} instruction to a dock which is not
1029 %clogged and whose instruction fifo contains no {\tt clog} instructions
1030 %will cause the dock to deadlock.
1035 The following additional restrictions have been imposed on the dock in
1036 the Marina test chip:
1038 \subsection*{Both Docks}
1043 A Marina dock initializes with the {\tt ILC}, {\tt OLC}, and flags in
1044 an indeterminate state.
1047 The instruction immediately after a {\tt move} instruction must not be
1048 a {\tt set flags} instruction which utilizes the {\tt C}-flag (the
1049 value of the {\tt C}-flag is not stable for a brief time after a {\tt
1053 If a {\tt move} instruction is torpedoable (ie it has the {\tt I} bit
1054 set to {\tt 0}), it {\it must} have either the {\tt Ti} bit or {\tt
1055 Di} bit set (or both). It is not permitted for a torpedoable {\tt
1056 move} to have both bits cleared.
1061 \subsection*{Dock with Ivan's Counter (non-stretch)}
1067 A torpedoable {\tt move} instruction must not be followed immediately
1068 by a {\tt set olc} instruction or another torpedoable {\tt move}.
1072 This document specifies that when a torpedoable {\tt move} instruction
1073 executes successfully, the {\tt D} flag is unchanged. In Marina, when
1074 a torpedoable {\tt move} instruction executes successfully, it causes
1075 the {\tt D} flag to be set if the {\tt OLC} was zero and causes it to
1076 be cleared if the {\tt OLC} was nonzero. Thus, in the following
1077 instruction sequence:
1082 send token to self:i;
1084 [*] send token to self;
1090 Will leave the {\tt D} flag {\it set} on Marina, whereas a strict
1091 implementation of this document would leave it cleared.
1093 In practice, this distinction rarely matters.
1097 \subsection*{Dock with Kessels Counter (``stretch'')}
1099 With the Kessels counter, the {\tt D}-flag {\it is exactly equal to}
1100 the zeroness of the {\tt OLC}; it cannot be ``out of sync'' with it.
1105 Every ``load OLC'' instruction must be predicated on the {\tt D}-flag
1106 being {\it set}. This is a sneaky way of forcing the programmer to
1107 ``run down'' the counter before loading it, because Kessels' counter
1108 does not support ``unloading.''
1111 Every ``decrement OLC'' instruction must be predicated on the {\tt
1112 D}-flag being {\it cleared}. This way we never have to check if the
1113 counter is already empty before decrementing.
1116 The instruction after a torpedoable {\tt move} must not be predicated
1117 on the {\tt D}-flag being {\it set} (it may be predicated on the {\tt
1118 D}-flag being {\it cleared}. This is because, while the move
1119 instruction is waiting to execute, the {\tt D}-flag will be cleared,
1120 and the predicate stage believes that it can skip the instruction even
1121 though {\tt do[ins]} is still high (I think this is dumb).
1129 \section*{External Instruction Encoding Map\color{black}}
1132 \vspace{3mm}\hspace{-1cm}{\tt shift}\hspace{1cm}\vspace{-6mm}\\
1135 \vspace{3mm}\hspace{-1cm}{\tt set}\hspace{1cm}\vspace{-6mm}\\
1138 \vspace{3mm}\hspace{-1cm}{\tt move}\hspace{1cm}\vspace{-6mm}\\
1142 \vspace{3mm}\hspace{-1cm}{\tt abort}\hspace{1cm}\vspace{-6mm}\\
1145 \vspace{3mm}\hspace{-1cm}{\tt head}\hspace{1cm}\vspace{-6mm}\\
1148 \vspace{3mm}\hspace{-1cm}{\tt tail}\hspace{1cm}\vspace{-6mm}\\
1153 %\epsfig{file=all,height=5in,angle=90}
1156 %\subsection*{Input Dock}
1157 %\epsfig{file=in,width=8in,angle=90}
1160 %\subsection*{Output Dock}
1161 %\epsfig{file=out,width=8in,angle=90}
1165 %\epsfig{file=ports,height=5in,angle=90}
1168 %\epsfig{file=best,height=5in,angle=90}
1171 \section*{Internal Instruction Encoding Map\color{black}}
1173 Marina Instructions in main memory occupy 37 bits. Of this, 11 bits
1174 give the path to the dock which is to execute the instruction; thus,
1175 only 26 of these bits are interpreted by the dock.
1177 It is easiest to design the OD and EX stages of the dock if the
1178 control bits supplied there are mostly one-hot encoded. Moreover, due
1179 to layout considerations there is very little cost associated with
1180 making the instruction fifo 36 bits wide rather than 26 bits wide.
1182 Due to these two considerations, all 26-bit instructions
1183 binary-coded-control instructions are expanded into 36-bit
1184 unary-coded-control instructions upon entry to the instruction fifo.
1185 This section documents the 36-bit unary-coded-control format.
1187 \subsection*{Predicate Field}
1189 The {\tt Predicate} field, common to many instructions, consists of a
1190 six-bit wide, one-hot encoded field. The instruction will be {\bf
1191 skipped} (not executed) if {\bf any} condition corresponding to a
1192 bit whose value is one is met.
1194 \setlength{\bitwidth}{3.5mm}
1195 {\footnotesize\tt\begin{bytefield}{36}
1196 \bitheader[b]{0,29-35}\\
1208 For example, if bits 31 and 34 are set, the instruction will be
1209 skipped if either the {\tt B} flag is cleared or the {\tt A} flag is
1210 set. Equivalently, it will be executed iff the {\tt B} flag is set
1211 and the {\tt A} flag is cleared.
1213 \subsection*{Set Flags}
1215 Each of the {\tt FlagA} and {\tt FlagB} fields in the Set Flags
1216 instruction gives a truth table; the new value of the flag is the
1217 logical OR of the inputs whose bits are set to {\tt 1}.
1219 \setlength{\bitwidth}{5mm}
1220 {\tt\begin{bytefield}{6}
1221 \bitheader[b]{0-5}\\
1231 \newcommand{\common}{%
1232 \bitbox{6}{Predicate}%
1241 \oddsidemargin 0.9in
1244 \begin{sidewaysfigure}[h!]
1247 \setlength{\bitwidth}{5mm}
1251 {\tt\begin{bytefield}{36}
1252 \bitheader[b]{0,18,19,21-30,35}\\
1267 \bitbox{19}{immediate}
1270 {\tt\begin{bytefield}{36}
1271 \bitheader[b]{0,13,14,15,21-30,35}\\
1290 \bitbox{14}{immediate to sign ext}
1291 \end{bytefield}} \\\hline
1293 Move, Immediate$\rightarrow$Path &
1294 {\tt\begin{bytefield}{36}
1295 \bitheader[b]{0,13,14-20,21-30,35}\\
1318 \bitbox{13}{Immediate}
1320 Move, DP[37:26]$\rightarrow$Path &
1321 {\tt\begin{bytefield}{36}
1322 \bitheader[b]{0,12-13,14-20,21-30,35}\\
1349 Move, Path unchanged &
1350 {\tt\begin{bytefield}{36}
1351 \bitheader[b]{0,11-13,14-20,21-30,35}\\
1375 \bitbox{1}{F$\dagger$}
1383 {\tt\begin{bytefield}{36}
1384 \bitheader[b]{0,11,12,21-30,35}\\
1400 \end{bytefield}} \\\hline
1403 {\tt\begin{bytefield}{36}
1404 \bitheader[b]{0,20-30,35}\\
1423 {\tt\begin{bytefield}{36}
1424 \bitheader[b]{0,19-30,35}\\
1446 {\tt\begin{bytefield}{36}
1447 \bitheader[b]{0,5,19-30,35}\\
1467 \bitbox{6}{Immediate}
1468 \end{bytefield}} \\\hline
1471 {\tt\begin{bytefield}{36}
1472 \bitheader[b]{0,19,21-30,35}\\
1492 {\tt\begin{bytefield}{36}
1493 \bitheader[b]{0,5,7,19,21-30,35}\\
1513 \bitbox{1}{0${}^\star$}
1517 \bitbox{6}{Immediate}
1520 {\tt\begin{bytefield}{36}
1521 \bitheader[b]{0,7,21-30,35}\\
1540 \bitbox{1}{1${}^\star$}
1545 \end{bytefield}} \\\hline
1548 {\tt\begin{bytefield}{36}
1560 {\tt\begin{bytefield}{36}
1563 \bitbox{6}{Predicate}
1589 {\tt\begin{bytefield}{36}
1602 $\star$ -- Bit 8 is the ``infinity'' bit \\
1603 $\dagger$ -- When a ``Move, Path unchanged'' is performed, bit 12 is copied to the ``flushing latch''. \\
1604 .\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. \\
1605 $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. \\
1606 Tp\ \ = Torpedoable (1=Torpedoable, 0=Not-Torpedoable) \\
1607 rD\ \ = recompute D-flag (1=recompute, 0=leave unchanged)
1609 \end{sidewaysfigure}
1612 \section*{Marina Dock Block Diagram}
1613 This diagram was produced by Ivan Sutherland.
1615 \epsfig{file=blockDiagram,width=8in,angle=90}