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

{\em 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 {\em 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 {\em 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 {\em 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}). The other fields
of the {\sym Kick Register} are only relevant to the intermodule
gluing process (cf.\ next section).


\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 {\em 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 {\em 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
{\em 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.}

\figonegiven{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 offset
(as indicated by 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}.

\figonegiven{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 {\em some} \dram{} in the same order as it was picked up.

\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 {\em within} each sector.

\figonegiven{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 {\em 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 {\em shaded} area in \fig{kick-thru} we will hand it to the
sector just to the {\em 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.ps}

\figonegiven{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.\ \sect{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.

\figonegiven{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
{\em left}, with the results of \fig{kick-1-neg}.

\figonegiven{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 {\em left} of their sector, and the results in terms of sector contents
(b) are a wholesale shift of 5 places to the left.}

\medskip

Together, the {\sym Kick Amount} and the {\sym Kick Sign} encode the kick
in two's complement notation. In the present example, with a sector
length of 8, the {\sym Kick Amount} is three bits wide, and the two fields
together can represent any kick value from $-8$ to $+7$. However, a kick
of $-8$ (the entire contents of each sector is copied to the sector on its
right) is also possible. This case is represented by a value of 1 in the
{\sym Kick Max Flag}, as more explicitly tabulated in \eq{kick-range}.

