% -*- Mode:Text -*- 

\addtocontents{toc}{\newpage}

\appendix

\chapter{The CAM-8 architecture}\label{sect.cam8}

Conventional computers can, of course, be programmed to run
cellular-automata-like models. However, if ordinary electronic
hardware in an amount comparable to that in a Cray {\sc x-mp} or a
Thinking Machines \cm-2 is configured into the architecture described
here, one obtains a flexible computer capable of running cellular
automata at least two (and in many cases three or four) orders of
magnitude faster.


\section{What is programmable in programmable matter?}\label{what is}

Once one is satisfied that the above claims are valid, one may be
tempted to say: ``I'll grant you a gain of a few orders of magnitude
over a general-purpose computer; but of course---you must
understand---yours is an extremely specialized piece of hardware,
designed to do just one thing over and over.''

In fact, with a {\em really} dedicated machine---a \vlsi{} implementation
of a specific fine-grained model (think of a ``silicon wind
tunnel'')---one could easily gain {\em many more} orders of magnitude
in performance (cf., e.g., \cite{despain}). Such a cast-in-concrete
machine might eventually be able to play an important role in a
production environment, but would probably be of much less use as a
research tool.  On the other hand, in spite of its definite
specialization, \cam-8 remains a {\em wide-purpose} architecture.

\bigskip

With the benefit of hindsight, let us define {\em programmable matter}
as a three-dimensional, uniformly textured, fine-grained computing
``medium'' having the following properties:

 \begin{enumerate}
	\item It can be assembled into lumps of arbitrary size (the limits
being given by economics rather than technology). 
	\item It can be dynamically reconfigured into any uniform,
fine-grained, three-dimensional computing network,
	\item It can be interactively driven, in the sense that its
dynamical evolution can be started, interrupted, and resumed at any
moment in response to the occurrence of specified internal or external
events.  Moreover, the dynamical laws themselves can be varied from
moment to moment; this allows one to specify time-dependent dynamics,
and also to ``microprogram'' a complex dynamical step as a sequence of
simpler interactions.
	\item It is totally accessible to real-time observation, analysis, and
modification.
 \end{enumerate}

\Cam-8 substantially meets all of the above specifications. Much of
its flexibility derives from a careful compromise between parallel and
serial processing. Briefly, the machine consists of a
three-dimensional array of {\em modules}, with each module responsible
for a certain ``volume'' of simulation space consisting of millions of
sites (the actual number is $2^n$, where $n$ depends on the current
\dram\ technology and is, in the near term, in the range 22--24,
corresponding to 4--16 million sites). Site updating within a module
is performed serially, with all modules operating in parallel and in
lockstep. Overall, the array of modules is controlled by a 
{\em host} workstation.

\medskip

Total simulation volume, as in point (1), can be
``programmed'' by simply purchasing the appropriate number of modules.  As
for point (2), the programmability of \cam-8 ``matter'' extends to the
following features:
 \begin{itemize}
	\item
\parhead{Number of dimensions} The total simulation volume can be
logically configured into an array having, besides the three main
dimensions $x,y$ and $z$ which are indefinitely extendible, a number of
extra dimensions of bounded size. This number is, of course, limited
by the fact that the product of the sizes along all dimensions cannot
exceed the total volume of programmable matter available, and the
product of the sizes of the extra dimensions cannot exceed the volume
of a module.
  	\item \parhead{Aspect ratio} Within the above bounds,
the size of each dimension is independently adjustable (by powers of
2), so that one can choose, for instance, a square array or a
long-and-thin one.
  	\item \parhead{Interconnectivity} Direct
communication between sites is not restricted to first neighbors in
the array. For a given number of dimensions $d$ and aspect ratio,
there is defined a $d$-parallelepiped of volume slightly greater than
$2^{n+d}$ centered on the given site, such that {\em any} site within
that volume can be chosen as a neighbor. For example, in two
dimensions, and with $n=22$, at each step a site can have neighbors
anywhere within a 4K\by4K square; in three dimensions, and with
$n=24$, anywhere within a 512\by512\by512 cube.  Furthermore, by
slowing the simulation down by a factor $k$, the diameter of the
neighborhood can be increased by a factor of $k$.

This rich interconnectivity is the most significant innovation of
\cam-8: earlier cellular automata machines were handcuffed by the
limitations of ``canned' neighborhoods (cf.\ \cite{cambook} and
\cite{rap1}).  Now one can perform three dimensional simulations,
synthesize a variety of spacetime ``crystallographic groups,'' and
use widely different speeds of propagation of information within the
same simulation (e.g., fast ``photons'' and slow ``electrons'').
	\item \parhead{Amount of state per site} For a given overall number of
bits of state, one can trade off number of sites for number of bits
per site.
  	\item \parhead{Transition function} In the current
implementation, the local transition function, that is, the rule used
to update a site as a function of its neighbors, is determined by a
lookup table, and thus can be assigned in an arbitrary way. This
lookup table is double-buffered, so that a new table can be downloaded
while an updating step is in progress, in preparation for a subsequent
updating step that will use a different rule.

The size of the lookup tables is currently 16\by$2^{16}$,
corresponding to 16 inputs and 16 outputs, and thus direct lookup can
be used as long as the amount of input to a node does not exceed 16
bits.  For a state-variable set larger than that, graceful degradation
occurs as one makes more and more recourse to table composition.
	\item \parhead{Serial/parallel ratio} Finally, the same number
of physical processors can be concentrated on relatively few sites,
for maximum speed, or shared by many sites, for maximum simulation
size.  Intermediate choices are of course possible.
 \end{itemize}

\section{Programmer's model}\label{model}

The generality of \cam-8's programmable matter is reflected in
a very simple ``programmer's model'' for the machine.

\medskip

We are all familiar with representing the history---and thus the
evolution---of a system by a spacetime diagram: a cycle-free directed
graph whose arcs represent {\em signals} and whose nodes represent
{\em events} in spacetime (\fig{spacetime}a). \Cam-8 supports
spacetime diagrams that are uniform and fine-grained
(\fig{spacetime}b).  Uniform means that the layout of arcs and nodes
is invariant for spacetime translations; of course, the {\em values}
of the signals will in general change from place to place.
Fine-grained means that only a small number of signals can interact at
each event, and each signal has a small set of available states. (In
fact, in \cam-8 all arcs carry {\em binary} signals; more complex
signals can, of course, be synthesized by bundling together a few
arcs.)

The operation of \cam-8 is simply the steady unfolding of such a
uniform and fine-grained spacetime history.

\figonegiven{spacetime}{\hbox to\linewidth{\hfill
\llap{\raise.5in\hbox{(a)}}\psfig{file=fig/random-st.ps,height=1.5in}\hfill
\llap{\raise.5in\hbox{(b)}}\psfig{file=fig/regular-st.ps,height=1.5in}\hfill}}{(a) A spacetime diagram, consisting of
signals (arcs) and events (nodes). (b) A uniform spacetime diagram.}

\medskip

Basically, all one has to do to program \cam-8 is 
\begin{itemize}
	\item\parhead{Signals} Specify the diagram's interconnection
pattern.  Since the diagram is uniform, it is enough to specify the
geometry of a ``primitive unit cell.'' This, in turn, is simply given
by a list of {\em neighborhood vectors}, one for each of the arcs that
impinge on a node, specifying where each arc comes from.
	\item\parhead{Events} Specify the event's transition function,
i.e., for each possible combination of states for the signals that
converge to an event, specify the desired combination of states for
the signals that radiate out of it. (Note that, by construction, there
is exactly one output signal for each input signal.)
	\item\parhead{Initial conditions} Assign the values of the
signals that cross a spacelike surface, typically of the form
$t_0={\rm const}$ (cf.\ \fig{sample-diagram}).
\end{itemize}

\figonegiven{sample-diagram}{\psfig{file=fig/regular4-st.ps}}{A
uniform spacetime diagram in which four signals ($a$, $b$, $c$, $d$)
converge on each event. The function $f$, associated with the event itself,
has these four signals as inputs and four corresponding signals as
outputs.}

For example, for the diagram of \fig{sample-diagram}, which represents
the time evolution of a one-dimensional system, the neighborhood
vectors are ($-2$), (0), ($+1$), and ($+1$), since the four signals
converging on any event at time $t$ originate from events at time
$t-1$ that are offset by those amounts with respect to the destination
event.

\figonegiven{hpp-spacetime}{\psfig{file=fig/marg-spacetime.ps}}{Spacetime layout of the HPP gas. }

\fig{hpp-spacetime} illustrates the spacetime layout for the HPP
gas mentioned in the previous section. The four directions of travel
for the particles are labeled $a,b,c,d$, and the transition function
is labeled $f$. For this system, the neighborhood vectors are
 $$
  \begin{array}{ll}
	a: & (-1,-1) \\
	b: & (+1,-1) \\
	c: & (+1,+1) \\
	d: & (-1,+1)
  \end{array},
 $$\noindent
	and the transition function $f$ is given by the table
 $$
   \begin{array}{cc|c}
	&{\rm in}&{\rm out}\\
	&abcd&abcd\\\cline{2-3}
	&0000&0000\\
	&0001&0001\\
	&0010&0010\\
	&0011&0011\\
	&0100&0100\\
	\ast&0101&1010\\
	&0110&0110\\
	&0111&0111\\
   \end{array}\quad
   \begin{array}{cc|c}
	&{\rm in}&{\rm out}\\
	&abcd&abcd\\\cline{2-3}
	&1000&1000\\
	&1001&1001\\
	\ast&1010&0101\\
	&1011&1011\\
	&1100&1100\\
	&1101&1101\\
	&1110&1110\\
	&1111&1111
    \end{array}
 $$\noindent
	where 1 represents the presence and 0 the absence of a
particle on a particular spacetime track. Note that in only two cases
(marked with an asterisk) out of sixteen does an interaction take
place; in all other cases, each signal proceeds undisturbed.

\medskip

Uniformity of structure at the hardware level does not mean, of
course, that one cannot have properties in the modeled system that
vary from place to place. 

For instance, we may want to study turbulence by letting a fluid flow
past a solid obstacle. Then one bit at each site will be used as a
parameter (left unchanged by the transition function) specifying
whether that site belongs to the obstacle or to the space occupied by
the fluid. Depending on the value of that bit, different sections of
the lookup table, and thus different laws, will be activated.

Similarly, by using extra state at each site, one can model systems
with sources and sinks, potential wells, lenses,
etc.\cite{cambook,smith-topo}, and even systems in which the initial
conditions are specified on a spacelike surface which isn't
flat\cite{margolus-thesis}. 

In the next section we'll briefly mention other ways of ``modulating''
in space or time (or both) the structural parameters of the computing
network. 

\medskip

Finally, a few words about data analysis.  \Cam-8 will generate new
data at a steady rate of about 0.5 Giga-bits/sec {\em per module}.  Of
course, one can always suspend the simulation for a moment and read
out the entire state of the system (``core dump''), but this involves
a lot of data transfer and puts the entire analysis burden on the
host.  In ordinary circumstances one would want data selection,
compression, and extraction to take place continuously, in real time,
and without significantly interfering with the updating itself.
Therefore, flexible resources for low-level data reduction must be
built-in, and must grow in direct proportion to the size of the
system.

We have seen that the transition function is responsible for producing
the output signals of an event as arbitrary functions of its input
signals. Using the same machinery, one can produce additional binary
outputs, each telling whether the input signals represent an occurrence
of an arbitrarily specified condition (for example, whether there is a
collision involving an even number of particles).  The number of these
occurrences is integrated over selected portions of space and time
(for this, we take advantage of \cam-8's flexible scanning order, as
explained in the next section); the corresponding counts, accumulated
by dedicated hardware counters, are made available to the host
computer.

For instance, for a lattice gas, one can subdivide the array into a
number of volume elements each containing a few thousand sites, and
(in parallel with the updating) tabulate the total number of particles
moving in each direction in each step---thus constructing a
macroscopic picture of the flow. Instead of many Giga-bits/sec of
fine-grained detail (which is, in a sense, an artifact of this type of
model), the host will see only the relevant hydrodynamical data---at a
rate a few thousand times slower than the raw data rate.


\section{Implementation notes}

To give the reader a feeling for quantitative aspects of \cam-8's
modeling environment, we shall briefly discuss how some of the
functional behavior described in the previous section is achieved in
practice.  This section may be skipped without loss of continuity; a
more detailed discussion of the hardware appears in \cite{cams}.

\medskip

Consider a regular array of bits that extends indefinitely in all
directions (for concreteness, you may think of a two-dimensional
array---a ``bit-plane''); we shall call such an array a {\em conveyor}.
We will now superpose, in good registration, a number $p$ of
conveyors---so that at each site we have a {\em pile} of $p$ bits. This
entire collection of bits will be made to evolve by repeated
application of the following procedure, called a {\em step},
consisting of two stages:
 \begin{itemize}
	\item\parhead{Data convection} Each conveyor is independently
shifted as a whole by an arbitrary number of positions in an arbitrary
direction. We still end up with a pile at each site, but with a new
make-up.
	\item\parhead{Data collision} We now take each pile
and we send it to a $p$-input, $p$-output lookup table; the lookup
table returns a new pile, which we put in place of the original one.
 \end{itemize}
	Note that at the collision stage each pile is processed
independently, so that the {\em order} in which the piles are updated
is irrelevant.  We could even have several copies of the lookup table,
and do some (or all) of the processing in parallel. Also note that, at
the data convection stage, the shift performed on each conveyor is a {\em
uniform} and {\em data-blind} operation (each bit is moved by a fixed
offset, quite independently of its position and its value); thus, it
becomes possible, in a suitable implementation, to replace this
operation by one that shifts the frame of reference (by incrementing a
single pointer) rather than moving the data themselves.

\bigskip

There is an obvious one-to-one correspondence between a dynamics
specified in this way and one defined by a uniform, fine-grained
spacetime diagram as in the previous section. For example, in
\fig{sample-diagram}, all the arcs labeled $a$ make up a
conveyor (and similarly those labeled $b$, $c$, and $d$\/); the
corresponding neighborhood vector ($-2$) specifies the amount of shift
of this conveyor at the data convection stage. Events represent the data
collision stage: still referring to \fig{sample-diagram},
the four arcs entering a node represent the make-up of a pile just
before being given to the lookup table, and the four arcs leaving it,
the pile as it comes out of the lookup table.

The present way of specifying a dynamics in terms of movement of
conveyors and updating of piles closely reflects \cam-8's hardware
organization, briefly described below.

\medskip

It will be convenient to consider for a moment conveyors that wrap around
on themselves along each dimension (the topology is that of a
hypertorus) and so have finite size. In a \cam-8 module, there are
$p=16$ of these conveyors, each represented by a separate \dram\ chip.
To implement the {\em data collision} stage, these chips are
sequentially scanned in lockstep, site by site, providing a 16-bit
pile (one bit per conveyor) at every clock cycle.  The lookup table is
implemented by a \sram\ chip (16 inputs, 16 outputs) which accepts a
pile at every clock cycle (30 nsec) and returns new piles at the same
rate. Each new pile is deposited back where the corresponding old one
came from, again one bit per conveyor. One complete scan represents one
updating step for the entire volume encompassed by the module.

To visualize the scanning order, think of a nested {\sc do}-loop, with
one nesting level for each spatial dimension.  Each of the indices of
the loop deals with one component ($x$, $y$, etc.) of the site
address, and drives a separate subset of the \dram\ address lines.  The
state of the complete set of these lines represents the current site
address.  The ``volume'' represented by the \dram\ chip is shaped into
the desired number of dimensions and aspect ratio (cf.\ Sect.~2) by
altering the parameters of the {\sc do}-loop.

Now, even though the same site address is intended for use by all 16
\dram\ chips, we route a separate copy of these lines to
each individual chip. This allows us, by inserting an adder stage in
the address path, to add a different {\em offset} to the site address
for each chip. This offset determines from where---along each
dimension---the scanning of the chip's internal data will actually
start. As far as the stream of data that comes out of the chip during
an updating step is concerned, changing the offset is equivalent to
shifting the entire contents of the chip.  This mechanism, then,
implements the {\em data transport} stage.

More specifically, the current offset is kept in the conveyor's {\em
offset} register, which is incremented before each updating pass by
the value of that conveyor's neighborhood vector (cf.\ previous section),
which is kept in the {\em kick} register. All these registers have the
same width as the site address, and like it are subdivided into
sections each corresponding to one spatial dimension.  Addition is
performed independently on each section, i.e., the carry is inhibited
at the boundary between one section and the next.  (This splitting of
the site address is simply controlled by the {\em dimension} register,
each of whose bits, when set, inhibits carry propagation at the
corresponding position in the adders.)

\medskip

The above discussion explains the operation of a single module, with
space wrapped around within the module itself. When we lay an
indefinite number of modules side-by-side in order to achieve an
arbitrarily large spatial extent, we must cut open the individual
pieces of space and glue them edge-to-edge.  Because each module is
updating only one cell at a time, only 16 wires are required to glue
two adjacent modules together---one per conveyor.

To understand the basic technique, think of a one dimensional chain of
modules.  When a given conveyor is shifted by less than the width of a
module, all of the new data for a given module comes either from what
is already inside of that module, or from one of its nearest
neighbors---via a connecting wire.  Moreover, since {\em all} of the
conveyor shifts in the same direction, each interconnection need only
carry data in one direction.  By updating the shifted data before
storing it away, we can combine the shift and the update, just as in
the single module case.

\medskip

The fine-grained dynamics of \cam-8 is completely determined by the
contents of the lookup table (1 Mbyte of \sram) and the neighborhood
vectors (a few bytes stored in the kick registers). Typically, this
information will be the same for all modules. By rewriting tables and
vectors, one gets a new dynamics. This can be done at every step, thus
obtaining an arbitrarily {\em time-dependent} dynamics.

Since scanning order is under our control, we can even scan, for
instance, all even-positioned sites first; then change the dynamics,
and scan all odd-positioned sites. As long as the number of sites
scanned between changes is large compared to the number of changes in
the lookup table, this way of modulating the spatial aspects of the
dynamics entails little or no overhead. Thus, it becomes possible to
use ``checkerboard'' dynamics (one rule for black, one for white) and
similar coarser-grained spacetime textures for the dynamics.  More
complicated textures can be obtained in a similar manner by using the
extra dimensions discussed earlier to group bits together: using a
time-dependent dynamics allows one to perform arbitrary function
compositions on these groups.

\bigskip

Finally, a few words about efficiency. The two main resources needed
by any simulation model are {\em memory}, for the state variables, and
{\em processing}, for the updating of these variables.  Fine-grained
models offer great conceptual simplicity and the sincerity that comes
from relying as far as possible on first principles; but, in exchange,
they demand very large amounts of memory and processing resources.

As we have seen, \cam-8 is able to use ordinary \dram\ chips for its
state variables. These chips are today an inexpensive commodity, and
allow one to go further, in terms of simulation size, than any other
practical alternative. Similarly, the \cam-8 architecture is able to
use ordinary \sram\ chips for processing; these too are a relatively
inexpensive commodity, and allow one to go far in terms of processing
power. The ``glue'' that turns these raw commodities into programmable
matter is a gate array of moderate complexity ($\approx$ 10K gates),
16 copies of which go into each module.

A clock period of 30 nsec uses 30-nsec \sram\ chips at full
bandwidth. While the contents of a pile, which is used as an address
to the \sram, is essentially unpredictable, the bits within the \dram\
chips are accessed in a predictable {\em sequence}; thus, one can make
use of {\em nybble-wide} \dram{}s, for which, as long as one remains
in the same memory row, four consecutive bits can be read and four
written in 120 nsec, i.e., in four clock cycles. Therefore, this
organization allows one to use storage and processing resources at
{\em full bandwidth} on a close-to-100\% duty-cycle.

Independently of the number of modules, the updating rate for the
model as a whole ranges from 8 steps per second (when all of a
module's \dram\ capacity is actually allocated to sites) to thousands
of steps per second (when, for sake of speed, each lookup table is
time-shared over thousands rather than millions of sites).

\medskip

Though we have in mind substantial installations consisting of
hundreds or thousands of modules---with a processing power of up to a
few Tera-events/sec---this architecture is fully usable in
configurations of just one or two modules, where its performance in
conveyor-collision processes compares with that of a Cray {\sc x-mp}.

