% -*- Mode:Text -*- 
\chapter{The Programmable Matter Lab}

In brief, the aim of the present proposal is to make available to the
scientific community a novel kind of research facility which may be
described as a ``Programmable Matter Lab''. The timing of our proposal
reflects the fact that computing hardware ideally suited for this
purpose has just appeared on the scene, in the form of our \cam-8
scalable multiprocessor.  What we want to do now is develop, as it
were, a ``Manual of Laboratory Concepts and Techniques'' that will
accompany this hardware and allow it to be used by a variety of
scientists as a broad-scope physical modeling platform.

Perhaps the best way to explain what will be entailed by this {\em
methodology development} effort is to imagine using the programmable
matter lab for tackling a variety of problems.  Like the peasant in
{\em Le Bourgeois Gentilhomme} who ``spoke prose without knowing it,''
physicists will realize that to a great extent they already know how
to ``program'' the programmable matter lab.  In fact, many of the
statistical mechanics models physicists are most familiar with
constitute---directly in their original formulation---ready-to-run
``programs'' for the programmable matter lab.


\section{A modeling scenario}

Suppose we want to study the flow of a two-phase immiscible fluid
(``water'' and ``oil'') through a three-dimensional porous medium
(``sandstone'') (cf.\ \cite{rothman-emulsions}). The questions we have
in mind might be of the following kind
 \begin{itemize}
	\item How does the bulk permeability (flux over pressure
gradient) change with the size and spatial distribution of pores? with
temperature? with pressure?
	\item If we add soap to the water, how sudden is the
transition to a one-phase flow?
	\item Suppose that oil wets the sandstone while water doesn't.
Then droplets of oil will accrete on the walls and constrict the
channels.  Depending on geometry and dynamical parameters, these
accretions may either choke off the flow, or instead, as they
grow too large, snap off the walls.  In the latter case, what is
the accretion-vs-ablation steady state?
 \end{itemize}

In pre-computer days, one would try to answer these questions by {\em
verbatim} simulations (with real sand, water, and oil) in the geology
lab. Besides the model ingredients, one would need storage tanks,
pumps, heaters, thermometers, pressure and flow probes, cameras, etc.\
to set up appropriate conditions and monitor the relevant variables.

\medskip

The programmable matter lab supports a modeling style that has this
{\em verbatim}, hands-on flavor; the difference, of course, is that
system components and interfacing devices are synthesized out of the
programmable matter medium.

The user sits at the console of a ``host''---such as a {\sc
sparc}station---which is connected to a \cam-8 ``box'' (see \app{cam8}
for implementation details and technical data). The entire contents of
this box, representing a volume of the stone/water/oil system, is
directly and continuously visible in real time on a separate monitor
(cf.\ \fig{plurality}a). {\em What} is seen and {\em how} it is seen
(sandstone, water, oil, interfaces; by projection, by cross-section,
from what angle; with what ``staining'' technique, with what shading
and hidden-object rules, etc.) is programmable.

All the while, the system in the box evolves according to its internal
dynamics complemented by external forcing conditions (e.g., flow
sources and sinks), as specified by a \ccp{} model. Internal and
external parameters can be adjusted interactively or driven by a
pre-established schedule.

In parallel with this, a variety of front-end preprocessing operations
are performed directly within the programmable-matter box, such as
coarse-grained averaging of site variables (to obtain region-by-region
values of density, pressure, flow-rate), or multichannel analysis of
selected patterns or events (to obtain the distribution of oil-droplet
sizes, or to count at what rates oil droplets get stuck to or unstuck
from the walls).

While this happens in the \cam-8 box, the host processor remains fully
available for further high-level processing of the preprocessed data,
performing tasks that are more typical of a conventional
scientific-computer environment.

\medskip

A few dozen \cam-8 modules costing perhaps a thousand dollars each, can
support a model of this kind at a resolution of 1024\by1024\by1024
elemental cells (one billion 16-bit sites!) and an update rate of a
couple of frames per second. In spite of the isometric correspondence, in
the \cam-8 architecture, between system space/time and model-hardware
space/time, the space-space and space-time aspect ratios can be
reconfigured at the {\em software} level, so that this same \cam-8
hardware setup would be able to model a slab of 2048\by2048\by256 (or even
32K\by32K\by1) at
the same rate, or a 256\by256\by256 cube at {\em video} rate ($\approx$100
frames/sec). Likewise, resolution in the space domain can be traded
for resolution in the state domain: one can have more complex, though
proportionately fewer, cells.

By the same token, a larger number of modules will indifferently
satisfy needs for higher speed, larger simulation volume, or a more
complex dynamics.

\medskip




\section{The model {\em is} the program}

Efficiently implementing a simulation model of some physical system on
a conventional computer entails three levels of translation. At the
top level (``conceptual computational model'') one has to express the
state-variables and the dynamical laws of the physical system in terms
of data structures and algorithms (e.g., finite-difference schemes for
partial differential equations) that are appropriate for the questions
one intends to investigate and well-matched to the given computer
architecture.  At the middle level (``programming''), one explicitly
encodes the conceptual model into a general-purpose algorithmic
language such as {\sc fortran}, {\sc c}, or {\sc lisp}.  The bottom
level (``compilation''), which translates the program into a sequence
of machine-language primitives (or, when appropriate, calls to
pre-compiled system functions), is automatically performed by system
software and is not normally the user's concern.

What do these three levels look like within the programmable-matter
discipline?

\smallsection{Conceptual computational model}

Coming up with a good conceptual computational model of the mechanisms
that may underly a certain phenomenology remains, of course, the
scientist's main responsibility. The methodology that we will provide
will include a wealth of worked-out examples showing how different
kinds of physical situations can be expressed in terms of \ccps{}
(\chapt{methods}).  This methodology will also include general
techniques for efficiently translating other cellular-automata-like
models into \ccps{}, so that any such models can be considered as
equivalent to \ccps.

A great variety of conceptual models discussed in the literature
(e.g., the Ising and Potts models; many Monte-Carlo dynamics for the
exploration of constant-energy surfaces or the search for ground
states; lattice-gas models of fluid dynamics; many models of diffusion
and wave-propagation phenomena; many lattice gauge models) are natural
instances of cellular-automata models. This is not a coincidence.
As Leo Kadanoff pointed to us at a workshop where the first cellular
automata machines were unveiled, there is no fear that
cellular-automata-like models will be overlooked by physicists: on the
contrary, because of its conceptual simplicity, a model couched in
discrete, uniform, and local terms is likely to be a physicist's first
reflex when confronted with a new problem.

\smallsection{Programming}

Once the conceptual computational model is couched in a \ccp{} (or
equivalent) format, the model {\em as is} is in essence a \cam-8 {\em
program}---since \cam-8 is a native \ccp{} processor.
\fig{hpp-program} shows what a \ccp{} program for the \hpp{} lattice
gas would look like.  In this program, note that all instructions
directly refer to \cam-8 primitives. For instance, each
\verb|dimension| introduces a new level of nesting in the loop by
which the hardware scans the \dram{}, \verb|convey| specifies the
hardware offset added to the loop index of each dimension, and
\verb|collide| specifies the contents of the \sram{} lookup table.

 \begin{figure*}[htb]
 \small
 \begin{verbatim}
                       dimension: x          |    Define two dimensions, "x" and "y"
                       dimension: y          |   
                                             |   
                        conveyor: North 2    |    Define four conveyors,
                        conveyor: South 2    |      "North", "South", "East", "West",
                        conveyor: East 2     |      carrying 2-state variables
                        conveyor: West 2     |   
                                             |   
                                             |   
                            step: HPP        |    Define the HPP rule as follows:
      convey: North  1 y                     |    At each step, shift North conveyor
              South -1 y                     |       by +1 in the y direction
              East   1 x                     |      (similar directives for South,
              West  -1 x                     |      West, and East)
     collide:                                |   
         if   North = South and              |    If collision condition occurs
              East = West                    |      ..
         then East <-> North ,               |      rearrange particles as needed
              West <-> South                 |      ..\end{verbatim}
 \caption{Sample \cam-8 program for the \hpp{} rule.}
 \label{fig.hpp-program}
 \end{figure*}



\smallsection{Compilation}

Once the user is aware in a general way of what resources are
ultimately available, it is convenient to let the software handle
many details of how to match model features to machine resources.  For
example, a multiple-species competitive process studied by Griffeath
(see \fig{plurality}b) involves deciding which species is in the majority
in a window of, say, 11\by11 around each site\cite{griffeath}. While the rule
thus entails an interaction at each site of several hundred bits of
data, \cam-8's collision primitive---the lookup table---can only
handle 16 bits at a time. To achieve the desired result, one step of
the given rule must be ``microcoded'' as a sequence of several \cam-8
updating steps; however, there is no need for the user to be concerned
with the details of this conversion.

Let's use a metaphor from chemistry. My conceptual model of a reaction
is likely to be something like
 \begin{equation}\label{eq.coarse}
	\hbox{hydrochloric acid}+{\rm iron}=\hbox{ferric chloride}+{\rm hydrogen}.
 \end{equation}
	\noindent Indeed, in the chemistry lab I can grab a
bottle of muriatic acid, pour it on some steel wool, and immediately
see the hydrogen bubble forth. Stoichiometric details such as
 \begin{equation}\label{eq.fine}
	6{\rm HCl}+2{\rm Fe}_3=2{\rm FeCl}_3+3{\rm H}_2
 \end{equation}
	\noindent happen to be irrelevant to me---and also happen to
be taken care of automatically by the reaction's ``hardware.''

In terms of this metaphor, one of our tasks as methodology suppliers
will be to specify a convenient language in which descriptions at the
conceptual level of formula \eq{coarse} can be expressed, and develop
a compiler that will drive the \cam-8 hardware with instructions at
the conceptual level of formula \eq{fine}. A third important task for
the software is providing appropriate system utilities.

\figtwogiven{plurality}{
\hbox to\textwidth{\hfill
\llap{(a)\ }
\psfig{figure=fig/therm620.ps,height=3in}\hfill
\llap{(b)\ }
\psfig{figure=fig/plur.ps,height=3in}\hfill
}}{(a) Spongy three-dimensional structure
obtained by ``majority'' annealing. (b) Typical attractor texture
produced by one of Griffeath's ``plurality'' rules.}


\smallsection{Utilities}\label{sect.heat-bath}

When modeling on a conventional computer, if one needs random numbers
one can easily write a random-number generator in the same language
as the rest of the experiment.  However, most programming environments
come with a ready-made \verb|RANDOM| facility, presumably designed
by experts to be accurate and efficient. Ultimately, both user program
and system facilities share the same \cpu{} resources.

In an analogous way, in a programmable matter experiment one might
want to couple the system under study to a ``heat bath'' having a
specified, perhaps adjustable, temperature. Such a bath could easily
be designed by the user as an explicit part of the model. But it is
convenient to have a standard, professionally designed, and
well-documented heat bath available in the form of a system facility.
At run time, the heat bath will be synthesized out of the same kind of
programmable matter resources as the other components of the
experiment.

There are a host of other functions (initialization, boundary
conditions, monitoring, visualization, data analysis, etc.)  that in
principle could be left as an ``exercise for the reader'' but that in
practice represent full-fledged research projects. We plan to provide
many of these functions as standard, well thought-out facilities of
the programmable matter lab.


\section{Making the model}\label{sect.making}

Even with the best-conceived hardware and software, the principal task
remains a conceptual one: how to make a model that addresses certain
questions, and how to run it so as to answer those questions.
These topics are touched on in this and the following section.

\medskip

The basic approach of programmable matter is to substitute, for the
known or conjectured microscopic dynamics, a digital, stylized
``pseudo-dynamics'' that one has reason to believe will retain the
essential features of the former; and then run the latter on a large
enough scale to support the study of macroscopic behavior.  The key
element here is ``reason to believe.'' By what criteria, what
precedents, what correspondence rules should one be guided in
constructing an appropriate pseudo-dynamics? What are the likely
ingredients of a model?

As previously discussed in \sect{examples}, many familiar statistical
mechanical models are directly usable as programmable matter
``pseudo-dynamics.''  For example, the random element in Monte-Carlo
dynamics can simply be programmed using extra digital degrees of
freedom distributed throughout the simulation volume, and heat baths
(see \sect{heat-bath} and \sect{other-models}) can similarly be
programmed.  One can also construct fully deterministic
pseudo-dynamics that explore the correct energy surface, as was
discussed in \sect{ising}.

In the course of using our previous cellular automata machines, we
have accumulated a variety of techniques for incorporating specific
physical properties into a digital pseudo-dynamics.  For example,

 \begin{itemize}
	\item {\em Exact conservations:}  In conveyor-collision
processes, if the quantity in question is represented by explicit
tokens (particles, quanta of energy), it is trivial to insure its
conservation at each collision (just define the collision rule
appropriately), and consequently its global conservation.
	\item {\em Microscopic reversibility:} Microscopic
reversibility is usually a prerequisite for a realistic
thermodynamics.  Though achieving this is not a trivial matter in
general, specific recipes for reversibility are available (for
example, if the collision rule in a conveyor-collision process is
reversible, then so is the global evolution).
 \end{itemize}

There are many unresolved issues in modeling physical systems with a
digital pseudo-dynamics that are the subject of current investigation.
For example, unlike fluid dynamics, the study of the propagation of
deformations and stresses in cellular automata solids is still in its
infancy.  Complex molecular species are normally modeled as point
particles with many bits of ``properties'' that move along with them,
rather than as extended objects.

Finally, a promising source of interesting digital pseudo-dynamics
models comes from quantum mechanics via Trotterization.  By making use
of the well known connection between quantum mechanical systems in $d$
dimensions and classical systems in $d+1$ dimensions, classical Monte
Carlo simulations can be extended to quantum mechanical many body
systems (see \cite{suzuki}).


\section{Using the model}

In our programmable matter lab, we will follow as far as possible the
metaphor of a physical laboratory, since the kinds of systems we are
focused on all have a quite physical aspect.  Unlike real physics,
though, we have complete control of the microscopic dynamics: it
becomes possible to adjust the dynamics to make features of interest
easy to ``see'' and to ``measure''.  In other words, we will often
design the system with probes ``built-in.''

In this context, the \cam-8 control-host computer plays the role of a
computer controlling a physical experiment.  It controls the
adjustable parameters of the experiment in real-time (e.g., wind
velocity, pressure gradients, illumination, etc.) and directs the
placement and operation of data ``probes.''  The final stages of data
analysis will be done largely on the control-host using rather
conventional techniques, but the early stages of data aquisition and
reduction will be performed directly by \cam-8.


\subsection{Event counting}

The primary tool that is provided by the \cam-8 architecture for data
gathering is {\em event counting}.  This facility is built in at a low
level in the hardware, and proceeds in parallel with the dynamical
updating of the space.  As is discussed in \app{cam8}, we take
advantage of the sequentiality and scan flexibility of the basic
hardware elements of \cam-8 to allow us to count any function of the
cell data, accumulating separate totals for patches of our space of a
chosen size and shape.  Using event counting and by appropriately
augmenting the system dynamics with extra degrees of freedom, we can
make essentially any desired property of the system quantitatively
visible.  For example,

 \begin{itemize}

 	\item {\em Macroscopic variables:} Both intensive and
extensive quantities can be counted.  Depending on the system under
study, these might include detailed spatial profiles (averaged over
small regions) of particle density, pressure, temperature, energy
density, magnetization density, momentum flux, charge flux, viscosity,
collision density, etc.  By counting only along contours of interest,
we can directly monitor such quantities as drag on a wing in a wind
tunnel experiment, or particle flux through a nozzle.
  	\item {\em Correlation functions:} This architecture is very
efficient at calculating correlation functions.  For example, we can
very quickly count the number of times that an arbitrary spatial
arrangement of bits occurs embedded within the system.  In
\cite{super}, we give results on space-space and space-time
autocorrelation functions in lattice gases, which were accumulated on
\cam-6 while the systems ran, without slowing down the simulation.
	\item {\em Critical exponents:} \cam-8 is well suited to
performing Monte Carlo Renomalization Group calculations using
Swendsen's method\cite{swendsen}.  As has already been discussed, this
machine can very efficiently perform large Monte Carlo simulations to
generate equilibrium states at a given temperature (the event counts
can monitor the approach to equilibrium).  An ensemble of such
equilibrium states can be used as the starting point of a real-space
renormalization group transformation such as a block spin
transformation, which can also be efficiently performed by \cam-8
using event counts.  Finally, the correlation functions that lead to
the linearized form of the renormalization group transformation can
also be computed using this hardware.  The extraction of eigenvectors
(scaling fields) and eigenvalues (critical exponents) would probably
be done on the workstation host that controls \cam.
 \end{itemize}

For more details and more examples, see our book, {\em Cellular
Automata Machines---A new environment for modeling}\cite{cambook}.


\subsection{Visualization}

By appropriately augmenting the system dynamics with extra degrees of
freedom (probes), we can make interesting properties of the system
directly visible.  For example,

 \begin{itemize}
	\item {\em Surfaces:} By adding particles of simulated
``light'' to our system, we can continuously generate a 2-dimensional
rendering of surfaces of interest within a 3-dimensional system.
Unlike real light, our dynamics for this synthetic illumination can be
chosen so that it doesn't disturb the system of interest in any way.
We can also choose what properties of the system the ``light''
responds to, in order to directly see features such as particle
density, pressure, temperature, etc.  Similar techniques can be
applied to make selected data on selected subsections (e.g.,
cross-sections) of the system visible.
	\item {\em Flows:} By adding ``ink'' (marked particles) to our
system, or adding ``weather-vane'' variables that accumulate average
momentum information, we can make flows within a fluid system
continuously visible.  
 \end{itemize}

Note that the \cam-8 hardware has direct support for system
visualization, including zooming, panning, and rotations of the system
data, as well as the ability to generate output that can be directly
videotaped.


\subsection{Controlling the experiment}

In a real physical experiment, the experimenter doesn't normally have
to build all pieces of apparatus from scratch.  Similarly, in our
programmable matter lab many useful components of an experiment (and
in some cases all of them, including all dynamical laws needed) will
already be available: providing an extensive toolkit of these
components will be a major part of our task.  These pieces will need
to be hooked together in an appropriate fashion, using appropriate
software tools running on the control host computer.

This control host computer has intimate real-time control over the
simulation.  At every step of evolution, any or all parameters of the
updating can be changed, perhaps on the basis of feedback (such as
event counts) from previous steps.  This kind of closed loop operation
is particularly useful in investigating a parameter space: for
example, we could vary parameters in the definition of a dynamical law
in order to try to match a macroscopic phenomenology as closely as
possible.  This mode of operation is also useful in an engineering
context, where we may want to optimize some macroscopic variable such
as drag in a fluid flow experiment.

In addition to user-defined control over the simulation, there are
some generic control features that will be available to all
experiments, such as default methods of visualizing and panning around
the system under study, as well as generic tools for creating and
editing initial data.

\endinput

