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


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

 \begin{figure}[htb]
  \psfig{figure=/im/tt/ps/yard.ps,height=2in,width=2in}
  \caption{Testing}
 \label{fig.module}
 \end{figure}


\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.


  \psfig{figure=/im/tt/ps/yard.ps,height=2in,width=2in}


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.

\end{document}