\chapter{Introduction}

     Cellular automata are a special class of discrete dynamic systems.  A
cellular automaton consists of a universe of cells laid out in a regular
pattern.  Each cell in the grid is characterized by a certain state which
changes in time.  The evolution of a cell's state is determined by its
current state and the states of its neighbors.  A cellular automata rule
specifies exactly how the new state is derived from the old one.

     Much of the research on cellular automata has focussed on the development
of the rules that are iteratively applied to the cellular automata universe
of cells.  It turns out that when the system is run with carefully chosen
rules, its evolution (as determined by the changing states of its cells) can
accurately model a large class of physical phenomena.  For
example, diffusion, crystallization, gas models, reflection and refraction of
waves, as well as numerous other processes have been investigated through
cellular automata models.
    
     Conventional general-purpose computers are not suited to the requirements
of cellular automata simulations.  To be effective, many cellular automata
experiments call for the execution of billions or trillions of cell-updating 
operations.
At best, sequential computers can perform an updating operation in a few
microseconds.  Hence they would take several days to complete a single cellular
automata run!

     The limitations of conventional computers and the nature of the
cellular automata process call for the development of specialized computer
hardware to perform cellular automata simulations.  Two characteristics of 
cellular automata are particularly useful in directing hardware development
---
locality and parallelism.   Cell updates in cellular automata depend only on
the states of a cell and its neighbors.  Furthermore, at each temporal 
iteration, all cells in the cellular automata universe are updated in
parallel.  This suggests that cellular automata machines (CAMs) should consist
of arrays of parallel processors operating in a SIMD-like\footnote{SIMD is 
short for Single Instruction Multiple Data computer.} fashion.  This has
indeed been the general architecture of the CAMs that have been developed
to date.

     The Information Mechanics group at the MIT Laboratory for Computer
Science has pioneered the development of cellular automata machines.  After
much experimentation, this group successfully developed and marketed a 
general-purpose cellular automata machine (CAM-6).

     CAM-6 allowed for the simulation of a ``toroidal space''\footnote{Toroidal
space means that the cells on the left and right edges of the space are 
considered to be neighbors, as are the cells on the top and bottom edges.}
consisting of 256x256 cells.  Each cell was assigned 4 bits of state.  
The processors used to apply the temporal
rule consisted of suitably programmed SRAM lookup tables.  A cell update
in CAM-6 involved using a subset of the 36 state bits associated with the
cell and its 8 neighbors as a pointer to the SRAM lookup table.  The value
contained at that table location was taken as the new state of the cell.
Cellular automata rules could be programmed into CAM-6 by downloading suitable
data into the lookup tables. 

     The cell states of CAM-6 were mapped as pixels on a CRT screen.  This
allowed graphic visual output from the system --- the operation of the cellular
automata rule could be viewed on a monitor as the iterations progressed.
CAM-6 was implemented on a circuit board with ordinary memory chips and
standard TTL components.  It was plugged into a host IBM-PC from which it
could be programmed and run.  The book {\em Cellular Automata Machines: A New
Environment for Modeling} \cite{b2} describes CAM-6 in more detail and provides many
examples of experiments which have been  performed with its
hardware.

     Encouraged by the success of CAM-6, the Information Mechanics group at
MIT has begun work on the development of a much more powerful cellular
automata machine, CAM-8.  CAM-8 will allow for the updating of billions of 16-bit cells which are arranged in a multidimensional
array.  Thousands of lookup tables will be used, each of which will service
a million cells.  The proposed architecture will provide neighborhoods
spread over a large radius: a cell will see a neighborhood consisting of 
up to 16 bits
chosen from a few million neighboring cells.

     Unlike CAM-6, the new CAM-8 is based on the principle of partitioning
cellular automata --- a procedure whereby cells are divided into blocks and
subjected to block updates.  By changing the block partitions between 
iterations, the effect of conventional cell-based cellular automata can be
achieved.  This leads to a much neater and more flexible hardware realization
than that of CAM-6.  Indeed, the CAM-8 architecture promises to significantly
extend the
size, speed and versatility of cellular automata simulations.

     The CAM-8 project is the source of this Master's thesis.  The
thesis involves the design of an input-output (I/O) system for the CAM-8
machine.  The input-output system connects the CAM-8 hardware to a
host computer and serves as a communication medium over which the host can
control the operation of CAM-8.  In addition, the statistical data gathered
from CAM-8 runs may be transmitted to the host over the I/O interface.
The following section describes the input-output system in greater detail.

\section{The Input-Output System}

\begin{figure*}
\begin{center}
\mbox{\psfig{figure=iosys.ps}}
\end{center}
\caption{The Input-Output System of the CAM-8 Machine.}
\label{iosys}
\end{figure*}

     Figure~\ref{iosys} shows the main elements which compose the CAM-8 input-output
system.  A Sun Sparcstation host sits at one end and is responsible
for controlling the operation of CAM-8 by communicating with the CAM-8 hardware
over the I/O system. 
The host initializes the state of 
the cellular automata universe modelled by CAM-8 and generates and downloads
lookup tables to the processing modules before a simulation.  The lookup table
contents will depend on the particular rule that CAM-8 is to apply to the
cellular automata universe during the experiment. Thereafter, as the 
simulation progresses,
the host may  change control parameters, lookup tables and/or gather statistical
information over the I/O system.

     The modules which make up CAM-8 are located at the other end of the I/O
system.  Each space module consists of 16 CAM-8 controller chips; 16 DRAMS which
store the state of an area of the cellular automata universe; and two SRAMs 
which serve as the lookup table processors through which the cellular 
automata rule
is applied.  

     The host controls
the machine by writing to special registers on the controller chips. 
Statistical data
gathered during a simulation and stored in other chip registers may also be
accessed by the host.  The thesis includes the design of the I/O circuitry
of the controller chips.  Such circuitry provides for
the update of the control registers; the reading of status registers; the
initialization and possible update of the lookup tables; and the initialization
of the cell states.

     The optimum performance of CAM-8 involves operating the machine at near
memory bandwidth.  To facilitate this, a suitably pipelined tree bus is used
to pass control and data information to the space modules.  As illustrated in
Figure~\ref{iosys}, the pipelined bus or PBus links the space modules to an 
interface board which is connected to the host computer.  The root of the
PBus is connected to the interface board and the leaves of the bus are 
tied to the CAM-8 space modules.  Bus nodes are located at the origin
of each branch of the PBus.  The tree-like structure of the bus gives the
I/O system a high degree of fanout to the numerous modules that may
compose a CAM-8 machine.  The pipelined structure, which involves placing 
registers at each bus node, supports the fanout and allows the system to be
run at the required throughput.  The PBus operates at the CAM-8 clocking rate.

     The Sun Sparcstation host computer communicates with the outside world
over the Sun SBus.  As described above, however, the CAM-8 controller chips
communicate with the PBus using the PBus protocol.  Conversion circuitry is
therefore required for data and control transmission from the SBus to the
PBus and vice versa.  This circuitry is implemented in the interface board 
shown in Figure ~\ref{iosys}.  The interface board is more than just a protocol
converter.  It possesses some intelligence which allows it to interpret certain
low level commands from the host.  The interface board therefore reads CAM-8
control programs stored in the host memory, interprets them and generates the
correct PBus signals that are needed to execute these programs on the CAM-8 
hardware.

     The following chapters of this thesis describe the input-output protocols
used in the CAM-8 I/O system as well as the hardware designs of the
major sections described above.  Chapter 2 discusses the typical data transfers
needed to run different types of cellular automata experiments on CAM-8. Chapter 3
describes the design of the pipelined PBus and its associated protocol.

     Chapters 4 and 5 of the thesis present the design and operation of the
input-output section of the CAM-8 controller chip.  Chapter 6 provides an
in-depth discussion of the interface board.  The command format, system
hardware and state machine controllers of the board are described.  Chapter
7 explains the present state of the implementation of the CAM-8 input-output
system, and indicates what future work still needs to be done.


