% -*- Mode:TeX -*-
% CAM-8 proposal to DARPA, technical rationale

\chapter{Technical rationale}\label{rationale}


\section{Preliminaries}

We propose to provide an integrated set of tools and methodologies for
the development and use of simulation models based on cellular automata.
The proposal includes (a) the {\em construction} of \cam-8, a parallel
computer based on the cellular-automaton architecture and offering
unprecedentedly high performance and efficiency in the fine-grained
modeling of spatially-extended systems; (b) the {\em development} of
essential system and application software for \cam-8; and (c)
the {\em identification and evaluation} of realistic models for problems
for which this architecture is best suited; and (d) the {\em
documentation} of concepts and methodologies appropriate for this
modeling environment.

The {\em design} of \cam-8 is at present essentially complete.  This
design is the culmination of previous work of ours aimed at
identifying a {\em general-purpose} cellular automata architecture---to
match a broad range of pressing computational needs that have arisen in
the area of fine-grained modeling. Its potential for {\sl applications}
is clear from the experience that we and others have gained, in problems
of realistic interest, with smaller realizations of similar
architectures and with models and algorithms for which this architecture
is particularly suited.

Indeed, all of our experience, both in modeling with cellular automata
and with designing and constructing cellular automata machines, has been
condensed in a simple and powerful manner into the architecture of
\cam-8.

\section{Motivation}

In the study of macroscopic phenomena of applied physics (hydrodynamics,
materials science, etc.), models based on discrete lattice dynamics have
recently come to the forefront because of their directness, flexibility,
stability, and ability to cope with arbitrary boundary conditions (see
Section \ref{hydro}).  These models, which have great
relevance for a number of technological problems of immediate interest,
are poorly served by conventional scientific computers---which are
optimized for the numerical solution of differential equations.  When
the same gross amount of electronic hardware (chips, wires, etc.) is
reconfigured into an appropriate architecture, one obtains a flexible
computer in which discrete lattice dynamics models can run from
thousands to millions of times faster.

Indeed, \cam-6---a tiny cellular automata machine that plugs into a slot
of an {\sc ibm-pc} and is available as an inexpensive commercial
product---can already run these models about as fast as a {\sc cray-1}.
\Cam-8 will offer much greater flexibility and a ten- to
hundred-thousand-fold increase in performance.

It turns out that a computer designed with discrete lattice dynamics in
mind need not be a narrow-purpose computer.  On the contrary, the
resulting architecture claims an optimal range of applications as broad
as that of traditional ``von Neumann'' computers or of the more recently
introduced ``trees'' and ``hypercubes.'' As broad---but centered on a
different segment of the spectrum of computational needs; so that such a
machine will significantly expand the range of problems accessible to
computational investigations rather than compete for already
well-served niches.

\medskip

Most of the current exploration of cellular automata as computational
models for science is being done using machines which were designed for
very different purposes.  Such experimentation doesn't make apparent the
tremendous computational power that is potentially available to models
tailored for uniform arrays of simple processors.  Nevertheless, we
already have seen examples of interesting physical systems which have
been quantitatively analyzed for the first time using cellular automata
(see Section~\ref{hydro}).  {\sc Cam}-8 will add several orders of
magnitude in performance to what is possible today: we expect that the
existence of this machine will be an important stimulus to the entire
field of cellular automata, and will provide an incentive for scientists
working in a broad range of disciplines to investigate a new class of
computational models.


\section{A cellular automata supercomputer}

In the realm of massive computation, the proposed \cam-8 machine is the
first significant implementation of a {\sl local} and {\sl uniform}
interconnection scheme---an architecture that directly reflects the
topology of physical spacetime and is therefore {\sl indefinitely
extensible}.

The proposed architecture is aimed at exploring a broad range of
applications, and thus stresses flexibility rather than ultimate speed.
It uses conventional technology and is targeted at performances up to
about {\sl one Tera-event/sec}.  (An {\sl event} is the primitive
site-updating process of this architecture.  In \cam-8, an event
computes in a single clock cycle 16 {\sl arbitrary} functions of 16 {\sl
independently-addressed} variables---and typically corresponds to a long
sequence of instructions in a conventional computer.)

Using slightly more refined technologies---as may be expected to become
widely available in the next few years---the same architecture will
easily and affordably yield {\sl tens of Tera-events/sec}.  Should it
become vital to achieve much greater throughput for a particular
problem, {\sl application-specific} adaptations of this architecture are
feasible {\sl even today} that would run several orders of magnitude
faster.  Finally, for applications
where the local-and-uniform interconnection scheme is suitable, a
fully-parallel implementation coupled to mass-production techniques can
lead to dedicated ``ultracomputers'' of truly astronomical performance
(see Section \ref{ultra}).
						
\subsection{Function}\label{function}

The functional architecture of \cam-8 is fundamentally that of a {\sl
cellular automaton}---where a large number of identical atomic
processors are uniformly interconnected to form an indefinitely extended
two- or three-dimensional network (``polynomial interconnection''
architecture) and operated in synchronism.
This approach gives \cam-8
unmatched performance in dealing with discrete, fine-grained models of
systems whose topology reflects that of ordinary spacetime.

Our specific implementation of the basic cellular-automaton plan
includes major refinements recommended by recent theoretical
developments, and makes use of a number of original solutions suggested
by the current technological context.  Some of these features allow
\cam-8 to retain a high level of performance even in certain areas where
one might expect that an ``exponential interconnection'' architecture
(e.g., tree or hypercube) would be mandatory.

For many applications, this machine may be visualized as a volume of
simulated {\sl programmable matter} in which a large variety of
experiments on spatially-extended physical systems can be performed
rapidly and conveniently (Fig.\ \ref{matter})---a useful metaphor for
this is a ``silicon wind-tunnel.'' Other examples (see
\cite{cambook,wolfram-book,los-alamos,santa-fe} and references therein)
include the simulation of physical phenomena such as diffusion,
aggregation, and phase separation; the study of properties of materials
such as plasmas and alloys, and of chemical reactions; the exploration
of certain models of fundamental physics; and a number of practical
applications such as the study of how waves propagate in a
nonhomogeneous medium and are reflected by arbitrarily-shaped obstacles
(e.g., radar and sonar echo analysis).


\figw{matter}{5.57in}{(a) Drift along the flow lines and diffusion
of smoke tracers in a wind tunnel.  (b) Colonization by competing
species.  (c) Evolution of elastic domain boundaries.  (d) Magnetic
domains.}

In addition, \cam-8 will constitute a powerful computer for many
information-processing applications dealing with fine-grained structures
having a high degree of regularity in at least two dimensions---for
instance, a ``silicon retina'' with real-time performance. Indeed, this
appears to be an ideal architecture for many pattern-recognition and
-tracking tasks (cf.\ \cite{texture-lock}).

Further, \cam-8 will provide a natural environment for the simulation of
large-scale logic circuits; in particular, for exploring the potential
of reconfigurable circuits (``downloadable hardware''). 

Finally, a machine of the functionality of \cam-8 will be
indispensable for designing and emulating the algorithms that will
constitute the firmware of a new generation of fully-parallel
cellular-automaton ultracomputers (see Section \ref{ultra}).

\subsection{Structure}\label{structure}

The three resources that a large simulation model will demand and absorb
in virtually unlimited amounts are (a) {\sl storage} machinery for its
distributed {\sl state variables}, (b) {\sl processing} machinery for
its distributed {\sl transition function}, and (c) {\sl data movement}
machinery for {\sl interconnection}, i.e., for steadily pumping state
variables in and out of the transition function.  In \cam-8 most data
movement is virtual, that is, what are moved are pointers to large
blocks of data rather than the data themselves; this function is
performed by a relatively simple {\sc vlsi} chip, which constitutes the
heart of each processing node (and provides all other ancillary
functions).  Thanks to this chip---which quite literally ``embodies''
the \cam-8 architecture---our machine is able to employ, respectively
for storage and processing, {\sl commodity} \dram{}s and \sram{}s, both
used at maximum bandwidth on a 100\% duty cycle.

This leanness of implementation is essential if one wants to make
substantial use of the most characteristic feature of a
cellular-automaton architecture, namely its {\sl indefinite scalability}
within the constraints of real-world physics.

\medskip

In fact, \cam-8 is designed to be modularly expandable, and {\sl
affordably} expandable.  An installation of ``nominal size'' (a size
chosen arbitrarily but once and for all in order to provide a consistent
term of reference throughout this proposal), which is expected to cost
approximately \$2 million/unit for a small production run, will handle
one billion ($2^{30}$) 16-bit sites, for a total of 2 Gigabytes of
state-variables, which can be arranged in a number of topologies.
Typical topologies include a three-dimensional array (of 1K\by 1K\by 1K
sites), a two-dimensional array (of 32K\by 32K sites), or a sequential
network with up to 16K ``parallel nodes'' (each consisting of a square
array of 1 million individual elements).  In all cases, the net
throughput will be 25 Giga-events/sec, or {\sl an effective update
bandwidth of 0.4 Tera-bits/sec}.

Though a \cam-8 event handles a number of bits comparable to that of a
conventional computer operation, the manipulations performed on these
bits in a single step are of a much more general nature, and include any
necessary data movement (all 16 input bits that interact in an event may
come from different, independently-addressed sources, and the 16 bits of
the result go to different destinations), so that an event would
typically corresponds to a long sequence of instructions in a
conventional computer.  We introduce the distinguished term {\sl event}
as a reminder that a performance comparison in terms of ``operations per
second'' between \cam-8 and a more conventional computer can be
meaningfully made only with reference to a specific kind of task.

\medskip

The maximum-size machine one can make out of the \cam-8 architecture is
limited by economics rather than by any essential features of the
architecture.  For example, within the cost range of a supercomputer
($\approx$ \$20 million), an assembly of sixteen ``nominal size'' units
would provide 0.4 Tera-events/sec, or 6 Tera-bits/sec of net
state-variable updating bandwidth.  Larger assemblies are possible
at a proportionate cost.

\Cam-8 is also usefully scalable downwards, since the nominal-size,
2-Gigabyte unit discussed here consists of much smaller modules
(2 Megabytes) that can be operated independently.\footnote
    {One such module would make a complete drop-in ``cellular automata
accelerator'' card for a personal computer---with a size and cost
comparable to those of the \cam-6 card currently in commercial
production but with sixteen times the raw processing power, a larger
number of cells (up to $2^{20}$), and much greater flexibility.
Directly connected to an ordinary 512-line color monitor, such a card
would process and display at 60 frames/sec the evolution of a system of
512\by512 16-bit sites (0.25 Giga-bits/sec).  This machine will
accommodate substantial parallel-processing tasks---including useful
experiments in lattice-gas hydrodynamics.}
    Indeed, the overall volume of \cam-8 ``stuff'' present in small
installations may well end up exceeding that present in nominal-size
(or larger) installations.  Applications developed on inexpensive small
installations will be directly transferable to larger machines if faster or
more massive simulations are needed.

\medskip

The proposed design includes facilities for continuous monitoring of
overall system parameters and detailed probing of the activity in
selected areas of the array. Concurrently with the simulation,
the machine can also be used as a programmable parallel analyzer, to
provide real-time preprocessing of the current system
state for subsequent analysis by more conventional means.


\section{An emulator of cellular automata ultracomputers}\label{ultra}

Besides providing a major kind of computing resource immediately capable
of concrete applications, \cam-8 will allow the scientific community to
explore how to make effective use of the astronomical amounts of raw
processing power that are achievable with a local and uniform
interconnection scheme.

\medskip

Once the computing medium is structured like a sheet of postage stamps,
it becomes possible to use mass-production techniques to ``print''
virtually unlimited amounts of it (cf.\ \cite{feynman-bottom}).  We
estimate that within twenty years it will be technologically and
economically feasible to build a problem-specific, fully-parallel
cellular automata processor which updates an entire array of $10^{16}$
bits once every 200 pico-seconds (a few trillion {\sl trillion}
bit-updates per second!).  Recent studies (e.g., lattice-gas models of
fluid dynamics) indicate that there are important classes of
applications for which the processing capabilities of such dedicated
``ultracomputers'' would be welcome---and would be utilized at 100\%
efficiency.

The decision to cast in millions of copies the firmware that embodies a
specific cellular-automaton rule is not one to be taken lightly.  Today,
confronted with the analogous problem when developing an
application-specific integrated circuit, we can make recourse to
extensive simulation on a general-purpose computer.  However, the
macroscopic properties of a particular brand of ``programmable matter''
(cf.\ Section \ref{function}) may fully emerge only when millions or
billions of microscopic sites are updated billions of times. To certify
a cellular-automaton rule as ``the one we really wanted'' for a certain
modeling task, emulation on a conventional computer is out of the question.

\medskip

Though much slower than the target machines envisioned above,
\cam-8 offers flexibility, instant reprogrammability, and breakpoint
and analysis facilities, and it would be able to emulate dedicated
programmable matter thousands to millions of times faster than a
conventional computer---thus narrowing by several orders of magnitude
the gap between currently available design tools and the intended
targets.

To be concrete, it is conceivable that with an investment of the order
of a billion dollars one may build, based on a cellular-automaton rule,
a chunk of simulated weather or a chunk of simulated wind tunnel large,
fast, and accurate enough to be useful for actual ``production'' work
(rather than just contributing to the understanding of the phenomena
involved).  In planning such a facility one would certainly want first
to ``simulate the simulator,'' even if at the rate of one second per
week, before casting any silicon.  A machine like \cam-8 would be
usable for this kind of emulation; on the other hand, to simulate one
second's worth of activity of the target facility on a conventional
supercomputer might take several lifetimes.


\section{Performance summary}

This section summarizes the key performance parameters of the \cam-8
architecture. For comparison purposes, this section also lists
plausible parameters for a dedicated, highly-parallel implementation
restricted to the simulation of a {\sl specific} model.

The generality and flexibility of \cam-8 permits extensive
experimentation with and simulation of various rules, which may then be
cast directly in silicon to achieve 5 to 6 orders of magnitude speedup.

\subsection{CAM-8 architecture}

The nominal-size \cam-8 machine discussed in this proposal consists of
1024 modules operating in parallel, updating 16-bit sites by table
lookup.  Within each module, a single 64K\by16 {\sc sram} table is time
shared among a million sites.  A single such module is already a usable
machine; on the other hand, the design accommodates machines much larger
than nominal-size: scalability is limited by economics rather than by
any essential feature of the architecture.  In the cost estimates of
Table~\ref{summ8} we ignore non-recurring engineering costs, and assume
a production run of a single machine of the given size.

\begin{table}[htb]\label{summ8}
$$
\begin{tabular}{|l||r|r|r|} 
\multicolumn{1}{c}{} &\multicolumn{3}{c}{Machine size} \\\cline{2-4}
\multicolumn{1}{c|}{} &  1 module  & $2^{10}$ modules   &  $2^{16}$ modules \\
\multicolumn{1}{c|}{} &             & (nominal-size\footnotemark\ \cam-8) 
                                & (64\by nominal size)\\\cline{2-4}\hline
Site updates/sec    &  25 Mega   & 25 Giga            &  1.6 Tera \\\hline
Number of sites     &   1 Mega   &  1 Giga            &  64 Giga  \\\hline
Estimated cost      &  \$4000      & \$2.5 million             &  \$64 million    \\\hline
\end{tabular}
$$
\caption{Performance summary for the \cam-8 architecture.}
\end{table}
\footnotetext{The proposed prototype is 1/4 of this nominal size.}

\subsection{Problem-specific parallel implementation}\label{ps-parallel}

Cellular automata are ideally suited to be cast into highly-parallel {\sc vlsi}
chips which run at very high clock rates.  When one has developed specific
models which are deemed to be very useful, then one can make dedicated chips for
running these models in a highly-parallel fashion.  Given today's
interconnect technology, we would put 1024 simple processors on each chip,
and time share each processor among 64 8-bit sites.\footnote
        {If the problem requires a substantial third dimension, we would
put fewer processors and more memory on each chip, so that the third
dimension could be done by a two-dimensional array of processors time
shared in the third dimension.} The numbers in Table~\ref{summp} reflect
these assumptions.

\begin{table}[htb]\label{summp} $$ \begin{tabular}{|l||r|r|r|}
\multicolumn{1}{c}{} &\multicolumn{3}{c}{Machine size} \\\cline{2-4}
\multicolumn{1}{c|}{} & 1 chip & $2^{10}$ chips & $2^{20}$ chips
\\\cline{2-4}\hline Site updates/sec & .5 Tera & 500 Tera & 500,000 Tera
\\\hline Number of sites & 64 Kilo & 64 Mega & 64 Giga\\\hline Estimated
cost & \$1000 & \$1 million & \$1 billion \\\hline \end{tabular} $$
\caption{Performance summary for a parallel {\sc asic} implementation of
a simple two-dimensional lattice gas model.} \end{table}


\section{Cellular automata}

Cellular automata machines (\cam{}s) represent a departure from ordinary
``von Neumann'' architectures, which are optimized for
randomly-sequenced computations acting on relatively large lumps of
data.  Here we base our architecture on models that are ideally suited
for uniformly-sequenced computations on fine-grained data---namely {\sl
cellular automata}.

Cellular automata are the computer scientist's counterpart to the
physicist's concept of `field'.  A cellular automaton can be thought of
as a stylized universe.  It consists of a uniform grid, with each site
or cell containing a few bits of data; time advances in discrete steps;
and the laws of the universe are represented by a single rule---e.g., a
small lookup table---through which at each time- step each cell
determines its new state from that of its
neighbors\cite{burks,toffoli-thesis,wolfram-stat}.  Consequently, the
system's laws are {\sl local} and {\sl uniform}.  Given suitable rules,
such a simple mechanism is capable of supporting a whole hierarchy of
structures, phenomena, and properties.
\medskip

Discrete lattice dynamics---which is but another name for
``physically-minded cellular automata''---provide, as an alternative to
differential equations, new, powerful methods and techniques for
studying a large class of physical systems in which a digital
microscopic dynamics gives rise to the same macroscopic dynamics as the
physical process of interest.  These methods exploit the resources of
digital computing in a more direct way than the methods of calculus, and
are expected to lead to models that can be formulated more naturally and
treated more efficiently on digital hardware.

In addition to providing an alternative modeling tool for the study of
systems that are traditionally represented by continuous models,
cellular automata offer a natural approach to the modeling of systems
that are intrinsically discrete, and whose complexity arises from the
presence of a large number of structural elements (parameters and
state-variables).  Such models are common in physics and in materials
science (e.g., discrete spin models\cite{creutz,herrmann}) and in
computer science (e.g., logic simulation\cite{cambook}).

\medskip

The structure of cellular automata directly reflects those ultimate
physical constraints to large-scale computation (e.g., topology and
connectivity of physical space, finite speed of propagation of signals)
that are already felt to some extent by current computers, and which are
going to be more and more significant in the design of larger computers.
In this context, the proposed machine will offer an advanced testing
ground for developing modeling and programming concepts suitable for
massively-parallel, large-scale computation.


\subsection{Modeling with cellular automata}

Cellular automata are most naturally used, and cellular automata
machines most efficiently exploited, in modeling systems whose
geometric and causal relations are close to those of ordinary
space-time\cite{cambook}. These include:
 \begin{enumerate}
  \item Problems of a direct physical nature: statistical mechanics,
fluid dynamics, microscopic mechanics, etc.
  \item Collective phenomena which are in principle reducible to the
laws of physics, such as are encountered in chemistry, biology, and
geology: reaction dynamics (Fig.\ \ref{zhabo-drift}a), phase separation,
aggregation (Fig.\ \ref{dendrite-forget}a), surface tension (Fig.\
\ref{matter})c, and, in general, materials science.
  \item Problems analogous to the above, but entailing a higher level of
aggregation: weather, geology, population dynamics (Figs.\ \ref{matter}b
and \ref{zhabo-drift}b), epidemiology, macroeconomics, and
communications networks.
  \item Issues of self-organization, stability, resistance to noise,
self-reproduction, and evolution; fractality (Fig.\
\ref{dendrite-forget}); chaotic behavior arising from
simple laws and simple initial conditions; and, in general, nonlinear
dynamics in complex systems.
  \item Problems satisfying realistic space-time constraints, but
whose laws are arbitrarily assigned: simulation of large digital
circuits; distributed computation and control; inventory and shipping,
flows in networks; certain questions in graph theory, dynamic
programming, operations research; certain board games;
and, in general, simulation of universes provided with
an {\sl ad hoc} set of laws.
  \item Miscellaneous problems having a strong geometric component:
image processing, analysis, and generation; parallel encryption and
decryption; certain problems of pattern recognition\cite{texture-lock}).
  \item The specific implementation of the cellular automata
architecture that we propose for \cam-8 provides in a natural way
additional interconnection and processing features that go beyond those
required for strictly local and uniform processing.  In particular, the
1024 processors can each run a {\sl different} program; moreover the
cells that in one step influence a given cell are not restricted to be
{\sl immediate} neighbors, but can be arbitrarily chosen from within a
rather large radius (about 1000 sites in two
dimensions, and 100 in three dimensions).  These features make \cam-8
particularly attractive for certain applications (e.g., detection of
long-range correlations, routing, and hierarchical processing) which are
traditionally not deemed appropriate for cellular automata.
 \end{enumerate}

\figw{zhabo-drift}{3in}{(a) Interacting-particle model of the
Zhabotinsky reaction.  (b) Genetic drift.  The sixteen ``Petri dishes''
represent small, geographically segregated populations which started out
with an identical gene pool.  Genetic drift in this situation leads to
strong fluctuations, with gradual depletion of the original gene pool.}

\figw{dendrite-forget}{3in}{(a) Fractal dendrite produced by
diffusion-limited aggregation.  (b) Regular fractal produced by a linear
rule.}


\subsection{An example: Fluid dynamics}\label{hydro}

In the past few years, {\sl lattice gases} have come to the forefront as
a promising approach to fluid-dynamics modeling (see \cite{santa-fe} and
references therein).  Considering that a substantial fraction of the
processing capacity of today's supercomputers is devoted to fluid
dynamics calculations, and considering also that hydrodynamics tends to
be regarded as a rather mature discipline, the introduction of a novel
method in this area was bound to raise some excitement\cite{kadanoff}.

\medskip

For concreteness, let us consider the Navier-Stokes equation---the
``master equation'' of hydrodynamics.  A conventional way to study the
evolution of a system governed by this equation is to discretize space
and time, rewrite the equation (which involves {\sl real numbers}
representing density, direction of flow, etc.) in terms of a
finite-difference scheme, code this scheme as a {\sc fortran} program,
and run the program on a general-purpose computer.  

On the other hand, in a cellular automata machine such as \cam-8 one
starts with a multitude of {\sl binary variables} (each representing the
presence or absence of a particle at a given site, or the presence or
absence of an obstacle).  By the machine's very architecture, these
variables are interconnected locally and uniformly (i.e., in a way that
directly reflects the structure of the physical space-time in which the
hydrodynamical system resides), and all one has to do is give a look-up
table that specifies the behavior of an individual binary variable as a
function of the state of its neighbors.  This table, which consists of a
small number of binary entries, bears no direct resemblance to the
Navier-Stokes equation; yet on a macroscopic scale and within a certain
range of parameters the resulting model agrees with the Navier-Stokes
equation---and furthermore may be able to answer physical questions that
this equation is not even equipped to deal with.

\medskip

What has happened is that the ``matter'' of \cam-8 has been programmed
to be a {\sl fluid}.  The synthetic fluid's individual particles (which
represent in a simplified and abridged way the particles of the real
fluid) carry on their simple-minded particles' routine (travel straight,
bounce, and so on {\sl ad infinitum}) which is simple and certainly not
{\sl governed} by the Navier-Stokes equation.  The latter arises from
the {\sl statistics} of these particles, provided we can represent and
follow the individual histories of a very large number of them (Fig.\
\ref{salem})

\figw{salem}{2.6in}{Flow past an obstacle (from Salem and Wolfram).
Each arrow represents the average flow in a 64\by64-cell area.} 

To a model of this kind, computing the flow past a complex-shaped
obstacle is no harder than past a cylindrical rod.  As in any model, the
final accuracy will depend on the degree of stylization and the amount
of detail; however, the lattice-gas approach is intrinsically immune to
instabilities, diverging solutions, and other artifacts against which
great caution must be exercised in a conventional numerical computation.


% This figure was 5.5in

\figw{lens}{5in}{Refraction and reflection of a plane wave by a
spherical lens on a 256\by256-site grid.  The wave is realized as a
density perturbation of a simple lattice gas rule.}
%; the {\sl same} rule
%is use outside and inside the lens, but is applied {\sl half as often}
%inside the lens, leading to an index of refraction $k=2$.}


\subsection{Related models}\label{related-models}

Fluid-like behavior is ubiquitous in nature, showing up in phenomena
ranging from electromagnetism to the behavior of stars and galaxies, and
encompassing such commonplace phenomena as diffusion and waves.  For this
reason, hydrodynamic models play a singularly important role in the
construction of further models of physical interest: one can construct
an endless variety of new models by suitably elaborating on fluid
models.

For example, the refraction example of Fig.~\ref{lens} is just a variant
of a simple fluid model with an extra ``lens'' bit added to each cell.
The areas of higher refractive index are marked using this extra
bit---in the case shown, we simply draw our lens.  During half of the
updating steps, all cells follow the fluid rule, but during the other
half only the unmarked cells are updated.  This results in the speed of
sound within the lens being half as great as it is outside of the lens,
and hence the refractive index inside is double that outside.

In a similar manner, by adding more particle species, more particle
directions and speeds, and new kinds of particle interactions, a number
of physical models are constructed in \cite{dhumieres,montgomery} and in
\cite{cambook}, including models of interface phenomena and phase
changes.  It is to a large extent this new mechanism for constructing
models of physical interest that has led to the current climate of
rising excitement among researchers involved in CA modeling (the fluid
models have also acted as a stimulus by showing that important
macroscopic physical phenomena can be modeled accurately by cellular
automata).

Results in this field are coming quickly now---the estimates in
\cite{discrete-fluids} (which has just been published) for the biggest
hydrodynamic simulation that is computationally accessible with current
hardware is now obsolete by two orders of
magnitude\cite{doolen-private}, due not to new hardware, but to
algorithmic breakthroughs in the efficiency with which CA can model
fluids.  There is no reason to believe that models will not be available
soon that can deal practically with supersonic flows, and even flows at
high Mach numbers.

A criticism that has been leveled at CA simulations in general is that
they are verbatim simulations, and so there is some fear that the number
of particles that one must simulate in order to capture macroscopic
phenomena may be astronomical.  One answer to this concern is that
systems which had not previously been analyzed have now been studied
using only a few million cells in fluid flow
experiments\cite{discrete-fluids}, and that phenomena involving waves
have been simulated well using only a few thousand cells (see
Fig.~\ref{lens}, and also reference \cite{doolen-waves}).  And of course
once one leaves the confines of fluid dynamics, there are many examples
of discrete systems that physicists have found useful (such as Ising
systems and their relatives) on scales that can be handled by even
rather modest computers today.  In fact it will undoubtedly be the
materials science types of models, and fluid models with chemical
reactions added in, which will be the first extensively used CA models.

A direct implementation of a CA model of physics requires that at every
point in space we must represent as much detail as will be required
anywhere in the simulation---thus in a hydrodynamic model we will find
ourselves computing everywhere just as hard as we need to compute in the
most turbulent regions we wish to handle.  This property, for example,
(together with the size and speed of hardware and the efficiency of the
CA rules used) limits the Reynolds numbers that can be achieved in such
a CA simulation.  Simple dimensional arguments\cite{yakhot} suggest that
the storage requirements of CA simulations at high Reynolds numbers may
be much worse than conventional calculations, but more careful
analysis\cite{discrete-fluids} indicates that this is not necessarily the
case.  In any event, verbatim simulation (in the form of CA) already has
a useful role in fluid models which involve complicated initial
conditions (which we just ``draw,'' much as we did in the lens example
above) and in the rapid ``prototyping'' of unusual flow
situations\cite{doolen}.  The wastefulness (in certain
cases) of verbatim simulation is just the obverse of its convenience and
simplicity.  And after all, hardware that is exactly duplicated can be
rather easy to produce: biology routinely duplicates billions of pages
of genetic code, giving each cell the whole complement, even though most
of those pages will never be read by each individual cell.

A medieval scribe would have balked at the waste inherent in the
Sunday edition of the New York Times, but we know that printing it costs
only a few cents.  In a similar vein, the potential of cellular automata
models should be assessed in terms of the appropriate technology.
\Cam-8 is intended to let us preview and decide {\sl what} may be worth
printing; the actual computers that will run production-scale fluid
dynamics models will be much more highly parallel (cf.
Section~\ref{ultra}).\footnote
     {Ultimately it will be possible to build CA machines with truly
astronomical numbers of cells---perhaps by borrowing some of the
construction techniques employed by biological cells for self
reproduction.  Then we will actually be able to run simulations
involving astronomical numbers of particles, when necessary.}


\section{CAM-8}

\Cam-8 is a general purpose cellular automata machine.  The \cam-8
architecture establishes a very tight match between a certain scheme for
general-purpose parallel computation---namely, {\sl partitioning
cellular automata} (see below)---and the kind of computing resources
that are most readily made available by current electronic technology.
The main goals of this architecture  (of which an up-to-date description
appears in \cite{cam8-book}) are speed, flexibility,
expandability, and economy.

In conventional terms, \cam-8 is a MIMD multiprocessor in which the
current instruction of each individual processor is applied in a uniform
way to every site of a large two- or three-dimensional array---rather
than to a single set of operands.  Within each processor, the updating
of its portion of the array, which logically is a {\sl parallel}
operation, is actually performed {\sl serially} (with pipelining).  At
each site, execution of the instruction is by the ``flash'' technique;
that is, all operands are simultaneously submitted to an exhaustive
lookup table, which embodies the instruction's ``opcode.'' All results
are returned simultaneously, in one clock cycle ($\approx40$ nsec).
Although the serial processors exchange cell data in order to simulate a
large uniformly interconnected space, the predictability of the array
scanning allows this communication to proceed concurrently without
slowing down the computation.

A nominal-size \cam-8 will consist of 1024 processors, each employing a
1 Mega-bit lookup table to serve a 1 Mega-site portion of an overall 1
Giga-site space.

\subsection{Partitioning cellular automata}
                                        
Imagine $n$ data-planes stacked on top of one another, so that at each
site you see a ``pile'' of $n$ data-items.  An updating step for the
whole array consists of two processing phases:
    \begin{itemize} 
        \item {\sl Data interaction}.\quad Take an arbitrary function
$f$ that maps $n$ data-items to $n$ data-items, and apply this function
to each site (that is, give the site's current contents as an argument
to $f$, and take $f$'s result as the site's new contents).

Note that what is done to each site is {\sl totally independent} of any
other site.  Thus, this processing phase can be carried out in parallel,
without any communication between processors; or sequentially (in an
arbitrary order), without any carry-over from one site to the next.
        \item {\sl Data movement}.\quad Take each data-plane and shift
it as a whole any number of sites in any direction (for instance, plane
0 may move 7 units north and 25 east, plane 1 may stay in place, plane 2
may move 17 units south, etc.).

Note that in this processing phase what is done to each {\sl plane} is
totally independent of any other plane.  Moreover, this phase is
``data-blind,'' so that in an appropriate implementation the same result
can be achieved by simply changing the logical origin of the array
(stored in a pointer) rather than bodily moving the data.
    \end{itemize}

\subsection{Implementation}\label{cam8-imp}

One can easily imagine a number of conceptual and practical variations
of the above computing scheme.  Data items could be bits, bytes, fixed-
or floating-point variables, or even more complex data structures;
instead of a two-dimensional array one could use a three-dimensional
one; the function $f$ or the shifts (which respectively specify the
transition function and the interconnection pattern) could be changed
from step to step; etc.

In the \cam-8 implementation, two and three dimensions are wired-in,
with provisions for additional ``short'' dimensions and an additional
``sequential-network'' dimension.  The number of data-planes (or their
three-dimensional equivalent) is $n$=16---so that at each site 16 input
streams interact to yield 16 output streams.  The data items are single
bits.

The array, whose maximum size depends on implementation economics rather
than architectural limitations or technological constraints, is
physically subdivided into identical {\sl modules} (which can be
visualized as ``square tiles'' or ``cubic building blocks,'' depending
on the dimensionality of the array) comprising up to about a million
sites each.  Sites within each module are updated sequentially by a
single processor; the modules themselves operate in parallel, with
processors running in lockstep (e.g., the top left corner is processed
at the same moment in all tiles).


% Note: 4.4in is figure size at 85% reduction      <nhm>module.imp

\figw{fig.module}{4in}{A single module.  A million cells are scanned
internally, data from neighboring modules is incorporated into this
scan, and the net result is converted by table lookup into the new cell
values.  Direct access to each module's scan is permitted by the
flywheel inputs and outputs; the I/O bus is used for communication with
the host computer.}

Within a module, each of the 16 data-planes is stored in a separate 1
Mbit (256K\by 4) dynamic \ram\ chip.  The most general interaction of 16
bit-streams can be explicitly specified by a lookup table of manageable
size ($2^{16}$\by16).  Indeed, the processor within a \cam-8 module is
simply a 16-bit-wide static \ram\ which, operating at full bandwidth (40
nsec), can be time-multiplexed over one million sites in 1/25-th of a
second.  This processing rate matches quite well the rate at which site
variables can be sequentially read out of and written back into \dram.
Thus, the data-interaction phase for each module simply consists of
streaming at full bandwidth the entire set of site variables out of the
\dram\ chips, through the \sram\ chips, and back into the \dram.
Fig.~\ref{fig.module} shows schematically a single module of \cam-8:
within the module, data from the cell-array is filtered through a lookup
table to produce new cell values.

The data-movement phase is achieved by suitably adjusting at each step
the pointers that specify the origin of coordinates for each \dram\
chip---that is, the origin of the sequential-scanning process; this
phase takes virtually no time!  The pointers themselves, as well as a
substantial amount of ancillary circuitry, are contained in a \vlsi\
``glue'' chip (the {\em controller} chip mentioned
in Section \ref{sow}) associated with each \dram\ chip.  In particular, the glue
chip contains short pipelines tying \dram\ to \ram, with taps for the
{\sl flywheel bus};\footnote
        {This is fast parallel port through which, as a simulation runs,
the {\sl entire} contents of the multiprocessor is continuously
accessible in real-time (for inspection and/or modification) to the
outside world.}
        the logic for joining modules edge-to-edge into an arbitrarily
large array; registers and counters useful for data-analysis functions;
\dram\ control circuitry; interface with an I/O bus for communication
with the host; and diagnostic services.

%Note: 3.9in is figure size at 65% reduction      <nhm>connect.imp

\figw{fig.connect}{4.5in}{Interconnection of modules.  Bidirectional
connections 16 bits wide connect each module to its 6 neighbors in a
cubic lattice.  The flywheel bus, distributed throughout the machine,
makes every cell ``visible'' somewhere during each step in which it
participates.  The I/O bus allows the host to communicate with modules.}

In order to tie the various modules into a single uniform space, modules
exchange data with neighboring modules.  In Figs.\ \ref{fig.module} and
\ref{fig.connect} we show only four connections for simplicity, but in
our design modules are actually physically interconnected to form a
three-dimensional cubic ``crystal'' of modules, with nearest-neighbor
interaction.  Thus six connections (each 16 bits wide) are time-shared
as a given module sequentially processes its complement of one million
cells: connecting wires are reduced by a factor of a million when
compared with a fully parallel implementation.

Modules are joined edge-to-edge (or face-to-face, in three dimensions)
in a totally transparent way; in particular, each site can access all of
its neighbors (which are not restricted to being ``first
neighbors''---they may reside hundreds of locations away!) in one clock
cycle, no matter whether these neighbors reside in the same module or in
adjacent ones.  How this is accomplished is explained below with the
help of Fig.~\ref{fig.glue}.

%Note: fig is 2in at 65%     <nhm>glue.imp

\figw{fig.glue}{2in}{Gluing modules together: a 1-dimensional analogy.
To shift left by 3 positions, (1) data in alphabetical order in 4
modules is (2) rotated within each module.  Shaded data should have
shifted into adjacent modules for a true shift, and in (3) it is used by
neighboring modules at the appropriate moment.}

\medskip

{\small

{\sl Gluing details.}\quad Imagine that we have a one-dimensional chain
of 16 cells residing within four adjacent modules each containing four
cells; each cell can hold one letter of the alphabet.  We'll illustrate
our module-gluing technique by applying it to this simple system for a
left shift of the entire space by three positions.

Initially (1) we fill the cells with the letters A through P in
alphabetical order.  Note that each module is connected to only the two
adjacent modules, with the last connected to the first.  In (2) we
change the origin from which data within each chain-module is scanned,
causing each module's data to appear circularly rotated three positions
to the left.  The data which has passed out the left end of each module
and been reinjected into the right end of the {\sl same} module is shown
shaded.  This is the data which should have been injected into the
module to the left if we wanted a true shift.  In (3) we make use of the
fact that all modules scan the same cell position at the same moment, in
order to let each module ``borrow'' the shaded data scanned internally
by the module to its right.  The combination of internal data (white)
and borrowed data (shaded) constructed in this manner by each module
provides a four-cell window into a truly shifted version of the 16-cell
array.

The bit-arrays making up \cam-8's cell array are shifted in three
dimensions using exactly this technique to glue the modules together in
each of the three directions in turn.  Each of the 16 bit-arrays that
make up a \cam-8 module can be independently shifted in an arbitrary
direction and by an arbitrary amount up to the width of the space
serviced by each module, allowing bits from a neighborhood containing
millions of cells to be brought together for simultaneous application to
a lookup table.  Notice in Fig.~\ref{fig.glue} that in (3) the flow of
``borrowed'' data is all in the direction of the intended shift: at any
moment, each connecting link need carry data in only one direction.
Thus, individual bidirectional wires (half-duplex communication) rather
than pairs of one-way wires (full-duplex) can be used to connect
modules, both in this example and in \cam-8.

}

\medskip

In conclusion, the whole data array, consisting of two Gigabytes of
state-variables for the nominal-size installation contemplated here, is
updated in 40 msec---net of all ancillary functions.  If updating rate
rather than model size is paramount, one can restrict the activity of
each module to a smaller number of sites and update the whole array in a
proportionally shorter time.  For instance, if all the processors are
concentrated on a million-site space (1K sites/module), then this space
will be updated 25,000 times per second!


\subsubsection{Monitoring and control}

In addition to simulating the logical operation of a fully parallel
cellular automaton, \cam-8 makes extensive provisions for the continuous
monitoring and control of the ongoing simulation.

\Cam-8 is designed to be managed by a {\sl host} (typically a
high-performance workstation) which communicates with the controller
chips of each module via the host bus (see Fig.~\ref{fig.connect}).
This host performs several important control functions:

    \begin{enumerate}
        \item Real-time control of the machine's parameters (including
the shifting of bit-planes).
        \item Downloading appropriate initial data and transition
functions at the beginning of each simulation phase.
        \item Monitoring in real-time the pre-analyzed data continuously
made available by the machine.
        \item Supervising fault detection and error correction.
        \item Performing moderate amounts of off-line data analysis.
For more exhaustive off-line analysis, accumulated data may be analyzed
by appropriate external computers.
    \end{enumerate}

Since each site in our lattice is updated independently of all other
sites, the sequential scan of cells performed by each module can proceed
in any order selected by the host.  This property is exploited both for
display and for analysis purposes.  For example, \cam-8 processes
cell-data at a rate such that a single module can update 256K sites up
to 100 times per second: this makes it possible to slave the updating to
the frame rate and format of an ordinary \crt\ monitor, allowing direct
real-time display at 60 frames/sec.  Data can even be scanned in such an
order that two-dimensional slices of a three dimensional ``chunk'' of
space serviced by a given module will appear arrayed on the screen in
real time as the updating takes place.  Similarly, no matter what size
or shape the chunk of space being handled by each module is, it is
always possible to scan it in an order that permits a useful display.
This capability to act as its own frame buffer for video output is
clearly useful for small (few modules), highly interactive \cam-8
installations; it will, however, also avoid the need for frame buffers
in certain schemes for producing true three-dimensional output from
nominal-size \cam-8 machines.

Low-level data analysis on \cam-8 is performed by counters located on
the controller chips---arbitrary functions of the 16 cell-bits are counted as
each module scans its data.  If the data within each module is scanned
as a collection of small chunks, each of which is scanned in turn, then the
count from each such chunk can be read by the host separately---allowing
averaging of an arbitrary function of the data to be performed on any
desired scale in parallel with the simulation directly by \cam-8 itself.
The counts obtained in this manner may be averages of energy, density,
magnetization, etc., or they may be correlations between different parts
of a single system, or between two systems run simultaneously.  If the
neighborhood needed for the analysis is different than that needed for
the updating, then analysis steps may be alternated with updating steps,
or one half of the machine may be dedicated to analyzing the simulation
being performed by the other half.

In a similar manner, one of the provisions for error detection (and
correction) included in the design of \cam-8 allows each machine to be
split into two half-machines,\footnote
     {The three-dimensional crystal of 1024 modules that constitutes a
nominal-size machine can be split along any of its three axes into two
machines (the even numbered modules make up one, the odd numbered
modules the other).  Thus the space serviced by any number of \cam-8
machines can be split up into as many as 8 tightly coupled sublattices,
for analyzing correlations, monitoring errors, etc.}
     both of which run the same simulation while continuously comparing
their results in real time against one another.  Each module saves both
the original and the final state of the cell being updated when a
mismatch is detected, so that the host will be able to look at this data
at the end of the step and correct the error (by deciding which of the
pair of modules involved is correct).  Such provisions for error
detection and correction must be made in a scalable architecture such as
\cam-8, since a large assemblage of \cam-8 machines will have many
giga-bytes of memory, and yet we want to ensure exactly correct
operation indefinitely.


\subsection{Summary of original features}\label{sum-orig}

From the above technical choices and other choices of a more conceptual
nature, the following features emerge:
    \begin{enumerate}
        \item Complete generality of transition function (by table
lookup) and of neighborhood interconnection pattern.  The 16 neighbors
can be chosen from anywhere within a volume of a few million sites
centered on the site to be updated (a neighborhood radius of about
one-thousand site units in two dimensions, or one-hundred units in three
dimensions).
        \item Thanks to a single custom chip of moderate complexity that
handles all the control logic for the updating of a bit-plane, ordinary
\dram{}s can be employed for data storage and ordinary \sram{}s for data
processing, both used at full bandwidth on a 100\% duty cycle.
        \item Lockstep operation allows a large number of sites to be
served by a much smaller number of processors without any carry-over
overhead (from site to site within each processor) or overhead due to
interprocessor communication.
        \item Although each processor serially services many sites, the
processors themselves are physically connected as a cellular-automaton
network.  Thus size is indefinitely scalable, while speed remains
strictly independent of size.
        \item A substantial amount of data analysis and reduction can be
performed in parallel with the data processing, so as to provide the
host with manageable amounts of timely information about the ongoing
process.
        \item As a simulation runs, the {\sl entire} contents of the
multiprocessor is accessible in real-time (for inspection and/or
modification) to the outside world, through the {\sl data flywheel} bus.
        \item Our {\sl data flywheel} has little inertia: an interrupt
corresponding to the detection of a particular event is generated on the
same step as the event occurs, and {\sl within one step} the host can
respond by appropriately modifying the process---or even instantly
freezing the entire simulation for detailed examination.
    \end{enumerate}




