\documentstyle{pd}

 \begin{document}
 \title{PROGRAMMABLE MATTER: CONCEPTS AND REALIZATION}
 \shorttitle{Programmable Matter}
 \author{Tommaso Toffoli and Norman Margolus}
 \address{MIT Laboratory for Computer Science\\Cambridge, MA 02139, USA}
 \shortauthor{T. Toffoli, N. H. Margolus}
 \received{31 January 1990}
 \revised{31 January 1990}
 %\volume{999} \issue{9}
 %\firstpage{19} \lastpage{25}

 \begin{abstract}
	This paper is a manifesto, a brief tutorial, and a call for
experiments on {\em programmable matter} machines.
 \end{abstract}

 \maketitle

\renewcommand{\mathindent}{1.0em}
\renewcommand{\topfraction}{1}
\renewcommand{\dbltopfraction}{1}
\renewcommand{\bottomfraction}{1}
\renewcommand{\textfraction}{0}
\setcounter{topnumber}{10}
\setcounter{dbltopnumber}{10}
\setcounter{totalnumber}{10}


\def\cam{{\sc cam}}
\def\Cam{{\sc Cam}}
\def\dram{{\sc dram}}
\def\sram{{\sc sram}}

\newcommand{\by}{$\times$}
\newcommand{\parhead}[1]{{\sl #1}.\quad}


%%%% Single-column figure
 \newcommand{\figone}[3]{% label, height, caption
 \begin{figure}
  \hbox{\vrule height#2}
  \caption{#3}
 \label{#1}
 \end{figure}                 }

\section{Introduction}

After several years of issue analysis (see \cite
 {toffoli-thesis,marg-thesis,cambook,ica} and \cite
 {pde,strings2,four-topics,cheap,frontiers}),
conceptual design\cite
 {physics-like,cams,cams-rev,bond-energy,physem,cambook}, and
hands-on experience with more modest realizations\cite
 {super,cam5,cambook,vichniac}, we have finally
embarked on the construction of \cam-8, a scalable cellular automata
machine offering unprecedented performance in the fine-grained
modeling of distributed, spatially-extended systems.

Technically speaking, one could describe \cam-8 as a fine-grained
multiprocessor, and elaborate on design issues\cite{cams-rev}.
Here, however, we will concentrate on the most essential feature of the
\cam-8 architecture: it embodies the concept of {\em programmable matter}.

In programmable matter, the same cubic meter of machinery can become a
wind tunnel at one moment, a polymer soup at the next; it can model a
sea of fermions, a genetic pool, or an epidemiology experiment at the
flick of a console key.  Ten times as large a simulation will simply
require ten cubic meters of machinery, instead of one.  Flexibility,
instant reconfigurability, variable resolution, total accessibility,
and handling safety make such programmable matter worth a premium over
ordinary matter.

All computers can realize programmable matter to some extent.  The
real question is whether the above features can be achieved today on a
sufficiently large scale (in terms of spatial resolution and updating
rate) and with sufficient flexibility (in terms of choice of the
underlying fine-grained model) for the concept of `programmable
matter' to come to life.  It is in this respect that \cam-8, a machine
optimized for fine-grained material simulations, has a role to play.
In brief, \cam-8 will provide {\sl a general-purpose instrument for
the systematic exploration of a previously inaccessible region of the
computational spectrum.}

Our principal goal in this paper is to make the scientific
community---physicists in particular---aware of the possibilities of
this kind of instrument, and to invite suggestions for experiments
that will make significant use of its novel capabilities.


\section{Fine-grained models of matter}\label{fine grain}

The properties of `gold' as a material (for instance, specific weight,
hardness, conductivity) are quite distinct from the properties of an
isolated gold atom (atomic number, mass, spin, etc.).  Certain
statistical features emerge and become better and better characterized
as we consider a larger and larger lump of gold; beyond a certain
size, these bulk properties have stabilized enough that we can speak
of `gold' in a generic way, without having to specify the size or the
shape of the lump.

Similarly, if we consider an indefinitely-extended, uniformly
interconnected network of identical personal computers, we will have
defined a synthetic ``material'' having well-defined bulk properties.
These properties remain (to a good approximation) well characterized
even when we implement only a finite---but sufficiently
large---portion of the network. Connecting together three personal
computers does not yield a {\em larger} personal computer---it yields
a new kind of object; but joining together three large pieces of
this material does yield a larger piece of the {\em same} material.

If we changed the network's interconnection pattern, or if we replaced
the processor at every node with a different kind of processor, we
would obtain a different ``material,'' with potentially different bulk
properties.

\medskip

So far we have been speaking in rather metaphorical terms---we would
really like our computer networks to be able to mimic real materials.
With this in mind, lets consider certain aspects of our
computer-network model more carefully.
\begin{itemize}
\item\parhead{Fine grain}
A personal computer contains a large amount of state.  Even if it had
only 256 bytes of memory (instead of a million or so), it would still
be able to run programs having on the order of $2^{8\cdot 256}$
($\approx${}$10^{600}$) distinct states---much longer (at one new
state every microsecond) than the life of the universe. With so much
potential for complexity hidden in each node, well-characterized bulk
properties might emerge only on a scale spanning an astronomical
number of nodes.

To ensure that bulk properties emerge at a reasonably short scale
(today we can build networks with millions or billions of nodes at
most) the nodes must be very simple, i.e., to each node there must be
associated just a few bits' worth of state variables. This is what we
mean by a {\em fine-grained} computing network.

Our focus on fine-grained models is motivated, of course, by
conceptual as well as practical considerations. By Occam's razor,
before resorting to complex building blocks one should try to
synthesize complex behavior from simple building blocks.

	\item\parhead{Polynomial interconnection} We have mentioned
{\sl uniform}, {\em indefinitely-extended} networks---i.e., networks
whose geometry is invariant under an infinite group of
transformations---but we have not mentioned what kinds of group we
have in mind. The essential distinction, illustrated in Fig.\
\ref{fig.growth}, is between groups having {\em exponential} growth
(the number of new nodes one can reach from a given
node in $n$ steps grows as $a^n$) and groups having {\em
polynomial} growth (this number grows as $n^a$).

\figone{fig.growth}{1.9in}{In the {\em exponential} network at left,
the number of new nodes reachable in $n$ steps grows as $2^n$; in
the {\em polynomial} network at right, it grows as $n^2$.}

Malthus' centuries-old argument still holds: the physical world does
not support indefinite exponential growth. One can conceive of an
exponential architecture---say, a binary-tree network;
but one cannot concretely implement it for an indefinite number of
levels using uniform technological parameters (same wire size, clock
rate, etc.) at all levels.  In the end, the exponential structure
will have to be embedded within a polynomial architecture---at most
{\em three-dimensional}, to be specific.

Our attention, therefore, will be restricted to polynomial networks
that extend indefinitely in at most three spatial dimensions.
 \end{itemize}

\medskip

For concreteness, let's give a simple example of the kind of synthetic
``materials'' we'd like to be able to program within a
programmable-matter machine---namely, a {\em fluid} modeled by a {\em
lattice gas}.

The idea behind lattice-gas hydrodynamics is to model a fluid by a
system of particles that move in discrete directions at discrete
speeds, and undergo discrete interactions. In the HPP lattice
gas\cite{hpp}, identical particles move at unit speed on a
two-dimensional orthogonal lattice, in one of the four possible
directions.  Isolated particles move in straight lines.  When two
particles coming from opposite directions meet, the pair is
``annihilated'' and a new pair, traveling at right angles to the
original one, is ``created'' (Fig.\ \ref{fig.hpp}a). In all other
cases, i.e., when two particles cross one another's paths at right
angles (Fig.\ \ref{fig.hpp}b) or when more than two particles meet,
all particles just continue straight on their paths.

\figone{fig.hpp}{1in}{In the HPP gas, particles colliding head-on
are scattered at right angles (a), while particles crossing one
another's paths go through unaffected (b).}

As soon as the numbers involved become large enough for averages to be
meaningful---say, averages over spacetime volume elements containing
thousands of particles and involving thousands of collisions---a
definite continuum dynamics emerges. And, in the present example, it
is a rudimentary {\em fluid} dynamics, with quantities recognizably
playing the roles of density, pressure, flow velocity, viscosity, etc.

According to Pomeau, seeing this model of his running on one of our
early cellular automata machines made him realize that what had been
conceived primarily as a {\em conceptual} model could indeed be
turned, by using suitable hardware, into a {\em computationally
accessible} model: this stimulated his interest in finding lattice-gas
rules which would provide better models of fluids. A landmark was
reached with the slightly more complicated FHP model\cite{fhp}, (it uses
six rather than four particle directions) which gives, in an appropriate
macroscopic limit, a fluid obeying the well-known {\em Navier-Stokes}
equation, and thus suitable for modeling actual hydrodynamics (see
\cite{discrete-fluids} for a tutorial). Soon
after, analogous results for three-dimensional models were obtained by
a number of researchers\cite{frisch-doolen}.

\bigskip

On what scale can one implement models of the above kind?  Let
$\ell$ be the linear size of the lattice, so that a three-dimensional
lattice of roughly cubic shape will consist of $\ell^3$ nodes.
Typically, the duration $t$ (number of updates of the entire network)
of a significant experiment will be at least one order of magnitude
greater than $\ell$ (since macroscopic motion will be much slower
than the maximum speed of information transmission in the computing
medium). Taking $t\approx 10\ell$, the experiment will entail
$\approx 10\ell^4$ individual site updates, or {\em events}.

With today's fastest general-purpose computers, fine-grained
three-dimensional models of physically interesting phenomena (e.g.,
low-Reynolds-number hydrodynamics, diffusion in nonhomogeneous media,
phase separation in two-component systems) can be updated at a rate of
about $10^8$ events/sec\cite{shimomura,boghosian,boghosian-p}. Note that
processing speed rather than memory size is the limiting factor; it is
remarkable that machines with such different architectures as a Cray
X-MP and a Thinking Machines CM-2 yield comparable performance in tasks
of this kind.

With one day's worth of computer time, or about $10^5$ sec, one
obtains $\approx10^{13}$ events, corresponding to $\ell\approx
1000$.  This allows one to get a glimpse, but just a glimpse, at bulk
dynamics.  In fact, to arrive at bulk properties we typically
have to average over volume elements containing (at least) a thousand
sites, and thus having a diameter of (at least) 10 sites.  If each of
these volume elements corresponds to a ``pixel'' in the resulting
macroscopic picture, with $\ell\approx1000$ we are left with a picture
having a resolution of only 100 pixels per side.

\medskip

If an amount of electronic hardware (chips, wires, etc.) comparable to
that in an X-MP or a CM-2 is reconfigured into an appropriate
architecture---such as that of \cam-8---one obtains a flexible
computer capable of running this class of models at least two (and in
many cases three or four) orders of magnitude faster. This means that
each of the four factors in $\ell^3 t$ can grow by up to one order of
magnitude with respect to current computers, making new phenomena
accessible to fine-grained simulation.

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

Once you are satisfied that the above claims are valid, you 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\break {\em
programmable matter} as a three-dimensional,\break
uniformly textured, fine-grained computing\break
``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,
polynomially-interconnected, fine-grained 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.
	\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} computer (which may be a conventional 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.~\ref{spacetime}a).

\figone{spacetime}{1.7in}{(a) A spacetime diagram, consisting of
signals (arcs) and events (nodes). (b) A uniform spacetime diagram.}

\Cam-8 supports spacetime diagrams that are uniform and fine-grained
(Fig.~\ref{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.

\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.\ \ref{fig.sample-diagram}).
\end{itemize}
 	For example, for the diagram of Fig.\
\ref{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.

\figone{fig.sample-diagram}{2.2in}{A spacetime diagram with four
input signals associated with each event.}

Fig.\ \ref{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}, and even systems in which the initial
conditions are specified on a spacelike surface which isn't
flat\cite{marg-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.

\figone{fig.hpp-spacetime}{3in}{Spacetime layout of the HPP gas. }

\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 an earlier
paper\cite{cams-rev}.

\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 layer}.
We will now superpose, in good registration, a number $p$ of
layers---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 movement} Each layer 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 interaction} 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 interaction 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 movement stage, the shift performed on each layer 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.~\ref{fig.sample-diagram}, all the arcs labeled $a$ make up a
layer (and similarly those labeled $b$, $c$, and $d$\/); the
corresponding neighborhood vector ($-2$) specifies the amount of shift
of this layer at the data movement stage. Events represent the data
interaction stage: still referring to Fig.~\ref{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
layers and updating of piles closely reflects \cam-8's hardware
organization, briefly described below.

\medskip

It will be convenient to consider for a moment layers 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 layers, each represented by a separate \dram\ chip.
To implement the {\em data interaction} stage, these chips are
sequentially scanned in lockstep, site by site, providing a 16-bit
pile (one bit per layer) 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 layer. 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 layer's {\em
offset} register, which is incremented before each updating pass by
the value of that layer'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 layer.

To understand the basic technique, think of a one dimensional chain of
modules.  When a given layer 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
layer 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 will use 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 will range 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---we are also developing a minimal, two-module
version (66 Mega-events/sec, 8 Mega-sites), suitable for individual
interactive experimentation, with a hardware complexity and cost
comparable to that of an inexpensive workstation computer.  Such a
machine will act as its own frame buffer, able to synchronize its scan
with the beam of various raster-scan monitors so that, for instance,
the contents of a module scanning a 512\by512 array can be viewed in
real time at 60 frames/sec, and 1024\by1024 at 15 frames/sec.

\section{Conclusions}\label{conclusions}

We have presented a hardware structure that is optimized for the
fine-grained simulation of spatially-extended physical systems. There
is the attractive possibility, in the near term, of achieving systems
consisting of hundreds of billions of sites, updated a few times per
second.  Likely applications will immediately come to mind to any
scientist who has worked with lattice models; many other scientists
are already aware, at least in a vague way, of the possibilities that
lie behind such a tool.

The simplicity of \cam-8's functional description does not, of course,
mean that physical modeling is thereby made trivial.  It should,
however, spare those attempting to implement fine grained
neighborhood models the significant effort needed to twist such models
to fit conventional architectures efficiently.  This, together with
unprecedented computing power, should make such models attractive to a
wide range of disciplines.

The book \cite{cambook} illustrates a variety of modeling techniques
suitable for the modeling environment discussed here.  Much of the
recent literature on cellular automata and lattice gases discusses
specific fine-grained models of physics-like systems, and thus
provides a wealth of examples.

\medskip

The reader should be aware that our main interest is in the
fundamental connections between physics and computation, and one of
the reasons we developed \cam-8 is to work on certain questions in
that area (cf.\ \cite{marg-thesis,cheap}). As theoretical material
scientists---for one---we are mere amateurs, and undoubtedly many of
the most obvious applications of \cam-8 have not yet come to our
attention.  For this reason, we solicit proposals for imaginative and
demanding experiments to be performed on this machine---on themes
spannining physics, mathematics, and computer science---that will
allow us to exercise its design, possibly avoid costly mistakes or
omissions, and help make hardware, software, and methodology
accessible to more people in a shorter time.


\section{Acknowledgments}
This research was supported in part by the Defense Advanced Research Projects
Agency (N00014-89-J-1988), and in part by the National Science Foundation
(8618002-IRI).

 \newcommand{\bib}[1]{\bibitem{#1}} 

 \begin{thebibliography}{99}

	\bib{bond-energy} {\sc Bennett}, Charles, {\sc Margolus},
Norman, and {\sc Toffoli}, Tommaso, ``Bond-energy variables for Ising
spin-glass dynamics,'' {\sl Phys.\ Rev.\ \bf 37B} (1988), 2254.
	\bib{boghosian} {\sc Boghosian}, Bruce H., Washington {\sc Taylor},
and Daniel {\sc Rothman}, ``A cellular-automaton simulation of two-phase flow
on the CM-2 computer,'' in Proc. ``Supercomputing '88,'' vol.\ 2:
Science and Applications (ed.\ J. Margin and Stephen Lundstrom), IEEE (1989),
34--44.
	\bib{boghosian-p} {\sc Boghosian}, Bruce, personal communication.
	\bib{rap1} {\sc Clouqueur}, Andr\'e, and Dominique {\sc
d'Humi\`eres}, ``RAP1, A cellular automaton machine for fluid
dynamics,'' {\sl Complex Systems \bf 1} (1987), 585--597.
	\bib{strings2} {\sc Chopard}, Bastien, ``A cellular automata
model of large scale moving objects,'' to appear in {\sl J.  Phys.\
\bf A}.
	\bib{despain} {\sc Despain}, A., ``Prospects for a lattice-gas
computer,'' {\sl Lattice-Gas Methods for Partial Differential
Equations} (Gary {\sc Doolen} et al., ed.), Addison-Wesley (1990),
211--218.
	\bib{fhp} {\sc Frisch}, Uriel, Brosl {\sc Hasslacher}, and
Yves {\sc Pomeau}, ``Lattice-Gas Automata for the Navier-Stokes
Equation,'' {\sl Phys.\ Rev.\ Lett.} {\bf 56} (1986), 1505--1508.
	\bib{frisch-doolen} {\sc Frisch}, Uriel, et al., ``Lattice gas
hydrodynamics in two and three dimensions,'' {\sl Lattice-Gas Methods
for Partial Differential Equations} (Gary {\sc Doolen} et al., ed.),
Addison-Wesley (1990), 77--135.
	\bib{hpp} {\sc Hardy}, J., O. {\sc de Pazzis}, and Yves {\sc Pomeau},
``Molecular dynamics of a classical lattice gas: Transport properties and
time correlation functions,'' {\it Phys.\ Rev.\ \bf 13A} (1976),
1949--1960.
	\bib{discrete-fluids} {\sc Hasslacher}, Brosl, ``Discrete
Fluids,'' {\sl Los Alamos Science}, Special Issue No.~15(1987),
175--200 and 211--217.
	\bib{physics-like} {\sc Margolus}, Norman, ``Physics-like
models of computation,'' {\sl Physica} {\bf 10D} (1984), 81--95.
	\bib{marg-thesis} {\sc Margolus}, Norman, ``Physics and
Computation'' (Ph.\ D. Thesis) {\sl Tech.\ Rep.\ MIT/LCS/TR-415}, MIT
Laboratory for Computer Science (1988).
	\bib{forth-conf} {\sc Margolus}, Norman, ``Cellular Automata
Machines---A New Environment for Modeling,'' in the proceedings of the
{\sl 1988 Rochester Forth Conference} (L. {\sc Forsley} ed.),
Institute for Applied Forth Research (1988).
	\bib{cams} {\sc Margolus}, Norman, {\sc Toffoli}, Tommaso,
``Cellular Automata Machines,'' {\sl Complex Systems \bf 1}, 967--993
(1987).
	\bib{cams-rev} {\sc Margolus}, Norman, Tommaso {\sc Toffoli},
``Cellular Automata Machines,'' revised version of \cite{cams}, in
{\sl Lattice-Gas Methods for Partial Differential Equations} (Gary
{\sc Doolen} et al., ed.), Addison-Wesley (1990), 219--249.
	\bib{super} {\sc Margolus}, Norman, Tommaso {\sc Toffoli}, and
G\'erard {\sc Vichniac}, ``Cellular-Automata Supercomputers for Fluid
Dynamics Modeling,'' {\sl Phys.\ Rev.\ Lett.} {\bf 56} (1986),
1694--1696.
	\bib{shimomura} {\sc Shimomura}, T., G. {\sc Doolen}, B.  {\sc
Hasslacher}, and Castor {\sc Fu}, ``Calculations Using Lattice Gas
Techniques,'' {\sl Los Alamos Science}, Special Issue No.\ 15 (1987),
201--211.
	\bib{smith} {\sc Smith}, Mark, `` Representations of geometrical
and topological quantities in cellular automata,'' submitted to {\em Physica 
\bf D} (***CA issue?***).
	\bib{toffoli-thesis} {\sc Toffoli}, Tommaso, ``Cellular
Automata Mechanics,'' {\sl Tech.\ Rep.\ 208}, Comp.\ Comm.\ Sci.
Dept., The University of Michigan (1977), 255 pp.
	\bib{cam5} {\sc Toffoli}, Tommaso, ``CAM: A high-performance
cellular-automaton machine,'' {\sl Physica} {\bf 10D} (1984),
195--204.
	\bib{pde} {\sc Toffoli}, Tommaso, ``Cellular automata as an
alternative to (rather than an approximation of) differential
equations in modeling physics,'' {\sl Physica \bf 10D} (1984),
117--127.
	\bib{frontiers} Tommaso {\sc Toffoli}, ``Frontiers in
Computing,'' {Information Processing} (G. X. Ritter ed.),
North-Holland (1989), 1.
	\bib{cheap} Tommaso {\sc Toffoli}, ``How cheap can mechanics'
first principles be?''  to appear in the proceedings of the workshop
{Complexity, Entropy, and the Physics of Information}, Santa Fe
Institute (April 1989).
	\bib{four-topics} {\sc Toffoli}, Tommaso, ``Four topics in
lattice gases: Ergodicity; Relativity; Information flow; and Rule
compression for parallel lattice-gas machines,'' {\sl Discrete Kinetic
Theory, Lattice Gas Dynamics and Foundations of Hydrodynamics} (R.
Monaco {\sl ed.}), World Scientific (1989), 343--354.
	\bib{physem} {\sc Toffoli}, Tommaso, ``Cellular automata
machines as physics emulators,'' in {\sl Impact of Digital
Microelectronics and Microprocessors on Particle Physics} (M.  {\sc
Budinich} et al., ed.), World Scientific (1988), 154--160.
	\bib{cambook} {\sc Toffoli}, Tommaso, and Norman {\sc
Margolus}, {\sl Cellular Automata Machines---A new environment for
modeling}, MIT Press (1987).
	\bib{ica} {\sc Toffoli}, Tommaso, and Norman {\sc Margolus},
``A review of invertible cellular automata,'' submitted to {\sl
Physica \bf D}. (***CA issue?***).
	\bib{vichniac} {\sc Vichniac}, G\'erard, ``Simulating physics
with cellular automata,'' {\it Physica \bf 10D} (1984), 96--115.
\end{thebibliography}

\end{document}

