1 \documentclass[10pt]{article}
6 \usepackage{bytefield1}
18 \bibliographystyle{alpha}
19 \pagestyle{fancyplain}
21 \definecolor{light}{gray}{0.7}
23 \setlength{\marginparwidth}{1.2in}
24 \let\oldmarginpar\marginpar
25 \renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize #1]%
26 {\raggedright\footnotesize #1}}
29 \newcommand{\footnoteremember}[2]{
32 \setcounter{#1}{\value{footnote}}
33 } \newcommand{\footnoterecall}[1]{
34 \footnotemark[\value{#1}]
42 %\oddsidemargin 0.25in
43 %\evensidemargin 0.25in
45 \def\to{\ $\rightarrow$\ }
55 \title{\vspace{-1cm}The FleetTwo Dock}
67 & added epilogue fifo to diagrams \\
68 & indicated that a token sent to the instruction port is treated as a torpedo \\
70 & replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
71 & replaced {\tt literal} with {\tt shift} instruction \\
74 & Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
75 & Removed ability to manually set the {\tt C} flag \\
76 & Expanded predicate field to three bits \\
77 & New literals scheme (via shifting) \\
78 & Instruction encoding changes made at Ivan's request (for layout purposes) \\
79 & Added summary of instruction encodings on last page \\
81 & removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
83 & extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
84 & update table 3.1.2 \\
85 & rename {\tt S} flag to {\tt C} \\
86 & noted that {\tt setFlags} can be used as {\tt nop} \\
88 & removed the {\tt L} flag (epilogues can now do this) \\
89 & removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
90 & renamed {\tt data} instruction to {\tt literal} \\
91 & renamed {\tt send} instruction to {\tt move} \\
93 %& added ``if its predicate is true'' to repeat count \\
94 %& added note that red wires do not contact ships \\
95 %& changed name of {\tt flags} instruction to {\tt setFlags} \\
96 %& removed black dot from diagrams \\
97 %& changed {\tt OL} (Outer Loop participant) to {\tt OS} (One Shot) and inverted polarity \\
98 %& indicated that the death of the {\tt tail} instruction is what causes the hatch to be unsealed \\
99 %& indicated that only {\tt send} instructions which wait for data are torpedoable \\
100 %& added section ``Torpedo Details'' \\
101 %& removed {\tt torpedo} instruction \\
104 %& renamed loop+repeat to outer+inner (not in red) \\
105 %& renamed {\tt Z} flag to {\tt L} flag (not in red) \\
106 %& rewrote ``inner and outer loops'' section \\
107 %& updated all diagrams \\
110 %& Moved address bits to the LSB-side of a 37-bit instruction \\
111 %& Added {\it micro-instruction} and {\it composite instruction} terms \\
112 %& Removed the {\tt DL} field, added {\tt decrement} mode to {\tt loop} \\
113 %& Created the {\tt Hold} field \\
114 %& Changed how ReLooping works \\
115 %& Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
122 \epsfig{file=overview,width=1.5in}
123 \epsfig{file=indock,width=3in}
128 \section{Overview of Fleet}
130 A Fleet processor consists of a {\it switch fabric} with several
131 functional units called {\it ships} connected to it. At each
132 connection between a ship and the switch fabric lies a programmable
133 element known as the {\it dock}.
135 A {\it path} specifies a route through the switch fabric from a
136 particular {\it source} to a particular {\it destination}. The
137 combination of a path and a single word {\it payload} is called a {\it packet}. The
138 switch fabric carries packets from their sources to their
139 destinations. Each dock has two destinations: one for {\it
140 instructions} and one for {\it data}. A Fleet is programmed by
141 depositing packets into the switch fabric; these packets' paths lead
142 them to the instruction destinations of the docks.
144 When a packet arrives at the instruction destination of a dock, it is
145 enqueued for execution. Before the instruction executes, it may cause
146 the dock to wait for a packet to arrive at the dock's data destination
147 or for a value to be presented by the ship. It may present a data
148 value to the ship or transmit it for transmission to some other
151 When an instruction sends a packet into the switch fabric, it may
152 specify that the payload of the packet is irrelevant. Such packets
153 are known as {\it tokens}, and consume less energy than data packets.
154 From a programmer's perspective, a token packet is indistinguishable
155 from a data packet with a unknown payload.
157 In the diagram below, the red wires carry instructions and the blue
158 wires carry data; the switch fabric (gray area) carries both. Notice
159 that the red (instruction) wires do not contact the ships. This is an
160 advantage: ships are designed without any consideration for the
161 instructions used to program their docks.
164 \epsfig{file=overview,width=2.5in}\\
165 {\it Overview of a Fleet processor; gray shading represents a
166 packet-switched network fabric; blue lines carry data, red lines
173 \section{The FleetTwo Pump}
175 The diagram below represents a {\it programmer's} conceptual view of
176 the interface between ships and the switch fabric. Actual
177 implementation circuitry may differ substantially. Sources and
178 destinations that can send and receive only tokens -- not data items
179 -- are drawn as dashed lines.
182 \epsfig{file=indock,width=3.5in}\\
183 {\it an ``input'' dock}
185 \epsfig{file=outdock,width=3.5in}\\
186 {\it an ``output'' dock}
189 The term {\it port} refers to an interface to the ship, the {\it
190 dock} connecting it to the switch fabric, and the corresponding
191 sources and destinations on the switch fabric.
193 Each dock consists of a {\it data latch}, which is as wide as a single
194 machine word and a {\it pump}, which is a circular fifo of
195 instruction-width latches. The values in the pump control the data
198 Note that the pump in each dock has a destination of its own; this is
199 the {\it instruction destination} mentioned in the previous section.
200 Note that unlike all other destinations, there is no buffering fifo
201 guarding this one. The size of these fifos are exposed to the
202 software programmer so he can avoid deadlock.
205 \section{Instructions}
207 In order to cause an instruction to execute, the programmer must first
208 cause that instruction word to arrive in the data latch of some output
209 dock. For example, this might be the ``data read'' output dock of the
210 memory access ship or the output of a fifo ship. Once an instruction
211 has arrived at this output dock, it is {\it dispatched} by sending it
212 to the {\it instruction port} of the dock at which it is to execute.
214 Each instruction is 26 bits long, which makes it possible for an
215 instruction and an 11-bit path to fit in a single word of memory.
216 This path is the path from the {\it dispatching} dock to the {\it
219 \setlength{\bitwidth}{3.5mm}
221 \begin{bytefield}{37}
222 \bitheader[b]{0,10,11,36}\\
223 \bitbox{26}{instruction}
224 \bitbox{11}{dispatch path}
227 {\bf Note:} the instruction encodings below are simply ``something to
228 shoot at'' and a sanity check to make sure we haven't overrun our bit
229 budget. The final instruction encodings will probably be
232 All instruction words have the following format:
234 \newcommand{\bitsHeader}{
240 \setlength{\bitwidth}{3.5mm}
242 \begin{bytefield}{37}
243 \bitheader[b]{0,10,11,36}\\
248 \bitbox{11}{dispatch path}
252 Each instruction word is called a {\it micro instruction}.
253 Collections of one or more micro instruction are known as {\it
254 composite instructions}.
256 The {\tt I} bit stands for {\tt Interruptible}. The {\tt OS} (``One
257 Shot'') bit indicates whether or not this instruction is part of an
258 outer loop. Both of the preceding bits are explained in the next
263 The abbreviation {\tt P} stands for {\it predicate}; this is a two-bit
264 code that indicates if the instruction should be executed or ignored.
269 \subsection{Life Cycle of an Instruction}
271 The diagram below shows an input dock for purposes of illustration
272 (behavior at an output dock is identical).
275 \epsfig{file=indock,width=3in}\\
279 Note the circle on the path between ``instr horn'' and ``instr fifo'';
280 this is known as ``the hatch''. The hatch has two states: sealed and
281 unsealed. When the machine powers up, the hatch is unsealed; it is
282 sealed by the {\tt tail} instruction and unsealed whenever the outer
283 loop counter is set to zero (for any reason\footnote{this
284 includes {\tt OLC} being decremented to zero, a {\tt setOuter} with
285 a literal field of zero, a {\tt setOuter} which copies a zero from
286 the data register to {\tt OLC}, or the occurrence of a
289 When an instruction arrives at the instruction horn, it waits there
290 until the hatch is in the unsealed state. The instruction then enters
291 the instruction fifo. When an instruction emerges from the
292 instruction fifo, it arrives at the ``on deck'' stage, where it may
295 \subsubsection{Inner and Outer Loops}
297 A programmer can perform two types of loops: {\it inner} loops of only
298 one micro-instruction and {\it outer} loops of multiple
299 micro-instructions. Inner loops may be nested within an outer loop,
300 but no other nesting of loops is allowed. The paths used by inner
301 loops and outer loops are shown below:
304 \begin{minipage}{2in}
306 \epsfig{file=inner-loop,width=2in}\\
307 {\it inner loop (in red)}
310 \begin{minipage}{2in}
312 \epsfig{file=outer-loop,width=2in}\\
313 {\it outer loop (in red)}
318 Each type of loop has a counter associated with it: the {\tt ILC}
319 counter for inner loops and the {\tt OLC} counter for outer loops.
320 The inner loop counter applies only to certain ``inner-looping''
321 instructions (see the table below for details). When such an
322 instruction reaches On Deck, if its predicate is true it will execute
323 a number of times equal to {\tt ILC+1}, and leave {\tt ILC=0} after
324 executing. Non-inner-looping instructions and instructions whose
325 predicate is false do not decrement {\tt ILC}.
327 The outer loop counter applies to all instructions {\it except} the
328 instruction {\tt setOuter} with {\tt OS=1}, because such instructions
329 are needed to reset the outer loop counter after it becomes zero.
330 However, predicated {\tt setOuter} with {\tt OS=0} is useful for
331 resetting the loop counter in the middle of the execution of a loop.
333 \subsubsection{On Deck}
335 The table below lists the actions which may be taken when an
336 instruction arrives on deck:
339 \def\side#1{\begin{sideways}\parbox{15mm}{#1}\end{sideways}}
340 \begin{tabular}{|r|ccccc|cccccc|}\hline
341 %&\multicolumn{10}{c}{Predicate}&\\
342 %&\multicolumn{10}{c}{True}&\\\hline
343 &\multicolumn{5}{c}{Outer-Looping} &\multicolumn{5}{c}{One-Shot}&\\
344 &\multicolumn{5}{c}{{\tt (OS=0)}} &\multicolumn{5}{c}{{\tt (OS=1)}}&\\
346 &\side{{\tt literal}}
347 &\side{{\tt setFlags}}
348 &\side{{\tt setInner}}
349 &\side{{\tt setOuter}}
351 &\side{{\tt literal}}
352 &\side{{\tt setFlags}}
353 &\side{{\tt setInner}}
354 &\side{{\tt setOuter}}
357 Wait for hatch sealed, & + & + & + & + & + & - & - & - & - & - & \\
358 then IF0 w/ copy of self & & & & & & & & & & & \\\hline
359 Potentially torpedoable & P+I & P+I & P+I & P+I & P+I & P+I & P+I & P+I & P+I & PI & \\
360 Execute & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P+ & P & \\
361 Inner-looping & P+ & - & - & - & - & P & - & - & - & - & \\
365 \begin{tabular}{|r|l|}\hline
366 + & Only if {\tt OLC>0} (ie {\tt OLC} is positive) \\
367 P & Only if predicate is true \\
368 P+ & Only if predicate is true and {\tt OLC>0} \\
369 PI & Only if predicate is true and {\tt I=1}. \\
370 P+I & Only if predicate is true and {\tt OLC>0} and {\tt I=1}. \\\hline
374 {\bf Note:} a non-one-shot instruction may {\it execute} before the
375 hatch is sealed, but may not {\it fill IF0} before the hatch is
376 sealed. The instruction will not vacate On Deck until both of these
377 tasks are complete, so the second non-one-shot instruction in a loop
378 will not execute until the hatch is sealed, {\it but the first
383 \subsubsection{Torpedo}
386 There is a small fifo marked ``Epilogue'' just beyond the instruction
387 destination; after the {\tt tail} instruction seals the hatch, any
388 subsequent instructions will queue up in this fifo until the hatch is
389 unsealed. This is typically used as storage for a ``loop epilogue''
390 -- a sequence of instructions to be executed after a torpedo arrives
391 or the outer loop counter expires.
393 A {\it token} sent to a ship's instruction destination is treated as a
394 torpedo; the check for a torpedo is performed {\it before} the head of
395 the Epilogue fifo. Note that because the check for a token is
396 performed ``upstream'' of the epilogue fifo, torpedos will still be
397 effective even when the Epilogue fifo is nearly full.
400 The dock also has a {\it torpedo acknowledgment path latch},
401 which stores the path along which a token should be sent when a
404 When a data item or token arrives at the torpedo destination, it lies
405 there in wait until On Deck holds a potentially torpedoable
406 instruction (see previous table). Once this is the case, the torpedo
407 causes the inner and outer loop counters to be set to zero (and
408 therefore also unseals the hatch)\footnote{it is unspecified whether
409 the torpedoed instruction is requeued or not; this may or may not
410 occur, nondeterministically. It is the programmer's responsibility
411 to ensure that the program behaves the same whether this happens or
412 not. We think that this will not matter in most situations.} and
413 sends a token along the path stored in the torpedo acknowledgment path
420 The pump has three flags: {\tt A}, {\tt B}, and {\tt C}.
423 \item The {\tt A} and {\tt B} flags are general-purpose flags which
424 may be set and cleared by the programmer.
428 % The {\tt L} flag, known as the {\it last} flag, is set whenever
429 % the value in the outer counter ({\tt OLC}) is one,
432 % that the dock is in the midst of the last iteration of an
433 % outer loop. This flag can be used to perform certain
434 % operations (such as sending a completion token) only on the last
435 % iteration of an outer loop.
437 \item The {\tt C} flag is known as the {\it control} flag, and it is
438 set every time the data latch takes on a new value. At outboxes
439 its value is determined by the ship; at inboxes its value is
440 copied from an unused address bit in the destination to which
441 the received value was sent.
444 Many instruction fields are specified as
445 three-bit {\it predicates}. These fields
446 contain one of eight values, indicating if an action should be taken
447 unconditionally or conditionally on one of the {\tt A}, {\tt B}, or
452 \item {\tt 000:} if {\tt A} is set
453 \item {\tt 001:} if {\tt A} is cleared
454 \item {\tt 010:} if {\tt B} is set
455 \item {\tt 011:} if {\tt B} is cleared
458 \item {\tt 100:} if {\tt C} is set
459 \item {\tt 101:} if {\tt C} is cleared
460 \item {\tt 110:} unused
461 \item {\tt 111:} always
468 \section{Instructions}
470 Here is a list of the instructions supported by the dock:
473 \begin{tabular}{|l|}\hline
474 {\tt move} (variants: {\tt moveto}, {\tt dispatch}) \\
487 \subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
489 \newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
491 \begin{bytefield}{26}
492 \bitheader[b]{14-20}\\
506 \begin{bytefield}{26}
507 \bitheader[b]{0,12,13}\\
508 \bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt LiteralPath\to Path})}
511 \bitbox{13}{\tt LiteralPath}
514 \begin{bytefield}{26}
515 \bitheader[b]{11,12,13}\\
516 \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\tt DP[37:25]\to Path})\ \ }
526 \begin{bytefield}{26}
527 \bitheader[b]{11,12,13}\\
528 \bitbox[1]{11}{\raggedleft {\tt move} ({\tt Path} unchanged):}
540 \item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
541 \item {\tt Di} - Data Input: wait for the data predecessor to be full and drain it.
542 \item {\tt Dc} - Data Capture: pulse the data latch.
543 \item {\tt Do} - Data Output: fill the data successor.
544 \item {\tt To} - Token Output: fill the token successor.
547 The data successor and token successor must both be empty in order for
548 a {\tt move} instruction to attempt execution.
550 The inner loop counter can hold a number {\tt 0..MAX} or a special
551 value $\infty$. If {\tt ILC} is nonzero after execution of a {\tt
552 move} instruction, the instruction will execute again, and {\tt ILC}
553 will be latched with {\tt (ILC==$\infty$?$\infty$:max(ILC-1, 0))}. When
554 the inner loop counter reaches zero, the instruction ceases executing.
559 \subsection{{\tt set}}
563 The {\tt set} command is used to set or decrement the inner loop
564 counter, outer loop counter, and data latch.
566 \newcommand{\bitsSet}{
567 \setlength{\bitwidth}{5mm}
569 \begin{bytefield}{26}
570 \bitheader[b]{0,14-15,16-20}\\
585 \begin{tabular}{|r|r|l|l|}\hline
586 Source & SRC & DST & Destination \\\hline
588 Payload & 00 & 00 & OLC \\
589 Data Latch & 01 & 00 & OLC \\
590 OLC-1 & 10 & 00 & OLC \\
591 Payload & 00 & 01 & ILC \\
592 Data Latch & 01 & 01 & ILC \\
593 $\infty$ & 10 & 01 & ILC \\
594 Payload & 00 & 10 & Torpedo Ack Path \\
595 Payload, 0-extend & 01 & 10 & Data Latch \\
596 Payload, 1-extend & 10 & 10 & Data Latch \\
597 see below & & 11 & Flags \\
602 The FleetTwo implementation is likely to have an unarchitected
603 ``literal latch'' at the OD stage, which is loaded with the
604 possibly-extended literal {\it at the time that the {\tt set}
605 instruction comes on deck}. This latch is then copied into the data
606 latch when the instruction executes.
608 If the {\tt Dest} field is flags, the {\tt Payload} field is
609 interpreted as two fields, each giving the truth table for the new
610 value of one of the two user-settable flags:
613 \setlength{\bitwidth}{5mm}
615 \begin{bytefield}{26}
616 \bitheader[b]{0,5,6,11}\\
633 Each field has the following structure, and indicates which old flag
634 values should be logically {\tt OR}ed together to produce the new flag
641 \bitbox{1}{${\text{\tt A}}$}
642 \bitbox{1}{$\overline{\text{\tt A}}$}
643 \bitbox{1}{${\text{\tt B}}$}
644 \bitbox{1}{$\overline{\text{\tt B}}$}
645 \bitbox{1}{${\text{{\tt C}\ }}$}
646 \bitbox{1}{$\overline{\text{{\tt C}\ }}$}
650 Each bit corresponds to one possible input; all inputs whose bits are
651 set are {\tt OR}ed together, and the resulting value is assigned to
652 the flag. Note that if none of the bits are set, the value assigned
653 is zero. Note also that it is possible to produce a {\tt 1} by {\tt
654 OR}ing any flag with its complement, and that {\tt set Flags} can
655 be used to create a {\tt nop} (no-op) by setting each flag to itself.
661 \subsection{{\tt shift}}
665 \newcommand{\shiftPayloadSize}{19}
667 Each {\tt shift} instruction carries a payload of \shiftPayloadSize\
668 bits. When a {\tt shift} instruction is executed, this payload is copied
669 into the least significant \shiftPayloadSize\ bits of the data latch,
670 and the remaining most significant bits of the data latch are loaded
671 with the value formerly in the least significant bits of the data latch.
672 In this manner, large literals can be built up by ``shifting'' them
673 into the data latch \shiftPayloadSize\ bits at a time.
675 \newcommand{\bitsShift}{
676 \setlength{\bitwidth}{5mm}
678 \begin{bytefield}{26}
679 \bitheader[b]{0,18-20}\\
686 \bitbox{\shiftPayloadSize}{Payload}
691 The FleetTwo implementation is likely to have an unarchitected
692 ``literal latch'' at the OD stage, which is loaded with the literal
693 {\it at the time that the {\tt shift} instruction comes on deck}.
694 This latch is then copied into the data latch when the instruction
699 \subsection{{\tt tail}}
701 \newcommand{\bitsTail}{
702 \setlength{\bitwidth}{5mm}
704 \begin{bytefield}{26}
705 \bitheader[b]{19-20}\\
716 When a {\tt tail} instruction reaches {\tt IH}, it seals the hatch.
717 The {\tt tail} instruction does not enter the instruction fifo.
721 %\subsection{{\tt takeOuterLoopCounter}}
723 %\setlength{\bitwidth}{5mm}
725 %\begin{bytefield}{26}
726 % \bitheader[b]{16-19,21}\\
740 %This instruction copies the value in the outer loop counter {\tt OLC}
741 %into the least significant bits of the data latch and leaves all other
742 %bits of the data latch unchanged.
744 %\subsection{{\tt takeInnerLoopCounter}}
746 %\setlength{\bitwidth}{5mm}
748 %\begin{bytefield}{26}
749 % \bitheader[b]{16-19,21}\\
763 %This instruction copies the value in the inner loop counter {\tt ILC}
764 %into the least significant bits of the data latch and leaves all other
765 %bits of the data latch unchanged.
770 %%\subsection{{\tt interrupt}}
772 %%\setlength{\bitwidth}{5mm}
774 %\begin{bytefield}{26}
775 % \bitheader[b]{0,5,16-19,21}\\
786 %When an {\tt interrupt} instruction reaches {\tt IH}, it will wait
787 %there for the {\tt OD} stage to be full with an instruction that has
788 %the {\tt IM} bit set. When this occurs, the instruction at {\tt OD}
789 %{\it will not execute}, but {\it may reloop} if the conditions for
791 %\footnote{The ability to interrupt an instruction yet have it reloop is very
792 %useful for processing chunks of data with a fixed size header and/or
793 %footer and a variable length body.}
796 %\subsection{{\tt massacre}}
798 %\setlength{\bitwidth}{5mm}
800 %\begin{bytefield}{26}
801 % \bitheader[b]{16-19,21}\\
813 %When a {\tt massacre} instruction reaches {\tt IH}, it will wait there
814 %for the {\tt OD} stage to be full with an instruction that has the
815 %{\tt IM} bit set. When this occurs, all instructions in the
816 %instruction fifo (including {\tt OD}) are retired.
818 %\subsection{{\tt clog}}
820 %\setlength{\bitwidth}{5mm}
822 %\begin{bytefield}{26}
823 % \bitheader[b]{16-19,21}\\
835 %When a {\tt clog} instruction reaches {\tt OD}, it remains there and
836 %no more instructions will be executed until an {\tt unclog} is
839 %\subsection{{\tt unclog}}
841 %\setlength{\bitwidth}{5mm}
843 %\begin{bytefield}{26}
844 % \bitheader[b]{16-19,21}\\
850 % \bitbox[lrtb]{2}{11}
856 %When an {\tt unclog} instruction reaches {\tt IH}, it will wait there
857 %until a {\tt clog} instruction is at {\tt OD}. When this occurs, both
858 %instructions retire.
860 %Note that issuing an {\tt unclog} instruction to a dock which is not
861 %clogged and whose instruction fifo contains no {\tt clog} instructions
862 %will cause the dock to deadlock.
867 \section*{\color{red}Instruction Encoding Map\color{black}}
869 \hspace{-1cm}{\tt move}\\
872 \hspace{-1cm}{\tt shift}\\
875 \hspace{-1cm}{\tt set}\\
878 \hspace{-1cm}{\tt tail}\\
885 \epsfig{file=overview,height=5in,angle=90}
888 \subsection*{Input Dock}
889 \epsfig{file=indock,width=7in,angle=90}
892 \subsection*{Output Dock}
893 \epsfig{file=outdock,width=6.5in,angle=90}
897 %\epsfig{file=ports,height=5in,angle=90}
900 %\epsfig{file=best,height=5in,angle=90}