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}AM33: The FleetTwo Dock
70 & \color{red} Factored in Russell Kao's comments (thanks!)\\
71 & \color{red} Added mechanism for setting C-flag from fabric even on outboxes\\
73 & \color{red} Made {\tt OLC} test a predicate-controlled condition\\
74 & \color{red} Rewrote ``on deck'' section \\
75 & \color{red} Added ``{\tt unset}'' value for {\tt ILC}\\
76 & \color{red} Changed {\tt DP} to {\tt DataPredecessor} for clarity\\
79 & added comment about address-to-path ship \\
80 & changed {\tt DST} field of {\tt set} instruction from 2 bits to 3 \\
81 & changed the order of instructions in the encoding map \\
83 & added epilogue fifo to diagrams \\
84 & indicated that a token sent to the instruction port is treated as a torpedo \\
86 & replaced {\tt setInner}, {\tt setOuter}, {\tt setFlags} with unified {\tt set} instruction \\
87 & replaced {\tt literal} with {\tt shift} instruction \\
89 & Made all instructions except {\tt setOuter} depend on {\tt OLC>0} \\
90 & Removed ability to manually set the {\tt C} flag \\
91 & Expanded predicate field to three bits \\
92 & New literals scheme (via shifting) \\
93 & Instruction encoding changes made at Ivan's request (for layout purposes) \\
94 & Added summary of instruction encodings on last page \\
96 %& removed ``+'' from ``potentially torpedoable'' row where it does not occur in Execute \\
98 %& extended {\tt LiteralPath} to 13 bits (impl need not use all of them) \\
99 %& update table 3.1.2 \\
100 %& rename {\tt S} flag to {\tt C} \\
101 %& noted that {\tt setFlags} can be used as {\tt nop} \\
103 %& removed the {\tt L} flag (epilogues can now do this) \\
104 %& removed {\tt take\{Inner|Outer\}LoopCounter} instructions \\
105 %& renamed {\tt data} instruction to {\tt literal} \\
106 %& renamed {\tt send} instruction to {\tt move} \\
108 %& added ``if its predicate is true'' to repeat count \\
109 %& added note that red wires do not contact ships \\
110 %& changed name of {\tt flags} instruction to {\tt setFlags} \\
111 %& removed black dot from diagrams \\
112 %& changed {\tt OL} (Outer Loop participant) to {\tt OS} (One Shot) and inverted polarity \\
113 %& indicated that the death of the {\tt tail} instruction is what causes the hatch to be unsealed \\
114 %& indicated that only {\tt send} instructions which wait for data are torpedoable \\
115 %& added section ``Torpedo Details'' \\
116 %& removed {\tt torpedo} instruction \\
119 %& renamed loop+repeat to outer+inner (not in red) \\
120 %& renamed {\tt Z} flag to {\tt L} flag (not in red) \\
121 %& rewrote ``inner and outer loops'' section \\
122 %& updated all diagrams \\
125 %& Moved address bits to the LSB-side of a 37-bit instruction \\
126 %& Added {\it micro-instruction} and {\it composite instruction} terms \\
127 %& Removed the {\tt DL} field, added {\tt decrement} mode to {\tt loop} \\
128 %& Created the {\tt Hold} field \\
129 %& Changed how ReLooping works \\
130 %& Removed {\tt clog}, {\tt unclog}, {\tt interrupt}, and {\tt massacre} \\
137 \epsfig{file=all,height=1.5in}
138 \epsfig{file=overview-new,height=1.5in}
143 \section{Overview of Fleet}
145 A Fleet processor is organized around a {\it switch fabric}, which is
146 a packet-switched network with reliable in-order delivery. The switch
147 fabric is used to carry data between different functional units,
148 called {\it ships}. Each ship is connected to the switch fabric by
149 one or more programmable elements known as {\it docks}.
151 A {\it path} specifies a route through the switch fabric from a
152 particular {\it source} to a particular {\it destination}. The
153 combination of a path and a single word to be delivered is called a
154 {\it packet}. The switch fabric carries packets from their sources to
155 their destinations. Each dock has two destinations: one for {\it
156 instructions} and one for {\it data}. A Fleet is programmed by
157 depositing instruction packets into the switch fabric with paths that
158 will lead them to instruction destinations of the docks at which they
161 When a packet arrives at the instruction destination of a dock, it is
162 enqueued for execution. Before the instruction executes, it may cause
163 the dock to wait for a packet to arrive at the dock's data destination
164 or for a value to be presented by the ship. When an instruction
165 executes it may consume this data and may present a data value to the
166 ship or transmit a packet.
168 When an instruction sends a packet into the switch fabric, it may
169 specify that the payload of the packet is irrelevant. Such packets
170 are known as {\it tokens}, and consume less energy than data packets.
174 \epsfig{file=overview-new,width=2.5in}\\
175 {\it Overview of a Fleet processor; gray shading represents the switch
176 fabric; docks are shown in blue.}
182 \section{The FleetTwo Dock}
184 The diagram below represents a conceptual view of the interface
185 between ships and the switch fabric; actual implementation circuitry
189 \epsfig{file=all,width=3.5in}\\
190 {\it An ``input'' dock and ``output'' dock connected to a ship. Solid
191 blue lines carry either tokens or data words, red lines carry either
192 instructions or torpedoes, and dashed lines carry only tokens.}
195 Each dock consists of a {\it data latch}, which is as wide as a single
196 machine word and a {\it pump}, which is a circular fifo of
197 instruction-width latches. The values in the pump control the data
198 latch. \color{red}The dock also includes a {\it path latch}, which
199 stores the path along which outgoing packets will be sent.\color{black}
201 Note that the pump in each dock has a destination of its own; this is
202 the {\it instruction destination} mentioned in the previous section.
204 \color{red} From any source to any dock's data destination there are
205 two distinct paths which differ by a single bit. This bit is known as
206 the ``signal'' bit, and the routing of a packet is not affected by it;
207 the signal bit is used to pass control values between docks. Note that paths
208 terminating at an {\it instruction} destination need not have a signal
212 \section{Instructions}
214 In order to cause an instruction to execute, the programmer must first
215 arrange for that instruction word to arrive in the data latch of some
216 output dock. For example, this might be the ``data read'' output dock
217 of the memory access ship or the output of a fifo ship. Once an
218 instruction has arrived at this output dock, it is {\it dispatched} by
219 sending it to the {\it instruction port} of the dock at which it is to
222 Each instruction is 26 bits long, which makes it possible for an
223 instruction and an 11-bit path to fit in a single word of memory.
224 This path is the path from the {\it dispatching} dock to the {\it
227 \setlength{\bitwidth}{3.5mm}
229 \begin{bytefield}{37}
230 \bitheader[b]{0,10,11,36}\\
231 \bitbox{26}{instruction}
232 \bitbox{11}{dispatch path}
238 \subsection{Life Cycle of an Instruction}
240 The diagram below shows an input dock for purposes of illustration:
243 \epsfig{file=in,width=4in}\\
247 Note the mux on the path between {\tt EF} (epilogue fifo) and {\tt IF}
248 (instruction fifo); this is known as ``the hatch''. The hatch has two
249 states: sealed and unsealed. When the machine powers up, the hatch is
250 unsealed; it is sealed by the {\tt tail} instruction and unsealed
251 whenever the outer loop counter is set to zero (for any
252 reason\footnote{this includes {\tt OLC} being decremented to zero, a
253 {\tt set} instruction, or the occurrence
256 When an instruction arrives at the epilogue fifo ({\tt EF}), it waits
257 there until the hatch is in the unsealed state; the instruction then
258 enters the instruction fifo. When an instruction emerges from the
259 instruction fifo, it arrives at the ``on deck'' ({\tt OD}) stage,
260 where it may execute.
263 \epsfig{file=out,width=4in}\\
267 \subsubsection{Torpedoes}
269 A token sent to an instruction destination is called a {\it torpedo}.
270 When a torpedo arrives at the tail of {\tt EF}, it is deposited in a
271 waiting area (not shown) rather than being enqueued into {\tt EF}.
273 There is a latch (not shown) called the {\it torpedo acknowledgment path
274 latch} ({\tt TAPL}) which stores a path. When a torpedo is consumed
275 (see section ``On Deck''), a token is sent along the path held in this
278 \subsection{Format of an Instruction}
280 All instruction words have the following format:
282 \newcommand{\bitsHeader}{
288 \setlength{\bitwidth}{3.5mm}
290 \begin{bytefield}{37}
291 \bitheader[b]{0,10,11,31,32,34-36}\\
296 \bitbox{11}{dispatch path}
301 \item The {\tt I} bit stands for {\tt Interruptible}, and indicates if an
302 instruction is vulnerable to torpedoes.
304 \item The {\tt OS} (``One Shot'') bit indicates whether or not this
305 instruction can pass through the pump more than once. If set to
306 {\tt 1}, then the instruction is a ``one-shot'' instruction, and
307 does not pass through the instruction fifo more than once.
309 \item The {\tt P} bits are a {\it predicate}; this
310 holds a code which indicates if the instruction should be executed or
311 ignored depending on the state of flags in the dock.
315 \subsection{Loop Counters}
317 A programmer can perform two types of loops: {\it inner} loops of only
318 one instruction and {\it outer} loops of multiple instructions. Inner
319 loops may be nested within an outer loop, but no other nesting of
323 The dock has two loop counters, one for each kind of loop:
326 \item {\tt OLC} is the Outer Loop Counter
327 \item {\tt ILC} is the Inner Loop Counter
330 The {\tt OLC} applies to all instructions and can hold integers {\tt
333 The {\tt ILC} applies only to {\tt move} instructions and can hold
334 integers {\tt 0..MAX_ILC} as well as a special value: $\infty$. When
335 {\tt ILC=0} the next {\tt move} instruction executes zero times (ie is
336 ignored). When {\tt ILC=$\infty$} the next {\tt move} instruction
337 executes until interrupted by a torpedo. After every {\tt move}
338 instruction the {\tt ILC} is reset to {\tt 1} (note that it is reset
339 to {\tt 1}, {\it not to 0}).
342 \subsection{Flags and Predication}
344 The pump has three flags: {\tt A}, {\tt B}, and {\tt C}.
347 \item The {\tt A} and {\tt B} flags are general-purpose flags which
348 may be set and cleared by the programmer.
352 % The {\tt L} flag, known as the {\it last} flag, is set whenever
353 % the value in the outer counter ({\tt OLC}) is one,
356 % that the dock is in the midst of the last iteration of an
357 % outer loop. This flag can be used to perform certain
358 % operations (such as sending a completion token) only on the last
359 % iteration of an outer loop.
362 \item The {\tt C} flag is known as the {\it control} flag, and may be
363 set by the {\tt move} instruction based on information from the
364 ship or from an inbound packet. See the {\tt move} instruction
372 The {\tt P} field specifies a three-bit {\it predicate}. The
373 predicate determines which conditions must be true in order for the
374 instruction to execute; if it is not executed, it is simply {\it
375 ignored}. The table below shows what conditions must be true in
376 order for an instruction to execute:
380 \begin{tabular}{|r|ll|}\hline
381 \color{red}Code & Execute & if \\\hline
382 {\tt 000:} & {\tt OLC$\neq$0} & and {\tt A=0} \\
383 {\tt 001:} & {\tt OLC$\neq$0} & and {\tt A=1} \\
384 {\tt 010:} & {\tt OLC$\neq$0} & and {\tt B=0} \\
385 {\tt 011:} & {\tt OLC$\neq$0} & and {\tt B=1} \\
386 {\tt 100:} & {\tt OLC$\neq$0} & and {\tt C=0} \\
387 {\tt 101:} & {\tt OLC$\neq$0} & and {\tt C=1} \\
388 {\tt 110:} & {\tt OLC$\neq$0} & \\
389 {\tt 111:} & always & \\
398 When an instruction arrives on deck, two concurrent processes are
399 started. No subsequent instruction may come on deck until both
400 processes have completed:
406 \item If the outer loop counter is zero ({\tt OLC=0}) or the
407 instruction on deck is a one-shot instruction ({\tt
409 \item {\it Otherwise} wait for the hatch to be sealed and
410 enqueue a copy of the instruction currently on deck.
417 If the instruction's predicate condition is not met (see
418 section on predicates), do nothing.
421 {\it Otherwise} if the instruction is interruptible ({\tt I=0})
422 and a torpedo is present in the waiting area: consume the
423 torpedo, set the outer loop counter to zero ({\tt OLC=0}),
424 unseal the hatch, and transmit a token along in the
425 {\it torpedo acknowledgment path latch} ({\tt TAPL}).
428 {\it Otherwise} if {\tt ILC$\neq$0} or the instruction is {\it
429 not} a {\tt move}: execute the instruction.
438 \section{Instructions}
440 The dock supports for instructions:
441 {\tt move} (variants: {\tt moveto}, {\tt dispatch}),
448 \subsection{{\tt move} (variants: {\tt moveto}, {\tt dispatch})}
450 \newcommand{\bitsMove}{\setlength{\bitwidth}{5mm}
452 \begin{bytefield}{26}
453 \bitheader[b]{14-20}\\
467 \begin{bytefield}{26}
468 \bitheader[b]{0,12,13}\\
469 \bitbox[1]{11}{\raggedleft {\tt moveto} ({\tt Payload\to Path})}
472 \bitbox{13}{\tt Payload}
475 \begin{bytefield}{26}
476 \bitheader[b]{11,12,13}\\
477 \bitbox[1]{11}{\raggedleft {\tt dispatch} ({\footnotesize {\tt DataPredecessor[37:25]\to Path}})\ \ }
486 \begin{bytefield}{26}
487 \bitheader[b]{11,12,13}\\
488 \bitbox[1]{11}{\raggedleft {\tt move} ({\tt Path} unchanged):}
499 \item {\tt Ti} - Token Input: wait for the token predecessor to be full and drain it.
500 \item {\tt Di} - Data Input: wait for the data predecessor to be full and drain it.
501 \item {\tt Dc} - Data Capture: pulse the data latch.
502 \item {\tt Do} - Data Output: fill the data successor.
503 \item {\tt To} - Token Output: fill the token successor.
506 The data successor and token successor must both be empty in order for
507 a {\tt move} instruction to attempt execution.
511 Every time the {\tt move} instruction executes, the {\tt C} flag may
515 \item At an {\it input} dock the {\tt C} flag is set to the signal bit
516 of the incoming packet if {\tt Di} or {\tt Ti} is set.
518 \item At an {\it output} dock the {\tt C} flag is set to a value
519 provided by the ship if the {\tt Di} bit is set, and to the
520 signal bit of the incoming packet if {\tt Di} is clear and {\tt
528 \subsection{{\tt set}}
530 The {\tt set} command is used to set or decrement the inner loop
531 counter, outer loop counter, and data latch.
533 \newcommand{\bitsSet}{
534 \setlength{\bitwidth}{5mm}
536 \begin{bytefield}{26}
537 \bitheader[b]{0,13-15,16-20}\\
552 \begin{tabular}{|r|r|l|l|}\hline
553 Source & SRC & DST & Destination \\\hline
555 Payload & 00 & 000 & OLC \\
556 Data Latch & 01 & 000 & OLC \\
557 OLC-1 & 10 & 000 & OLC \\
558 Payload & 00 & 001 & ILC \\
559 Data Latch & 01 & 001 & ILC \\
560 $\infty$ & 10 & 001 & ILC \\
561 Payload & 00 & 010 & TAPL \\
562 Payload, 0-extend & 01 & 100 & Data Latch \\
563 Payload, 1-extend & 10 & 100 & Data Latch \\
564 see below & & 111 & Flags \\
569 The FleetTwo implementation is likely to have an unarchitected
570 ``literal latch'' at the on deck ({\tt OD}) stage, which is loaded
571 with the possibly-extended literal {\it at the time that the {\tt set}
572 instruction comes on deck}. This latch is then copied into the data
573 latch when \color{red}a {\tt set Data Latch} instruction
574 executes\color{black}.
576 If the {\tt Dest} field is {\tt flags}, the {\tt Payload} field is
577 interpreted as two fields, each giving the truth table for the new
578 value of one of the two user-settable flags:
581 \setlength{\bitwidth}{5mm}
583 \begin{bytefield}{26}
584 \bitheader[b]{0,5,6,11}\\
601 Each field has the following structure, and indicates which old flag
602 values should be logically {\tt OR}ed together to produce the new flag
609 \bitbox{1}{${\text{\tt A}}$}
610 \bitbox{1}{$\overline{\text{\tt A}}$}
611 \bitbox{1}{${\text{\tt B}}$}
612 \bitbox{1}{$\overline{\text{\tt B}}$}
613 \bitbox{1}{${\text{{\tt C}\ }}$}
614 \bitbox{1}{$\overline{\text{{\tt C}\ }}$}
618 Each bit corresponds to one possible input; all inputs whose bits are
619 set are {\tt OR}ed together, and the resulting value is assigned to
620 the flag. Note that if none of the bits are set, the value assigned
621 is zero. Note also that it is possible to produce a {\tt 1} by {\tt
622 OR}ing any flag with its complement, and that {\tt set Flags} can
623 be used to create a {\tt nop} (no-op) by setting each flag to itself.
629 \subsection{{\tt shift}}
631 \newcommand{\shiftPayloadSize}{19}
633 Each {\tt shift} instruction carries a payload of \shiftPayloadSize\
634 bits. When a {\tt shift} instruction is executed, this payload is copied
635 into the least significant \shiftPayloadSize\ bits of the data latch,
636 and the remaining most significant bits of the data latch are loaded
637 with the value formerly in the least significant bits of the data latch.
638 In this manner, large literals can be built up by ``shifting'' them
639 into the data latch \shiftPayloadSize\ bits at a time.
641 \newcommand{\bitsShift}{
642 \setlength{\bitwidth}{5mm}
644 \begin{bytefield}{26}
645 \bitheader[b]{0,18-20}\\
652 \bitbox{\shiftPayloadSize}{Payload}
657 The FleetTwo implementation is likely to have an unarchitected
658 ``literal latch'' at the on deck ({\tt OD}) stage, which is loaded
659 with the literal {\it at the time that the {\tt shift} instruction
660 comes on deck}. This latch is then copied into the data latch when
661 the instruction executes.
665 \subsection{{\tt tail}}
667 \newcommand{\bitsTail}{
668 \setlength{\bitwidth}{5mm}
670 \begin{bytefield}{26}
671 \bitheader[b]{19-20}\\
682 When a {\tt tail} instruction reaches the hatch, it seals the hatch.
683 The {\tt tail} instruction does not enter the instruction fifo.
687 %\subsection{{\tt takeOuterLoopCounter}}
689 %\setlength{\bitwidth}{5mm}
691 %\begin{bytefield}{26}
692 % \bitheader[b]{16-19,21}\\
706 %This instruction copies the value in the outer loop counter {\tt OLC}
707 %into the least significant bits of the data latch and leaves all other
708 %bits of the data latch unchanged.
710 %\subsection{{\tt takeInnerLoopCounter}}
712 %\setlength{\bitwidth}{5mm}
714 %\begin{bytefield}{26}
715 % \bitheader[b]{16-19,21}\\
729 %This instruction copies the value in the inner loop counter {\tt ILC}
730 %into the least significant bits of the data latch and leaves all other
731 %bits of the data latch unchanged.
736 %%\subsection{{\tt interrupt}}
738 %%\setlength{\bitwidth}{5mm}
740 %\begin{bytefield}{26}
741 % \bitheader[b]{0,5,16-19,21}\\
752 %When an {\tt interrupt} instruction reaches {\tt IH}, it will wait
753 %there for the {\tt OD} stage to be full with an instruction that has
754 %the {\tt IM} bit set. When this occurs, the instruction at {\tt OD}
755 %{\it will not execute}, but {\it may reloop} if the conditions for
757 %\footnote{The ability to interrupt an instruction yet have it reloop is very
758 %useful for processing chunks of data with a fixed size header and/or
759 %footer and a variable length body.}
762 %\subsection{{\tt massacre}}
764 %\setlength{\bitwidth}{5mm}
766 %\begin{bytefield}{26}
767 % \bitheader[b]{16-19,21}\\
779 %When a {\tt massacre} instruction reaches {\tt IH}, it will wait there
780 %for the {\tt OD} stage to be full with an instruction that has the
781 %{\tt IM} bit set. When this occurs, all instructions in the
782 %instruction fifo (including {\tt OD}) are retired.
784 %\subsection{{\tt clog}}
786 %\setlength{\bitwidth}{5mm}
788 %\begin{bytefield}{26}
789 % \bitheader[b]{16-19,21}\\
801 %When a {\tt clog} instruction reaches {\tt OD}, it remains there and
802 %no more instructions will be executed until an {\tt unclog} is
805 %\subsection{{\tt unclog}}
807 %\setlength{\bitwidth}{5mm}
809 %\begin{bytefield}{26}
810 % \bitheader[b]{16-19,21}\\
816 % \bitbox[lrtb]{2}{11}
822 %When an {\tt unclog} instruction reaches {\tt IH}, it will wait there
823 %until a {\tt clog} instruction is at {\tt OD}. When this occurs, both
824 %instructions retire.
826 %Note that issuing an {\tt unclog} instruction to a dock which is not
827 %clogged and whose instruction fifo contains no {\tt clog} instructions
828 %will cause the dock to deadlock.
833 \section*{Instruction Encoding Map\color{black}}
835 \hspace{-1cm}{\tt shift}\\
838 \hspace{-1cm}{\tt set}\\
841 \hspace{-1cm}{\tt move}\\
844 \hspace{-1cm}{\tt tail}\\
851 \epsfig{file=all,height=5in,angle=90}
854 \subsection*{Input Dock}
855 \epsfig{file=in,width=8in,angle=90}
858 \subsection*{Output Dock}
859 \epsfig{file=out,width=8in,angle=90}
863 %\epsfig{file=ports,height=5in,angle=90}
866 %\epsfig{file=best,height=5in,angle=90}