% -*- Mode:Text -*- 

 \newcommand{\up}{\uparrow}
 \newcommand{\dn}{\downarrow}

\chapter{Background}

In this chapter we briefly discuss the conceptual and technological
background for programmable matter.

\section{Cellular-automata-like models}

Cellular automata were introduced in the late forties by John von
Neumann (who also pioneered stored-program computers), following a
suggestion of Stan Ulam\cite{ulam}, to provide a more realistic
computational paradigm than the Turing machine for modeling the
behavior of spatially-extended systems\cite{vonneumann}.  They can
be viewed as the computer scientist's counterpart to the physicist's
concept of `field'.

\medskip

A {\em cellular automaton} consists of an indefinitely extended array
of identical, uniformly interconnected finite-state automata, called
{\em cells}. Each cell gets its input data from certain cells in its
vicinity, called its {\em neighbors}, as specified by the
interconnection pattern.\footnote
	{This is simply a table that lists the relative position of the
neighbors with respect to the generic cell.}
	At each updating step, the cell determines its new state as a
function of its neighbors' current state by means of a lookup table.
Taken together, the interconnection pattern and the lookup table
represent a local, finite prescription---the cellular-automaton {\em
rule}---for the evolution of the indefinitely extended system.

A cellular automaton can be thought of as a stylized physical
universe.  Each element of the array corresponds to an elementary
volume of space, while each updating step corresponds to an elementary
increment of time. The dynamical laws are given by the rule; as in
physics, these laws are uniform and local.\footnote
	{``Uniform'' means that the laws are the same everywhere: I
can only tell one place from another by the data it happens to
contain, not by any difference in the laws. ``Local'' means that to
know what will happen here in a moment I only have to look at the
state of things near me: no action-at-a-distance is permitted.}

Given a suitable rule, out of such simple local machinery there
naturally emerge, on a larger scale, complex structures and phenomena.
Indeed, cellular automata support a wide range of complex behavior,
and provide useful models for investigations in natural science,
materials science, dynamical systems theory, combinatorial
mathematics, and computer
science\cite{farmer,preston,ca86,gutowitz,wolfram-book}.

\smallsection{Cellular automata vs finite-difference schemes}

Local and uniform interconnections in discrete spacetime are found in
other well-known computational models, such as finite-difference
schemes for partial differential equations.  However, while in those
schemes the state variables are {\em numerical} quantities ranging
over a {\em continuum}, cellular-automata-like models use {\em
symbolic} quantities ranging over a {\em finite}---and typically
small---set. (Of course, continuum quantities may still emerge in the
macroscopic limit.)

This distinction entails profound differences in modeling methodology
and in approach to computer design. With much simpler variables and
interactions it becomes possible, especially with suitably designed
hardware, to explicitly handle a much larger number of them, and one
is encouraged to use modeling strategies more akin to those of
statistical mechanics.


\smallsection{Cellular automata vs \CCPs}

The cellular-automaton scheme of computation has an obvious {\em
verbatim} implementation in \vlsi{}. All one needs is a regular array
of macrocells---each consisting of a few flip-flops and a few gates
embodying the cellular-automaton rule---connected edge-to-edge.  This
approach, however, has severe limitations in terms of configuration
flexibility, scalability, and I/O and control access, and at least
with today's technology is not suitable as a general-purpose modeling
platform.

The computational scheme used in \cam-8, namely {\em \CCPs{}}
(see \sect{ccp}), is based on a sharper distinction between
data-movement and data-interaction primitives than in traditional
cellular automata, and on a relaxation of the time-uniformity
constraint.  Modest as these innovations may be, they make possible
the radically different architectural approach of which we take
advantage here.


\section{Examples of physical models}\label{sect.examples}

For concreteness, let us give two simple examples of the kind of
synthetic ``materials'' one can easily program within a
cellular-automata-like model, namely, a {\em fluid} modeled by a lattice
gas, and a {\em ferromagnetic material} modeled by an Ising spin
system.


\subsection{Lattice-gas hydrodynamics}\label{sect.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 Pomeau's \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{hpp}a). In all other
cases, i.e., when two particles cross one another's paths at right
angles (\fig{hpp}b) or when more than two particles meet,
all particles just continue straight on their paths.

\figonegiven{hpp}{\rlap{(a)}\relax
 \begin{picture}(64,64)(0,0)
	\thicklines
	\put(0,32){\line(1,0){28}}
	\put(32,36){\vector(0,1){28}}
	\put(28,36){\oval(8,8)[br]}
	\put(64,32){\line(-1,0){28}}
	\put(32,28){\vector(0,-1){28}}
	\put(36,28){\oval(8,8)[tl]}
 \end{picture}\relax
 \qquad\qquad
 \rlap{(b)}\relax
 \begin{picture}(64,64)(0,0)
	\thicklines
	\put(0,32){\vector(1,0){64}}
	\put(32,64){\line(0,-1){30}}
	\put(32,30){\vector(0,-1){30}}
 \end{picture}}{In the HPP gas, particles colliding head-on (a)
are scattered at right angles, while particles crossing one
another's paths (b) go through unaffected.}

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 recognizable
as density, pressure, flow velocity, viscosity, etc.

By Pomeau's own account, seeing this model running on one of our early
cellular automata machines made him realize that what he had 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{hasslacher} for a tutorial). This model started off the
burgeoning scientific business of {\em lattice-gas hydrodynamics}.
Soon after, analogous results for three-dimensional models were
obtained by a number of researchers\cite{frisch-doolen}.


\subsection{Ising spin systems}\label{sect.ising}

A permanent magnet will suddenly loose its magnetization at a
critical temperature called the {\em Curie point}. This aspect of
magnetism is captured by a very simple model, namely an Ising spin
system\cite{hill}.

\figonegiven{ising}{
 \newcommand{\spinup}{\begin{picture}(0,8)(0,-4)\thicklines
	\put(0,-4){\vector(0,1){8}}\end{picture}}
 \newcommand{\spindown}{\begin{picture}(0,8)(0,-4)\thicklines
	\put(0,4){\vector(0,-1){8}}\end{picture}}
 \newcommand{\spin}[1]{$\ifodd#1\spinup\else\spindown\fi$}
		% args: 4 bonds, 4 corner spins, 1 center spin
 \newcommand{\ising}[9]{\begin{picture}(48,48)(0,0)
	\setlength{\unitlength}{1.5pt}
	\thinlines
	\multiput(3,3)(8,8){4}{\makebox(0,0){.}}
	\multiput(5,5)(8,8){4}{\makebox(0,0){.}}
	\multiput(3,29)(8,-8){4}{\makebox(0,0){.}}
	\multiput(5,27)(8,-8){4}{\makebox(0,0){.}}
	\put(8,24){\makebox(0,0){\footnotesize#1}}
	\put(24,24){\makebox(0,0){\footnotesize#2}}
	\put(8,8){\makebox(0,0){\footnotesize#3}}
	\put(24,8){\makebox(0,0){\footnotesize#4}}

	\put(0,32){\makebox(0,0){\spin{#5}}}
	\put(32,32){\makebox(0,0){\spin{#6}}}
	\put(0,0){\makebox(0,0){\spin{#7}}}
	\put(32,0){\makebox(0,0){\spin{#8}}}
	\put(16,16){\makebox(0,0){\spin{#9}}}\end{picture}}
 \newcommand{\isinghood}[1]{\begin{picture}(48,56)(0,-4)
	\put(0,0){#1}
	\put(24,24){\circle{12}}\end{picture}}
 \begin{tabular}{cc}
    \begin{tabular}{c}
    \begin{picture}(96,104)(0,-4)
	\put( 0,48){\ising 111111110}
	\put(48,48){\ising 010010111}
	\put( 0, 0){\ising 001111100}
	\put(48, 0){\ising 110111000}
    \end{picture}
    \end{tabular}
    &
    \begin{tabular}{c@{}c}
	\isinghood{\ising 010110101} & \raise24pt\hbox{before}\\\\
	\isinghood{\ising 101010100} & \raise24pt\hbox{after}
    \end{tabular}
    \\
    (a) & (b)
 \end{tabular}
}{(a) Array of spins; 0s and 1s denote the
energy associated with each bond. (b) A spin flip is allowed if
it would leave unchanged the sum of the energies of its four bonds.}

The ferromagnetic material is represented by a regular array of binary
variables, called spins (\fig{ising}a); the two states of a spin are
called {\em up} ($\up$) and {\em down} ($\dn$). The net magnetization
of the material is the difference between the fraction of spins up and
that of spins down.  Also the interaction energy between two adjacent
spins has only two possible values, depending on
whether or not the spins point in the same direction.

The essential statistical-mechanical aspects of the material are
captured by the following cellular-automaton dynamics (cf.\
\cite{creutz}): At each time step,\footnote
	{\label{foot.checker}For technical reasons, it is expedient to
treat the array as a checkerboard, and on each step separately update
first all the ``black'' squares and then all the ``white'' one.}
	a spin will ``flip'' (change state) only if two of its
neighbors are pointing up and the other two are pointing down
(\fig{ising}b). It is easy to verify that, besides being local and
uniform, this dynamics is microscopically reversible and satisfies
energy conservation.

\medskip

To determine by numerical experiment the value of magnetization at a
given temperature, one would like to sample in a fair way the ensemble
of microscopic configurations corresponding to equilibrium at that
temperature.

To do this, one starts the cellular automaton in an arbitrary
configuration having a given total energy. (If the array is
sufficiently large, there is a one-to-one correspondence between
energy density and temperature.) Repeated application of the
rule will drive the system along an orbit that is essentially a random
walk through a constant-energy surface in phase space. Over a
sufficiently long time, the points of this orbit will represent a fair
sample of the equilibrium state.

In agreement with the physical situation, this model predicts
that above a critical temperature $t_{\rm c}$ spins are oriented
essentially at random (\fig{crit}a), leading to a zero net
magnetization, while below that temperature adjacent spins tend to
align in the same direction (\fig{crit}b), leading to large domains
having magnetization close to +1 or $-1$.

\figone{crit}{1.7in}{Typical equilibrium configurations of an Ising spin
system (a) above the critical temperature and (b) at the critical
temperature (where macroscopic magnetic domains begin to appear).
Below the critical temperature, one of the two domains would
eventually spread over the whole system.}

\subsection{Other models}\label{sect.other-models}

There is a vast literature of more complex physical phenomena
adequately characterized by cellular automata models\cite[and
references therein]{farmer,ca86,gutowitz}. By gradually adding simple
features to basic models as simple as the ones described above one
rapidly expands one's expressive power and modeling repertoire.

In a lattice-gas model of a fluid, for example, one can add obstacles
(a pipe, an airfoil) so as to generate turbulence; one can introduce
particles traveling at different speeds, so as to have temperature
besides density and pressure; one can introduce a second molecular
species, so as to have (depending on the interaction details) either
mutual diffusion or two-phase flow (cf.\ \cite{rothman-emulsions}).

In models like the above Ising system, one can more efficiently
explore a constant-energy surface by introducing a network of
``bankers''\cite{creutz} through which spins can borrow and deposit
small amounts of energy (this is equivalent to placing the Ising
system on a substrate having a certain specific heat and thermal
conductivity).  Or one can couple the spin system to a heat bath,
realized by a suitable random number generator, so as to simulate a
canonical ensemble (Monte-Carlo simulation).

In a similar model, one interprets the two states of a cell as
different molecular species rather than spin states; the basic interaction
is a permutation between adjacent molecules compatible with energy
conservation. In this way one can start studying alloys, phase separation,
annealing, etc.


\section{Emergent computation}

In principle, all technical questions about a complex macroscopic
object such as a bridge could be answered by a computer model that
explicitly represented the bridge as built out of atomic physics.
From such microscopic foundations one could directly compute bulk
mechanical properties (e.g., flexion and torsion under load or wind)
as well as more subtle behavioral aspects (metal fatigue, noise
damping, resistance to corrosion, etc.).  Modeling on such a scale,
however, would entail explicitly representing some 10$^{30}$ primitive
objects (nuclei and electrons) and their interactions, which is
far out of reach of today's computer technology.

Fortunately it turns out that, in most practical situations, this span
of 30 powers of ten naturally breaks up into distinct subranges.
In fact, by about 20 powers of ten from the bottom most of the
microscopic bustle has averaged out, and what is left can be
summarized by a {\em macroscopic} phenomenology typically involving
just a few numerical variables and parameters (such as current,
viscosity, temperature, etc.), and governed by differential equations
(e.g., Ohm's law, the Navier-Stokes equation).

For routine questions, the bridge modeler will find the relevant
macroscopic laws and parameters in the appropriate handbooks, so that
the model will only have to address the last 10 powers of ten of the above
30-power span.  Often, of course, even higher levels of the modeling
hierarchy are available in precompiled form (e.g., mechanical data for
beams of different cross-sections). Representative of this context
would be a finite-element model involving a few thousand nodes;
each node would be an object of moderate complexity, described by a
handful of floating-point numbers; and the interactions between nodes
would be described by algebraic equations.  Conventional scientific
computers are, not surprisingly, ideally suited for handling models of
this kind.

\medskip

While a typical domain of application for differential equations is
thus the upper range of the above $10^{30}$ scale span---where a
continuum regime is firmly established---differential equations begin
to fail where the subject of investigation is the very {\em emergence}
of macroscopic properties. This is, of course, the domain of materials
science, where the ``grain'' of matter, even though perhaps still
lying many powers of ten below, begins to be felt. In fact, as we
proceed downwards, the calculus's stress on {\em how much} gradually
shifts to combinatorics' stress on {\em how many}, and the appropriate
mathematics becomes that of the composition of many elementary
interactions. We enter the largely uncharted regions of complex system
theory, where one may discover a system's surprisingly critical
dependence on certain parameters (e.g., phase transitions), alongside a
surprisingly broad insensitivity to most other details of its
microscopic dynamics.  Note that an analogous situation may arise on a
totally different physical scale; for instance, in the study of
galaxies, when the discreteness of individual stars (rather than of
atoms) begins to be felt; or in quantum gravity, where the scale may
be set by Planck's length.

\section{Need for a creative approach}\label{sect.substitute}

What is characteristic in the study of emergent behavior is the need
to explicitly take into account interactions that, though individually
simple and usually arranged in repetitive patterns in space and time,
are astronomical in number. Conventional scientific computers are not
well suited for this task: they are optimized for {\em numerical
operations} involving high-resolution fixed- or floating-point
numbers, and {\em random sequential access}, in a large centralized
memory, to individual words of size large enough to contain such numbers.

It is clear that the computational demands of emergent behavior can be
better addressed by alternative, ``emergent computation''
architectures based on fine-grained massive parallelism. But would
even this make enough of a quantitative difference to make the desired
kind of modeling effectively accessible? We are convinced that this is
not going to be the case---unless one is willing to take a more creative
approach to the problem.

\medskip

\figonegiven{range}{\begin{tabular}{@{}ccc@{}}
 \begin{picture}(16,156)(0,-6)
	\put(0,0){\makebox(0,0)[l]{$10^0$}}
	\put(0,48){\makebox(0,0)[l]{$10^{10}$}}
	\put(0,96){\makebox(0,0)[l]{$10^{20}$}}
	\put(0,144){\makebox(0,0)[l]{$10^{30}$}}
 \end{picture}
 &
 \begin{picture}(104,150)(24,-6)
	\put(24,0){\makebox(0,0)[l]{microscopic mechanisms}}
	\put(48,40){\makebox(0,0)[l]{\shortstack{microscopic\\phenomena}}}
	\put(48,80){\makebox(0,0)[l]{\shortstack{emergent\\dynamics}}}
	\put(24,96){\makebox(0,0)[l]{\hbox to 104pt{\dotfill}}}
	\put(48,112){\makebox(0,0)[l]{\shortstack{macroscopic\\phenomena}}}
	\put(24,144){\makebox(0,0)[l]{macroscopic systems}}
	\thicklines
	\put(40,8){\vector(0,1){48}}	%ends at 56
	\multiput(40,60)(0,8){4}{\line(0,1){4}}	%ends at 88
	\put(40,92){\vector(0,1){44}}
 \end{picture}
 &
 \begin{picture}(104,150)(24,-6)
	\put(76,32){\makebox(0,0)[l]{\parbox{28pt}{substitute\par microscopic\par dynamics}}}
	\put(48,80){\makebox(0,0)[l]{\shortstack{emergent\\dynamics}}}
	\put(24,96){\makebox(0,0)[l]{\hbox to 104pt{\dotfill}}}
	\put(48,112){\makebox(0,0)[l]{\shortstack{macroscopic\\phenomena}}}
	\put(24,144){\makebox(0,0)[l]{macroscopic systems}}
	\thicklines
	\put(40,56){\vector(0,1){0}}	%ends at 56
	\put(72,56){\oval(64,48)[bl]}
	\multiput(40,60)(0,8){4}{\line(0,1){4}}	%ends at 88
	\put(40,92){\vector(0,1){44}}
 \end{picture}
 \\
 & (a) & (b)
 \end{tabular}}{(a) Macroscopic phenomenology emerges, at a
certain level of aggregation, from microscopic mechanisms. (b) One can
try to arrive at macroscopic phenomena by a shorter route, starting
from a substitute microscopic dynamics.}

Let's go back to the simplistic but illustrative picture of a
$10^{30}$ scale range between microscopic mechanisms and systems built
upon macroscopic laws, and let us grant that conventional scientific
computers do an excellent job at spanning the $10^{20}$--$10^{30}$
range (see \fig{range}a).  If somebody claimed to have found an
alternative architecture that today, for a comparable outlay of
resources, spanned the $10^0$--$10^{20}$ range (\fig{range}a), we
would dismiss them without further thought: start where one may, with
a few billion bytes and a few billion machine cycles one cannot cover
a stretch of much more than 10 powers of ten.


What we claim is that there are architectures that allow one to arrive
at the $10^{20}$ region (macroscopic properties) starting from far
below---indeed from microscopic dynamical primitives.  Not, however,
from the {\em actual} microscopic mechanisms of physics, which inhabit
the $10^0$ region: starting from electrons and nuclei, with explicit
modeling today one can reach at best the scale region of molecular
orbitals. What we {\em can} do is start from some simple {\em
substitute} dynamics (\fig{range}b) hovering no more than 10 powers of
ten below macroscopic phenomenology, but which we may have reasons to
believe will ``recapitulate'' the {\em essential aspects} of the
microscopic dynamics of the nether regions. {\em By this ritualized
re-enactment of the battle scene, we may hope to gain an understanding
of the real battle.}

Substituting a cleverly devised board game for the real microscopic
dynamics is one of the most common modeling approaches in
physics---especially in statistical mechanics and disciplines that
rely heavily on it, such as materials science. Such a game
is usually proposed in the hope that one may arrive, by
pencil-and-paper, at some exact or asymptotic closed-form solution;
otherwise all one is left with is a cute conceptual restatement of
the original problem. 

Unless, of course, one can {\em play} the game---that is, perform
explicit simulations. Ordinary scientific computers are
first and foremost numerical integrators of partial differential
equations. In an analogous fashion, the methodology discussed here
addresses the formulation and the numerical solution of fine-grained
``board games'' proposed by physicists as models of materials and
other spatially-extended systems.


\section{Cellular automata machines}\label{sect.cams}

From a logic designer's viewpoint, a cellular automaton
is a {\em uniform} sequential network with {\em polynomial}
interconnectivity.  That is, the number of new nodes one
can reach in $n$ steps grows as $n^a$; by contrast, in an {\em
exponential} network (e.g., hypercube, binary tree) this number grows
as $a^n$ (cf.\ \fig{growth}).

These constraints make possible very direct and efficient physical
implementations of the sequential network. Specifically, polynomial
growth (with $a\leq3$) permits an {\em isometric} embedding of the
network in ordinary three-dimensional space: nodes that are directly
connected are also physically close.  With that, since all connections are
local, one can clock the network at a rate that is independent of
network size; thus, the implementation is {\em indefinitely scalable}.

\figonegiven{growth}{\hbox to\linewidth{\hfill
\rlap{\quad(a)}\psfig{file=fig/expo.ps,height=1.6in}\hfill
\rlap{\quad(b)}\psfig{file=figspoly.ps,height=1.6in}\hfill}}
{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$.}

\medskip

Several computer architectures have been proposed that take advantage of
the above constraints, and a few have actually been implemented.

The {\sc nec} {\sc gapp} chip consists of a 3\by4 array of miniature
processors that can be microprogrammed for a specific
cellular-automaton rule; larger arrays are obtained by interconnecting
these chips in a ``postage stamp sheet'' fashion. This approach
becomes mechanically cumbersome beyond a few hundred chips, and does not
readily lend itself to real-time input/output and control (such as
modifying the rule between one step and the next).

Though it was ostensibly an architecture for emulating
randomly-interconnected logic networks, Thinking Machine's \cm-1 is in
fact basically organized as a regular, locally interconnected
two-dimensional array of miniature ``{\sc risc}'' (two-bit wide {\sc
cpu}) processors. Action ``at a distance'' is supported by a separate
routing network, during whose operation the array activity is
suspended. The processors' microprogram is not stored, but is
broadcast by the host in real time, instruction by instruction, at
every step. These and other compromises buy \cm-1 great flexibility,
but impose severe cost/performance burdens on the running of
cellular-automaton-like models. The \cm-2 improves on this design, and
adds emphasis on servicing a large number of floating-point units.  It
is remarkable that, in spite of fine-grained processing and massive
parallelism, the \cm-2's performance on cellular automata tasks
compares with that of the {\sc cray} {\sc x-mp}---a much more
conventional scientific-computing architecture.

Our group at {\sc mit} pioneered the concept of `cellular automata
machines', first with in-house prototypes\cite{cam5} and then with a
commercial version, \cam-6 (subsequently joined by \cam-{\sc pc}, an
improved second-source).  One original aspect of this approach is
that, though many modules can be connected in parallel, the cells within
each module (a 256\by256 array in \cam-6) are scanned and updated {\em
sequentially}. By implementing the cellular-automaton rule as a lookup
table and by pipelining all cell-updating operations (neighbor
gathering, rule lookup, and cell write-back) one obtains, with simple
hardware, enough speed to update and display the entire system at TV
frame rate.  These machines, together with our book {\em Cellular
Automata Machines---a new environment for modeling}, have been
influential in popularizing the potential of cellular automata for
physical modeling.  They have also provided a rich nurturing
environment for the development of \cam-8.

The {\sc rap}1 prototype, built by a French group\cite{rap1}, is a
variation of \cam-6 more oriented towards lattice-gas simulations.
Particles moving in different directions are stored on different
bit-planes, making it possible to move the particles themselves by a
combination of data shifts (horizontally) and memory-pointer
increments (vertically). Unlike \cam-6, {\sc rap}1 modules cannot be
connected together to implement larger spaces.


\medskip

The design of \cam-8 (see \sect{ccp} and \app{cam8}) draws upon our the
accumulated experience with previous cellular automata machine designs,
as well as on an improved understanding of their potential for
modeling and of their likely applications.

A study on the prospects for dedicated cellular automata machines for
hydrodynamics simulations, made by the {\sc jason} group in
1988\cite{despain}, concluded that ``there is a considerable amount of
enthusiasm about the potential of a dedicated lattice-gas computer.
\ldots such a machine could surpass the present performance of a
general-purpose supercomputer by a factor of about $10^8$ and possibly
considerably more. \ldots In view of the combination of large cost
and high scientific potential for such a machine, it will be imperative
 \ldots\ to build intermediate-scale hardware implementations of dedicated
cellular automata computational engines \ldots\ {\em A promising example of
such an intermediate engine is the \cam-8 machine recently proposed
by Margolus and Toffoli\ldots}'' [italics ours].

Now that it has come into being, \cam-8 fully realizes that promise,
and gives one great flexibility in exploring the potential of the
present computational approach to physical modeling. This is a
scalable architecture: size and speed are limited essentially only by
economic considerations. For a similar hardware cost, \cam-8 gives a
performance gain of at least 1000 over existing computers for this
kind of computations.




\section{Conveyor-collision processors}\label{sect.ccp}

In the \hpp{} lattice gas sketched in \sect{lattice-gas}, all the
particles that at a given moment are moving in the eastward
direction can be viewed as being carried by an indefinitely-extended,
two-dimensional {\em conveyor belt} advancing one position eastward at
each clock cycle.  This belt has regularly spaced ``pockets'' arranged
in the same regular pattern as the lattice sites; each pocket contains
at most one particle. Thus, at each step the belt conveys every
pocket's load from one lattice node to the one eastward of it.

Imagine similar conveyor belts for all four directions of motion,
overlayed on one another like transparency slides.  During each
clock cycle, four pockets, one from each belt, converge toward each
site, pass by one another as they go over the site, and then diverge
from that site. In this fleeting encounter, we can arrange to have the
contents of the four pockets ``collide,'' i.e., interact according to
a given rule, so that what each pocket carries away from the site may
be different from what it carried to it.  By {\em conveyor collision}
we mean the simultaneous interaction, at all sites and according to
the same rule, of every set of converging pockets: the entire contents
of the four conveyors are colliding in parallel.

\medskip

In a lattice gas (which is a particular form of cellular automaton),
this convey/collide cycle is indefinitely repeated.  Each lattice gas
is completely characterized by its collection of conveyor belts, each
with an assigned discrete direction and speed, and by the given
interaction rule. The dynamical parameters are therefore assigned once
and for all before the ``beginning of time.''

Let us now consider conveyor belts that, intead of moving at a steady
rate, can independently be shifted in an arbitrary direction for an
arbitrary distance (but still over an integral number of lattice
sites) at each cycle; and an interaction rule that can be specified
afresh at every cycle.  We thus get a dynamics, called a {\em
\CCP}, that is still uniform over space but
whose parameters are {\em time-dependent}. A conveyor belt may remain
at rest for two cycles, shift two sites up and seventeen to the right
at the next cycle, etc.\ Similarly, the rule may be to swap the
contents of two conveyor belts at one cycle, apply the \hpp{}
interaction at the next cycle, then clear the northward moving belt,
etc.

\medskip

In a sense, a conveyor-collision processor is to a cellular automaton
what an ordinary computer is to a finite automaton. At any one moment,
the activity of a conventional \cpu\ is basically that of a finite
automaton---with registers and flags representing the state variables
and the current instruction representing the transition function.
However, the nature of this automaton gets continually renewed by the
program stream and by data exchanges with the ``external world''
(\dram{} and I/O channels). Analogously, under program control and
with occasional data exchanges with the outside world, a
conveyor-collision processor may act as a different cellular automaton
at every cycle.

\medskip

\Cam-8 is a {\em native} \CCP{}or, implementing the above programmer's
model in a faithful and efficient fashion (see \app{cam8} for
details). Data movement is done mainly through address manipulation,
and so is very fast. Updating is done using lookup tables, which can
be specified anew for each scan of the space with no time penalty.
The same pool of computational resources can be dynamically
reallocated between different functions, so that, for example, the
machine can be reconfigured for the desired number of dimensions
and conveyors.

The sequence of instructions is not stored in the machine itself, but
is generated and transmitted to the machine by a general-purpose
workstation acting as a host. The machine instruction set is augmented
by appropriate generalizations of opcodes such as {\sc flag test} and
{\sc flag set}, so that the host can get feedback from the machine
and interactively steer a computation.


\endinput

