%-*- Mode:Text -*- 
\chapter{Geometry and scanning}\label{sect.geo}

In this chapter we present the  basic geometrical and kinematical
aspects of \step's data organization, data movement, and data
interaction.

\section{Sites and layers}\label{sect.sites-layers}

\Step's main business is the fine-grained simulation of spatially-extended
systems; this is achieved by the iterated updating of a large
collection of bit-sized state variables according to laws that are, by
and large, local and uniform.

One may visualize these bits as arranged in a multidimensional
array---which we shall call \step\ \tdf{space}---that plays in the
simulated system a role somewhat analogous to that of ordinary
physical space.  Each element of the array consist of a collection of
bits, which play a role somewhat analogous to that of state-components
in ordinary physics.  This arrangement is illustrated in
\fig{site-layer}, where dots represent bits. In this figure the array
is two-dimensional, and the different state-components are drawn on
separate planes for clarity.

We shall formalize the above concepts by saying that each
state-variable bit in a \step\ machine is uniquely identified by a
combination of two labels, namely a \tdf{site address} (``which array
element'') and a \tdf{layer number} (``which state-component'').  If we
fix the site address and let the layer number run through all its
possible values, we obtain a data structure called a \tdf{site} (the
vertical ``pile'' of bits in \fig{site-layer}). If we fix the layer
number and let the site address run through all its possible values, we
obtain a data structure called a \tdf{layer} (the horizontal ``sheet''
of bits in the same figure). The present implementation of \step\ uses
sixteen layers, numbered 0 through 15 or, where hexadecimal is more
convenient, \ttt{0} through \ttt{F}.

\figonecol{site-layer}{
 \setlength{\unitlength}{0.88pt}
 \begin{picture}(256,96)(-16,0)
	\thicklines
 \savebox{\toy}(0,32){
	\multiput(0,0)(48,32){2}{\line(1,0){192}}
	\multiput(0,0)(192,0){2}{\line(3,2){48}}
	\multiput(44,8)(64,0){3}{\circle*{5}}
	\multiput(68,24)(64,0){3}{\circle*{5}}
 }
	\put(0,0){\usebox{\toy}}
	\put(0,64){\usebox{\toy}}

	\multiput(44,56)(64,0){3}{\circle*{5}}

	\put(0,48){\line(1,0){192}}
	\put(0,48){\line(3,2){24}}
	\put(192,48){\line(3,2){48}}
	\put(240,80){\line(-1,0){24}}
	\thinlines
	\multiput(68,72)(64,0){3}{\circle{3}}
	\put(24,64){\line(3,2){24}}
	\put(48,80){\line(1,0){168}}
	\thicklines\put(44,8){\line(0,1){56}}
	\thinlines\put(44,64){\line(0,1){8}}
	\put(-16,36){\makebox(0,0)[l]{site}}	
	\put(4,36){\vector(1,0){40}}
	\put(-16,80){\makebox(0,0)[l]{layer}}	
	\put(10,80){\vector(1,0){14}}

 \end{picture}}{State-variable bits in \step\ are arranged in \tdf{layers}
and \tdf{sites}.}

\Step\ layers can extend indefinitely in one, two, or three
dimensions called \tdf{extendible} dimensions. By ``indefinitely'' we
mean that no limits are set by the architecture: an arbitrary
extension along any of these dimensions can be achieved by connecting
end-to-end an appropriate number of \step\ modules. The last
module of the chain will be connected to the first, so as to achieve
wraparound (see \chapt{block-structure} for more details).
Thus, the three extendible dimensions of \step\ space have the structure
of a three-dimensional torus (\tdf{3-torus}).

Additional wrapped-around dimensions, called \tdf{internal}
dimensions, are possible, but the number and extension of the internal
dimensions are subject to certain implementation-dependent
tradeoffs, since these internal dimensions are assembled out of the
finite resources contained \emph{within} a module.\footnote
	{Basically, the volume of the hyperspace spanned by the
internal dimensions cannot exceed the site capacity of a \step{}
module.}

\medskip

Though the internal dimensions are naturally arranged as a
multidimensiona torus much as the extendible dimensions, no spatial
interpretation need to associated to this arrangement. In particular,
the space spanned by the internal-dimensions coordinates can be treated
as the address space of a ``heap'' of data associated with each site
(\cf{constructs}).


\section{Updating}\label{sect.updating}

The entire array of \step\ sites (or a selected subarray if desired)
is made to evolve in time by repeated applications of a basic
procedure, called a \tdf{scan}, conceptually consisting of
two stages:
 \begin{itemize}
	\item \parhead{Data transport} Each of the sixteen layers is
independently shifted as a whole by an arbitrary number of positions
in an arbitrary direction. We still end up with a pile of bits at each
site, but with a new make-up.
	\item \parhead{Data interaction} We now take each pile of bits
and we send it to a 16-input, 16-output lookup table; the lookup
table returns a new pile, which we put in place of the original one.
 \end{itemize}
	Two remarks are in order.  At the data-transport stage, the
shift performed on each layer is a \emph{uniform} and \emph{data-blind}
operation (each bit is moved by a fixed offset, independently of its
position and its value); in a suitable implementation, this can be
achieved by simply shifting the frame of reference (i.e., incrementing
a pointer) rather than moving the data themselves.  At the
data-interaction stage, each site is processed independently: sites do
not need to look at one another, and the \emph{order} in which they are
processed is irrelevant. Thus, the implementation is free to use any
combination of serial an parallel processing.

\medskip

Most of the rest of this manual can be thought of as a description
of how the above conceptual updating scheme is implemented by the
\step\ architecture.


\section{Sectors, modules}\label{sect.sectors}

Functionally, a \step\ machine consists of a number of identical 
\emph{modules} interconnected as a three-dimensional array (cf.\
\fig{big-crate}). Each dimension is wrapped around on itself (for
example, in \fig{big-crate}, the side facing in the positive $x$
direction joins the side facing in the negative $x$ direction),
yielding the structure of a three-dimensional torus (the canonical way
to achieve this wraparound is discussed in \chapt{block-structure}).

Each module is responsible for storing and updating a portion, called
a \tdf{sector}, of the entire array of sites. The number of sites in a
sector is a fixed power of two ($2^n$, where $n$ equals 22 or 24 in
the present implementation, depending on the size of the \dram\ chips
used), while there is no design limit on the number of sectors (in
practice, a limit is set by economic factors sooner than by
engineering constraints).

\medskip

The site address consists of two parts: the first tells where in a
sector a site lies, while the second identifies the sector itself
(cf.\ \fig{full-site-address}).  When dealing with an individual
module, there will be no danger of confusion if we use the term `site
address' just for the first part, i.e., for the address within the
sector served by the module; similarly, the meaning of `layer' will be
restricted to that portion of a layer which is contained within the
sector.

\section{Dimensions}\label{sect.dimensions}

For definiteness, let us consider a \step\ machine consisting of $2^6$=64
modules physically arranged in a 4\by4\by4 array, using 16-Mbit \dram\
chips ($2^{24}$ bits) to store the layers within each module.

 \figonecol{big-crate}{
 \begin{picture}(232,96)(-24,-16)
	\thicklines
	\multiput(0,0)(0,8){5}{\line(6,1){192}} % front 5 horizontal lines
	\multiput(0,0)(0,8){5}{\line(-1,1){16}} % side 5 horizontal lines
	\multiput(0,0)(48,8){5}{\line(0,1){32}} % front 5 vertical lines
	\multiput(0,0)(-4,4){5}{\line(0,1){32}} % side 5 vertical lines
	\multiput(0,32)(-4,4){5}{\line(6,1){192}} % top 5 lengthwise lines
	\multiput(0,32)(48,8){5}{\line(-1,1){16}} % top 5 across lines
	\thinlines
	\put(192,64){\line(6,1){16}}\put(208,66.67){\vector(4,1){0}}
		% unfortunately there are no vectors of slope 6:1
		\put(204,60){\makebox(0,0){$x$}}
	\put(0,32){\vector(0,-1){48}}\put(8,-12){\makebox(0,0){$y$}}
	\put(0,32){\vector(-1,1){24}}\put(-20,44){\makebox(0,0){$z$}}
 \end{picture}
 }{Sixty-four sectors (each realized by one \step\ module) arranged
in a 4\by4\by4 array. Each sector has been configured as a
three-dimensional array of 1024\by128\by128 sites, with the longer
side along the $x$ dimension.}

\noindent Suppose further that each sector of $2^{24}$ sites has been
configured, as will be explained in a moment, as a parallelepiped of
1024\by128\by128 sites ($2^{10}$\by$2^7$\by$2^7$). In this situation,
illustrated in \fig{big-crate}, a full site address will consist of a
string of 24+6 bits having the format of \fig{full-site-address},
where address bits are grouped and labeled $x$, $y$, and $z$ according
to the dimension they refer to---with $x'$, $y'$, and $z'$ denoting
those portions of the site address that spill over the sector
address.  Thus, the total size of the site array will be 4096
(1024\by4) in the $x$ dimension and 512 (128\by4) in both the $y$ and
$z$ dimensions, for a total of 1 Gigasite.

  \figonecol{full-site-address}{
 \def\qq{\rule{2.8mm}{0mm}}
 \setlength{\tabcolsep}{0em}
 $\overbrace{
 \overbrace{
 \begin{tabular}{|c|*{23}{c|}}
	\multicolumn{10}{|c|}{$x$}&\multicolumn{7}{c|}{$y$}&
		\multicolumn{7}{c|}{$z$}\\\hline
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&
\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq\\\hline
	\multicolumn{1}{c}{$\scriptstyle0$}&
	\multicolumn{22}{c}{}&
	\multicolumn{1}{c}{$\scriptstyle23$}
 \end{tabular}
 }^{\displaystyle\hbox{position within sector}}
 \overbrace{
 \begin{tabular}{|c|*{5}{c|}}
	\multicolumn{2}{|c|}{$x'$}&\multicolumn{2}{c|}{$y'$}&
		\multicolumn{2}{c|}{$z'$}\\\hline
\qq&\qq&\qq&\qq&\qq&\qq\\\hline
	\multicolumn{1}{c}{$\scriptstyle0$}&
	\multicolumn{4}{c}{}&
	\multicolumn{1}{c}{$\scriptstyle5$}
 \end{tabular}
 }^{\displaystyle\hbox{sector}}
 }^{\displaystyle\hbox{full site address}}%end \overbrace
 $}{Representation of full site address. The 24+6 address bits have been
grouped according to whether they encode $x$, $y$, or $z$ coordinates.
Primed letters denote bits devoted to the sector address.}

How does one establish the number of dimensions and the number of
address bits devoted to each dimension?

The structure of the sector address (right portion of \fig{full-site-address})
is essentially determined by how many modules
are present and how they are wired together.\footnote
	{Quite a bit of flexibility still remains even at this stage,
since the fixed interconnecting wires can be used in different ways
to achieve different configurations, as discussed in \chapt{addressing}.}
	Moreover, the typical mode of operation for the machine is for
all sectors to operate in parallel carrying out identical orders;
clearly, when programming the parameters of a such a mode of operation,
the sector address is not a relevant variable.
  \figonecol{dimension-cuts}{
 \def\qq{\rule{8pt}{0mm}}
 \def\0{\hbox to 8pt{}}
 \def\1{\hbox to 8pt{\hfill$\bullet$\hfill}}
 \def\vl{\hbox to 8pt{\vrule width1pt height12pt\hfill}}
 \def\vr{\hbox to 8pt{\hfill\vrule width1pt height12pt}}
% \renewcommand{\arraystretch}{}\relax
 \begin{tabular}{c}
 \setlength{\tabcolsep}{0em}\relax
 \begin{tabular}{|*{23}{c|}}
	\multicolumn{1}{c}{$\scriptscriptstyle0$}&
	\multicolumn{21}{c}{\sym Dimension Cut Mask}&
	\multicolumn{1}{c}{$\scriptscriptstyle22$}\\\hline
	\0&\0&\0&\0&\0&\0&\0&\0&\0&\1&
	\0&\0&\0&\0&\0&\0&\1&
	\0&\0&\0&\0&\0&\0\\\hline
	\multicolumn{9}{c}{}&
	\multicolumn{1}{c}{$\downarrow$}&
	\multicolumn{6}{c}{}&
	\multicolumn{1}{c}{$\downarrow$}&
	\multicolumn{6}{c}{}
 \end{tabular}\\\relax
 \setlength{\tabcolsep}{0em}\relax
 \renewcommand{\arraystretch}{0}\relax
 \begin{tabular}{|*{24}{c|}}\hline
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\qq\\\hline
	\multicolumn{24}{c}{\rule{0mm}{1mm}}\\
	\multicolumn{1}{c}{$\scriptscriptstyle0$}&
	\multicolumn{8}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle9$}&
	\multicolumn{1}{c}{$\scriptscriptstyle10$}&
	\multicolumn{5}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle16$}&
	\multicolumn{1}{c}{$\scriptscriptstyle17$}&
	\multicolumn{5}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle23$}
 \end{tabular}
 \end{tabular}
}{Each `$\bullet$', representing a `1' in the {\sym Dimension Cut
Mask}, introduces a cut (indicated by a thick band) in the
corresponding position of the site address. The resulting slices of
the site address represent separate components (one for each
dimension) of a site's spatial coordinates.}

For the above reasons, here we shall restrict our attention to the
site address within a sector.  Since this is a 24-bit string, there
are 23 points where one can ``cut'' it.  By actually cutting the
string at two of these places, as in \fig{dimension-cuts}, one obtains
three separate strings corresponding to the three address slices
denoted  by $x$, $y$, and $z$ in \fig{full-site-address}. The cut points
are specified by a 23-bit\footnote
	{This register actually consists of 24 bits, but the last bit
is not used.}
	{\sym Dimension Cut Mask} (\sect{DR}); each `1' in
this register specifies a cut at the correponding position.  Each of
the resulting three slices will be treated by the \step\ machinery as a
separate component of a site's spatial coordinates, corresponding to a
separate dimension.

More generally, by cutting the site-address string (and other
registers of the same format associated with address arithmetic) at
$d${}$-$1 two places, one obtains $d$ address \tdf{slices} of various
lengths (the sum of these lengths will, of course, total 24).  The
actual effect of the ``cutting'' is that arithmetic carries and
borrows are prevented from propagating across the cutpoints, thus
making address-arithmetic operations performed on one slice
independent of those performed on the adjacent slices.

In this way, the $2^n$ sites of a sector are formally arranged into a
$d$-dimensional parallelepiped of sides $2^{n_1}$, $2^{n_2}$, \ldots,
$2^{n_d}$, where $n_1$, \ldots, $n_d$ are the lengths of the $d$
site-address slices.

In the following figures, it will not be necessary to explicitly show
the {\sym Dimension Cut Mask}; the position of the cuts will simply be
indicated by dark bands as in \fig{dimension-cuts}.  Shifting the
positions of the cuts from (a) to (b) to (c) in \fig{various-cuts}
changes the aspect ratio of a sector from 4:$1\over2$:$1\over2$ to
1:1:1 to 1:2:$1\over2$, as in (a), (b), and (c) of \fig{various-aspects}.

 \figonecol{various-cuts}{
 \def\qq{\rule{8pt}{0mm}}
 \def\qqq{\rule{0mm}{6ex}}
 \def\0{\hbox to 8pt{}}
 \def\1{\hbox to 8pt{\hfill$\bullet$\hfill}}
 \def\vl{\hbox to 8pt{\vrule width1pt height12pt\hfill}}
 \def\vr{\hbox to 8pt{\hfill\vrule width1pt height12pt}}
 \setlength{\tabcolsep}{0em}\relax
 \begin{tabular}{cc}
 (a)\ \ \ \ &  \renewcommand{\arraystretch}{0}\relax
       \begin{tabular}{|*{24}{c|}}\hline
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\qq\\\hline
	\multicolumn{24}{c}{\rule{0mm}{1mm}}\\
	\multicolumn{1}{c}{$\scriptscriptstyle0$}&
	\multicolumn{8}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle9$}&
	\multicolumn{1}{c}{$\scriptscriptstyle10$}&
	\multicolumn{5}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle16$}&
	\multicolumn{1}{c}{$\scriptscriptstyle17$}&
	\multicolumn{5}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle23$}
       \end{tabular}\\
 \qqq (b)\ \ \ \ & \renewcommand{\arraystretch}{0}\relax
       \begin{tabular}{|*{24}{c|}}\hline
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\qq&\qq\\\hline
	\multicolumn{24}{c}{\rule{0mm}{1mm}}\\
	\multicolumn{1}{c}{$\scriptscriptstyle0$}&
	\multicolumn{6}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle7$}&
	\multicolumn{1}{c}{$\scriptscriptstyle8$}&
	\multicolumn{6}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle15$}&
	\multicolumn{1}{c}{$\scriptscriptstyle16$}&
	\multicolumn{6}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle23$}
       \end{tabular}\\
 \qqq (c)\ \ \ \ &  \renewcommand{\arraystretch}{0}\relax
       \begin{tabular}{|*{24}{c|}}\hline
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\qq&\qq&\vr&
	\vl&\qq&\qq&\qq&\qq&\qq&\qq\\\hline
	\multicolumn{24}{c}{\rule{0mm}{1mm}}\\
	\multicolumn{1}{c}{$\scriptscriptstyle0$}&
	\multicolumn{6}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle7$}&
	\multicolumn{1}{c}{$\scriptscriptstyle8$}&
	\multicolumn{7}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle16$}&
	\multicolumn{1}{c}{$\scriptscriptstyle17$}&
	\multicolumn{5}{c}{}&
	\multicolumn{1}{c}{$\scriptscriptstyle23$}
       \end{tabular}
 \end{tabular} }{Different sets of cuts in the site-address string, as
in (a), (b), and (c), yield different aspect ratios for a sector, as
in \protect\fig{various-aspects}.}

 \figonecol{various-aspects}{\psfig{file=fig/various-aspects.ps}}{Different
sector aspect ratios, namely 4:$1\over2$:$1\over2$ in (a), 1:1:1
in (b), and 1:2:$1\over2$ in (c), arise from different sets of cuts
in the site-address string (cf.\ \protect\fig{various-cuts}).}

\medskip

As explained above, the {\sym Dimension Cut Mask} determines the
number of dimensions of a sector and their aspect ratio, but does not
specify which (if any) of these dimensions should be associated with
the $x$, $y$, and $z$ axes along which the sectors themselves are
arranged in \step\ space. This is done by the three {\sym
Dimension Cut Pointer}s ({\sym XDCP}, {\sym YDCP}, and {\sym ZDCP};
\sect{DR}), each of which points to the high end (i.e., the carry
position out of the most significant bit) of one of the above
dimension slices---as indicated in \fig{dcp-xyz}.

\figonecol{dcp-xyz}{\psfig{file=fig/dcp-xyz.ps}}{The three {\sym
Dimension Cut Pointer}s tell which dimension slices are to be
associated with the array axes $x$, $y$, or $z$.  Any dimension thus
marked becomes an \emph{extendible} dimension: the dimension marked
$x$, say, is continued from one sector to the next along the $x$ axis
instead of wrapping around within each sector.
The present arrangement of pointers corresponds to the situation depicted
in \protect\fig{big-crate} and \protect\fig{full-site-address}).}

In \fig{dcp-xyzuv} we illustrate a more general situation.
The site-address string is cut into five slices by the {\sym
Dimension Cut Mask}. Of these, three are identified as extendible
dimensions $x$, $y$, and $z$ by the {\sym Dimension Cut Pointer}s
(note that the order is different from \fig{dcp-xyz}). The remaining
two slices, labeled $u$ and $v$, represent the address components for
additional \tdf{internal} dimensions---which wrap around within
each sector rather than extend from one sector to the next.

 \figonecol{dcp-xyzuv}{\psfig{file=fig/dcp-xyzuv.ps}}{Here the site
address is partitioned into five slices by the {\sym Dimension Cut
Mask}. Of these, three have been associated with the $x$, $y$, and $z$
axes by the {\sym Dimension Cut Pointers}; the remaining two slices,
labeled $u$ (address bits 10--13) and $v$ (address bits 20--23)
correspond to nonextendible or \emph{internal} dimensions.}

\medskip

With reference to \fig{big-crate}, where all three extendible
dimensions are used, each sector is in contact with the six adjacent
sectors through its six faces, which will be labeled in an obvious way
$x_-$, $x_+$, \ldots, $z_-$, $z_+$, as in \fig{faces}. (Note that
sectors wrap around in each dimension, so that no faces remain exposed.)

\newpage

	\figonecol{faces}{
 \begin{picture}(252,108)(-60,-48)
	\thicklines
	\put(0,0){\line(6,1){144}}	% x lines
	\put(-12,12){\line(6,1){144}}
	\put(0,-24){\line(6,1){144}}
	\put(0,0){\line(0,-1){24}}	% y lines
	\put(-12,12){\line(0,-1){24}}
	\put(144,24){\line(0,-1){24}}
	\put(0,0){\line(-1,1){12}}	% z lines
	\put(0,-24){\line(-1,1){12}}
	\put(144,24){\line(-1,1){12}}
	\thinlines
		\put(-42,-12){\line(6,1){36}}	% x axis
			\put(-50,-13){\makebox(0,0){$x_-$}}
		\put(174,24){\line(-6,-1){30}}
			\put(182,25){\makebox(0,0){$x_+$}}
		\put(66,48){\line(0,-1){30}}	% y axis
			\put(66,54){\makebox(0,0){$y_-$}}
		\put(66,-36){\line(0,1){23}}
			\put(66,-42){\makebox(0,0){$y_+$}}
		\put(93,-21){\line(-1,1){21}}	% z axis
			\put(99,-27){\makebox(0,0){$z_-$}}
		\put(39,33){\line(1,-1){10}}
			\put(33,39){\makebox(0,0){$z_+$}}
 \end{picture}
}{Labeling of a sector's faces, with
respect to the orientation of the coordinate axes $x$, $y$, and $z$ of
\step\ space (cf.\ \protect\fig{big-crate}).}


\section{Block structure}\label{sect.block-structure}

In the \step\ architecture, the minimal functional unit is the
individual module: realizations of arbitrary size can be built by
simple iteration of this basic unit.

However, for reasons of concrete interconnection geometry it is
desirable to introduce a larger ``prefabricated'' structure, called a
\tdf{block}, consisting of eight sectors that stand in a distinguished
geometrical relationship with one another within \step\ space.
This logical grouping of sectors is reflected in the implementation,
where the eight modules that realize the eight sectors of a block are
housed in the same physical \tdf{box} (\cf{system-overview} and
\sect{block-wiring}).

We have seen (\sect{sites-layers}) that the topology of the three
extendible dimensions of \step\ space is that of a 3-torus.
The block structure discussed here provides a systematic way to embed
the 3-torus into ordinary 3-space (three-dimensional space) in
such a way that
 \begin{itemize}
	\item Boxes can be stacked in a straightforward
three-dimensional array (no circular arrangement of boxes to make
opposite ends of the array meet).
	\item No matter what size the array, modules that realize
logically contiguous sectors are found in adjacent boxes. This
arrangement avoids size-dependent propagation delays.
 \end{itemize}


\subsection{Glue ports}\sectlabel{glue-ports}

As mentioned in \sect{sectors}, each \step\ module is responsible for
storing and updating the dynamical variables associated with a 
\emph{sector}, i.e., a parallelepiped-shaped portion of simulation space.  A
sector exchanges information with contiguous sectors, along the three
extendible dimensions $x$, $y$, and $z$, through its six
faces---labeled $x_-$, $x_+$, \ldots, $z_-$, $z_+$ as in \fig{faces}.

Since a module scans the sites of its sector \emph{sequentially}
(\cf{scanner}), data communication between contiguous modules is
handled serially by serial \tdf{glue ports}, using a modest number of
pins. For the purposes of the present chapter, a glue port's detailed
structure and the direction of data flow (in or out of a module) on a
particular port line at a given moment are irrelevant; all that
matters is that the glue ports handle the flow of information in and
out of a sector's faces.

The assignment of a specific glue port to a specific face
is software-reconfigurable. Here, by `glue port $x_-$', say, we shall mean
whatever port has been assigned to face $x_-$.


\subsection{Wraparound}

In some applications, the simulation volume represented by an array of
\step\ sectors arranged as in \fig{big-crate} will correspond to a
similarly shaped volume of the system under study.  The exposed faces
which delimit this volume represent the interface between the
simulated portion of the system and the rest of the system which
surrounds it; the latter is not explicitly modeled within the \step{}
machine. In these circumstances, it is up to the experimenter to feed
appropriate boundary conditions (e.g., constant, random)
to the exposed faces so as to approximate the influence of the
surroundings.\footnote
	{This can be done in a variety of ways, as explained
elsewhere.\relax \plug{boundary conditions}}
 \figonecol{cylinder}{\psfig{file=fig/cylinder.ps}}{Two-dimensional
array wrapped around in one dimension (\tdf{cylinder}).}

However, in most applications (and chiefly in those of a more
conceptual nature) the experimenter will prefer to model a
self-contained system having no distinguished boundaries.  To
this purpose, one can bend the \step{}-space volume back onto itself,
directly connecting each exposed face to the corresponding one on the
opposite side.\footnote
	{Physicist often use the term `periodic boundary conditions'
for such an arrangement.}
	\fig{cylinder} shows a two-dimensional array
wrapped around in one dimension (cylinder), while \fig{torus} shows
a two-dimensional array wrapped around in both dimensions (torus).

\newpage

 \figonecol{torus}{\psfig{file=fig/torus.ps}}
{Two-dimensional array wrapped around in two dimensions (\tdf{torus}).}


With \step, the most demanding situation is when a three-dimensional
array as that of \fig{big-crate} is to be wrapped around in all three
dimensions, yielding a \tdf{3-torus}. That is, how is this functional
wraparound going to be achieved physically?

A simple way is to arrange the modules in straight rows as in
\fig{big-crate}, and join ports at opposite ends with
long ``return'' cables, as shown in \fig{wrap-one} for one dimension.

 \figonecol{wrap-one}{\relax
 \begin{picture}(224,40)(-112,-24)
	\thicklines
	\multiput(-88,16)(48,0){4}{\line(1,0){32}}
	\multiput(-88,16)(48,0){4}{\line(0,-1){32}}
	\multiput(-88,-16)(48,0){4}{\line(1,0){32}}
	\multiput(-56,16)(48,0){4}{\line(0,-1){32}}
	\multiput(-56,0)(48,0){3}{\line(1,0){16}}
	\put(-88,-24){\line(1,0){176}}
	\put(-88,-12){\oval(40,24)[l]}
	\put(88,-12){\oval(40,24)[r]}
	\multiput(-88,-4)(48,0){4}{\makebox(32,8)[tl]{$\;x_-$}}
	\multiput(-88,-4)(48,0){4}{\makebox(32,8)[tr]{$x_+$}}
 \end{picture}
 }{Wraparound of modules, in one dimension.}
 
\noindent However, as the number of modules in a row increases, such an
arrangement would lead to proportionally longer propagation delays,
and the clock rate would have to be slowed down correspondingly.


\section{Blocks and strands}\label{blocks-strands}

Let us consider now the \emph{interleaved} arrangement of
\fig{wrap-fix}, where both legs of a round trip are evenly strewn
with modules.  In this arrangement the physical distance between
logically contiguous sectors is somewhat greater than in
\fig{wrap-one}, but the need for a return wire of unbounded length is
eliminated.

 \figonecol{wrap-fix}{\relax
 \begin{picture}(224,56)(-112,-40)
	\thicklines
	\multiput(-88,16)(96,0){2}{\line(1,0){32}}
	\multiput(-88,16)(96,0){2}{\line(0,-1){32}}
	\multiput(-88,-16)(96,0){2}{\line(1,0){32}}
	\multiput(-56,16)(96,0){2}{\line(0,-1){32}}
	\multiput(-96,0)(96,0){2}{\line(1,0){8}}
	\multiput(-56,0)(96,0){2}{\line(1,0){56}}

	\multiput(-40,-8)(96,0){2}{\line(1,0){32}}
	\multiput(-40,-8)(96,0){2}{\line(0,-1){32}}
	\multiput(-40,-40)(96,0){2}{\line(1,0){32}}
	\multiput(-8,-8)(96,0){2}{\line(0,-1){32}}
	\multiput(-96,-24)(96,0){2}{\line(1,0){56}}
	\multiput(-8,-24)(96,0){2}{\line(1,0){8}}

	\put(-96,-12){\oval(24,24)[l]}
	\put(96,-12){\oval(24,24)[r]}
	\multiput(-88,-4)(96,0){2}{\makebox(32,8)[tl]{$\;x_-$}}
	\multiput(-88,-4)(96,0){2}{\makebox(32,8)[tr]{$x_+$}}
	\multiput(-40,-28)(96,0){2}{\makebox(32,8)[tl]{$\;x_+$}}
	\multiput(-40,-28)(96,0){2}{\makebox(32,8)[tr]{$x_-$}}
 \end{picture}
 }{Interleaved wraparound, in one dimension.}

\fig{wrap-fix} suggests that in the interleaved arrangements
individual modules may be left in essentially the same physical
position as in \fig{wrap-one} (and, in three dimensions, as in
\fig{big-crate}); only their interconnection is modified.  While the
new interconnection may entail a longer propagation delay, the extra
delay is a \tdf{fixed} one, independent of the number of modules in
the chain.\footnote
	{A closer packing of modules in the given dimension is of
course possible, but that only at the cost of building up
thickness---and thus propagation delays---in another dimension.}

\medskip

The interleaved arrangement of \fig{wrap-fix} consists of two parallel
\tdf{strands} of modules, one with the $x_+$ ports facing rightward
and one leftward (and conversely for $x_-$). 
With this arrangement, the minimal repetitive unit is no longer
the individual module, but a \emph{block} of two modules---one
from each strand---as shown in \fig{wrap-block}. Though in close
physical proximity, the two modules of a block are not connected to
one another within the block itself.

 \figonecol{wrap-block}{\relax
 \begin{picture}(224,64)(-112,-44)
	\thicklines
	\multiput(-88,16)(96,0){2}{\line(1,0){32}}
	\multiput(-88,16)(96,0){2}{\line(0,-1){32}}
	\multiput(-88,-16)(96,0){2}{\line(1,0){32}}
	\multiput(-56,16)(96,0){2}{\line(0,-1){32}}
	\multiput(-96,0)(96,0){2}{\line(1,0){8}}
	\multiput(-56,0)(96,0){2}{\line(1,0){56}}

	\multiput(-40,-8)(96,0){2}{\line(1,0){32}}
	\multiput(-40,-8)(96,0){2}{\line(0,-1){32}}
	\multiput(-40,-40)(96,0){2}{\line(1,0){32}}
	\multiput(-8,-8)(96,0){2}{\line(0,-1){32}}
	\multiput(-96,-24)(96,0){2}{\line(1,0){56}}
	\multiput(-8,-24)(96,0){2}{\line(1,0){8}}

	\put(-96,-12){\oval(24,24)[l]}
	\put(96,-12){\oval(24,24)[r]}
	\multiput(-88,-4)(96,0){2}{\makebox(32,8)[tl]{$\;x_-$}}
	\multiput(-88,-4)(96,0){2}{\makebox(32,8)[tr]{$x_+$}}
	\multiput(-40,-28)(96,0){2}{\makebox(32,8)[tl]{$\;x_+$}}
	\multiput(-40,-28)(96,0){2}{\makebox(32,8)[tr]{$x_-$}}
	\thinlines
	\multiput(-92,-44)(96,0){2}{\dashbox{2}(88,64){}}
 \end{picture}
 }{With interleaved wraparound, the minimal
repetitive unit is a two-module \tdf{block}.}

In \step, the above doubling up and interleaving of module chains is
carried out for all three dimensions, leading to a minimal repetitive
unit consisting of an eight-module block. A block can be thought of as
a sector-size ``window'' on the eight three-dimensional strands that
run parallel to one another when the 3-torus is ``squashed'' onto
ordinary 3-space.  Figures \ref{fig.squashed} and \ref{fig.4strand}
illustrate the analogous situation in two dimensions.

\figonecol{squashed}{\psfig{file=fig/squashed.ps}}{A two-dimensional
torus, which is usually visualized as embedded in three-dimensions,
here is shown in the process of being ``squashed'' onto
two-dimensions. Like a folded handkerchief, the resulting structure has a
``thickness'' of four two-dimensional layers, or \tdf{strands}.}

\figonecol{4strand}{\psfig{file=fig/4strand.ps}}{In the squashed
torus of \protect\fig{squashed}, a \tdf{block} is a sector-size window
cutting through all four two-dimensional strands.}

Note that, just as in the one-dimensional case there are two separate
strands of one-dimensional space that run parallel to one another but
with \emph{opposite orientations} within a block (cf.\
\fig{wrap-block}), and in the two-dimensional case there are four
separate strands of two-dimensional space (\fig{4strand}), thus in
three dimensions each block is traversed by \tdf{eight} separate
strands of 3-space, one for each of the eight possible orientations.

These eight strand orientations (and thus the eight sectors within a
block) will be labeled by three binary parameters, $s_x$, $s_y$, and
$s_z$, defined as follows. For a given strand, we'll let $s_x$=0 if
the $x_+$ ports of that strand face in the positive $x$ direction of
physical space, and $s_x$=1 if they face in the opposite direction
(cf.\ \fig{wrap-block}); and similarly for $s_y$ and $s_z$.  To each of the
eight strands there will correspond a different value of the triplet
$\langle s_x,s_y,s_z \rangle$, which can also be interpreted in an
obvious way as an integer $S$ in the range 0--7,
as in the following table
 \begin{equation}\label{eq.strands}
 \let\slab=\bullet
 \begin{array}{|c|c|}\hline
	s_xs_ys_z & S\\\hline\hline
	000 & 0\\
	100 & 1\\
	010 & 2\\
	110 & 3\\
	001 & 4\\
	101 & 5\\
	011 & 6\\
	111 & 7\\\hline
 \end{array}.
 \end{equation}

\medskip

To each of the eight strands the block contributes
a six-ported module, for a total of 8 modules and 48 ports in each
block, as detailed in the following table \eq{block-ports}

 \begin{equation}\label{eq.block-ports}
 \let\slab=\bullet
 \begin{array}{|cc||c@{}c|c@{}c|c@{}c|}\hline
	\multicolumn{2}{|c||}{\rm strand} & \multicolumn{6}{c|}{\rm ports}\\
	s_xs_ys_z& S & \multicolumn{1}{c@{}}{x_-} & \multicolumn{1}{@{}c|}{x_+}
	      & \multicolumn{1}{c@{}}{y_-} & \multicolumn{1}{@{}c|}{y_+}
	      & \multicolumn{1}{c@{}}{z_-} & \multicolumn{1}{@{}c|}{z_+}\\\hline\hline
	000 & 0 & \slab & \slab & \slab & \slab & \slab & \slab\\
	100 & 1 & \slab & \slab & \slab & \slab & \slab & \slab\\
	010 & 2 & \slab & \slab & \slab & \slab & \slab & \slab\\
	110 & 3 & \slab & \slab & \slab & \slab & \slab & \slab\\
	001 & 4 & \slab & \slab & \slab & \slab & \slab & \slab\\
	101 & 5 & \slab & \slab & \slab & \slab & \slab & \slab\\
	011 & 6 & \slab & \slab & \slab & \slab & \slab & \slab\\
	111 & 7 & \slab & \slab & \slab & \slab & \slab & \slab\\\hline
 \end{array}
 \end{equation}

\noindent Each of a blocks's 48 glue ports, represented here by black
dots, is uniquely identified by a face label ($x_-$, $x_+$, \ldots,
$z_+$) and a strand label ($S=0,\ldots,7$). It is possible to
physically arrange a block's glue ports so that adjacent blocks
directly mate both mechanically and electrically.

\medskip

Block wiring (between blocks and within blocks) is discussed in
\sect{block-wiring}.


\section{Scanning}\label{sect.scanner}

While the \step\ modules operate in parallel (and it is in this sense
that \step\ is a parallel processor), sites within each sector are
accessed \emph{serially}. Here we are concerned with the scanning
mechanism that determines which sites are accessed and in what
order.

Scanning is concerned with a site's \emph{address}---rather than its
contents and what is done with it.  Thus, though the following
considerations are coached in terms of site-updating---where the mode
of access is \emph{read-modify-write}, they apply equally well to the
\emph{read-only} and \emph{write-only} access modes, which are used in a
variety of situations involving display, analysis, and input/output of
site data.

\medskip

In the most basic mode of operation of \step, an identical
updating procedure is used for each sector, so that there is complete
symmetry between the sectors. The procedure itself is applied in turn
to every site of the sector.\footnote
	{This is done in parallel on all sectors,
so that homologous sites in different sectors are affected at the same
moment.}
	(or of whatever portion of the sector one wishes to restrict
one's attention; cf.\ below). Thus, within each sector certain sites
are updated before others. However, the functional symmetry between
the sites of a sector is not destroyed by this ordering, because the
results of updating are \emph{independent} of the actual sequential
order of site access.  This invariance leaves one free to manipulate
the order of access for other purposes, such as producing a display of
a given format (e.g., quadruple-interlaced) or accessing sites in the
most convenient order for accumulating site statistics (\cf{event-counter}).

Many variations of the above basic mode are possible.  In some
situations, one may want to restrict the updating activity within each
module to just a fraction of a sector, so as to have more frequent
updates. In other situations, a sector is divided into a number of
subsectors, and the parameters for the updating procedure are changed
from one subsector to the next (e.g., one may use different lookup
tables).

\medskip

From the host's viewpoint, the primitive hardware function used by
\step\ for sequentially accessing sites is called a \tdf{scan}; this is
an indivisible, uninterruptible sequence of site-accesses,
autonomously performed and timed by the module.\footnote
	{Within each module, each of the sixteen layers is served by a
separate \chip, which contains a full implementation of the scanning
mechanism.  In principle, while accessing in a given layer the bit
located at site address $i$, one may access in another layer the bit
located at a different site address $j$.  Unless explicitly
stated, we shall assume that the same \tdf{site} address is generated by all
sixteen \chip{}s of a module.}
	After setting the desired scan parameters within a given
module the host \tdf{schedules} a scan; this scan will be started by
the module at the earliest appropriate moment and will proceed to
completion without host assistance (\sect{RMR}). The module will then
notify the host that the scan machinery is available for a new scan.

\medskip

\fig{scanner} gives a simplified view of the scan generator. Duch greater
detail is shown in \fig{scanning}; details will be expanded in the following
sections.

The prime mover of the entire address-generation chain is the {\sym
Scan Index Register} (\sect{SIR})---a straightforward 24-bit binary
counter which during a scan is normally incremented at the system
clock rate, thus converting the steady passage of time into an
ascending sequence of integers.

Let us for a moment identify the contents of this register, or 
\emph{scan index}, with the \emph{site address}: as the scan index increments
during a scan, the space of all possible $2^{24}$ site addresses
within a sector is traversed in the most straightforward fashion. For
instance, if the site address has been partitioned into three slices
corresponding to dimensions $x$, $y$, and $z$, as in
\fig{dcp-xyz}, regular incrementing of the scan index would scan
this space as if by three nested loops, the $x$ dimension corresponding
to the inner loop and being scanned fastest.

In reality, the \step\ scan generator provides a programmable
conversion stage, called the \tdf{scan index permuter}, between the
scan index and the site address (\fig{scanner}); by this means, the
regular ascending order of the scan index can be transformed into a
variety of more complex access patterns at the site-address level
(\sect{scan-permuter}).  Another programmable stage, the \tdf{offset
adder}, converts the site address into a \emph{\dram\ address}, taking
into account ``kick'' information (\sect{kicking})---which is in
general different from layer to layer. The \dram\ address is the
ultimate offspring of the scan generator, and points directly at a
physical bit in the \dram\ chip.

Besides controlling the \dram, the scan generator also
controls the glue circuitry that regulates the exchange of scanned
data between adjacent sectors; in a sense, this section of the scan
generator interfaces the ``site-within-sector'' portion of the site
address with the ``sector'' portion (cf.\ \fig{full-site-address}).

\figonecol{scanner}{
 \begin{picture}(192,152)(-80,-72)
	\thinlines
	\put(-32,64){\framebox(64,16){\tsy{scan index}}}
%	\put(0,40){\oval(48,16)\makebox(0,0){permuter}}
	\put(0,36){\oval(64,24)\makebox(0,0){\shortstack{scan index\\permuter}}}
	\put(4,12){\makebox(0,0)[l]{site address}}
	\put(-80,-16){\framebox(64,16){\tsy{offset}}}
	\put(48,-16){\framebox(64,16){\tsy{kick}}}
	\put(32,-32){\circle{16}}
	\put(32,-32){\makebox(0,0){\Large$-$}}
	\put(0,-32){\circle{16}}
	\put(0,-32){\makebox(0,0){\Large$+$}}

	\thicklines
	\put(0,64){\vector(0,-1){16}}
	\put(0,24){\vector(0,-1){48}}
	\put(0,0){\circle*{4}}
	\put(0,0){\line(4,-1){32}}
	\put(32,-8){\vector(0,-1){16}}

	\put(-16,-16){\vector(1,-1){10}}
	\put(48,-16){\vector(-1,-1){10}}
	\put(0,-40){\vector(0,-1){32}}
	\put(32,-40){\vector(0,-1){32}}

	\put(-4,-64){\makebox(0,0)[r]{\dram\ address}}
	\put(36,-64){\makebox(0,0)[l]{glue control}}
 \end{picture}
	}{Simplified view of the \step\ scan generator. Square boxes
indicate registers (for instance, `kick' denotes the contents of the
{\sym Kick Register}); round boxes, combinational logic.  Though the
scan index increments steadily during a scan, the corresponding
site-address sequence may be more complex, since through the permuter
the twenty-four bits of the scan index may undergo an arbitrary
permutation. By adding a constant to the site address, the $\oplus$
box shifts the spatial origin of a layer, resulting in a virtual shift
of the layer's contents. The offset specifies the current value of
this constant, while the kick specifies by how much the offset should
be modified between one scan and the next. (Not shown in the figure,
the kick is subtracted from the offset before the new scan;
during the scan itself, both kick and offset remain constant.) Data
carry-over from one sector to the next resulting from this offset
change is handled by the glue-control machinery, to which the
$\ominus$ box supplies the relevant information.}

\figtwocol[!p]{scanning}{\psfig{file=fig/scanning.ps}}{Block diagram of the
basic scanning/gluing/updating circuit. The little white circles denote data
taps from which signals are made available to additional circuitry not shown
in the figure. Conversely, each of the little boxes labeled \tsc{mix}
indicates a place where several signals, besides the main one
shown in the figure, are available for use. In particular, the data path from
\emph{glued data} to \emph{site source} through the \tsc{lut} can be
complemented by one going through an external coprocessor; the latter may
span several modules.}


\section{Scan index}\label{sect.scan-index}

The scan index steadily increments by one unit at a time during a
scan, cycling back to 0 after reaching its maximum value, $2^{24}-1$,
or, in hexadecimal, \ttt{FFFFFF}.

In the most basic situation, the scan index will start from 0 and
traverse the entire range in a single scan. However, one can request
shorter scans, spanning a submultiple (by a power of 2, and
boundary-aligned on the same power of 2) of this range.  In any case,
the next scan will start where the previous one left off (unless, of
course, in the intervening time the host writes a different value in
the {\sym Scan Index Register}).

For example, if the starting value is \ttt{000100} and the scan length
(as determined by the {\sym End-of-Scan Pointer}, \sect{SFR}) is {\tt
40}, on the next four scans the scan index will step through the
following values (columnwise)
 \begin{equation}\label{eq.four-scans}
	\newcommand{\tmp}[1]{\hbox\ttt{0001#1}}
	\begin{array}{cccc}
	\tmp{00} & \tmp{40} & \tmp{80} & \tmp{C0}\\
	\tmp{01} & \tmp{41} & \tmp{81} & \tmp{C1}\\
	\tmp{02} & \tmp{42} & \tmp{82} & \tmp{C2}\\
	\vdots & \vdots & \vdots & \vdots\\
	\tmp{3E} & \tmp{7E} & \tmp{BE} & \tmp{FE}\\
	\tmp{3F} & \tmp{7F} & \tmp{BF} & \tmp{FF}
	\end{array},
 \end{equation}
	coming to rest on the value of \ttt{000200}.


\section{Scan permuter}\label{sect.scan-permuter}

In the most basic situation, the scan index is used directly as a site
address, so that the site-address space itself is traversed in a
steadily ascending fashion (\cf{scan-index}). In many circumstances,
however, it is desirable to access sites in a more complex order.  The
\tdf{scan index permuter} (\sect{SIPR}) provides a certain class of
scan-index-to-site-address transformations; these include arbitrary
permutations of the scan-index bits.

\medskip

We shall introduce the \tdf{scan index permuter} by giving a
simple example of its use.

Let us first consider the basic situation. Suppose we have a system of
256K sites arranged as a two-dimensional array of 512\by512, or
$2^9\times2^9$. As shown in the following diagram
	$$\vcenter{\psfig{file=fig/site-xy.ps}},$$

\noindent the low-order 9 bits of the
site address span the $x$ dimension; the following 9 bits span the $y$
dimension; the remaining 6 bits are not used (and are not shown in the
diagram).

A \step\ module is able to update an array of this size in less than
1/60 sec. We shall arrange for the updating scan to match the format
and timing requirements of a {\sc vga}-like {\sc crt} monitor (namely,
a horizontal rate rate of about 31 KHz and a vertical rate of about 60
Hz), so that the evolution of the system can be displayed in real time
on the monitor, formatted as in \fig{raster-xy}, without the need for a frame
buffer.

 \figonecol{raster-xy}{
 \begin{picture}(208,208)(-16,0)
	\newcommand{\fs}{\footnotesize}
	\thinlines
	\multiput(0,0)(192,0){2}{\line(0,1){192}}
	\multiput(0,0)(0,192){2}{\line(1,0){192}}
	\put(0,194){\makebox(0,0)[bl]{\fs 0}}
	\put(192,194){\makebox(0,0)[br]{\fs 511}}
	\put(-2,192){\makebox(0,0)[tr]{\fs 0}}
	\put(-2,0){\makebox(0,0)[br]{\fs 511}}
	\put(96,204){\makebox(0,0){$x\longrightarrow$}}
	\put(-12,96){\makebox(0,0){\shortstack{$y$\\$\Big\downarrow$}}}
 \end{picture}}{A 512\by512 array can be updated at 60 frames/sec
and displayed in real time on a {\sc vga}-like \crt\ monitor.
The corresponding arrangement of the scan permuter is given
in \protect\fig{scan-xy}.}

Since the scan index is incremented sequentially, so that higher order
bits correspond to coarser time divisions, the low-order 9-bit slice
of the scan index, labeled $h$ in \fig{scan-xy}, will be associated
with the monitor's horizontal sweep, which takes place at the faster rate.
In other words, as $h$ increments from 0 to 511, the \crt\ beam will sweep
a horizontal line, displaying 512 pixels corresponding to the contents
of whatever sites are traversed by the site address during that time.
Since we want a horizontal sweep to correspond to the array's $x$
dimension, the $x$ slice of the site address will be derived directly
from the $h$ slice of the scan index, as shown in \fig{scan-xy}.

 \figonecol{scan-xy}{\psfig{file=fig/scan-xy.ps}} {When the bits that
make up the scan index are used in their natural order to make up the
site address, the least significant bits of the site address (those
associated with the $x$ dimension, in this case) are incremented at
the fastest rate.  The label $h$ denotes that section of the scan
index that cycles at a rate compatible with a \crt's horizontal sweep,
while $v$ corresponds to a vertical sweep. The resulting \crt\ display
format is shown in \protect\fig{raster-xy}.}

Similarly, the $y$ slice of the site address will be derived directly
from the $v$ slice of the scan index, so that the $y$ address will
steadily increase with time as the \crt\ beam performs a vertical
sweep.

Of course, in order to display a complete picture, incrementing of the
scan index will be suspended during horizontal and vertical retraces
(cf.\ {\sym Scan Sync Mode} in \sect{RMR}).

\medskip

Let us consider now a more complex scanning situation. We have a
system of 256K sites as in the previous example, but consisting of a
three-dimensional array of 64\by64\by64, or $2^6\times2^6\times2^6$.
As shown in the following diagram
	$$\vcenter{\psfig{file=fig/site-xyz.ps}},$$

\noindent the site address consists of three 6-bit slices,
corresponding to the $x$, $y$, and $z$ dimensions (the 6 unused bits
are not shown in the diagram).

One way to display this system on a \crt\ monitor is to show
64 two-dimensional slices, arranged side-by-side on an 8\by8 array as
in \fig{raster-xyz}.

 \figonecol{raster-xyz}{
 \begin{picture}(208,208)(-16,0)
	\newcommand{\fs}{\footnotesize}
	\thinlines
	\multiput(0,0)(24,0){9}{\line(0,1){192}}
	\multiput(0,0)(0,24){9}{\line(1,0){192}}
	\multiput(12,194)(24,0){8}{\makebox(0,0)[b]{\hbox to20pt{%
$\scriptscriptstyle0\hfill\cdots\hfill63$}}}
	\multiput(-2,2)(0,24){8}{\makebox(0,0)[br]{$\scriptscriptstyle63$}}
	\multiput(-2,8)(0,24){8}{\makebox(0,0)[br]{\shortstack{
$\scriptscriptstyle.$\\$\scriptscriptstyle.$\\$\scriptscriptstyle.$}}}
	\multiput(-2,22)(0,24){8}{\makebox(0,0)[tr]{$\scriptscriptstyle0$}}
	\put(0,204){\makebox(0,0)[l]{$x\longrightarrow$}}
	\put(-12,192){\makebox(0,0)[t]{\shortstack{$y$\\$\Big\downarrow$}}}

	\put(6,186){\makebox(0,0)[l]{$z\longrightarrow$}}
	\put(12,180){\makebox(0,0){\fs0}}
	\put(36,180){\makebox(0,0){\fs1}}
	\put(60,180){\makebox(0,0){\fs2}}
	\put(84,180){\makebox(0,0){\fs3}}
	\put(108,180){\makebox(0,0){\fs4}}
	\put(132,180){\makebox(0,0){\fs5}}
	\put(156,180){\makebox(0,0){\fs6}}
	\put(180,180){\makebox(0,0){\fs7}}
	\put(12,156){\makebox(0,0){\fs8}}
	\put(36,156){\makebox(0,0){\fs9}}
	\put(60,156){\makebox(0,0){\fs10}}
	\put(84,156){\makebox(0,0){\fs11}}
	\put(108,156){\makebox(0,0){\fs12}}
	\put(132,156){\makebox(0,0){\fs13}}
	\put(156,156){\makebox(0,0){\fs14}}
	\put(180,156){\makebox(0,0){\fs15}}

	\put(12,12){\makebox(0,0){\fs56}}
	\put(36,12){\makebox(0,0){\fs57}}
	\put(60,12){\makebox(0,0){\fs58}}
	\put(84,12){\makebox(0,0){\fs59}}
	\put(108,12){\makebox(0,0){\fs60}}
	\put(132,12){\makebox(0,0){\fs61}}
	\put(156,12){\makebox(0,0){\fs62}}
	\put(180,12){\makebox(0,0){\fs63}}
 \end{picture}}{A 64\by64\by64 array can be updated at 60 frames/sec
and displayed in real time on a {\sc vga}-like \crt\ monitor by
showing 64 two-dimensional slices arranged side-by-side on
an 8\by8 array. The corresponding arrangement of the scan permuter is
given in \protect\fig{scan-xyz}.}

In order to produce this arrangement on the \crt\ screen,\footnote
	{Note that the least significant half of the $z$ address
increments at a faster rate than $y$, while the most significant half
increments at a slower rate than $y$.}
	sites have to be scanned in nested loops as follows (starting
with the innermost loop)
	\begin{equation}
	\begin{tabular}{|c|c|l|}\hline
	loop & slice & \\
	length & width & site-address slice\\\hline\hline
	64 & 6 & $x$\\
	\ 8 & 3 & $z$ (lower half)\\
	64 & 6 & $y$\\
	\ 8 & 3 & $z$ (upper half)\\\hline
	\end{tabular}\ .
	\end{equation}

\noindent This scanning order is achieved by permuting the scan index lines so
that the low three bits of the site-address $z$ slice are driven by
the high three bits of the scan-index $h$ slice, and the high three
bits of the $z$ slice by the high three bits of the $v$ slice, as
shown in \fig{scan-xyz}.

 \figonecol{scan-xyz}{\psfig{file=fig/scan-xyz.ps}}{Here some of the
scan-index bits appear in the site address in a permuted order.
Namely, the coarser portions of the $h$ and $v$ sections control the
scanning of the $z$ dimension.  The resulting \crt\ display format is
shown in \protect\fig{raster-xyz}.}

\medskip

In general, the scan index permuter is programmed by specifying, as a
source for each of the 24 site-address bits, any of the 24 scan-index
bits or the contants 0 and 1 (cf.\ \sect{SIPR}). The transformations
thus obtainable include all the \tdf{combinations with repetition} of
the 24 scan-index bits---of which the permutations form a subset.  In
practice, however, permutations are all that we are generally
interested in.

The use of constants as sources of site-address bits during a scan is
illustrated by the following example.  Starting from the situation
of \fig{raster-xy} and \fig{scan-xy}, suppose we want to display
on the \crt\ screen a \tdf{magnified} view of just a portion of the
system. By modifying the scan index permuter arrangement as in
\fig{scan-4x}, each site of the array will be displayed four times, on four
consecutive pixels (since the two least significant bits of the scan
index are ignored), and similarly each row will be scanned four times,
thus giving a linear magnification of 4\by.

 \figonecol{scan-4x}{\psfig{file=fig/scan-4x.ps}}{By ignoring the two
least significant bits of the scan index, the same site will reappear
on four consecutive pixels, yielding a linear magnification of 4\by;
similarly, by ignoring two higher bits, the same row of the array
will reappear on four consecutive scan lines, yielding a vertical
magnification of 4\by. The constants on positions 7--8 and 16--17
select which portion of the array will be displayed in this magnified
fashion.}

The values of the constant site-address bits determine \tdf{which}
columns and rows are repeatedly scanned. With the values shown in
\fig{scan-4x} on positions 7--8 and 16--17, the magnified display will
show the upper-right portion (128\by128 sites) of the frame of
\fig{raster-xy}. Note that no updating must be taking places during
the magnified display.

\section{Kicking}\label{sect.kicking}

\tdf{Kicking} is the technique by which the data-transport stage
(\sect{updating}) is realized in \step. In this section we shall
restrict our discussion to a simplified situation involving a single
module.  The \tdf{gluing} of modules in a multi-module machine is
discussed in \sect{gluing}.

\medskip

As mentioned at the end of \sect{scanner} (also cf.\ \fig{scanner}),
the \dram\ address of a state-variable bit (\sect{sites-layers}) is
obtained by adding to its site address an \tdf{offset} specified by
the {\sym Offset Register} (\sect{OSR}); both site address and offset
are $d$-dimensional vectors, with the number $d$ of dimensions and the
number of bits devoted to each dimension determined by the {\sym
Dimension Cut Mask}, as explained in \sect{dimensions}.

The offset specifies where the origin of the bit array (site address
$\langle0,0,\ldots\rangle$) is located in \dram.  The operation of
modifying this offset, and thus shifting the origin of the array, is
called a \tdf{kick}. Kicking, of course, does not by itself physically
shift any data; however, it modifies the relative timing with which
data bits from different layers are fetched from \dram\ during a scan.
Bits that on the previous scan were fetched from \dram\ at the same
time---i.e., bits that belonged to the same ``bit pile''
(\cf{updating})---will, because of the change of offset, be fetched at
different times on the next scan; on the other hand, certain bits that
used to belong to different piles will now be part of the same pile: they
will be fetched from \dram\ together and will interact with
one another by going together go through the lookup table.

Kicking is done by subtracting from the {\sym Offset Register}
(\sect{OSR}) a $d$-dimensional vector specified by the {\sym Kick
Amount} field of the {\sym Kick Register} (\sect{KR}).  Further
aspects of kicking can only be appreciated in the context of
intermodule \tdf{gluing}, discussed in the next section.  In
particular, the other fields of the {\sym Kick Register} are only
relevant in that context. For more technical details, see also \sect{KR}.


\section{Gluing}\label{sect.gluing}

By modifying the offset, a kick influences the order in which the bits
of a layer are fetched from \dram.  If we restricted our attention to
a single, isolated sector, the net effect of a kick would be just a
virtual ``circular shift'' of layer data \tdf{within} the sector.
Because of address wraparaound, any data that shift out of, say, the right
edge of the sector are shifted back into the left edge of the same
sector (note that all this happens along each of the $d$ dimensions
separately, and typically with a different value of the kick for each
layer).

However, sectors are not isolated. After a bit has been shifted out of
one edge and before it is injected into the opposite edge, a process
called \tdf{gluing} switches the bit in question from the control of
the given module to that of an adjacent one, so that, in the above
example, the bit will be injected into the left edge of the sector
\tdf{immediately to the right} of the given sector. This happens in a
coordinated way on all right/left edges,\footnote
	{Using, as we shall see in a moment, the information
contained in the {\sym Kick Sign} and {\sym Kick Max Flag} fields of
the {\sym Kick Register} (\sect{KR}).}
	 effectively gluing homologous layers from all the sectors into
a single, machine-wide ``conveyor belt.''

\medskip

With gluing, some data actually move from one physical place to
another, i.e., from a certain \dram\ address in one module to the
identical \dram\ address in an adjacent module. Let us examine the
process in more detail, using, for sake of illustration, the case of a
one-dimensional array of length 8; the site address within each sector
will consist of three bits and will run from 0 through 7.

We shall assume that the lookup table contains the identity function
(i.e., the bit coming out of layer $n$ is returned unaltered to layer
$n$), so that no interaction between layers takes place.  In this way,
it will be sufficient to analyze the kicking and gluing of just one
layer.\footnote
	{This data movement in one layer is significant, of course,
only relative to the other layers with which it will eventually interact.
For simplicity, let us view the movement as taking place relative
to an unkicked layer.}

\figonecol{kick-0}{\psfig{file=fig/kick-0.ps}}{(a) Initial contents
of three adjacent sectors $a$, $b$, and $c$. (b) Actual layout of the
data in \dram, assuming a value of 5 for the {\sym Offset Register};
this value is indicated by the position of the dial pointer.}

Restricting our consideration to this layer, let us fix our attention
on three adjacent sectors, $a$, $b$, and $c$. In \fig{kick-0}a, the
sites are labeled by the site address (0 through 7); the initial
values of the bits contained in the three sectors are denoted by
$a_0,\ldots,a_7$, $b_0,\ldots,b_7$, and $c_0,\ldots,c_7$.  We want to
shift the layer data by 3 positions to the right, with the results
shown in \fig{kick-1}a.

\medskip

Now, let us look ``under the hood'' to see how this is actually done
in \step. In the \dram\ that implements sector $b$, the eight bits
$b_0,\ldots,b_7$ are found stored consecutively, but not necessarily
starting from \dram\ address 0. If the current offset is, say, 5,
that means that bit $b_0$ happens to be in \dram\ address 5, as shown
in \fig{kick-0}b.  Similar considerations apply to sectors $a$ and
$c$.

We shall assume that a complete scan of the site array will always run
through site addresses 0--7 in that order.\footnote
	{If the scan index permuter (\sect{scan-permuter}) specifies
other than the identity permutation, site addresses may be accessed
in a different order, but the overall results would be identical
tho those described here.}
	In the absence of a kick, the next scan will pick up bits
$b_0,\ldots,b_7$ in that order, that is, in the same order as they had
been deposited by the previous scan. In order to shift data by 3
positions to the right, we'll give a kick of +3; this kick will be
subtracted from the offset, resulting in an offset of 2 (=5$-$3).
In moving from the value of 5 to the value of 2, the offset
pointer will ``sweep'' over a certain fraction of the \dram\
circle, as indicated in \fig{kick-thru}.

\figonecol{kick-thru}{\psfig{file=fig/kick-thru.ps}}{In moving from
the value 5 to the value 2, the offset pointer swept over the shaded
\dram\ locations 4, 3, and 2.}

The next scan will start
picking up data bits from where the offset is pointing now, i.e.,
\dram\ address 2 (\fig{kick-thru}), and thus will successively get
ata bits
 $$
	b_5\ b_6\ b_7\ b_0\ b_1\ b_2\ b_3\ b_4 
 $$

\noindent from sector $b$ (cf.\ \fig{kick-no-glue}a), and similarly for
$a$ and $c$).  During the scan, each bit is eventually deposited back
to \tdf{some} \dram\ in the same order as it was picked up.

\medskip

\parhead{No gluing} In the absence of gluing, the scan would deposit
each bit in the same \dram, $a$, $b$, or $c$, where it found it, leaving
the situation as in \fig{kick-no-glue}.  Thus, with no gluing all that
physically changes is the offset; however the interpretation in terms
of site contents is now that of \fig{kick-no-glue}a: i.e., the data have
been rotated \tdf{within} each sector.

\figonecol{kick-no-glue}{\psfig{file=fig/kick-no-glue.ps}}{Changing
the offset without doing any gluing is equivalent to a rotation of
data independently within each sector. In this case, a kick of $+3$
has moved the offset (sector origin in \dram) three places
counterclockwise, equivalent to moving the data three places
clockwise.}

\medskip

\parhead{Gluing} Let us go back to the situation of \fig{kick-0}, and
this time apply the same kick of +3 but \tdf{with} gluing. The new
scan starts with \dram\ and offset as in \fig{kick-no-glue}b, and
picks up data bits as before, in parallel for the three sectors $a$,
$b$, and $c$, in the order
 $$
 \begin{array}{ccc}
	a_{\phantom{0}}	&b_{\phantom{0}} &c_{\phantom{0}}	\\\hline

	a_5	&b_5	&c_5	\\
	a_6	&b_6	&c_6	\\
	a_7	&b_7	&c_7	\\
	a_0	&b_0	&c_0	\\
	a_1	&b_1	&c_1	\\
	a_2	&b_2	&c_2	\\
	a_3	&b_3	&c_3	\\
	a_4	&b_4	&c_4
 \end{array}.
$$

\noindent And now the critical step. Before depositing a bit back to
\dram\ (in the same \dram\ address where it came from), if the bit came
from the \tdf{shaded} area in \fig{kick-thru} we will hand it to the
sector just to the \tdf{right}, and we will use in its place the
homologous bit that is handed to us at the same moment by the sector
just to the left, as follows
 $$
 \begin{array}{cccc}
	a_{\phantom{0}}	&b_{\phantom{0}} &c_{\phantom{0}}	& \\\hline

		&a_5	&b_5	&c_5	\\
		&a_6	&b_6	&c_6	\\
		&a_7	&b_7	&c_7	\\
	a_0	&b_0	&c_0	\\
	a_1	&b_1	&c_1	\\
	a_2	&b_2	&c_2	\\
	a_3	&b_3	&c_3	\\
	a_4	&b_4	&c_4
 \end{array}.
 $$

\noindent For example, just as module $b$ hands bit $b_5$ to module
$c$, it receives bits $a_5$ from module $a$, and that is the bit that
gets deposited in \dram\ address 2 in place of bit $b_5$.  Thus,
while bits $b_0$--$b_4$ go back to their original places, bits
$b_5$--$b_7$ will end up in sector $c$, where they will take the place
of bits $c_5$--$c_7$, while their place will be taken by bits
$a_5$--$a_7$ from sector $a$, as shown in \fig{kick-1}.

\figonecol{kick-1}{\psfig{file=fig/kick-1.ps}}{(a) Same sector
contents as in \protect\fig{kick-0}, but shifted three places to the
right. (b) This has been achieved by moving the offset pointer three
places to the left, sweeping over \dram\ locations 4, 3, 2 (shaded
areas). During the subsequent scan, the gluing process moved the
contents of these three locations in \dram\ $a$ to the corresponding
locations in \dram\ $b$ (and similarly between $b$ and $c$).}

In conclusion, bits coming from the shaded area of \fig{kick-thru}
move one sector to the right before going back to \dram, while bits
coming from the clear area remain in their sector; in either case, the
\dram\ address of each bit remains unchanged.

\medskip

\parhead{Negative kick} Let us consider now a kick of $-5$ rather than
$+3$. Since the sector is of size 8, arithmetic is done modulo-8. The
{\sym Kick Amount} (\cf{KR}) is the same in both cases, nad
the offset pointer will land on the same position as in
\fig{kick-thru}. However, the {\sym Kick Sign} filed of the {\sym Kick
Register} keeps track of the fact that the pointer swept clockwise
over \dram\ locations 5, 6, 7, 0, 1 (\fig{kick-thru-neg}), rather
than counterclockwise over 4, 3, 2.

\figonecol{kick-thru-neg}{\psfig{file=fig/kick-thru-neg.ps}}{The shaded area
represents the fraction of \dram\ swept over by the offset pointer for a kick
of $-5$ (cf.\ \protect\fig{kick-thru}).}

As long as no gluing takes place, the results are the same as those of
\fig{kick-no-glue}. However, with gluing turned on, it is the data in
the new shaded areas (\fig{kick-thru-neg}) that hop from sector to
sector during the scan; moreover, as directed by the {\sym Kick Sign},
they will be handed by each sector to the sector immediately to the
\tdf{left}, with the results of \fig{kick-1-neg}. 

\figonecol{kick-1-neg}{\psfig{file=fig/kick-1-neg.ps}}{The result
of a $-5$ kick with gluing, starting from the situation
of \protect\fig{kick-0}. The shaded area in (b) is complementary to that
of \protect\fig{kick-1}; bits in the shaded areas move to the sector immediately
to the \tdf{left} of their sector, and the results in terms of sector contents
(b) are a wholesale shift of 5 places to the left.}

\medskip

If $n$ is the number of site address bits assigned to a certain
dimension by the {\sym Dimension Cut Mask} (cf.\
\fig{dimension-cuts}), then any kick value from $2^{-n}$ to $2^{+n}$
is admissible.

The two end-points of this range are only relevant for an extendible
dimension, and when gluing is in force.  A kick of $2^{-n}$
corresponds to copying the entire sector to the one before it along
that dimension; similarly a kick of $2^{+n}$ copies each sector to the
one after it. If the dimension is not extendible, or if gluing is
turned off, then both these extreme values for the kick coincide
with a kick of 0.

\medskip

The gluing process explained above takes place independently for each
of the extendible dimensions.





