 % -*- Mode:TeX -*- 
\documentstyle{article}
\input cam8form.tex

\begin{document}
\input notecomm.tex
\input notemath.tex

\let\sym\sf	    % symbols done in sans serif
%\let\sym\tt	    % symbols done in \tt

\title{\MACH\ data movement and interaction}



\newcommand{\symdex}[1]{{\sym #1}}

\newcommand{\mach}{{\sc step}}
\newcommand{\Mach}{{\sc Step}}
\newcommand{\MACH}{STEP}
\newcommand{\dram}{{\sc dram}}
\newcommand{\Dram}{{\sc Dram}}
\newcommand{\sram}{{\sc sram}}
\newcommand{\Sram}{{\sc Sram}}
\newcommand{\layer}{layer}


\newcommand{\Land}{{\sc and}}
\newcommand{\HI}{{\sc hi}}
\newcommand{\LO}{{\sc lo}}

\newcommand{\risc}{{\sc risc}}
\newcommand{\ram}{{\sc ram}}
\newcommand{\vlsi}{{\sc vlsi}}
\newcommand{\side}{\ell}                % "side": no. of rows or columns
\newcommand{\ply}{p}                    % "ply": the number of bit-planes in a module.
\newcommand{\stat}{S}                   % "static column capacity": information of a column = 2+side
\newcommand{\size}{N}                   % "size": information of the entire chip = 2+2*side
\newcommand{\multi}{d}                  % "multi": the number of dimensions of the model
\newcommand{\kick}{k}                   % "kick": amount of kick offset

 \newenvironment{examples}{\medskip\footnotesize{\sc Examples:}
        \begin{list}{\arabic{section}.\arabic{enumi}}{\usecounter{enumi}\topsep0pt\itemsep0pt}}{\end{list}}



\maketitle

\begin{history}
        \item[TT Mar 89] Started.
        \item[TT May 89] Major additions and revisions.
\end{history}

\section{Overview}

\Mach\ is a multiprocessor architecture optimized for fine-grained
simulations of physical systems.  From a functional viewpoint, the
\mach\ architecture can be thought of as a spatially-extended,
uniform, fine-grained medium of a rather general and abstract nature.
Specific behavior is obtained by specifying the medium's connectivity
and dynamical properties, and assigning its initial state.  In this sense,
\mach\ embodies the metaphor of ``programmable matter.''

In the \mach\ modeling environment, spacetime is conceived as a
uniform, indefinitely-extended, discrete lattice consisting of
point-like {\em events} connected by arc-like {\em signals}
(\fref{simple-lattice}).  An event can be thought of as the locus of
interaction of signals: a certain number of signals converge as inputs
to an event, interact according to a specified rule, and new signals
emerge as outputs.  Between events, signals travel unchanged.

We shall restrict our attention to an implementation in which all
signals are {\em binary}, i.e., can be in one of two states. Signals
from a larger state set can always be synthesized as ``bundles'' of
binary signals.

\medskip

In \mach's most basic mode of operation, the number and
nature of signals involved in an event, their origin and destination,
and the interaction taking place at the event itself obey a strict
discipline:
    \begin{itemize}
        \item At every event, to each input signal having a given
spacetime slope (i.e., traveling in a certain direction and at a
certain speed) there corresponds exactly one output signal, with the
same slope.  
        \item The interconnection geometry (i.e., number and slope 
of signals) and the interaction rule are identical for all events.  That
is, the system's {\em structural} specifications are uniform in
spacetime.  
    \end{itemize}

What will differ from event to event are, of course, the {\em states}
of the signals.  Indeed, it is the spacetime distribution of these
states that represents the system's evolution.


\medskip

Let us visualize the behavior of such as system under the most trivial
interaction rule, namely, ``no interaction at all,'' specified by the
{\em identity} function (each output is identical to the corresponding
input).  Then each bit of data will travel with constant direction and
speed, describing a straight line through spacetime.  In other
words, the most elementary form of behavior, when all interactions are
turned off, is {\em inertial} motion.

A special case of inertial motion is, of course, when a signal travels
at zero speed, i.e., when it connects a sequence of events that occur
at what can be regarded (in a given reference frame) as the ``same
site'' in space. Such a signal represents a bit of localized memory,
and can be used as a parameter.






In practice, the interconnection geometry and the interaction rule
can be 


  To each site
there are associated a certain number of bits of data, equal for all
sites, which encode the state variables and the parameters associated
with that site.  The collective state of these bits is called the {\em
state} of the site.

The basic processing unit of \mach\ is the {\em module}, which
represents a contiguous, regularly-shaped region of space called {\em
tile}; that is, the module contains all the machinery needed to encode
the state of its sites and compute their temporal evolution according to
prescribed laws.  By {\em gluing} edge-to-edge a sufficient number of
modules, one can represent an arbitrarily large region of space.



  The shape of
a tile is an 

\subsection{Conveyors and interactors}\label{module}

The \mach\ architecture is based on an original device called the {\em
conveyor}.  The principal function of this device is to organize the
contents of a conventional random-access memory into a
multidimensional array of individual bits, and sequentially scan the
array in any of a variety of sequences related to the array's
multidimensional structure.  Regardless of the actual number of
dimensions, it will be convenient to refer to this array of bits as a
{\em bit-layer}, or simply {\em \layer}. When speaking of the
conveyor, we'll usually mean not just the data-access mechanism, but
also the data themselves, i.e., the associated bit-\layer.

In a typical scan, the current value of each bit is read and placed on an
output stream (the {\em current} stream), while a new value, picked up from an
input stream (the {\em updated} stream), is written back in its place---so that
by the end of the scan the entire array has been updated.  Thus, the conveyor
is responsible for data movement in and out of the array; the actual
computation of updated values is the responsibility of a separate device,
called the {\em interactor}.

\medskip

The interactor can be thought of as a deterministic, memoryless transducer with
a certain number $\ply$ of binary inputs and an equal number $\ply$ of binary
outputs.  One interactor is served by $\ply$ conveyors which, acting in
concert, feed their current streams to it and receive from it their updated
streams (Figure \ref{fig.module}).  In streaming their data through the interactor,
conveyors act in lockstep according to a preordained routine, so that $\ply$
bits, one per conveyor, are simultaneously submitted to the interactor; in a
similar way, each conveyor will be ready to accept one of the $\ply$ bits that
are simultaneously produced by the interactor.  Conveyors do not communicate
with one another, and do not sense or modify the variables that they carry; the
only data-dependent action on the streams, as well as the only communication
between streams, takes place in the interactor itself.

\figone{fig.module}{\colwidth}%
{A \mach\ module, consisting of an interactor and a certain number of
conveyors attached to it.}

The structure consisting of an interactor and the $\ply$ conveyors attached to
it is called a {\em module}. As we shall see later, modules can be
interconnected to one another along three axes, so as to form a multiprocessor
capable of handling arrays that are arbitrarily extended in three dimensions.

The function computed by the interactor will typically remain the same during
an entire scan, but may change from one scan to the next.  Similarly, the
sequential order in which each conveyor accesses the associated array is
completely determined at the beginning of each scan, but may change from one
scan to the next.  For the above reasons, it will be useful to conceptually
regard a scan as an indivisible processing {\em step} acting in parallel on the
entire $\ply$-component array; from this viewpoint, the specific function
programmed into the interactor and the specific access sequences programmed
into the conveyors can collectively be thought of as a \risc-like ``machine
operation'' performed by the module on that step.

\subsection{Implementation briefs}

In \mach, a bit-\layer\ is stored in a single \dram\ chip having a capacity of
$2^\size$ bits (a typical value for $N$ is 20, corresponding to 1M bits); the
conveyor is implemented as a custom \vlsi\ chip (of the order of 10K gates).
Since all the pins of the \dram\ are directly and exclusively controlled by the
associated conveyor, from a conceptual viewpoint the \dram\ can be thought of
as being internal to the conveyor itself.


For reasonably small values of $p$ (the number of \layer{}s in a
module), it is practicable to realize the interactor as a direct lookup
table, consisting of $2^\ply$ $\ply$-bit entries.  In the standard
version of \mach, where $\ply=16$, this lookup table consists of a
\sram\ chip with 16 address lines and a 16-bit wide word, for a total
capacity of 1M bits.

A reasonable access time for a conventional \sram\ of this size is 40 nsec.  On
the other hand, a conventional static-column \dram\ has a cycle time (for a
read-write cycle) of, say, 160 nsec.  By using nybble-wide \dram{}s (and
letting the conveyor take care of the attendant parallel-to-serial and
serial-to-parallel conversion) one obtains a good match between \dram\ and
\sram\ bandwidth.  Indeed, a clock time of $\tau$=40 nsec for the bit streams
(corresponding to 25 Mbits/sec) will exploit at sustained full bandwidth
all three kinds of resources used in a a module (\dram\ for the
bit-\layer{}s, \sram\ for the lookup tables, and custom \vlsi\ for the
conveyors).

Moreover, with the above parameters, the updating time for a module (and
therefore for a system consisting of any number of modules, since modules
operate in parallel and are only locally interconnected) amounts to 40 msec,
yielding a frame rate of 25/sec (like a conventional movie); this is
an acceptable rate for real-time display. Note that in typical circumstances
the scanning of a module will be performed in a sequence and at a rate
comparable to the raster scan of an ordinary {\sc crt} monitor, so that
no frame buffering need to be provided.

\medskip

For larger values of $\ply$ (some interesting lattice-gas models require 24 or
more \layer{}s), direct lookup becomes impractical, and one must make
recourse, for the interactor, to an ad hoc sequential network (e.g., a few
levels of lookup assisted by a few levels of random logic).  In the \mach\
architecture, a latency of up to a few dozen clock times between interactor
input and output can be accomodated without affecting overall
throughput---provided that the interactor is fully pipelined, i.e., still
accepts input data from the current streams and returns output data to the
updated streams at the full clock rate.

An alternative solution, using the standard version of \mach, is to synthesize
a ``super-module'' out of 2, 4, or 8 individual modules, yielding up to 128
\layer{}s.  The updating of this supermodule will be done by a
``super-step''---a sequential algorithm consisting of a programmed sequence of
individual steps.  Typically, the contents of the lookup tables will be changed
at every step of this sequence, according to the needs of the algorithm.  Since
the look-up tables are still 16-bit wide, substantial and repeated data
transfers between modules may be necessary to achieve the desired interaction
between the desired number of \layer{}s, and some of the available \layer{}s
may have to be devoted to holding state-variables of the algorithm rather
than of the simulation proper (temporary registers).

\medskip

For convenience of exposition, the above representative values of
certain parameters (namely, $\size$=20, $\ply$=16, $\tau$=40 nsec, and
nybble-wide \dram) will be used as actually design values in the
following discussion, unless otherwise noted.


\subsection{Operation brief}

Before going into more detail, it will be useful to analyze the simplest
and most typical mode of operation.  Let us assume for simplicity that
the 16 bit-\layer{}s are actually organized as {\em one-dimensional}
arrays---bit-``tapes''---which for the moment we shall assume to be of
indefinite extent, so as to avoid boundary issues.  We can visualize a
bit-tape as a strip of paper, regularly subdivided into squares, with a
0 or a 1 written in each square; and the entire data structure as stack
of 16 such strips, superposed on one another in good registration,
yielding a vertical {\em pile} of 16 bits at each site (Figure
\ref{fig.tape}).

\figone{fig.tape}{\colwidth}{Bit-tapes and bit-piles.}

A step will consist of two distinct phases:
    \begin{enumerate}
        \item {\em Transport.}\quad Take each of the tapes and independently
shift it longitudinally by an arbitrary number of sites (a null
shift is allowed), so that the makeup of every pile changes but we
still end up with a one-dimensional array of 16-bit piles.
        \item {\em Interaction.}\quad Take one of the piles and give it to the
interactor; the interactor returns a new pile, which we put in place of the
original one.  Do the same to another pile, and so forth, until all piles have
gone through the interactor.  Note that piles are processed {\em independently}
of one another (the interactor is memoryless), so that the order of access is
irrelevant---all we care is that each pile be put through the interactor
exactly once.
    \end{enumerate}        

A typical simulation run with \mach\ will simply consist of indefinite
iteration of the above two-phase step---always using the same look-up table for
the interactor and always shifting the same tape by the same amount at every
step.

\medskip

Let us consider a run in which phase 2 is effectively turned off (by using the
identity lookup table in the interactor).  Then the contents of each bit-tape will
move, step after step, at a constant speed, and phase 1 reduces to a
prescription for {\em inertial motion}.

If we turned off phase 2 instead (by using null shifts), then each
bit-pile would behave as an isolated {\em finite-state automaton}.

Combining the two phases yields an array of {\em uniformly interconnected
finite-state automata}. Each bit-tape that does not move contributes one
bit of {\em memory} to the individual automaton, while each bit-tape that
moves contributes one bit of {\em input} and, correspondingly, one
bit of {\em output}.

\medskip

An appealing way of viewing the above process is as a {\em spacetime} history.
In Figure \ref{fig.spacetime}, where for clarity we use only one three
bit-tapes, the bundle of arcs entering a node represents the state of an
individual pile just before an interaction (phase 2), and the bundle leaving a
node, the state after the interaction.  A directed arc connecting two nodes
represents the transport, from origin to destination (phase 1), of an
individual bit.  Thus, phase 1 (arcs in the picture) characterizes {\em
signals}, and phase 2 (nodes in the picture) {\em events} in spacetime.  One
may think of the signals as ``particles'' in free flight, and of the events as
``collisions'' between these particles (with possible annihilation of particles and creation
of new particles).

\figone{fig.spacetime}{\colwidth}{This spacetime diagram illustrates
the flow of data for three bit-tapes that are shifted
by respectively 1, 0, and -2 grid positions at each step.}

Note that in this spacetime view the distinction between memory and
communication vanishes. Memory is just the special case of a signal
being sent from one event to another event that, in a particular inertial
frame, happens to be in the same place (vertically oriented signals
in Figure \ref{fig.spacetime}).

\bigskip

Note that the process of shifting an entire bit-tape by a specified
number of sites (phase 1) is a uniform, {\em data-blind} operation. For
each bit-tape separately, one could in principle achieve the same result
by shifting one's frame of reference rather than the data themselves.
In \mach, where individual bits of each bit-\layer\ are accessed
sequentially, this feature leads to a very natural and efficient way of
implementing the transport phase, as we shall explain in a moment.

A few paragraphs above we had considered arrays of {\em indefinite} size.  Such
arrays can in fact be contructed with the \mach\ architecture by ``gluing''
together an indefinite number of modules (\sect{}).  At present however, we
will be concerned with a single module, where each bit-\layer\ is a {\em finite}
data-structure---organized, in the present example, as a one-dimensional array
of $2^\size$ bits.  All arithmetic on the addresses used for pointing to
particular sites of this array will be done modulo $2^\size$, which is
equivalent to thinking of the array as wrapped around, with the right edge
glued to the left edge.  In this context, a `shift' of the \layer\ will mean a
{\em circular} shift.

\medskip

Let us perform a step by scanning all of a module's \layer{}s concurrently
and in lockstep.  Each \layer\ will be scanned in regular ascending order; we
may think of using an address pointer that starts from 0 and is repeatedly
incremented so as to successively point to every element of the array.  The
successive piles of 16 bits (one bit for each \layer) encountered during the
scan will be given to the interactor and replaced with updated piles, as
explained in \sect{module}.  At the end of this step, the pointers will all
have cycled back to the value of 0.

Before beginning the next scan, let us {\em kick} the initial value of
the pointer of \layer\ $k$ by adding to it a certain amount, say, +4,
and then proceed as above.  Then the bit at address 4 of \layer\ $k$ will
appear on the current stream at the same time as the bits at address 0
of the remaining \layer{}s; the bit at address 5 at the same time as those
at address 1, and so on.  Thus, as far as the \layer{}s' physical
contents are concerned, this scan will give the same results as if,
instead of altering the initial value of the pointer for \layer\ $k$, we
had
\begin{enumerate}
	\item shifted the entire {\em contents} of
\layer\ $k$ by 4 positions to the left before the beginning of the
scan,
	\item performed the scan, letting this \layer\ interact with the
others, and then
	\item\label{item.back} shifted the \layer\ by 4
positions to the right, i.e., restored it back to its original
alignment.
 \end{enumerate}
	The pointer for \layer\ $k$, however, will
have cycled back to its initial value of 4 at the end of the scan.  If
we take this position in the array as the new {\em logical} origin of
\layer\ $k$ (as contrasted to its {\em physical} origin, which is
always at physical address 0 by definition), then the restoring
operation (\ref{item.back} above) will in effect not have taken place;
the \layer\ will appear to have shifted by the desired amount before
the scan, and remained in the new alignment after the scan.

To sum up, one can always ``pretend'' that a bit-\layer\ has shifted by
a certain amount---by looking at it from a different reference frame. To
turn this pretense into a fact that will actually affect the dynamics of
the system, in \mach\ it is sufficient to correspondingly shift the {\em
temporal} sequence in which the different bits are accessed during the
interaction phase.  Moreover, it is clear that such a manipulation of
the reference frame can be performed {\em independently} for each
\layer, so as to exactly mimic the results of the transport phase.
Finally, such manipulations are {\em cumulative}; we can associate with
each \layer\ an {\em offset register}, which points to the current
logical origin of the bit-array, and which is kicked by an amount $-m$ every
time we want to perform a virtual shift of $+m$ with respect to the
current alignment of the layer.

We are thus led to considering five different quantities, each of which will be
explicitly represented in the conveyor:
    \begin{itemize}
        \item {\em Physical address.} This is the physical address of a bit
within the \dram\ chip in which the layer is stored.\footnote
        {Since this memory is nybble-oriented, the two least-significant
bits of this address will actually point at a bit within a nybble.}
        \item {\em Kick register.} This register specifies the amount of shift
that is to be applied to the layer during the transport phase.  It is set
by the user, and it may change from time to time depending on the needs of the
simulation.  Since it actually prescribes the coordinate transformation
equivalent to the desired shift in the data, a positive value of this register
corresponds to a negative shift.
        \item {\em Offset register.} This register, which is incremented at
each step by the value of the kick register, points at the current logical
origin of the bit-array that makes up the layer.
        \item {\em Site address.} This is the logical address of a particular
bit (a site address of 0 corresponds to the logical origin of the array).
To find the actual physical address of that bit, add the value of the
offset register. In what follows, a `site' will always mean a logical
site, since the particular mechanism by which shifts are achieved
must remain totally transparent to the user.
        \item {\em Scan address.} This is the sequential position in which a
site is accessed during a scan.  Scanning need not be in regular ascending
order.  For example, one may want to scan first the even-numbered sites and
then the odd-numbered ones, in which case to scan addresses 0,1,2,\ldots\ there
will correspond site addresses 0,2,4,\ldots.
    \end{itemize}

In the next section we shall formalize the above concepts and generalize them
to multidimensional arrays.

\subsection{Scan, site, and memory addresses}

In typical operation, all conveyors are programmed to arrange the
associated bit-\layer{}s into arrays of the same {\em shape} (i.e., same number
of dimensions and same size along each dimension), and to scan the elements
of these arrays in the same sequential order, so that there is a natural
correspondence between bits on the different \layer{}s: to each site of
the common array structure there are associated $\ply$ data bits, one
for each \layer.  Thus, within a module, each data bit may be
identified as residing at a particular {\em site} and on a particular
{\em \layer}.\footnote {In special circumstances, one may have
reasons to let interactions take places between arrays having different
shapes, or to scan different layers in different sequential orders,
so as to that deliberatly violate this correspondence. Our definition of
`site' will remain meaningful even in such situations.}


\medskip

The basic data structure of \mach\ is the {\em bit-plane}, a collection
of $2^\size$ bits naturally organized as a binary $\size$-cube; that is,
each of the $2^N$ bits is labeled by a distinct assignment of 0s or 1s
to an indexed collection of $\size$ variables called {\em components} or
{\em address lines}.  This structure is invariant under a permutation of
the address lines.

In any particular \mach\ experiment, this structure is further specialized as follows:\footnote
        {Still further specialization, involving the {\em gluing} of bit-planes, is irrelevant
here and will be discussed later.}
    \begin{enumerate}
        \item The set of $\size$ components is arbitrarily ordered, and then
consecutively segmented into $\multi$ nonempty subsets called {\em
dimensions}, of sizes $\size_1,\size_2,\ldots,\size_\multi$ (with
$\size_1+\size_2+\cdots+\size_\multi=\size$).
        \item The sequence of $\size_i$ binary components that make up the
$i-th$ dimension spans a set of $2^{\size_i}$ distinct values.  These values
are given the natural cyclic ordering (of the integers modulo $2^{\size_i}$)
that derives from treating the $\size_i$ components as binary digits (least significant
digit first).
    \end{enumerate}
After this, the bit-plane will have attained the structure of a $\multi$-dimensional
hypertorus, with a circumference $2^{\size_i}$ along the $i$-th dimension.

\medskip

The basic processing step of \mach\ consists of
    \begin{enumerate}
        \item Shifting the hypertorus by an amount $\kick_i$ along the $i$-th
dimension, for each $i=1,2,\ldots,\multi$.
        \item Updating its contents by scanning the individual
bits in a definite sequential order, and replacing the value of each bit
by a new value
    \end{enumerate}


State-variables in \mach\ are stored in a number of individually addressed
\dram\ chip.  Specifically, we shall consider nybble-wide, static-column chips,
with 4-bit nybbles; for the moment, however, we shall ignore these details of
internal organization (and the associated timing issues), and we shall treat
the chip simply as a collection of $2^N$ bits, individually accessible via
a set of $N$ binary address lines.  Informally, we shall call this collection
of bits a ``bit-plane.''

A bit-plane, then, is naturally organized as a binary $N$-cube, whose $N$
components are in a one-to-one correspondence with the chip's address lines.
Though these lines are individually marked on the manufacturer's spec sheets,
they are not, at the present level of analysis, intrinsically distinguishable.
In other words, the structure of the hypercube is invariant under an arbitrary
permutation of its components.

A {\em step} of \mach\ consists in replacing



The basic storage device for \mach\ is an

Nybbles are addressed by $\side$ {\em row address} lines and $\side$ {\em
column address} lines, corresponding to $2^\side$ rows and an
equal number of columns.  The total amount of storage on the chip is then
$2^\size=2^{2\side+2}$ bits ($\side=9$, 10, and 11 correspond, respectively,
to 1M, 4M, and 16M chips).  

Once the row address has been issued, the entire row becomes accessible as a
static \ram\ consisting of $2^\side$ nybbles, for a total of
$2^\stat=2^{\side+2}$ bits.  Since the unit of physical access to the
\dram\ is the nybble, access to individual bits within a nybble will be
mediated by buffering at the nybble level (e.g., serial/parallel conversion).


 is {\sl updated} by scanning (the whole or part of) it in a
specified sequential order, writing new data back to the same location where
the old data came from. The new data depend on the old data of 
several old-data from homologous



\medskip

For a moment, let us ignore the \dram\ addressing hierarchy (row address,
column address, bit position within a nybble) and the associated access-time
issues.
Now, let us consider an ordered partition the hypercube's $N$ components into $D$
subsets, of sizes $N_1$ which we shall call {\em dimensions}.  The first
three dimensions, which we shall call $x$, $y$, and $z$, will eventually be
distinguished by special hardware.  Within each dimension, let us order the
components of the hypercube

In \mach, a ``bit-plane'' (we shall keep using this term even though,
depending on the actual number of dimensions in which the data are organized,
it may be more proper to speak of a ``bit-cube'', ``bit-segment'', etc.) is
stored in a



Several (typically, 16) bit-planes are stacked together in a module







, we shall strive as far as possible to maintain
a steady stream of bits
at the nominal {\em bit rate}, which we will take to be 40MHz
({\em bit time}=25nsec).\footnote
        {Nominal target speed is  25MHZ (40nsec), but here we'll try to overshoot, for safer
design.}
        Within static-column mode, a read cycle or a read cycle each take two bit
times, so that one of each can be accommodated within one nybble time.  Also row
addressing takes one nybble time. With some exceptions to be discussed later, 
bits are read from one location, injected into a pipeline, and eventually returned
(as updated bits) to the same location with a delay of a few nybble times.

\subsection{One-dimensional array}

Let us consider a one-dimensional array of length $2^n$, scanned sequentially
and in its entirety.  As long as $n<\stat$, the array can be stored entirely
within one \dram\ row, and no row-address changes need to occur during the
entire scan.  Note that the scan need not start on a nybble boundary; in
general, the fist

For a longer array, row-address changes will occur, and the only way to be
assured that such changes will occur only at the boundary between sweeps is to
reduce the length of the sweep to just one site!\footnote
        {Even if the scan is subdivided into sweeps that are
no longer than $\stat$, there is in general no guarantee that a row change will
fall on an even multiple of $\stat$, or that such changes will all occur at the
same time in different bit-planes.}
        However, if the sweep itself is no longer than $\stat$, we can
guarantee that {\em no more than one row-address change} will occur during the
sweep.  Thus, a mechanism for digesting on-the-fly up to one randomly-placed
row change will allow us to make sweeps of any length from 1 up to $\stat$.

    \begin{examples}
        \item An array occupying an entire 1M \dram\ can be scanned by 512 sweeps of length 2048, with
minimal overhead. The same array can be analyzed as 64K blocks of 16 sites each (for
local averaging) with approximately \by3 overhead.
        \item With a 1M \dram, a 256K one-dimensional space can be scanned
by 512 sweeps of length 512, and displayed as a solid square of 512\by512 on
a 30KHz monitor.
    \end{examples}

\section{Sector scanning}




\subsection{Scan}

A {\em scan} is the process whereby a number of sites within a sector, up to
the size of the entire sector, are accessed sequentially for examination (read
only) or updating (read/write); the updating may be restricted to selected
bit-layers.

The sequence of site accesses during a scan is indexed by the {\em scan
counter}, which sequentially produces consecutive {\em scan
addresses} in the range 0--$2^N-1$. The scan counter is binary-encoded
and wraps around modulo $2^N$.

For each scan, one may specify the {\em length} and the {\em origin} of the
scan sequence.  The scan length must be a (nonzero) power of 2, and its
origin a multiple of the same power of 2.  If length and
origin are not specified afresh, a scan will have the same length as the
previous one, and will start where the previous one left off).

The scan addresss, i.e., the sequence index, is converted to a sequence element,
i.e., a {\em site address}, by the {\em scan permuter}, which performs an
arbitrary permutation of the bits that make up the scan address. 
The resulting binary string is the site address.

\medskip

There are $N-1$ distinct places where the site-address string, of length
$N$, can be cut.  With each of these points there is associated a binary
flag in the {\em dimension register}, specifying whether a cut should
indeed be made at that place.  Thus, according to the current contents of
the dimension register, the site-address string results segmented into
$D$ substrings (with $1\leq D\leq N$), called {\em dimension components}
(of the site address).  If $n_d$ is the number of bits of the $d$-th
component, one has
 \begin{equation*}
	1\leq n_d\leq N,\quad {\rm and}\quad \sum_{d=1}^D n_d=N.
 \end{equation*}






\medskip

The scan-address lines are grouped into three groups, namely (site)-bit,
(site)-column, and (site)-row. Consider the highest column line that
is not affected by the permuter. If 

\subsection{********}

A {\em sweep} is a noninterruptible portion of a scan, during which valid data
appear on the public streams in a predictable and regular timing pattern whose
origin coincides with that of the sweep itself, so that meaningful real-time
interaction of the data-streams is possible.

From a practical viewpoint, a sweep is a portion of a scan spanning (possibly
sparsely) a block that is no larger than a \dram\ row, and during which we can
guarantee a priori (that is, independently of the contents of the offset
register) that there will be no more than one row-boundary traversal.  The
rationale behind the definition of a sweep is the following.

\medskip

{\small 
Row-boundary traversals entail issuing a RAS cycle, and thus inserting a gap in
a steady sequence of CAS-only cycles.  These gaps will generally occur at
different moments on different bit-planes, since the offset registers 
may have different values.  To maintain over an entire scan the required
synchronism between the public streams of different bit-planes, the gaps will
have to be reabsorbed before they appear in public.  This entails providing
pipeline buffers of a size proportional to the maximum expected number of row
changes, and priming these buffers full before any data are ever put on the
public streams; each gap in the steady generation of data due to a row change
will then be tided over by data previously accumulated in the buffers.
However, since a scan may jump from row to row much more often than when scanning
an entire row at a time, a practically {\em indefinite} amount of buffering would
be required.

To circumvent the above problem, the obvious solution is to subdivide the scan
into separate sweeps.\footnote
    {Note that some form of regular suspension of the scan is needed in any case
for a different reason, i.e., in order to issue bursts of refresh pulses to the
\dram---since the time needed to scan the entire \dram\ is longer than the maximum
allowed interval between refreshes.}
        For any given scan, the sweep length will depend on the scanning
sequence of all the bit-planes involved; that is, one will choose a sweep
length such that during that time none of the bit-planes may have accumulated
more than an established maximum number of row changes.  In this way, pipeline
buffers a {\em fixed} size will do.  These buffers will be re-primed for a
fixed amount of time at the beginning of every sweep, and during this time the
public streams will be suspended.

Because of RAS timing constraints (and also because we may have performed
refresh cycles between sweeps), a RAS cycle must occur just before the
beginning of every sweep, regardless of whether the row address actually
changed from the end of the last sweep.  For any particular scanning pattern,
why not try to make the sweep short enough to insure that all row changes take
place {\em between} sweeps?  In this way, no RAS gaps would appear {\em within} a
sweep, and thus no pipeline buffering would be needed.  We shall show that in many
cases of practical interest this approach would lead to intolerably short
sweeps (either in terms of overall efficency or of real-time-display
requirements).  However, a dramatic performance improvement (and one that is
adequate for our purpose) arises as soon as one introduces a pipeline buffer
capable of absorbing a {\em single} row-change, as explained below.

In the hierarchical ordering of dimensions established by the dimension
register, consider a block of dimension $k$, composed of $N_k$ blocks of
dimension $k-1$.  Suppose that the block of dimension $k$ occupies two or more
\dram\ rows (always a power of 2), while the blocks of dimension $k-1$ are much
smaller than one \dram\ row.  Then, while within each of these smaller blocks
there will be no row boundaries, a row boundary may appear anywhere between two
adjacent smaller blocks.  If within the same sweep we scan through as many as
two of the smaller blocks, we risk encountering the row boundary during the
sweep even if the entire sweep is much shorter than one row.  On the other
hand, in this situation we can scan through as many of the smaller blocks as we
want, up to a total length equivalent to the length of one row, without risking
encountering {\em more than one} row boundary. Thus a mechanism capable of
absorbing a single row boundary will make a great deal of difference.

\par}
    \begin{examples}
        \item Let the entire array be organized as a single dimension,
1K row long.  The next lower dimension consists of
single-site blocks.  Even if we sweep only two sites at a time, we may still
encounter a row change between these two sites; thus, without row-change
buffering capabilities, we are restricted to sweeps consisting of {\em a single
site}, and the scan will have to consist of {\em 1M} separate one-bit
sweeps! Note that the overhead of a sweep (\sect{}) may be of the order of a few dozen
bit-clock times, so that the overall updating rate will be degraded by one to two
orders of magnitude.

On the other hand, with a mechanism capable of absorbing a single row boundary,
we'll be able to make 1K sweeps of 1K sites each.  At this sweep length, the
sweep overhead is negligible.
        \item Suppose we have three dimensions, $x$, $y$, and $z$, of size
64\by64\by64.  To display the entire cube on a CRT, we'll cut it along the $z$
dimension into 64 $x$\by$y$ slices of size 64\by64, and we'll spread these
slices on the two-dimensional face of the CRT, as an 8\by8 array of slices.
During the first raster line, the top row of the first slice will be scanned
and displayed in real time, immediately followed by the top row of the second
slice, and so on, terminating with the top row of the 8-th slice.  Each raster
line is followed by a horizontal-retrace interval---a natural place to
terminate a sweep and start a new one.  The second raster line will display the
second row of the same 8 slices; and so forth to the 64-th raster line, which
will display the 64-th row.  The 65-th raster line will display the top row of
the second group of 8 slices, and so on until the 512-th raster line, which
will display the bottom row of the last group of 8 slices.

...
    \end{examples}


There are two kinds of sweep
    \begin{itemize}
        \item In a {\em closed} sweep, the row part

    \end{itemize}

\end{document}