% -*- Mode:TeX -*-

\documentstyle[12pt]{article}
\input patmacros.tex

\begin{document}

 \begin{titlepage}
 \begin{flushright}
 {\large
 Massachusetts Institute of Technology\\
 Laboratory for Computer Science\\

 }
 \bigskip\bigskip\bigskip
 {\LARGE
 CAM-8: \\
 \medskip
 A uniform, scalable multiprocessor}

 \bigskip\bigskip

 {\large
 Claims information for patent purposes
 
 }

\vfill

 Prepared by Norman Margolus

\vfill

 \end{flushright}
 \end{titlepage}


\pagenumbering{roman}
\tableofcontents
\newpage

\pagenumbering{arabic}

Prefaced with appropriate background material, we present a list of the
claims that we would like to include in our patent application related
to our cellular automata work, along with a somewhat detailed
description of the ideas (including our present plans for best
implementation).

\section{Background}

As the basis of a computer architecture, cellular
automata\cite{burks,santa-fe,los-alamos,wolfram-book} have much to
recommend them: they are a local and uniform paradigm ideally suited for
implementation in terms of highly parallel digital hardware.  The basic
cellular automaton (CA) model consists of an array of simple processors
distributed uniformly in space, each communicating only with nearby
neighboring processors.  Each processor contains a small amount of state
information (a {\em cell}) that is updated iteratively as a function of
the state of neighboring processors.

Unlike more ``sophisticated'' approaches to massively parallel
computation, in CA there is no difficulty associated with coordinating
the activities of the processors or dividing up the task.  The
computation is mapped identically onto the action of the processors, and
the burden of making effective use of this approach is shifted entirely
onto the task of finding CA ``rules'' for the processors that perform
computations of interest.  In return for formulating computations in
this format, the user is rewarded with the availability of massive
computing power that cannot be made available in any other way: the
locality of interconnections permits extremely fast iterations, and also
allows the number of processors to be scaled astronomically.

% artificial handicap

\subsection{An example}\label{example}

Cellular automata rules are sometimes arrived at by deliberately
stylizing microscopic
physics\cite{creutz,fhp,fhp2,hpp,herrmann,kadanoff,phys-like,margolus-thesis,pde,toffoli-emulators,toffoli-lorentz,cambook,vichniac}.
For example, Pomeau\cite{hpp} constructed a simple {\em lattice gas}
(known as the HPP gas) as follows:

Particles move on a Cartesian lattice, all at unit speed (one cell per time
step) and in one of the four principal lattice directions.  All particles are
identical, and when two particles collide head-on, they come out at right
angles to their original motion---in all other cases, particles move straight.

To implement this lattice gas as a cellular automaton, we must formulate it as
a rule that applies to cells.  This can be done as follows:

Cells are arranged in a rectangular mesh, with nearest neighbor interactions.
Each cell contains 4-bits of state information---one bit for each of the four
possible particle directions.  For each of these bits, a \one\ indicates the
presence in that cell of a particle moving in the corresponding direction, a
\zero\ indicates the absence---thus each cell can contain up to four
particles.  Updating is a two stage process: first we move each particle one
position in the appropriate direction, and then we update the contents of each
cell.  These two stages are repeated alternately in order to produce a
dynamical evolution corresponding to our stylized physical model.

The movement of data can be visualized as four bit-planes, each of which is
shifted as a unit.  All of the bits corresponding to particles
moving right would constitute one of the bit-planes: by shifting this sheet of
data bits one position to the right, we would cause all appropriate particles
to move one position right.  The other three kinds of bits are treated
similarly.

The updating of cells is a process that involves looking at the contents of a
given cell, and changing it according to our rule.  If we have both a right-moving
and a left-moving particle in a given cell, and no other particles, then this
is a head-on collision.  In this case, the new contents of the cell should be
particles moving in the other two directions, and no other particles.  All
cases in which there is no head-on collision should leave the cell contents
unchanged, so that particles moving in a given direction continue to move in
that direction.

%

\figw{fig.sound}{2.5in}{A sound wave in the HPP lattice gas.  In (a) we
have a random distribution of particles on a 256\by256 lattice, with a
clump of a few thousand particles in the center.  In (b) and (c) we see
snapshots of its subsequent evolution, at about 30 and 90 steps
respectively.}

In Figure~\ref{fig.sound} (taken from reference \cite{super}) we
illustrate the propagation of a ``sound'' wave in this lattice
gas---note that despite the discrete velocities of the individual
particles, the sound wave is circular.  Slightly more complicated
lattice gas models such as the FHP model\cite{fhp,fhp2} (which involves
six particle directions, rather than four) and related
models\cite{santa-fe} can be used for realistic simulations of fluid
flows\cite{santa-fe,kadanoff,super,doolen,yakhot}.

The HPP lattice gas model will be a good example to keep in mind in
Section~\ref{arch} where we describe the architecture of \cam-8, as this
is the sort of model that maps most directly onto the architecture of
this machine.


\subsection{Partitioning cellular automata}

A scheme such as the HPP lattice gas discussed above in which we
partition the bits in our cellular space into disjoint groupings which
are updated separately we call a {\em partitioning} cellular automaton
(PCA).  Such CA are convenient for modeling physics, since each block of
the partition is a little window in which we can specify which scene
follows a given scene (in the lattice gas example, we were able to
easily include particle conservation, momentum conservation and
microscopic reversibility into our model).  PCA are also convenient in
terms of hardware, since each bit of the current state is accessed
exactly once in the process of constructing the new state (makes
efficient use of memory bandwidth to cell state), and each block of the
partition is updated separately from every other block (allowing blocks
to be updated in any order).

Unlike PCA, conventional CA are unconstrained in their use of neighbor
bits.  They are close kin to finite difference equations: the new state
of a given cell is (in general) a function of {\em all} of the bits in
some group of neighboring cells.  This means that each cell-bit is (in
general) used as a neighbor by several other cells during each updating
step, and so unless all cells are updated simultaneously we cannot
simply replace the contents of a given cell with its new value: we must
keep a copy of its old value available for use by neighbors until they
have all been updated.  This extra data buffering, along with increased
memory bandwidth demands needed in order to access each cell bit several
times during each step are disadvantages from a hardware point of view.

Since conventional cellular automata can be efficiently embedded into
PCA (cf.\ Footnote~\ref{moore} and reference \cite{cam8-book}) and since
PCA are both more natural for the sorts of physics-minded models we are
most interested in and much better suited for being turned into
hardware, we made the decision to base \cam-8 on PCA.


\section{CAM-8}\label{arch}

In light of current technological constraints and opportunities, we have
designed a machine which simulates fully parallel CA, and hence inherits
their scalability and natural parallelism.  Our machine, however, has
far fewer processors than cells---each processor is time-shared among a
large number of cells.  This allows us to use more flexible processors
suitable for general purpose experimental work (we actually use large
static-RAM lookup tables as processors in our design) and allows us to
use commercial memories intended for serial machines for storage of
state information.

Our machine continues to be a uniform array of processors, but in our
case each processor handles a million cells.  Our 16-bit cells are
stored in banks of 16 1-megabit DRAMs, and wires interconnecting
processors are time shared just as the processors themselves are, so
that we reduce the number of wires needed for interconnect by a factor
of a million, as compared to a fully parallel approach.  Of course we
also slow the machine down by a similar factor, and so we are
emphasizing size over speed; but by simply having each processor only
handle a portion of its cell memory (leaving the remainder unused) we
can achieve much greater speed in those applications that require speed
rather than size.

\section{Our claims}\label{claims}

What we claim is new in all of this is the scheme we have come up with
for bringing neighbor bits together in a way which allows us to have a
rich variety of neighbor choices while retaining the millionfold saving
in interconnect made possible by time-sharing the processors, and while
also permitting the use of commodity DRAM chips for the cell state
memory.  This scheme involves two ideas: {\em virtual shifts}
(instantaneous data movement within each processing module achieved by
pointer manipulation), and {\em gluing} (zero-overhead inter-module
communication made possible by lockstep processing).  Both of these
techniques only become available to an architecture based on PCA (which
we are the first to recognize as a distinct class of CA) and for this
reason we believe their application to parallel computation to be new.

Unlike traditional CA, PCA permit great freedom in the order in which
cells are updated, and we take advantage of this property in our
architecture for display and analysis purposes.  Again because of the
novelty of PCA, we believe that the schemes we have come up with for
allowing our machines to provide realtime display and analysis of the
simulation being run are also new.

Finally, our machine is made out of modules and can be expanded by
simply adding more modules in order to simulate larger spaces of cells
with no increase in the time required to update every cell of the space
once.  Similarly, smaller machines composed of just a few modules can
run the same simulations as the biggest machines, but only scaled down
to involve fewer cells.  Thus small simulations developed inexpensively
using a few modules can be transferred without change to run on large
machines---this allows the interactivity and ease of program development
of a personal computer to be coupled to the raw computing power of
cellular automata supercomputers.  Since such scalabilility is new, this
property is also new (whether such an idea is patentable I don't know).

\medskip

In addition to these claims based on the design of \cam-8, in
Section~\ref{addit} we discuss some other possible claims that we might
make based on various extensions and variations of \cam-8 ideas.


\subsection{Virtual shifts}

In \cam-8, cell data is processed within each module in a sequential
fashion: all of the data movement (within modules) required by PCA can
be accomplished by controlling the order of data accessing.  Since
control information can be set up for the next scan of the data array
while the current scan is running, this data movement doesn't slow down
the simulation.

More specifically, in our design each processor is responsible for the
updating of an array consisting of a million 16-bit cells.  The array
handled by a single processor can in principle be organized in any
number of dimensions, just as it could be in an ordinary digital
computer.  In our machine, the cell array is divided up physically into
16 bit-arrays: each bit-array contributes one bit to each cell.

Cell memory is updated as follows: each bit-array is scanned separately,
and the resulting groups of 16 1-bit values are the cell values
presented to the processor for updating; 16-bit results are inserted
back into the cell array.  We control the groupings of bits which get
presented as a unit to the processor by controlling the relative order
of scanning the different bit-slices.

In the cases of greatest interest, the cell array as a whole is scanned
as a two or three dimensional matrix in a fixed order.  If all
bit-slices were scanned in the same order, we would simply present the
individual cells to the processor as isolated 16-bit systems.  Instead,
we consider the contents of each bit-slice to be a spatially organized
object (a {\em sheet} in 2-dimensions, or a {\em block} in 3-dimensions)
and bodily shift this object by controlling our scan.

For example, in two dimensions we have 16 bit-planes which can be imagined as
16 sheets of graph paper lying one on top of another, with each square on the
paper representing a single bit of a cell.  A shift of one of these sheets
with wraparound (i.e., as bits are shifted out one edge, they reappear at the
opposite edge) corresponds to one particular relative order of scanning the
bit slices.  Such shifts only involve a decision about how to scan, rather
than the movement of any actual data, and so we refer to them as {\em virtual
shifts}.

Returning to our HPP lattice gas example of Section~\ref{example}, we
can directly implement this model on \cam-8 by using 4 bit-planes and
virtual shifts of one position.  Similar rules (such as FHP and its
relatives) involving more particle
directions and speeds can be realized by simply using more bit-planes
and other virtual shifts.


\subsection{Gluing}

What remains is the heart of our design: the method used to tie all of the
processing modules in our machine into a single uniform cellular
computation without slowing the individual modules down.

In a machine consisting of many modules, each module will produce a window
onto a chunk of a larger space, with the various bit-slices of this larger
space shifted relative to one another.  Each module will be responsible for
updating its own chunk of this space: the cells of the chunk are presented---
one at a time---to the processor, and the result is inserted into the
cell-state memory belonging to that module.

Thus it is really only the cells that need to be ``glued'' together into a
uniform space in such a way that each module sees a section of this
space---the updating is then straightforward.

If data is to shift between modules, clearly they must be physically
interconnected: in our design, modules are connected together to form a
uniform three dimensional array.  Each module is connected to each of
its six nearest neighboring modules (in three dimensions) by 16
wires---enough to make one cell of each of the neighboring modules
visible to the given module.  Now in order to show a window into a
shifted (and glued) bit-slice, each module simply gets data from
adjacent modules as needed.

%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.}

This gluing technique is illustrated in Fig.~\ref{fig.glue} using a one
dimensional analogue.  In (1) we show a 16-cell space, with each cell
containing a letter of the alphabet.  The cells are divided up evenly
among four modules, and we wish to shift all of the data 3 positions to
the left, with wraparound.  In (2) we show each module with its own data
internally shifted 3 positions to the left with wraparound
internally---the three letters that should have shifted out of the left
hand side of each module have been reinjected into the right hand side.
Note that each letter has moved the correct amount for the desired
shift; the shaded letters are simply in the wrong modules.  Now in (3)
we make use of the wires interconnecting the modules.  As each module
scans its data, presenting items one at a time for processing, each
module simply borrows the data from the module to its right at the
appropriate moment by substituting cell values scanned by the
neighboring module for internally scanned values---the arrows indicate
the direction of data movement.  Note that because of the cyclic
shifting within each module, data that one module needs to borrow is
made visible by the neighboring module at exactly the moment in the scan
when the data is needed---thus there is no slowdown or buffering
overhead involved in coordinating the communications activities of the
various modules needed for gluing.

In an exactly analogous manner, \cam-8 modules are glued together one
dimension at a time by a combination of internal shifts with wraparound and
data source multiplexing.  The internal shifts are achieved exactly as
described in the previous section, and there are three hardware levels of data
multiplexing: we first multiplex one dimensional chains of modules into
homogeneous strips, then multiplex strips into sheets, and finally we
multiplex sheets of modules into a uniform three dimensional space.  

In \cam-8, each module will have $2^{20}$ cells---using nearest neighbor
connections, this means that the neighborhood of a given cell in three
dimensions consists of 8 million cells surrounding it.  That is, any bit
within a volume of 8 million cells surrounding a given cell can be
shifted into the given cell, to be used together with other shifted bits
as the new cell value to be updated.  Since bit-slices are shifted as a
unit, all cells will see the same neighborhood: if one cell gets a bit
from 50 positions to the right, all cells do.  Similarly, if we arrange
the modules in a two dimensional configuration (so that only two levels
of glue multiplexing are used) then the neighborhood consists of an area
containing 4 million cells.

Note that in both two and three dimensions, even with only nearest
neighboring modules connected, some data from next-nearest neighbors
will become available to a given module by virtue of the several levels
of multiplexing.  In addition to this, we plan to also provide
connections between second-neighbors along all six principal lattice
directions.  This is primarily intended to allow the space to be divided
up into up to eight independent sublattices, which will then be able to
intercommunicate in order to perform error monitoring or multistep
updating with double buffering.  When not used for these purposes, these
connections will allow the range of gluing to be extended, giving even
larger neighborhoods.

Note also that arrays of various shapes and sizes can be achieved by
simultaneously controlling the scanning within each module and the
multiplexing between modules: shifting of cell data in more than three
dimensions can be achieved by simply controlling the scanning of cells
within individual modules.  The second-neighbor connections will
actually allow hardware gluing to be extended to up to six dimensions,
although three of these dimensions will only be two modules deep.


\section{Hardware details}

\Cam-8 will consist of a number of {\em space modules}, each handling
the simulation of a chunk of cellular space.  In our initial machine, we
plan to have each space module contain one million 16-bit cells, along
with a 64K\by16 lookup table used for updating, and various counters and
registers used for data analysis and error detection/correction (see
Figure~\ref{fig.module}).  Direct access to each module's scan is
permitted by the flywheel inputs and outputs, which are provided to
allow external hardware to be attached to various points in our
simulated space (see Section~\ref{flywheel}).  The I/O bus is used for
communication with a host computer that is responsible for initializing
cell and table data, determining the size and shape of the cell space,
and supervising shifting, display, analysis, and error handling.

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

\figw{fig.module}{4.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.}

Space modules are interconnected to have the topology of a three
dimensional array of processors, each communicating with its nearest
neighbor in each of six directions (see Fig.~\ref{fig.connect}).  Note
that the host bus actually consists of several buses, each of which
connects a fraction of the modules to the host; the flywheel bus
permits direct access to the time-multiplexed cell values scanned
separately by the different modules.

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

\figw{fig.connect}{3.9in}{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.}

The cell-data portion of each space module, along with some control and
analysis circuitry (i.e., everything but the lookup table) constitutes a
{\em cell module}.  Each cell module consists, in turn, of 16
bit-modules, each of which handles a bit-slice of the cell data
consisting of one bit from each of the million cells.  A bit-module
consists of only two chips: a 256K\by4 DRAM, and a semicustom controller
chip.  Thus a cell module consists of 32 chips, and when we add a
64K\by16 SRAM module, we have a complete space module.


\subsection{The controller chip}

Except for the controller chips, this design consists entirely of standard commodity
RAM chips: DRAM chips for cell-state storage, and SRAM chips for lookup-table
processors.  For a machine operating with a 40ns clock, we would use SRAMs with
somewhat faster than 40ns access, and DRAMs with a static-column mode
read/modify/write cycle of somewhat less than 160ns (since we are using nybble-wide
memories, our bit bandwidth to the DRAMs is multiplied by four).

The main function of each controller chip is to provide a sequence of
addresses to its associated DRAM chip, in order to coordinate the
relative order of scan of the 16 bit-modules.  In addition, these chips
handle a number of other important roles.  First, they are involved in
the data I/O of the DRAMs during updating: this involves changing
nybbles into a serial bitstream as the DRAMs are scanned, and grouping
bits into nybbles in preparation for storing the updated cell bits back
into the DRAM memories.  To save address setup time on the DRAMs, the
new data is stored back into the address that has just been read from,
using a read/modify/write cycle.  Because of unavoidable
serializing/unserializing delays, as well as the time actually taken for
the table lookup, the data written in a given nybble after updating will
correspond to different cells than the nybble's previous contents.  This
extra shift is simply compensated for, however, by an adjustment to the
virtual shift applied to each bit slice.  By picking one of the longest
dimensions of our space to be the first scanned along, and associating
it with a portion of a single memory row, we can make effective use of
static column mode in our DRAMs.  Note that the use of nybble-wide
memory in order to increase memory I/O bandwidth also makes it necessary
to use up to three bits of extra pipelining in order to allow arbitrary
shifts along this first dimension.  Of course the controller chip must
combine its own internally shifted data with data available from its
neighbors in order to produce a `glued' window into a uniform cellular
space, as discussed earlier.

In addition to this data scanning/buffering/gluing function, each controller is
responsible for selecting what signal goes to one address bit of a lookup table, and
what is done with one bit that the table returns.  For example, the glued data
constructed by a given controller could be looped back and stored in memory, turning a
virtual shift into actual data movement without any use being made of the bit returned
by the lookup table.  In such a case, that bit of the lookup table might be programmed
to provide some information useful for data analysis: the number of ones in the
resultant serial bitstream could be accumulated on the controller chip.  Even the bit
sent by the controller to the table need not be the cell data: for example, a constant
of \one\ or \zero\ could be substituted, chosen separately for each updating step in
order to select one or another of two possible subtables.

All such choices, as well as control of scanning order, dimensionality, gluing, and
many other details are supervised via a bussed connection to a conventional von
Neumann architecture computer used as a control-host.  By talking over this bus to
controller chips, the host configures the system, initializes cells and tables, shifts
bit-slices between updating steps, and reads various counters in order to analyze cell
data and detect errors.


\subsection{The flywheel bus}\label{flywheel}

In addition to the host bus, there is a second kind of ``bus'' supported
by this architecture.  As is shown in Fig.~\ref{fig.module}, the
connections to the lookup table processor may be broken, and the glued
output may be made directly available to external circuitry, while the
cell-bit input may be taken from an external source.  Since the entire
window into the cell space produced by a given bit-module is visible in
a time-multiplexed way at the glued output as the cell data is scanned,
you can picture the data as sitting on a data {\em flywheel} which turns
around and around.  Since all bits in a bit-module share this single
output line, we refer to it as a bit of the flywheel output; in a 1024
processor machine, this bus is 16K bits wide.  Similarly, we have 16K
flywheel input lines which can be used to input to any and all cell bits
active during a given step.  Whether flywheel inputs or outputs are used
is of course determined by the controller.

No enormous connector is brought out of this machine containing these 32K lines: this
bus is distributed throughout the machine as positions at which external circuitry can
attach.  In particular, display data is taken directly off this bus.  Special purpose
measurement and analysis equipment can be attached at certain positions in our array
of processors, just as specialized equipment is positioned to capture data in a
scientific experiment.  Similarly, external equipment can control
localized input processes (such as smoke particle sources in a wind tunnel
simulation).


\subsection{Doubling the connections}\label{doubling}

In addition to the physical interconnections described earlier which
involve a single bidirectional wire linking each bit-module to the {\em
closest} neighboring bit-module in each of six directions, our design
includes a second wire linking each bit-module to its {\em second nearest}
neighbor in each of these same six directions.

There are a number of reasons for providing these additional
interconnections.  One reason is that this permits the space to be divided
up into halves, quarters or eighths: by substituting second nearest
neighbor interconnections for the nearest ones along one dimension, we
split the machine into two halves, and further splitting can then be done
along the other two dimensions.

The most important reason for splitting the space in half has to do with
error detection and correction (see Section~\ref{error}).  For large
assemblages of \cam-8 machines, it will often be useful to split the space
in half and have both halves doing the same computation while continuously
checking one against the other.  Notice that when we use the second
neighbor connections along some direction to split the space, the nearest
neighbor wires along this direction become available for passing the
monitoring information between the two halves.

Another reason to split the space is to allow a given cell bit to be used
simultaneously by two modules, something that is not supported by the
nearest neighbor shifting mechanism.  Again, the nearest neighbor wires
connect the two halves: in this case, they carry the duplicate
information.  Such duplication is useful, for example, when one half of
the machine is used to analyze what is happening in the other half while
it is running, or when we do a multistep updating that requires double
buffering.\footnote
     {For example, to simulate a 3\by3 2-dimensional neighborhood with one
bit per cell, we could run \cam\ as two 32K\by16K arrays of cells, and
treat the 16 bits in each cell as a 4\by4 region of a bit-plane.  Half the
machine holds the ``old'' data while we construct the ``new'' data in the
other half using several steps by shifting around the 4\by4 window and
updating the four center elements after each shift.  This allows us to run
a space of 8 billion 1-bit cells.\label{moore}}
     Splitting \cam-8 is also useful in implementing rules that need more
than 16 bits of input.  Corresponding cells in the two halves are strongly
coupled: a bit from either cell may be used by both.  By using some cell
bits within each coupled pair of cells to store intermediate values, rules
that involve more than 16 bits of neighborhood can be synthesized as a
composition of completely arbitrary 16-input/16-output logical functions.

One additional benefit of these interconnections is that the width of the
neighborhood along each direction which we {\em don't} split will be
doubled.  This is particularly helpful in the 1K\by1K\by1K 3-dimensional
mode, where doubling the neighborhood along the single short dimension will
allow us to have a uniform neighborhood involving about 16 million cells
(257\by257\by257).

Finally, if we call a 2\by2\by2 block of space modules a {\em super
module}, and build \cam-8 out of such super modules which are never split
between different circuit boards, then we can replace all of the
(single-wire) nearest neighbor interconnections within each super module
with pairs of wires without increasing the number of wires going between
boards.  This would give us all of the connectivity needed to treat each
splitting of the machine as the creation of depth in an extra dimension:
we would actually be able to provide hardware gluing in 6 dimensions
(although three of the dimensions would only be two modules deep).  This
more general interconnection between halves of the machine would also
provide additional flexibility in applications that rely on strong
coupling between corresponding cells.

\subsection{Data analysis}\label{analysis}

Each bit-module contains a number of counters that are used for
real-time data analysis, error detection/correction, or both.

Table outputs are always counted (number of ones in each output).  A
step with simultaneous analysis can be performed by having some
bit-arrays remain unchanged (or just shift) while the corresponding
table outputs are being counted.  For example, if a bit-array is being
used to store a spatial parameter (such as an obstacle in a fluid-flow
experiment) the associated table output is not needed for updating, and
may be programmed for data analysis and counted.  If there aren't enough
such ``free'' tables, or if the analysis requires a different
neighborhood than the updating, separate analysis steps may be
interleaved between updating steps by rewriting tables.

The table output counters can be used to perform local averaging by
appropriately controlling the scan.  For example, a large 3-dimensional
array can be updated as a collection of small cubes, with table counts read
immediately after each cube is updated (these cubes can be much smaller
than the region serviced by each cell module).

\smallskip

When \cam-8 is operated as two half-machines, table outputs can be
continuously compared between corresponding parts of the two halves
and the number of differences counted by the {\sl table
correlation counters}.  Space and time autocorrelations can be
accumulated by running two versions of the same system
simultaneously, with a constant space or time shift between them.

Note that all counters are double-buffered, and can be read at any
time by the host without affecting a step that is in progress.


\subsection{Error handling}\label{error}

Like \cam-6, each \cam-8 machine will constitute a ``building block''
from which one can build much larger machines.  For example, forty
such blocks used together will have 40 billion cells and will perform
one trillion cell updates every second.  While there are no inherent
architectural limits on how many \cam-8's can be hooked together,
there is a practical problem which grows as more and more \cam\
``blocks'' are added, namely, error handling.  Because of the
built-in analysis capabilities described in the previous section, and
additional hardware consistency checks, it will be possible to
discover and recover from hardware errors.

Since tables are not supposed to evolve in time, it is relatively
straightforward to test whether or not a table contains an error.  We
can usually detect table errors by performing an analysis step during
which all tables are addressed by counter bits---we simply count the
number of ones in all table outputs.  As long as correlated pairs of
tables contain the same rule we can simultaneously perform a more
detailed check by comparing table outputs.  Alternatively, we can
have the host perform a verify-write of all tables, in which the old
contents is read and compared with what the host is writing.  

Cell-memory is tested by each bit-module during every step.
``Checksum'' bits reflecting the number of ones last written and their
positions are compared to corresponding checksums performed on the data
subsequently read.  Changing any bit of the configuration will, on the
average, change about half of the checksum bits, making the chance of an
undetected array-memory error very small.

Hard errors, caused by bad components, can be tested for whenever any
error is detected.  If we run an occasional analysis step during
which we test tables, bad chips should always be noticed quickly.

Soft errors, in which memory bits are typically changed, are principally
caused by alpha particles.  Modern commercial memory chips, which
constitute most of \cam-8, are inherently quite reliable: even with
absolutely no provision for error correction it should be possible to
run this machine with 32768 memory chips for several days at a time
without any errors.  Thus for a single \cam-8 it may be perfectly
practical in most cases to simply detect errors, and rerun an experiment
if any occur.

For longer runs, or for large machines built out of many \cam-8's, if
we want to guarantee exactly correct operation it is probably most
practical to use each machine as two correlated half-machines, both
running the same experiment.  Since the chance of two different
bit-modules both experiencing a soft error during the same step is
extraordinarily small (expected perhaps once in $10^{16}$ steps for a
single \cam-8 machine) we can assume that one out of every correlated
pair of bit-modules will always be correct.  Bits that were
updated incorrectly are fixed by using data from the correct twin,
and incorrect tables are simply rewritten.

Given a disagreement between correlated modules, there remains the
problem of deciding which of the pair is incorrect.  We make use of one
further facility provided by the hardware in order to quickly and
reliably find the error: whenever table comparisons disagree,
both the original contents of the cell where the error occurred and the
updated value are latched by the controller chips.  By examining this
information, the host can tell which of the modules was updated
incorrectly.


\subsection{Display}

Being able to display the state of our system in real time provides
important feedback as to whether or not everything is working as
expected, and what parts of the system are doing something interesting
that should be investigated more closely.  This is particularly
important in highly interactive work with fractional machines consisting
of just a few modules.

\medskip

Two dimensional display is not much of a problem for \cam-8, since
this machine can provide its data in the correct format for a color
monitor.  This machine can even, if desired, scan its data in the
correct format for an interlaced display---since each cell is updated
independently of all others the rows can be scanned in whatever order
you choose.

For a complete 64K\by16K display,\footnote
     {In order to realize a 64K\by16K space without adding extra
interconnections, we unfold \cam-8's basic 8\by8\by16 array of space
modules into a 64\by16 sheet by appropriately programming the use of the
existing interconnect wires.}
     we could cover an enormous wall with 1024 color monitors (more if
several \cam's are connected), each of which would show a 1024\by1024 patch
(using a four-fold interlaced scan on a 15kHz monitor).  Of course it would
be more practical to use only one monitor (or just a few), and shift the
data to move the window around.

Since all of the neighbors that would be used for a cell-update are
available simultaneously, it is a simple matter to display a function
of the neighborhood, rather than the neighborhood itself.  For
example, in a fluid-mechanics experiment you might want to show only
the smoke particles that trace the flow.

Another display technique would be to let the host computer use the
average data accumulated by counters (see Section~\ref{analysis}) in order
to produce a display on its own screen.

\medskip

In more dimensions, how to display the cell data is less obvious.  One
method that allows \cam-8 to {\em always} produce some sort of a display
is to map the million cell array serviced by each space module into a
1024\by1024 square in the most natural manner you can think of, and then
display this square array.  For example, a 128\by128\by64 configuration
could be arranged as an 8\by8 ``sheet'' of 128\by128 ``postage stamps.''
If we now scan the data in this flattened format (which just involves a
particular choice of the order in which cells are updated), then it can be
displayed on a 15kHz monitor, exactly as the 1024\by1024 configuration
that we discussed above for 2-dimensional displays.  If not all cells are
being updated, then we can map the cell array into a pattern that fits
{\em within} a 1024\by1024 array, and display the unused areas as black
areas on the monitor.\footnote
     {When we aren't locked to the framing format of a monitor, we
don't waste time on these unused areas, and the number of complete
updating steps per second therefore rises when we process smaller areas.}
     If 256K cells or less are being processed, we can get a better display
by mapping the cell array into a 512\by512 matrix, and displaying this
matrix on a 30kHz non-interlaced monitor as we scan it.

In any case, a single display can be used as a window to see any part of
the system by shifting the data appropriately (in however many dimensions).

\medskip

Finally, suppose we are displaying a large region of a 1K\by1K\by1K space
using a method such as the one described above that involves showing
slices through a section of the space, and suppose that we would like to
see a view of the cube rotated by 90 degrees about its $x$, $y$, or $z$
axis.  This is easily accomplished by \cam\ by actually rotating all of
the cell data using a simple split-and-shift algorithm.\footnote
        {This can be considered a special case of the problem of rotating
a 2-dimensional square image, where the number of bits in each pixel is
very large.  To rotate such a square image 90 degrees clockwise, you can
first split it into quarters, then shift the four quarters horizontally or
vertically until they have each been shifted to a position 90 degrees
clockwise of where they started.  Each quarter is similarly rotated, and
then each eighth, etc., until you reach the level of a single pixel.
Pixels don't look any different when rotated, so you're
done.\label{rotate}}
        Because of the instant shifts, such rotations can be accomplished
in a fraction of a second.


\section{Additional claims}\label{addit}

In addition to the claims of Section~\ref{claims}, there are a number of obvious
extensions and variations on the \cam-8 architecture which may themselves be
worthwhile to claim.

\subsection{More highly parallel versions}

While our discussion thus far has been oriented specifically towards an
implementation in terms of conventional memory chips, by abandoning this approach
and by sacrificing some flexibility, we can achieve much greater performance.

A 1024-module \cam-8 machine running with a 40ns clock would be able to perform 25
billion cell updates per second on a space of up to a billion 16-bit cells.

If we were to limit ourselves to rather simple processors, able to
simulate only a small variety of rules (e.g., a small set of lattice gas
rules), then we could put a large number on a single chip.  If we put
1024 processors on our chip, each servicing 64 8-bit cells using the
scanning/shifting/gluing techniques discussed above and running with a
5ns clock, then each chip would perform 200 {\em billion} cell updates
per second.  Clearly a variety of architectures intermediate between this
and \cam-8 are possible, depending upon the neighborhood required and
the dimensionality that we wish to simulate.  For practical
technological reasons, the physical interconnection between chips, at
least at present, would be limited to connecting the edges of
two-dimensional arrays of a few thousand processors (a few hundred
pins).  Additional dimensions would have to be internal ones, achieved
by the way in which individual processors scan the cell memory that they
are responsible for.


\subsection{More highly pipelined versions}

\Cam-8 makes provision for attaching external circuitry to the cell-modules, to
replace the lookup tables---in this case, additional stages to the data
serializing/deserializing pipelines may be added, to allow the computation delay for
such circuitry to be several bit-times longer than a lookup table (though such circuitry
must finish a computation each bit time, this may have been a multistage pipelined
computation).  There is no reason in principal why very long pipelines, involving
perhaps hundreds or thousands of stages, couldn't be used, since the computation
performed by each module is completely sequential, and the data access is perfectly
predictable.

\subsection{Other kinds of processors}

Our decision to use 16-bit cells in \cam-8 was arrived at by determining that a 16-bit
address was about the most we could handle by fast table lookup.  If we abandon table
lookup and use other kinds of processors, cells could in some cases be much larger.
For example, each cell might contains several 80 bit floating point numbers, and these
numbers could be virtually shifted just as we handle the bit-slices in \cam-8 (since
all bits in each number would shift together, we have a lot of flexibility in deciding
how (or even whether) to divide the bits up between memory chips.  Pipelining,
discussed above, would allow us to use commercial floating point chips to do the
desired calculations.

Similarly, various compositions of moderately sized lookup tables, appropriately
pipelined, could be used to handle the updating of large cells in many cases of
interest.


\section{What has appeared where}

\Cam-8 is really the latest in a line of cellular automata machines
(\cam{}s) that have been developed within our group at MIT.  Before
discussing what has appeared in print concerning \cam-8, we will briefly
cover the history of our machines, since some of what has appeared about
them could have a bearing on what is still patentable in \cam-8.

\subsection{Earlier machines}

The first of our \cam\ machines discussed in print is \cam-5 (see
\cite{cam5}) which scans a two dimensional space and runs traditional
2-dimensional CAs while displaying its results in real time (it
maintains a three line data buffer as it scans, in order to make a 3\by3
window of cell values available at a time).  This machine is somewhat
related to image processing machines of the sort discussed in references
\cite{preston,sternberg}, but is geared towards more general operations
(it does computations by table lookup) and has a real-time display of
the ongoing simulation, plus some provisions for data analysis using
counters to count a function of the cell data as it is sequentially
updated.\footnote
  {The {\sc rap1} (see \cite{rap1}) is a machine closely related to
\cam-5 that was built by some French
investigators in connection with lattice gas simulations---it has no
provision for gluing, and is restricted to a very small neighborhood.}
  \Cam-6 (see \cite{califano,porter,cambook}) is a commercial version of
this machine (commissioned by us to be produced under license by Systems
Concepts in San Francisco) allowing some flexibility of neighborhood
choice under software control, with bits selected from cells in a 3\by3
buffered window (and some other non-cell signals).  \Cam-6 also has some
provision for modularly expanding the space by connecting several
machines together, but it uses pipeline multiplexing to achieve a larger
uniform space, rather than the gluing technique discussed here.  \Cam-7
(see \cite{cam7}) was a proposed machine which was basically a greatly
scaled up \cam-6, consisting of many \cam-6-like modules.

A few groups have built special purpose hardware for simulating specific
CA models of physics (see, for example,
\cite{hoogland,kugelmass,pearson}), but these are very specialized, and
do not have any generality of neighborhood nor any provision for modular
expansion.


\subsection{References to CAM-8}

We have written a book\cite{cambook} about \cam-6 (appeared April 1987)
in which a 3-line footnote hinted at the neighbor-gathering technique
used by \cam-8 (but only in two dimensions).  This footnote mentions
that it involves shifting by changing scanning order, and nothing
else.\footnote
   {The machine mentioned in the footnote was called \cam-7, but
reflected later ideas than those discussed in \cite{cam7}---ideas that
eventually appeared in \cite{cams} (still with the name \cam-7).  In
\cite{cam8-book}, the name was changed to \cam-8.}

This is our earliest reference to any of the ideas claimed here.  The
next reference\cite{cams} appears in the August 1987 issue of {\sl
Complex Systems}, which wasn't actually published until January 1988.
This article contains everything discussed here except for the
generalization of the gluing to three dimensions, and the doubling of
the interconnections discussed in Section~\ref{doubling}.

A revised version of this article\cite{cam8-book}, giving our present
understanding of the \cam-8 architecture (though without explicitly
discussing more highly parallel or more highly pipelined versions) will
appear sometime in the next few months in a book entitled {\sl Large
Non-linear Systems,} edited by Gary Doolen.  Tom Toffoli has already
given away copies of this paper.


\newpage

\begin{thebibliography}{99}
        \bibitem{burks} {\sc Burks}, Arthur (ed.), {\sl Essays on Cellular Automata},
Univ.\ Illinois Press (1970).
        \bibitem{califano} {\sc Califano}, Andrea, Norman {\sc Margolus}, and
Tommaso {\sc Toffoli}, {\sl CAM-6 User's Guide}, Systems Concepts, San Francisco (1987).
        \bibitem{rap1} {\sc Clouqueur}, Andr\'e, and Dominique {\sc d'Humi\`eres},
``RAP1, A cellular automaton machine for fluid dynamics,'' {\sl Complex Systems \bf 1}:4 (1987), 585--597.
        \bibitem{creutz} {\sc Creutz}, Michael, ``Deterministic Ising
Dynamics,'' {\sl Annals of Physics} {\bf 167} (1986), 62--76.
        \bibitem{santa-fe}{\sc Doolen}, Gary (ed.), ``Workshop on Large Nonlinear Systems,''
collected in {\sl Complex Systems \bf1}:4--5 (August--October 1987).
        \bibitem{los-alamos} {\sc Farmer}, Doyne, Tommaso Toffoli, and Stephen {\sc Wolfram} (eds.),
{\sl Cellular Automata}, North-Holland (1984).
        \bibitem{fhp} {\sc Frisch}, Uriel, Brosl {\sc Hasslacher}, and Yves
{\sc Pomeau}, ``Lattice-Gas Automata for the Navier-Stokes Equation,''
{\sl Phys.\ Rev.\ Lett.} {\bf 56} (1986), 1505--1508.
        \bibitem{fhp2} {\sc Frisch}, Uriel, et al., ``Lattice gas hydrodynamics in two and three
dimensions,'' {\sl Complex Systems \bf 1}:4 (1987), 633-707.
        \bibitem{hpp} {\sc Hardy}, J., O. {\sc de Pazzis}, and Yves {\sc
Pomeau}, ``Molecular dynamics of a classical lattice gas: Transport
properties and time correlation functions,'' {\sl Phys.\ Rev.} 
{\bf A13} (1976), 1949--1960.
        \bibitem{herrmann} {\sc Herrmann}, Hans, ``Fast algorithm for the
simulation of Ising models,'' Saclay preprint no.\ 86-060 (1986).
        \bibitem{hoogland} {\sc Hoogland}, A., J.\ {\sc Spaa}, B.\ {\sc
Selman}, and A.\ {\sc Compagner}, ``A special-purpose processor for the
Monte Carlo simulation of Ising spin systems,'' {\sl J.\ Comp.\ Phys.}
{\bf51} (1983), 250--260.
        \bibitem{kadanoff} {\sc Kadanoff}, Leo, ``On two levels,''
{\sl Physics Today \bf 39}:9 (September 1986), 7--9.
        \bibitem{kittler} {\sc Kittler}, J., and M.\ J.\ B.\ {\sc Duff},
(eds.), {\sl Image Processing System Architectures}, Research Studies
Press, Ltd., John Wiley and Sons, Inc. (1985).
        \bibitem{kugelmass} {\sc Kugelmass}, S.\ D., R.\ {\sc Squier},
and K.\ {\sc Steiglitz}, ``Performance of VLSI Engines for Lattice
Computations,'' {\sl J.\ Complex Sys.}, {\bf 1}:5 (October 1987)
939--965.
        \bibitem{phys-like} {\sc Margolus}, Norman ``Physics-like models of
computation,'' {\sl Physica} {\bf 10D} (1984), 81--95.
        \bibitem{margolus-thesis} {\sc Margolus}, Norman, ``Physics and Computation,''
Tech.\ Rep.\ no.\ MIT/LCS/TR-415, MIT Laboratory for Computer Science (1988).
        \bibitem{super} {\sc Margolus}, Norman, Tommaso {\sc Toffoli}, and
G\'erard {\sc Vichniac}, ``Cellular-Automata Supercomputers for
Fluid Dynamics Modeling,'' {\sl Phys.\ Rev.\ Lett.} {\bf 56} (1986),
1694--1696.
        \bibitem{cams} {\sc Margolus}, Norman, Tommaso {\sc Toffoli}, ``Cellular Automata
Machines,'' {\sl Complex Systems \bf 1}, 967--993 (1987).
        \bibitem{cam8-book} {\sc Margolus}, Norman, Tommaso {\sc Toffoli},
``Cellular Automata Machines,'' revised version of preceding reference, to
appear in {\sl Large Nonlinear Systems}, Gary {\sc Doolen} ed.  (1988).
        \bibitem{pearson} {\sc Pearson}, R.\ B., J.\ L.\ {\sc
Richardson}, and D.\ {\sc Toussaint}, ``A fast processor for Monte-Carlo
simulation,'' {\sl J.\ Comp.\ Phys.} {\bf51} (1983), 241--249.
        \bibitem{porter} {\sc Porter}, Kenneth, {\sl CAM-6 Hardware Manual}, Systems Concepts,
San Francisco (1987).
        \bibitem{preston} {\sc Preston}, Kendall, and Michael J.\ B.\
{\sc Duff}, {\sl Modern Cellular Automata: Theory and Applications},
Plenum Press (1984).
        \bibitem{doolen} {\sc Shimomura}, T., G. {\sc Doolen}, B. {\sc Hasslacher}, and
Castor {\sc Fu}, ``Calculations Using Lattice Gas Techniques,'' {\sl Los Alamos Science},
special issue no.\ 15 (1987), 201.
        \bibitem{sternberg} {\sc Sternberg}, S.\ R., ``Pipeline
architectures for image processing,'' in {\sl Multicomputers and Image
Processing, Algorithms and Programs}, L.\ {\sc Uhr} ed., Academic Press
(1982).
        \bibitem{cam5} {\sc Toffoli}, Tommaso, ``CAM: A high-performance
cellular-automaton machine,'' {\sl Physica} {\bf 10D} (1984),
195--204.
        \bibitem{pde} {\sc Toffoli}, Tommaso, ``Cellular automata as an
alternative to (rather than an approximation of) differential equations
in modeling physics,'' {\sl Physica} {\bf 10D} (1984), 117--127.
        \bibitem{toffoli-emulators} {\sc Toffoli}, Tommaso, ``Cellular
automata as physics emulators,'' to appear in proceedings of {\sl Impact
of Digital Microelectronics and Microprocessors on Particle Physics},
a conference at the {\sc International Center for Theoretical Physics},
Trieste, Italy, 28--30 March 1988.
        \bibitem{toffoli-lorentz} {\sc Toffoli}, Tommaso, ``Lorentz invariance of
computations,'' in preparation.
        \bibitem{cam7} {\sc Toffoli}, Tommaso, and Norman {\sc Margolus}, ``The CAM-7
multiprocessor: A cellular automata machine,'' Tech.\ Memo MIT/LCS/TM-289,
MIT Laboratory for Computer Science (1985).
        \bibitem{cambook} {\sc Toffoli}, Tommaso, and Norman {\sc Margolus},
{\sl Cellular Automata Machines---a new environment for modeling},
MIT Press (1987).
        \bibitem{vichniac} {\sc Vichniac}, G\'erard, ``Simulating physics
with cellular automata,'' {\sl Physica} {\bf 10D} (1984), 96--115.
        \bibitem{wolfram-stat} {\sc Wolfram}, Stephen, ``Statistical mechanics of
cellular automata,'' {\sl Rev.\ Mod.\ Phys.\ \bf 55} (1983), 601--644.
        \bibitem{wolfram-book} {\sc Wolfram}, Stephen (ed.), {\sl Theory and
Applications of Cellular Automata}, World Scientific (1986).
        \bibitem{yakhot} {\sc Yakhot}, V., and S. {\sc Orszag}, ``Reynolds numbers scaling
of cellular-automaton hydrodynamics, {\sl Phys.\ Rev.\ Lett. \bf 56}
(1986), 1691--1693.
        \end{thebibliography}


\end{document}

