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}
385 There is a small fifo marked ``Epilogue'' just beyond the instruction
386 destination; after the {\tt tail} instruction seals the hatch, any
387 subsequent instructions will queue up in this fifo until the hatch is
388 unsealed. This is typically used as storage for a ``loop epilogue''
389 -- a sequence of instructions to be executed after a torpedo arrives
390 or the outer loop counter expires.
392 A {\it token} sent to a ship's instruction destination is treated as a
393 torpedo; the check for a torpedo is performed {\it before} the head of
394 the Epilogue fifo. Note that because the check for a token is
395 performed ``upstream'' of the epilogue fifo, torpedos will still be
396 effective even when the Epilogue fifo is nearly full.
399 The dock also has a {\it torpedo acknowledgment path latch},
400 which stores the path along which a token should be sent when a
403 When a data item or token arrives at the torpedo destination, it lies
404 there in wait until On Deck holds a potentially torpedoable
405 instruction (see previous table). Once this is the case, the torpedo
406 causes the inner and outer loop counters to be set to zero (and
407 therefore also unseals the hatch)\footnote{it is unspecified whether
408 the torpedoed instruction is requeued or not; this may or may not
409 occur, nondeterministically. It is the programmer's responsibility
410 to ensure that the program behaves the same whether this happens or
411 not. We think that this will not matter in most situations.} and
412 sends a token along the path stored in the torpedo acknowledgment path
419 The pump has three flags: {\tt A}, {\tt B}, and {\tt C}.
422 \item The {\tt A} and {\tt B} flags are general-purpose flags which
423 may be set and cleared by the programmer.
427 % The {\tt L} flag, known as the {\it last} flag, is set whenever
428 % the value in the outer counter ({\tt OLC}) is one,
431 % that the dock is in the midst of the last iteration of an
432 % outer loop. This flag can be used to perform certain
433 % operations (such as sending a completion token) only on the last
434 % iteration of an outer loop.
436 \item The {\tt C} flag is known as the {\it control} flag, and it is
437 set every time the data latch takes on a new value. At outboxes
438 its value is determined by the ship; at inboxes its value is
439 copied from an unused address bit in the destination to which
440 the received value was sent.
443 Many instruction fields are specified as
444 three-bit {\it predicates}. These fields
445 contain one of eight values, indicating if an action should be taken
446 unconditionally or conditionally on one of the {\tt A}, {\tt B}, or
451 \item {\tt 000:} if {\tt A} is set
452 \item {\tt 001:} if {\tt A} is cleared
453 \item {\tt 010:} if {\tt B} is set
454 \item {\tt 011:} if {\tt B} is cleared
457 \item {\tt 100:} if {\tt C} is set
458 \item {\tt 101:} if {\tt C} is cleared
459 \item {\tt 110:} unused
460 \item {\tt 111:} always
467 \section{Instructions}
469 Here is a list of the instructions supported by the dock:
472 \begin{tabular}{|l|}\hline
473 {\tt move} (variants: {\tt moveto}, {\tt dispatch}) \\
486 \subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
488 \newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
490 \begin{bytefield}{26}
491 \bitheader[b]{14-20}\\
505 \begin{bytefield}{26}
506 \bitheader[b]{0,12,13}\\
507 \bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt LiteralPath\to Path})}
510 \bitbox{13}{\tt LiteralPath}
513 \begin{bytefield}{26}
514 \bitheader[b]{11,12,13}\\
515 \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\tt DP[37:25]\to Path})\ \ }
525 \begin{bytefield}{26}
526 \bitheader[b]{11,12,13}\\
527 \bitbox[1]{11}{\raggedleft {\tt move} ({\tt Path} unchanged):}
539 \item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
540 \item {\tt Di} - Data Input: wait for the data predecessor to be full and drain it.
541 \item {\tt Dc} - Data Capture: pulse the data latch.
542 \item {\tt Do} - Data Output: fill the data successor.
543 \item {\tt To} - Token Output: fill the token successor.
546 The data successor and token successor must both be empty in order for
547 a {\tt move} instruction to attempt execution.
549 The inner loop counter can hold a number {\tt 0..MAX} or a special
550 value $\infty$. If {\tt ILC} is nonzero after execution of a {\tt
551 move} instruction, the instruction will execute again, and {\tt ILC}
552 will be latched with {\tt (ILC==$\infty$?$\infty$:max(ILC-1, 0))}. When
553 the inner loop counter reaches zero, the instruction ceases executing.
558 \subsection{{\tt set}}
560 The {\tt set} command is used to set or decrement the inner loop
561 counter, outer loop counter, and data latch.
563 \newcommand{\bitsSet}{
564 \setlength{\bitwidth}{5mm}
566 \begin{bytefield}{26}
567 \bitheader[b]{0,14-15,16-20}\\
582 \begin{tabular}{|r|r|l|l|}\hline
583 Source & SRC & DST & Destination \\\hline
585 Payload & 00 & 00 & OLC \\
586 Data Latch & 01 & 00 & OLC \\
587 OLC-1 & 10 & 00 & OLC \\
588 Payload & 00 & 01 & ILC \\
589 Data Latch & 01 & 01 & ILC \\
590 $\infty$ & 10 & 01 & ILC \\
591 Payload & 00 & 10 & Torpedo Ack Path \\
592 Payload, 0-extend & 01 & 10 & Data Latch \\
593 Payload, 1-extend & 10 & 10 & Data Latch \\
594 see below & & 11 & Flags \\
599 The FleetTwo implementation is likely to have an unarchitected
600 ``literal latch'' at the OD stage, which is loaded with the
601 possibly-extended literal {\it at the time that the {\tt set}
602 instruction comes on deck}. This latch is then copied into the data
603 latch when the instruction executes.
605 If the {\tt Dest} field is flags, the {\tt Payload} field is
606 interpreted as two fields, each giving the truth table for the new
607 value of one of the two user-settable flags:
610 \setlength{\bitwidth}{5mm}
612 \begin{bytefield}{26}
613 \bitheader[b]{0,5,6,11}\\
630 Each field has the following structure, and indicates which old flag
631 values should be logically {\tt OR}ed together to produce the new flag
638 \bitbox{1}{${\text{\tt A}}$}
639 \bitbox{1}{$\overline{\text{\tt A}}$}
640 \bitbox{1}{${\text{\tt B}}$}
641 \bitbox{1}{$\overline{\text{\tt B}}$}
642 \bitbox{1}{${\text{{\tt C}\ }}$}
643 \bitbox{1}{$\overline{\text{{\tt C}\ }}$}
647 Each bit corresponds to one possible input; all inputs whose bits are
648 set are {\tt OR}ed together, and the resulting value is assigned to
649 the flag. Note that if none of the bits are set, the value assigned
650 is zero. Note also that it is possible to produce a {\tt 1} by {\tt
651 OR}ing any flag with its complement, and that {\tt set Flags} can
652 be used to create a {\tt nop} (no-op) by setting each flag to itself.
658 \subsection{{\tt shift}}
660 \newcommand{\shiftPayloadSize}{19}
662 Each {\tt shift} instruction carries a payload of \shiftPayloadSize\
663 bits. When a {\tt shift} instruction is executed, this payload is copied
664 into the least significant \shiftPayloadSize\ bits of the data latch,
665 and the remaining most significant bits of the data latch are loaded
666 with the value formerly in the least significant bits of the data latch.
667 In this manner, large literals can be built up by ``shifting'' them
668 into the data latch \shiftPayloadSize\ bits at a time.
670 \newcommand{\bitsShift}{
671 \setlength{\bitwidth}{5mm}
673 \begin{bytefield}{26}
674 \bitheader[b]{0,18-20}\\
681 \bitbox{\shiftPayloadSize}{Payload}
686 The FleetTwo implementation is likely to have an unarchitected
687 ``literal latch'' at the OD stage, which is loaded with the literal
688 {\it at the time that the {\tt shift} instruction comes on deck}.
689 This latch is then copied into the data latch when the instruction
694 \subsection{{\tt tail}}
696 \newcommand{\bitsTail}{
697 \setlength{\bitwidth}{5mm}
699 \begin{bytefield}{26}
700 \bitheader[b]{19-20}\\
711 When a {\tt tail} instruction reaches {\tt IH}, it seals the hatch.
712 The {\tt tail} instruction does not enter the instruction fifo.
716 %\subsection{{\tt takeOuterLoopCounter}}
718 %\setlength{\bitwidth}{5mm}
720 %\begin{bytefield}{26}
721 % \bitheader[b]{16-19,21}\\
735 %This instruction copies the value in the outer loop counter {\tt OLC}
736 %into the least significant bits of the data latch and leaves all other
737 %bits of the data latch unchanged.
739 %\subsection{{\tt takeInnerLoopCounter}}
741 %\setlength{\bitwidth}{5mm}
743 %\begin{bytefield}{26}
744 % \bitheader[b]{16-19,21}\\
758 %This instruction copies the value in the inner loop counter {\tt ILC}
759 %into the least significant bits of the data latch and leaves all other
760 %bits of the data latch unchanged.
765 %%\subsection{{\tt interrupt}}
767 %%\setlength{\bitwidth}{5mm}
769 %\begin{bytefield}{26}
770 % \bitheader[b]{0,5,16-19,21}\\
781 %When an {\tt interrupt} instruction reaches {\tt IH}, it will wait
782 %there for the {\tt OD} stage to be full with an instruction that has
783 %the {\tt IM} bit set. When this occurs, the instruction at {\tt OD}
784 %{\it will not execute}, but {\it may reloop} if the conditions for
786 %\footnote{The ability to interrupt an instruction yet have it reloop is very
787 %useful for processing chunks of data with a fixed size header and/or
788 %footer and a variable length body.}
791 %\subsection{{\tt massacre}}
793 %\setlength{\bitwidth}{5mm}
795 %\begin{bytefield}{26}
796 % \bitheader[b]{16-19,21}\\
808 %When a {\tt massacre} instruction reaches {\tt IH}, it will wait there
809 %for the {\tt OD} stage to be full with an instruction that has the
810 %{\tt IM} bit set. When this occurs, all instructions in the
811 %instruction fifo (including {\tt OD}) are retired.
813 %\subsection{{\tt clog}}
815 %\setlength{\bitwidth}{5mm}
817 %\begin{bytefield}{26}
818 % \bitheader[b]{16-19,21}\\
830 %When a {\tt clog} instruction reaches {\tt OD}, it remains there and
831 %no more instructions will be executed until an {\tt unclog} is
834 %\subsection{{\tt unclog}}
836 %\setlength{\bitwidth}{5mm}
838 %\begin{bytefield}{26}
839 % \bitheader[b]{16-19,21}\\
845 % \bitbox[lrtb]{2}{11}
851 %When an {\tt unclog} instruction reaches {\tt IH}, it will wait there
852 %until a {\tt clog} instruction is at {\tt OD}. When this occurs, both
853 %instructions retire.
855 %Note that issuing an {\tt unclog} instruction to a dock which is not
856 %clogged and whose instruction fifo contains no {\tt clog} instructions
857 %will cause the dock to deadlock.
862 \section*{Instruction Encoding Map\color{black}}
864 \hspace{-1cm}{\tt move}\\
867 \hspace{-1cm}{\tt shift}\\
870 \hspace{-1cm}{\tt set}\\
873 \hspace{-1cm}{\tt tail}\\
880 \epsfig{file=overview,height=5in,angle=90}
883 \subsection*{Input Dock}
884 \epsfig{file=indock,width=7in,angle=90}
887 \subsection*{Output Dock}
888 \epsfig{file=outdock,width=6.5in,angle=90}
892 %\epsfig{file=ports,height=5in,angle=90}
895 %\epsfig{file=best,height=5in,angle=90}