doc/archman.tex

   1 \documentclass[10pt,oneside]{book}
   2 \reversemarginpar
   3 \usepackage{palatino}
   4 \usepackage{epsfig}
   5 \usepackage{parskip}
   6 \usepackage{register}
   7 \usepackage{bytefield}
   8 \renewcommand{\ttdefault}{cmtt}
   9 \title{The FleetTwo Architecture Manual}
  10 \begin{document}
  11 \maketitle
  12 \pagebreak
  13 \section*{Glossary}
  14
  15 Port\\
  16 Inlet\\
  17 Outlet\\
  18 Pump\\
  19 Packet\\
  20 Data Item\\
  21 Opcode Port\\
  22 Bypass\\
  23
  24
  25 \pagebreak
  26 \section*{Programmer's View of The Ship-Fabric Interface}
  27
  28 The diagram below represents a {\it programmer's} conceptual view of
  29 the interface between ships and the switch fabric.  Actual
  30 implementations may differ radically, as long as such differences are
  31 not visible to software programs.
  32
  33 %\begin{wrapfigure}{R}{2in}
  34 \epsfig{file=ports,width=6in}
  35 %\end{wrapfigure}
  36
  37 The term {\it port} refers to each interface to the ship (either
  38 inbound or outbound) and the machinery required to manage this
  39 interface.  The machinery consists of a {\it latch}, which is as wide
  40 as a single machine word, a {\it pump}, which is a circular fifo of
  41 instruction-width latches, and a number of {\it sources} or {\it
  42   destinations}.  Sources and destinations which can only send or
  43 recieve tokens (rather than data items) are drawn as dashed lines.
  44 Buffering fifos are drawn where they appear.
  45
  46 Note in particular that every pump is a destination capable of
  47 recieving a data word.  This is how instructions are dispatched to
  48 pumps -- they are inserted into the switch fabric as {\it packets}
  49 whose destination addresses
  50
  51 Note that addresses are actually paths.
  52
  53 Define packets.
  54
  55
  56
  57 \pagebreak
  58 \section*{Data Formats}
  59
  60 \subsection*{Packet Destination Address (12 bits)}
  61
  62 These bits appear physically within the switch fabric, and have
  63 ``address bit timing.''  The {\tt T} bit is the ``tokenhood'' bit; if
  64 set, this packet represents a token and it does not cause the switch
  65 fabric data latches to fire.
  66
  67 {\tt\footnotesize
  68 \begin{bytefield}{49}
  69   \bitheader[b]{37,47,48}\\
  70   \bitbox{1}{T}
  71   \bitbox{11}{Destination Address}
  72   \bitbox[l]{37}{}
  73 \end{bytefield}
  74 }
  75
  76 \subsection*{Data Word In Memory (37 bits)}
  77
  78 A word of memory is 37 bits wide.  For convenience, we assume that the
  79 memory word width is also the width of a pointer as well as the width
  80 of all on-chip data item registers.
  81
  82 {\tt\footnotesize
  83 \begin{bytefield}{49}
  84   \bitheader[b]{0,36}\\
  85   \bitbox[r]{12}{}
  86   \bitbox{37}{Data Word}
  87 \end{bytefield}
  88 }
  89
  90 \subsection*{Data Packet In Flight (49 bits)}
  91
  92 A {\it data packet} is a data item in the switch fabric, on its way to
  93 some destination.
  94
  95 {\tt\footnotesize
  96 \begin{bytefield}{49}
  97   \bitheader[b]{0,36,37,47,48}\\
  98   \bitbox{1}{T}
  99   \bitbox{11}{Destination Address}
 100   \bitbox{37}{Data Word}
 101 \end{bytefield}
 102 }
 103
 104 \subsection*{Instruction In Memory (37 bits)}
 105
 106 An instruction must be no wider than a memory word.  The next section
 107 explains the bits in greater detail.
 108
 109 {\tt\tiny
 110 \begin{bytefield}{49}
 111   \bitheader[b]{0,10,11,17,18-26,36}\\
 112   \bitbox[r]{12}{}
 113   \bitbox{11}{Instruction Register Address}
 114   \bitbox{1}{K}
 115   \bitbox{1}{L}
 116   \bitbox{1}{Ti}
 117   \bitbox{1}{Di}
 118   \bitbox{1}{Dc}
 119   \bitbox{1}{Do}
 120   \bitbox{1}{To}
 121   \bitbox{1}{Rq}
 122   \bitbox{7}{Count}
 123   \bitbox{11}{Data/Token Destination}
 124 \end{bytefield}
 125 }
 126
 127 \subsection*{Instruction Packet In Flight (49 bits)}
 128
 129 A {\it instruction packet} is an instruction in the instruction horn
 130 (which may or may not be the same thing as the data horn), on its way
 131 to some instruction register (Valve).
 132
 133 {\tt\tiny
 134 \begin{bytefield}{49}
 135   \bitheader[b]{0,10,11,17,18-25,37,47,48}\\
 136   \bitbox[r]{1}{0}
 137   \bitbox{11}{Instruction Register Address}
 138   \bitbox[lr]{11}{}
 139   \bitbox{1}{K}
 140   \bitbox{1}{L}
 141   \bitbox{1}{Ti}
 142   \bitbox{1}{Di}
 143   \bitbox{1}{Dc}
 144   \bitbox{1}{Do}
 145   \bitbox{1}{To}
 146   \bitbox{1}{Rq}
 147   \bitbox{7}{Count}
 148   \bitbox{11}{Data/Token Destination}
 149 \end{bytefield}
 150 }
 151
 152
 153 \pagebreak
 154
 155 \section*{Instruction Formats}
 156
 157 Instructions can be grouped into two categories: {\it killing}
 158 instructions, which are acted upon as soon as they leave the
 159 instruction horn, and {\it executing} instructions, which pass through
 160 the instruction queue before being acted upon.
 161
 162 Blank fields below are reserved for future use and must be set to
 163 zero.
 164
 165 Note that the arbiter is requested whenever {\it any of the first
 166   three bits is {\tt 1}}.  If the arbiter is not requested,
 167
 168
 169
 170 \setlength{\bitwidth}{5mm}
 171
 172 \subsection*{Killing Instructions}
 173
 174 Kill (kill anything other than a Clog)
 175
 176 {\tt
 177 \begin{bytefield}{26}
 178   \bitheader[b]{0,6,7,20-25}\\
 179   \bitbox{1}{0}
 180   \bitbox{1}{0}
 181   \bitbox{1}{1}
 182   \bitbox{1}{0}
 183   \bitbox{1}{1}
 184   \bitbox{14}{}
 185   \bitbox{7}{Count}
 186 \end{bytefield}}
 187
 188 UnClog (kill a Clog)
 189
 190 {\tt
 191 \begin{bytefield}{26}
 192   \bitheader[b]{0,20-25}\\
 193   \bitbox{1}{0}
 194   \bitbox{1}{0}
 195   \bitbox{1}{0}
 196   \bitbox{1}{1}
 197   \bitbox{1}{0}
 198   \bitbox{21}{}
 199 \end{bytefield}}
 200
 201 \subsection*{Executing Instructions}
 202 Clog
 203
 204 {\tt
 205 \begin{bytefield}{26}
 206   \bitheader[b]{0,20-25}\\
 207   \bitbox{1}{0}
 208   \bitbox{1}{0}
 209   \bitbox{1}{1}
 210   \bitbox{1}{0}
 211   \bitbox{1}{0}
 212   \bitbox{21}{}
 213 \end{bytefield}}
 214
 215 Literal (sign extended, implicit {\tt Rq=1})
 216
 217 {\tt
 218 \begin{bytefield}{26}
 219   \bitheader[b]{0,6,7,23-25}\\
 220   \bitbox{1}{0}
 221   \bitbox{1}{1}
 222   \bitbox{17}{Literal}
 223   \bitbox{7}{Count}
 224 \end{bytefield}}
 225
 226
 227 Normal
 228
 229 {\tt
 230 \begin{bytefield}{26}
 231   \bitheader[b]{0,6,7,17-25}\\
 232   \bitbox{1}{1}
 233   \bitbox{1}{Ti}
 234   \bitbox{1}{Di}
 235   \bitbox{1}{Dc}
 236   \bitbox{1}{Do}
 237   \bitbox{1}{To}
 238   \bitbox{1}{Ig}
 239   \bitbox{1}{Rq}
 240   \bitbox{11}{Dest}
 241   \bitbox{7}{Count}
 242 \end{bytefield}}
 243
 244
 245
 246
 247 \pagebreak
 248 \subsection*{Field Descriptions}
 249 {\tt
 250 \begin{bytefield}{26}
 251   \bitheader[b]{0,6,7,16-25}\\
 252   \bitbox{1}{0}
 253   \bitbox{1}{Ti}
 254   \bitbox{1}{Di}
 255   \bitbox{1}{Dc}
 256   \bitbox{1}{Do}
 257   \bitbox{1}{To}
 258   \bitbox{1}{Ig}
 259   \bitbox{1}{Rq}
 260   \bitbox{11}{Dest}
 261   \bitbox{7}{Count}
 262 \end{bytefield}
 263 }
 264
 265 \begin{itemize}
 266
 267   \item [\tt Ti] ({\bf Token Input}) wait for a token and accept
 268                  it\footnote{{\tt Ti}=1,{\tt Di}=1 is invalid on inbox.}
 269
 270   \item [\tt Di] ({\bf Data Input}) wait for a datum and accept it.
 271
 272   \item [\tt Dc] ({\bf Data Capture}) capture (latch) the accepted
 273                  datum.  This bit is ignored if the incoming packet is
 274                  a token. \footnote{ Note that {\tt Di}=0,{\tt Dc}=1
 275                  is meaningless and therefore reserved for other
 276                  uses.}
 277
 278   \item [\tt Do] ({\bf Data Output}) emit a datum.
 279
 280   \item [\tt To] ({\bf Token Output}) emit a token.\footnote{ {\tt To}=1,{\tt
 281                  Do}=1 have special meaning on an outbox.}
 282
 283   \item [\tt Ig] ({\bf Ignore {\tt To} Until Last Iteration}) ignore
 284                  the {\tt To} bit unless {\tt Count=0} \footnote{{\tt
 285                  To}=0,{\tt Ig}=1 is invalid}
 286
 287   \item [\tt Rq] ({\bf ReQueue}) if set, instructions having nonzero
 288                  count are ``Re-Queued'' rather than RePeated.  See
 289                  {\tt Count} for more detail. \footnote{ An
 290                  instruction {\it in memory} may not have {\tt
 291                  Rq=1,Count=0} (use {\tt Rq=0,Count=0})}
 292
 293   \item  [\tt Count] ({\bf Count}) {\it After} executing:
 294 \begin{verbatim}
 295 if (Count==0) {
 296     discard this instruction
 297 } else {
 298     if Count < MAX_COUNT {
 299       decrement count
 300     }
 301     if Rq=1 or Literal {
 302        put this instruction back into the instruction fifo
 303     } else {
 304        execute this instruction again
 305     }
 306 }
 307 \end{verbatim}
 308 Note how a ``standing'' instruction is encoded as {\tt Count=1111111}
 309
 310 \item [\tt Dest] ({\bf Data/Token Destination})
 311    Normally, this field is copied into the address portion of any
 312    outgoing packet ({\tt Do} on an outbox or {\tt To}).
 313
 314    However, in the special case of an outbox, if {\tt Do=1,To=1}, then
 315    the {\it most significant} {\tt 11} bits of the value in the {\it
 316    data register} are used as a destination address instead.  \footnote{This
 317    functionality eliminates the need for any sort of ``{\tt Execute}''
 318    ship, and lets a {\tt Fifo} ship act as an extension of the
 319    instruction queue in the pump.}
 320
 321 \end{itemize}
 322
 323 \pagebreak
 324 \section{Future Directions}
 325
 326 Looking back on the design of the pump, several things are now
 327 apparent which were not initially.  In particular, it seems that it
 328 could be useful to separate {\it loading the count register} from
 329 other types of instructions.  This would have a few advantages:
 330
 331 \begin{itemize}
 332 \item The size of the count field would not be a consideration in the
 333       ``instruction budget'' of normal execution instructions
 334 \item It would be possible to have finitely-repeating,
 335       infinitely-requeueing instructions (FIXME).
 336 \end{itemize}
 337
 338 \begin{verbatim}
 339 essence of the pump:
 340
 341 ti
 342 di
 343
 344 dc (data capture)
 345 dl (data literal, take from instruction bits)
 346
 347 di
 348 doi (data output, destination taken from instruction)
 349 dod (data output, destination taken from Data register)
 350
 351 set count
 352 decrement count
 353
 354 requeue if count>0
 355 requeue unconditionally
 356 repeat  if count>0
 357 repeat  unconditionally
 358
 359 \end{verbatim}
 360
 361