1 \documentclass[10pt]{article}
6 \usepackage{bytefield1}
18 \bibliographystyle{alpha}
19 \pagestyle{fancyplain}
21 \definecolor{light}{gray}{0.7}
23 \newcommand{\footnoteremember}[2]{
26 \setcounter{#1}{\value{footnote}}
27 } \newcommand{\footnoterecall}[1]{
28 \footnotemark[\value{#1}]
36 %\oddsidemargin 0.25in
37 %\evensidemargin 0.25in
39 \def\to{\ $\rightarrow$\ }
49 \title{\vspace{-1cm}The FleetTwo Dock}
61 & removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
63 & extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
64 & update table 3.1.2 \\
65 & rename {\tt S} flag to {\tt C} \\
67 & noted that {\tt setFlags} can be used as {\tt nop} \\
69 & removed the {\tt L} flag (epilogues can now do this) \\
70 & removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
71 & renamed {\tt data} instruction to {\tt literal} \\
72 & renamed {\tt send} instruction to {\tt move} \\
74 & added ``if its predicate is true'' to repeat count \\
75 & added note that red wires do not contact ships \\
76 & changed name of {\tt flags} instruction to {\tt setFlags} \\
77 & removed black dot from diagrams \\
78 & changed {\tt OL} (Outer Loop participant) to {\tt OS} (One Shot) and inverted polarity \\
79 & indicated that the death of the {\tt tail} instruction is what causes the hatch to be unsealed \\
80 & indicated that only {\tt send} instructions which wait for data are torpedoable \\
81 & added section ``Torpedo Details'' \\
82 & removed {\tt torpedo} instruction \\
85 & renamed loop+repeat to outer+inner (not in red) \\
86 & renamed {\tt Z} flag to {\tt L} flag (not in red) \\
87 & rewrote ``inner and outer loops'' section \\
88 & updated all diagrams \\
91 & Moved address bits to the LSB-side of a 37-bit instruction \\
92 & Added {\it micro-instruction} and {\it composite instruction} terms \\
93 & Removed the {\tt DL} field, added {\tt decrement} mode to {\tt loop} \\
94 & Created the {\tt Hold} field \\
95 & Changed how ReLooping works \\
96 & Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
103 \epsfig{file=overview,width=1.5in}
104 \epsfig{file=indock,width=3in}
109 \section{Overview of Fleet}
111 A Fleet processor consists of a {\it switch fabric} with several
112 functional units called {\it ships} connected to it. At each
113 connection between a ship and the switch fabric lies a programmable
114 element known as the {\it dock}.
116 A {\it path} specifies a route through the switch fabric from a
117 particular {\it source} to a particular {\it destination}. The
118 combination of a path and a single word {\it payload} is called a {\it packet}. The
119 switch fabric carries packets from their sources to their
120 destinations. Each dock has two destinations: one for {\it
121 instructions} and one for {\it data}. A Fleet is programmed by
122 depositing packets into the switch fabric; these packets' paths lead
123 them to the instruction destinations of the docks.
125 When a packet arrives at the instruction destination of a dock, it is
126 enqueued for execution. Before the instruction executes, it may cause
127 the dock to wait for a packet to arrive at the dock's data destination
128 or for a value to be presented by the ship. It may present a data
129 value to the ship or transmit it for transmission to some other
132 When an instruction sends a packet into the switch fabric, it may
133 specify that the payload of the packet is irrelevant. Such packets
134 are known as {\it tokens}, and consume less energy than data packets.
135 From a programmer's perspective, a token packet is indistinguishable
136 from a data packet with a unknown payload.
138 In the diagram below, the red wires carry instructions and the blue
139 wires carry data; the switch fabric (gray area) carries both. Notice
140 that the red (instruction) wires do not contact the ships. This is an
141 advantage: ships are designed without any consideration for the
142 instructions used to program their docks.
145 \epsfig{file=overview,width=2.5in}\\
146 {\it Overview of a Fleet processor; gray shading represents a
147 packet-switched network fabric; blue lines carry data, red lines
154 \section{The FleetTwo Pump}
156 The diagram below represents a {\it programmer's} conceptual view of
157 the interface between ships and the switch fabric. Actual
158 implementation circuitry may differ substantially. Sources and
159 destinations that can send and receive only tokens -- not data items
160 -- are drawn as dashed lines.
163 \epsfig{file=indock,width=3.5in}\\
164 {\it an ``input'' dock}
166 \epsfig{file=outdock,width=3.5in}\\
167 {\it an ``output'' dock}
170 The term {\it port} refers to an interface to the ship, the {\it
171 dock} connecting it to the switch fabric, and the corresponding
172 sources and destinations on the switch fabric.
174 Each dock consists of a {\it data latch}, which is as wide as a single
175 machine word and a {\it pump}, which is a circular fifo of
176 instruction-width latches. The values in the pump control the data
179 Note that the pump in each dock has a destination of its own; this is
180 the {\it instruction destination} mentioned in the previous section.
181 Note that unlike all other destinations, there is no buffering fifo
182 guarding this one. The size of these fifos are exposed to the
183 software programmer so he can avoid deadlock.
186 \section{Instructions}
188 In order to cause an instruction to execute, the programmer must first
189 cause that instruction word to arrive in the data latch of some output
190 dock. For example, this might be the ``data read'' output dock of the
191 memory access ship or the output of a fifo ship. Once an instruction
192 has arrived at this output dock, it is {\it dispatched} by sending it
193 to the {\it instruction port} of the dock at which it is to execute.
195 Each instruction is 26 bits long, which makes it possible for an
196 instruction and an 11-bit path to fit in a single word of memory.
197 This path is the path from the {\it dispatching} dock to the {\it
200 \setlength{\bitwidth}{3.5mm}
202 \begin{bytefield}{37}
203 \bitheader[b]{0,10,11,36}\\
204 \bitbox{26}{instruction}
205 \bitbox{11}{dispatch path}
208 {\bf Note:} the instruction encodings below are simply ``something to
209 shoot at'' and a sanity check to make sure we haven't overrun our bit
210 budget. The final instruction encodings will probably be
213 All instruction words have the following format:
215 \setlength{\bitwidth}{3.5mm}
217 \begin{bytefield}{37}
218 \bitheader[b]{0,10,11,36}\\
225 \bitbox{11}{dispatch path}
229 Each instruction word is called a {\it micro instruction}.
230 Collections of one or more micro instruction are known as {\it
231 composite instructions}.
233 The {\tt I} bit stands for {\tt Interruptible}. The {\tt OS} (``One
234 Shot'') bit indicates whether or not this instruction is part of an
235 outer loop. Both of the preceding bits are explained in the next
240 The abbreviation {\tt P} stands for {\it predicate}; this is a two-bit
241 code that indicates if the instruction should be executed or ignored.
246 \subsection{Life Cycle of an Instruction}
248 The diagram below shows an input dock for purposes of illustration
249 (behavior at an output dock is identical).
252 \epsfig{file=indock,width=3in}\\
256 Note the circle on the path between ``instr horn'' and ``instr fifo'';
257 this is known as ``the hatch''. The hatch has two states: sealed and
258 unsealed. When the machine powers up, the hatch is unsealed; it is
259 sealed by the {\tt tail} instruction and unsealed whenever the outer
260 loop counter is set to zero (for any reason\footnote{this
261 includes {\tt OLC} being decremented to zero, a {\tt setOuter} with
262 a literal field of zero, a {\tt setOuter} which copies a zero from
263 the data register to {\tt OLC}, or the occurrence of a
266 When an instruction arrives at the instruction horn, it waits there
267 until the hatch is in the unsealed state. The instruction then enters
268 the instruction fifo. When an instruction emerges from the
269 instruction fifo, it arrives at the ``on deck'' stage, where it may
272 \subsubsection{Inner and Outer Loops}
274 A programmer can perform two types of loops: {\it inner} loops of only
275 one micro-instruction and {\it outer} loops of multiple
276 micro-instructions. Inner loops may be nested within an outer loop,
277 but no other nesting of loops is allowed. The paths used by inner
278 loops and outer loops are shown below:
281 \begin{minipage}{2in}
283 \epsfig{file=inner-loop,width=2in}\\
284 {\it inner loop (in red)}
287 \begin{minipage}{2in}
289 \epsfig{file=outer-loop,width=2in}\\
290 {\it outer loop (in red)}
295 Each type of loop has a counter associated with it: the {\tt ILC}
296 counter for inner loops and the {\tt OLC} counter for outer loops.
297 The inner loop counter applies only to certain ``inner-looping''
298 instructions (see the table below for details). When such an
299 instruction reaches On Deck, if its predicate is true it will execute
300 a number of times equal to {\tt ILC+1}, and leave {\tt ILC=0} after
301 executing. Non-inner-looping instructions and instructions whose
302 predicate is false do not decrement {\tt ILC}.
304 The outer loop counter applies to all instructions {\it except} the
305 instruction {\tt setOuter} with {\tt OS=1}, because such instructions
306 are needed to reset the outer loop counter after it becomes zero.
307 However, predicated {\tt setOuter} with {\tt OS=0} is useful for
308 resetting the loop counter in the middle of the execution of a loop.
310 \subsubsection{On Deck}
312 The table below lists the actions which may be taken when an
313 instruction arrives on deck:
317 \def\side#1{\begin{sideways}\parbox{15mm}{#1}\end{sideways}}
318 \begin{tabular}{|r|ccccc|cccccc|}\hline
319 %&\multicolumn{10}{c}{Predicate}&\\
320 %&\multicolumn{10}{c}{True}&\\\hline
321 &\multicolumn{5}{c}{Outer-Looping} &\multicolumn{5}{c}{One-Shot}&\\
322 &\multicolumn{5}{c}{{\tt (OS=0)}} &\multicolumn{5}{c}{{\tt (OS=1)}}&\\
324 &\side{{\tt literal}}
325 &\side{{\tt setFlags}}
326 &\side{{\tt setInner}}
327 &\side{{\tt setOuter}}
329 &\side{{\tt literal}}
330 &\side{{\tt setFlags}}
331 &\side{{\tt setInner}}
332 &\side{{\tt setOuter}}
335 Wait for hatch sealed, & + & + & + & + & + & - & - & - & - & - & \\
336 then IF0 w/ copy of self & & & & & & & & & & & \\\hline
337 Potentially torpedoable & P+I & P+I & P+I & P+I & P+I & PI & PI & PI & PI & PI & \\
338 Execute & P+ & P+ & P+ & P+ & P+ & P & P & P & P & P & \\
339 Inner-looping & P+ & - & - & - & - & P & - & - & - & - & \\
343 \begin{tabular}{|r|l|}\hline
344 + & Only if {\tt OLC>0} (ie {\tt OLC} is positive) \\
345 P & Only if predicate is true \\
346 P+ & Only if predicate is true and {\tt OLC>0} \\
347 PI & Only if predicate is true and {\tt I=1}. \\
348 P+I & Only if predicate is true and {\tt OLC>0} and {\tt I=1}. \\\hline
354 {\bf Note:} a non-one-shot instruction may {\it execute} before the
355 hatch is sealed, but may not {\it fill IF0} before the hatch is
356 sealed. The instruction will not vacate On Deck until both of these
357 tasks are complete, so the second non-one-shot instruction in a loop
358 will not execute until the hatch is sealed, {\it but the first
362 \subsubsection{Torpedo}
364 There is a small fifo (not shown) before the latch marked
365 ``Instruction Horn''; after the {\tt tail} instruction seals the
366 hatch, any subsequent instructions will queue up in this fifo until
367 the hatch is unsealed. This is typically used as storage for a ``loop
368 epilogue'' -- a sequence of instructions to be executed after a
369 torpedo arrives or the outer loop counter expires.
371 Each dock has a fourth connection to the switch fabric (not shown),
372 called its {\it torpedo destination}. Anything (even a token) sent to
373 this destination is treated as a torpedo. Note that because this is a
374 distinct destination, instructions or data queued up in the other
375 destination fifos will not prevent a torpedo from occuring.
377 When a data item or token arrives at the torpedo destination, it lies
378 there in wait until On Deck holds a potentially torpedoable
379 instruction (see previous table). Once this is the case, the torpedo
380 causes the inner and outer loop counters to be set to zero (and
381 therefore also unseals the hatch).\footnote{it is unspecified whether
382 the torpedoed instruction is requeued or not; this may or may not
383 occur, nondeterministically. It is the programmer's responsibility
384 to ensure that the program behaves the same whether this happens or
385 not. We think that this will not matter in most situations.}
392 The pump has three flags: {\tt A}, {\tt B}, and {\color{red}{\tt C}\color{black}\ }.
395 \item The {\tt A} and {\tt B} flags are general-purpose flags which
396 may be set and cleared by the programmer.
400 % The {\tt L} flag, known as the {\it last} flag, is set whenever
401 % the value in the outer counter ({\tt OLC}) is one,
404 % that the dock is in the midst of the last iteration of an
405 % outer loop. This flag can be used to perform certain
406 % operations (such as sending a completion token) only on the last
407 % iteration of an outer loop.
409 \item The {\color{red}{\tt C}\color{black}\ } flag, known as the {\it control} flag.
410 \color{red}At outboxes its value is determined by the ship; at
411 inboxes its value is copied from an unused address bit in the
412 destination to which the received value was sent.
416 Many instruction fields are specified as two-bit {\it predicates}.
417 These fields contain one of four values, indicating if an action
418 should be taken unconditionally or conditionally on one of the {\tt A}
422 \item {\tt 00:} if {\tt A} is set
423 \item {\tt 10:} if {\tt B} is set
424 \item {\tt 01:} \color{red}if {\color{red}{\tt C}\color{black}\ } is set\color{black}
425 \item {\tt 11:} always
430 \section{Instructions}
432 Here is a list of the instructions supported by the dock:
435 \begin{tabular}{|l|}\hline
436 {\tt move} (variants: {\tt moveto}, {\tt dispatch}) \\
437 {\tt literal} (variants: {\tt literalhi}, {\tt literallo})\\
449 \subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
451 \setlength{\bitwidth}{5mm}
453 \begin{bytefield}{26}
454 \bitheader[b]{14-19,21}\\
469 %\begin{bytefield}{26}
470 % \bitheader[b]{12-18}\\
471 % \bitbox[]{8}{\raggedleft Input Dock:}
478 %\begin{bytefield}{26}
479 % \bitheader[b]{12-18}\\
480 % \bitbox[]{8}{\raggedleft Output Dock:}
487 \begin{bytefield}{26}
488 \bitheader[b]{0,12,13}\\
489 \bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt LiteralPath\to Path})}
492 \bitbox{13}{\tt LiteralPath}
495 \begin{bytefield}{26}
496 \bitheader[b]{12,13}\\
497 \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\tt DP[37:25]\to Path})\ \ }
506 \begin{bytefield}{26}
507 \bitheader[b]{12,13}\\
508 \bitbox[1]{11}{\raggedleft {\tt move} ({\tt Path} unchanged):}
518 \item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
519 \item {\tt Di} - Data Input: wait for the data predecessor to be full and drain it.
520 \item {\tt Dc} - Data Capture: pulse the data latch.
521 \item {\tt Do} - Data Output: fill the data successor.
522 \item {\tt To} - Token Output: fill the token successor.
525 The data successor and token successor must both be empty in order for
526 a {\tt move} instruction to attempt execution.
528 The inner loop counter can hold a number {\tt 0..MAX} or a special
529 value $\infty$. If {\tt ILC} is nonzero after execution of a {\tt
530 move} instruction, the instruction will execute again, and {\tt ILC}
531 will be latched with {\tt (ILC==$\infty$?$\infty$:max(ILC-1, 0))}. When
532 the inner loop counter reaches zero, the instruction ceases executing.
536 \subsection{{\tt literal}, {\tt literalhi}, {\tt literallo}}
538 These instructions load part or all of the data latch ({\tt D}).
540 {\tt literalhi: Literal[18:1]\to D[37:20]} (and {\tt Literal[18]\to S})
542 \setlength{\bitwidth}{5mm}
544 \begin{bytefield}{26}
545 \bitheader[b]{0,18,19,21}\\
559 {\tt literallo: Literal[19:1]\to D[19:1]}
561 \setlength{\bitwidth}{5mm}
563 \begin{bytefield}{26}
564 \bitheader[b]{0,18,19,21}\\
577 \setlength{\bitwidth}{5mm}
579 \begin{bytefield}{26}
580 \bitheader[b]{0,18,19,21}\\
592 \begin{tabular}{|r|c|c|c|}\hline
593 sel & D[37:20] & D[19:1] \\\hline
594 00 & Literal[18:1] & all 0 \\
595 01 & Literal[18:1] & all 1 \\
596 10 & all 0 & Literal[19:1] \\
597 11 & all 1 & Literal[19:1] \\
604 \subsection{{\tt setFlags}}
606 \setlength{\bitwidth}{5mm}
608 \begin{bytefield}{26}
609 \bitheader[b]{0,5,6,11,12,17-19,21}\\
622 The {\tt P} field is a predicate; if it does not hold, the instruction
623 is ignored. Otherwise the flags are updated according to the {\tt
624 nextA}, {\tt nextB}, and {\tt nextC} fields; each specifies the new
625 value as the logical {\tt OR} of zero or more inputs:
631 \bitbox{1}{${\text{\tt A}}$}
632 \bitbox{1}{$\overline{\text{\tt A}}$}
633 \bitbox{1}{${\text{\tt B}}$}
634 \bitbox{1}{$\overline{\text{\tt B}}$}
635 \bitbox{1}{${\text{\color{red}{\tt C}\color{black}\ }}$}
636 \bitbox{1}{$\overline{\text{\color{red}{\tt C}\color{black}\ }}$}
640 Each bit corresponds to one possible input; all inputs whose bits are
641 set are {\tt OR}ed together, and the resulting value is assigned to
642 the flag. Note that if none of the bits are set, the value assigned
643 is zero. Note also that it is possible to produce a {\tt 1} by {\tt
644 OR}ing any flag with its complement. Note that {\tt setFlags} can
645 be used to create a {\tt nop} (no-op) by setting each flag to itself.
651 \subsection{{\tt setInner}}
653 This instruction loads the inner loop counter with either a literal
654 number, the special value $\infty$, or the contents of the {\tt data}
657 \setlength{\bitwidth}{5mm}
659 \begin{bytefield}{26}
660 \bitheader[b]{16-19,21}\\
675 \begin{bytefield}{26}
676 \bitbox[r]{18}{\raggedleft from data latch:\hspace{0.2cm}\ }
683 \begin{bytefield}{26}
684 \bitheader[b]{0,5,6,7}\\
685 \bitbox[r]{18}{\raggedleft from literal:\hspace{0.2cm}\ }
687 \bitbox{6}{\tt Literal}
690 \begin{bytefield}{26}
691 \bitheader[b]{0,5,6,7}\\
692 \bitbox[r]{18}{\raggedleft with $\infty$\ \ }
700 \subsection{{\tt setOuter}}
702 This instruction loads the outer loop counter {\tt OLC} with either
703 {\tt max(0,OLC-1)}, a literal or the contents of the {\tt data}
706 \setlength{\bitwidth}{5mm}
708 \begin{bytefield}{26}
709 \bitheader[b]{16-19,21,24}\\
725 \begin{bytefield}{26}
726 \bitbox[r]{19}{\raggedleft {\tt max(0,OLC-1)}:\hspace{0.2cm}\ }
734 \begin{bytefield}{26}
735 \bitbox[r]{19}{\raggedleft from data latch:\hspace{0.2cm}\ }
742 \begin{bytefield}{26}
743 \bitheader[b]{0,5,6}\\
744 \bitbox[r]{19}{\raggedleft from literal:\hspace{0.2cm}\ }
746 \bitbox{6}{\tt Literal}
750 %\subsection{{\tt torpedo}}
752 %\setlength{\bitwidth}{5mm}
754 %\begin{bytefield}{26}
755 % \bitheader[b]{0,5,16-19,21}\\
767 %When a {\tt torpedo} instruction reaches the instruction horn, it will
768 %wait there until an instruction is on deck whose {\tt A}rmor bit is
769 %not set. The {\tt torpedo} will then cause ``Process \#2'' of the on
770 %deck instruction to terminate and will set the outer loop counter to zero.
772 \subsection{{\tt tail}}
774 \setlength{\bitwidth}{5mm}
776 \begin{bytefield}{26}
777 \bitheader[b]{0,5,16-19,21}\\
788 When a {\tt tail} instruction reaches {\tt IH}, it seals the hatch.
789 The {\tt tail} instruction does not enter the instruction fifo.
793 %\subsection{{\tt takeOuterLoopCounter}}
795 %\setlength{\bitwidth}{5mm}
797 %\begin{bytefield}{26}
798 % \bitheader[b]{16-19,21}\\
812 %This instruction copies the value in the outer loop counter {\tt OLC}
813 %into the least significant bits of the data latch and leaves all other
814 %bits of the data latch unchanged.
816 %\subsection{{\tt takeInnerLoopCounter}}
818 %\setlength{\bitwidth}{5mm}
820 %\begin{bytefield}{26}
821 % \bitheader[b]{16-19,21}\\
835 %This instruction copies the value in the inner loop counter {\tt ILC}
836 %into the least significant bits of the data latch and leaves all other
837 %bits of the data latch unchanged.
842 %%\subsection{{\tt interrupt}}
844 %%\setlength{\bitwidth}{5mm}
846 %\begin{bytefield}{26}
847 % \bitheader[b]{0,5,16-19,21}\\
858 %When an {\tt interrupt} instruction reaches {\tt IH}, it will wait
859 %there for the {\tt OD} stage to be full with an instruction that has
860 %the {\tt IM} bit set. When this occurs, the instruction at {\tt OD}
861 %{\it will not execute}, but {\it may reloop} if the conditions for
863 %\footnote{The ability to interrupt an instruction yet have it reloop is very
864 %useful for processing chunks of data with a fixed size header and/or
865 %footer and a variable length body.}
868 %\subsection{{\tt massacre}}
870 %\setlength{\bitwidth}{5mm}
872 %\begin{bytefield}{26}
873 % \bitheader[b]{16-19,21}\\
885 %When a {\tt massacre} instruction reaches {\tt IH}, it will wait there
886 %for the {\tt OD} stage to be full with an instruction that has the
887 %{\tt IM} bit set. When this occurs, all instructions in the
888 %instruction fifo (including {\tt OD}) are retired.
890 %\subsection{{\tt clog}}
892 %\setlength{\bitwidth}{5mm}
894 %\begin{bytefield}{26}
895 % \bitheader[b]{16-19,21}\\
907 %When a {\tt clog} instruction reaches {\tt OD}, it remains there and
908 %no more instructions will be executed until an {\tt unclog} is
911 %\subsection{{\tt unclog}}
913 %\setlength{\bitwidth}{5mm}
915 %\begin{bytefield}{26}
916 % \bitheader[b]{16-19,21}\\
922 % \bitbox[lrtb]{2}{11}
928 %When an {\tt unclog} instruction reaches {\tt IH}, it will wait there
929 %until a {\tt clog} instruction is at {\tt OD}. When this occurs, both
930 %instructions retire.
932 %Note that issuing an {\tt unclog} instruction to a dock which is not
933 %clogged and whose instruction fifo contains no {\tt clog} instructions
934 %will cause the dock to deadlock.
939 \epsfig{file=overview,height=5in,angle=90}
942 \subsection*{Input Dock}
943 \epsfig{file=indock,width=7in,angle=90}
946 \subsection*{Output Dock}
947 \epsfig{file=outdock,width=6.5in,angle=90}
951 %\epsfig{file=ports,height=5in,angle=90}
954 %\epsfig{file=best,height=5in,angle=90}