% -*- Mode:TeX -*- 
\documentstyle[macpsfig]{article}
\input psfig
\input /im/cam8/doc/tech/cam8spec

 \newsavebox{\toy}
\title{Cellular Automaton Algorithm for Real Space Renormalization
Group}
\author{Michael Biafore}
\begin{document}
\maketitle

\begin{abstract}
This is a section of a paper which describes a little more fully the
structure of CAM-8.
\end{abstract}

\catcode`\@=11
%number equations within each section
\def\theequation{\arabic{section}.\arabic{equation}}
\@addtoreset{equation}{section} %Adds counter equation to the list of
				%counters \cl@SECTION to be reset when
				% counter section is stepped.
 \catcode`\@=12
\tableofcontents
\listoffigures

\newtheorem{th}{Theorem}[section]
\newtheorem{cor}{Corollary}[section]
 %% MACROS FOR PROOFREADING REMARKS
 %Comment out before final printing, to make sure all have been
 %taken care of, or replace them with empty macros
	
 \def\D{{\sc Definition.} }
 \def\C{{\sc Corollary.} }
% \def\T{\\{\sc Theorem.}}
 \def\P{{\sc Proof.} }
 \def\p{  |\psi\rangle }
 \def\S{{\sl S} }
 \def\x{  x }
 \def\R{{\bf R}}
 \def\C{{\bf C}}
 \def\L{\\{\sc Lemma.} }

 \def\ben{  \begin{enumerate} }
 \def\een{  \end{enumerate} }
 \def\beq{  \begin{equation} }
 \def\eeq{  \end{equation} }
 \def\bea{  \begin{array} }
 \def\eea{  \end{array} }

\section{Cellular Automata Machines: CAM-8 Overview}
In this section we give a brief overview of the CAM-8 architecture
from  a user's point of view, and introduce certain essential 
terms used to describe the architecture and operation of the cellular
automaton machine. The most fundamental of these is the {\em
site}, which denotes a single spatial location in the cellular array.
Each site is typically comprised of 16 bits, and therefore has
$2^{16} = 65536$ possible states.
Each bit of a site is associated with one of 16 numbered {\em bitplanes} or {\em
layers}, as shown in Figure \ref{layers}.
\begin{figure}
	\begin{center}
\mbox{        \psfig{figure=./figs/layers.ps,height=3in}
     }
	\end{center}        
\caption{The 16 bits, one per bitplane,  comprising a single site of
the
cellular automaton array. }
		\label{layers}
\end{figure}

The bitplanes can be arbitarily displaced relative
to one another, but bits within a particular bitplane are fixed rigidly
with respect to each other. The rigid motion  a bitplane, which is the
principle method by which one site informs a neighbor of its state,
is
referred to as a {\em kick}. There is a (large) upper bound on the
allowable
size of kicks which is derived from the physical size of the DRAMs
(dynamic
random access memories) used in the machine. For physics applications
with reasonably local interactions, this limit is unlikely to be of
practical interest.

In Figure \ref{kick} we show how the von Neumann neighborhood,
consisting simply
of a cell and its nearest neighbors is implemented in the CAM-8
architecture for
the case of a cellular automaton rule which has 1 bit per cell.
First, each cell makes 5 copies of its single-bit state on bitplanes
$0-4$.
Then, each bitplane is rigidly kicked in one of the four compass
directions
by a distance of 1 cell. After these two operations, each site
contains
all necessary information about the state of its 4 nearest neighbors
and
itself. For example, to learn the state of its right neighbor, each
site
must look at bitplane 1.
\begin{figure}
	\begin{center}
\mbox{        \psfig{figure=./figs/kicks3.ps,height=3in}
     }
	\end{center}        
\caption{Implementation of the von Neumann neighborhood in CAM-8. The first
figure shows the required uniform motion of each bitplane, know as its {\em kick}.
The second figure shows the von Neumann neighborhood and indicates on
which
layer (or bitplane) each site must look to  find the state of the
corresponding neighbor.
                  }
		\label{kick}
\end{figure}

This collecting of all necessary information at each site permits the
sites to be updated independently via a  lookup table. The
operation
of the lookup table is depicted in Figure \ref{lut}. The 16 bits of
each site are combined to form an integer between $0-65535$ inclusive.
This
integer is then used as an index into a one-dimensional array known as
the
{\em lookup table}. Call the lookup table array $L$,
and let $i$ be the 16-bit integer from the site, then  updating the cellular array
simply entails
replacing $i$ with $L[i]$ for each site.
There is support for {\it mixing-in} data from external sources, such
as pre-stored patterns from the host workstation, or random number
generators
implemented in external hardware. The most common use of this feature
is
in loading some initial pattern into the cellular array.
Acceptable random numbers are more easily obtained by letting  lattice gases
with densities corresponding to the desired probabilities diffuse on
some of the unused bitplanes. At each site, the presence of a diffusing gas
particles on these bitplanes is a pseudo-random variable.

A single
site of CAM-8 can be updated
in $40ns$, and it can update a single {\em module}, which
consists of $2^{22} = 4,194,304$ sites, in about $.16 s$. Larger machines,
consisting
of perhaps $128$ modules would contain $1.0737\times 10^9$ sites and could
be 
completely updated
at the same rate as a single module, since the machine is a fully
parallel MIMD (multiple-instruction multiple data)  machine above the module level.
\begin{figure}
	\begin{center}
\mbox{        \psfig{figure=./figs/model7.ps,height=3in}
     }
	\end{center}        
\caption{The 16 bit state at each site evolves to its updated value
according to the contents of the lookup table. The initial site data
may, but need not, be combined with externally generated data before
going into the lookup table. This feature is used, for example, to
setup
the initial state of the cellular array.
                  }
		\label{lut}
\end{figure}

CAM-8 offers a variety of boundary conditions, the most common of
which is the completely periodic one, shown in Figure \ref{toroid<} for
the
case of two dimensions.

\begin{figure}
	\begin{center}
\mbox{        \psfig{figure=./figs/squashed.ps,height=2.5in}
     }
	\end{center}        
\caption{Periodic boundary conditions correspond to toroidal
geometry in two dimensions.  The actual array  contains
4,194,304 lattice sites. 
                  }
		\label{toroid}
\end{figure}

Finally, CAM-8 provides a mechanism for measuring the number of
occurences of a particular event on each bitplane. An {\em event
counter} for each bitplane records the number of ones bits emerging
from
various sources, typically from the output of the lookup table. By
programming
the lookup table with the appopriate function it is possible to count
the number of times that and arbitary event has occurred in the space
without
slowing down the simulation at all. The counts are available to be
sent back to the host workstation at the end of each update. For
example, this
mechanism can be used to evaluate
arbitrary correlation functions in a very efficient, fully parallel manner.

\section{CAM-8 Code}
Dana, this section contained some CAM-8 code for the paper 
I am writing on a particular application of CAM-8 to statistical
mechanics.
I left in purely for flavor. It is currently much like CAM-6 Forth.
It is in a state of rapid evolution, and there is no guarantee that
it will look much like this in the end.

\subsection{Correlation Function Code}
\begin{verbatim}
\ Single module, periodic bc, d=2
\ Zeroth Correlation function calculation
\ Actually we can do N.N., N.N.N, and 4-spin correlation func. calcs.
\ using only 8 planes total.

\ Overall cycle 
\ 1. Many MC steps
\ 2. Corr(n-1), starting at n = 1 (incl. all kicking necess. for Corr & RG
\ 3. RG(n)

\ Define Correlation lut
0 0 == self      
1 1 == est	
2 2 == sud	
3 3 == se	
4 4 == ne	
5 5 == nord	
6 6 == 4spin-ur	
7 7 == 4spin-lr	

\ We assume that previous parts of the experiment have left
\ copies of the state on the top 8  planes

\ We make site-src the glued-data bit, so it remains unchanged,
\ but make event-src the output of the lut, so we count the
\ result of applying the rule "corr", but do not change the data,
\ except for the kicks, which we then undo

\ The spin product with each of the N.N's and N.N.N's comes out of
\ the lut in the bit position of the non-self spin involved
\ The product of the two 4 spin interactions come out in bit positions
\ 6 and 7
: corr 
	self est = if
		1 -> est
		else
		0 -> est
		then
	self sud = if
		1 -> sud
		else
		0 -> sud
	
	self se = if
		1 -> se
		else
		0 -> se
	
	self ne = if
		1 -> ne
		else
		0 -> ne
	self est ne nord xor xor xor -> 4spin-ur
	self est se sud xor xor xor -> 4spin-lr
;

256 create-table corr-lut \ Short lut, remember to set lir to -256
rule>table corr corr-lut

23 16 * create-buffer corr-event-buf \ event count buffer for 4M space 

\ BEGIN  part that is particular to this iteration of RG
\ Sweeps and scans become 9 and 20 on next RG iteration, scan-perm
\ will become every other row and column, and kicks will increase
\ magnitude by factor of "b" = 2, here
	scan-format 	 10 eswp!  21 escp!   10 estp!   23 ecl!    5 rcl!   
	        3 sm! \ fastest scan mode, 4 bits, w/pipe, closed sweep
	scan-perm 	\ identity permutation
kick   	    0  10  dim   16-layers:  0    -1  0  -1   -1 0 0 0 .. ..  dim! \ x kicks
            11 21  dim   16-layers:  0    0  -1  -1    1 1 0 0 .. ..  dim! \ y kicks
				  \  self  e   s   se  ne n
\ END of part that depends on RG iteration

\ Don't kick back, leave for First application of RG

	site-src use-glue ecm!
	event-src use-selsrc ecm! lutout-bit ecs!
	event read corr-event-buf

  lut-index b# 1111111100000000 reg!     \ using an 8-bit (256 entries) table
					\ setting lir to -256
  lut-io corr-lut
  run  	1 alt! / toggle lut, so that scan uses lut just written
	1 ssm! / frame sync
  
  *step* \ may want to drop the stop

\ Questions: 
\  Can we keep site-data same while getting event-count of lut-out ?
\ Can we use fastest scan mode ?
\  Should estp = eswp ?
\  Can we use -1 in dim! ?

\rm
\end{verbatim}

\subsection{Renormalization Transformation Code}

\begin{verbatim}
\sf
\ Single module, periodic bc, d=2, b=2 Modified Majority Rule RG transf
\ First RG iteration only

\ Define RG lut
0 0 == ul \ self
1 1 == ur \ est
2 2 == ll \ sud
3 3 == lr \ se

\ We assume that previous parts of the experiment have left
\ copies of the state on the top 4 planes

: sum4 ul ur ll lr + + + ;

: mod-maj-rule
4sum 2 = if
           ul if
		255 \ recall Corr uses 8 planes
	       else
		0
	       then
	else drop
	4sum { 0 0 0 255 255 } \ does {...} work ?
	then ;

16 create-table mod-maj-rule-lut
rule>table mod-maj-rule mod-maj-rule-lut


\ Following is particular to this RG iteration
	scan-format 	 10 eswp!  21 escp!   10 estp!   23 ecl!    5 rcl!   
	        3 sm! \ fastest scan mode, 4 bits, w/pipe, closed sweep
	scan-perm 	30 sa0!  0 sa1!  1 sa2!  2 sa3! 3 sa4! 4 sa5! 5 sa6! 
			6 sa7! 	7 sa8!  8 sa9!  9 sa10! 
		        30 sa11! 11 sa12!  12 sa13! 13 sa14! 14 sa15! 15 sa16! 
			16 sa17! 17 sa18!  18 sa19!  19 sa20! 20 sa21!
			30 sa22!  30 sa23!  	
\ Kick may be unnecessary, Corr0 may have already kicked data appropriately
kick   	    0  10  dim   16-layers:  0  -1  0  -1  .. .. ..  dim! \ x kicks
            11 21  dim   16-layers:  0  0  -1  -1  .. .. ..  dim! \ y kicks
				  \  ul ur  ll  lr
  lut-index b# 1111111111110000 reg!     \ using a 4-bit (16 entries) table
  lut-io mod-maj-rule-lut
  run  	1 alt! \ toggle lut, so that scan uses lut just written
	1 ssm! \ frame sync
  
  step \ no need to do stop in *step*
\rm
\end{verbatim}




\begin{thebibliography}{99}

\bibitem{ma76} {\sc S.-k. Ma}  {\sl Phys. Rev. Lett.}
{\bf 37}, 461 (1976).
\bibitem{swen79} {\sc R. H. Swendsen}  {\sl Phys. Rev. Lett.}
{\bf 42},  859 (1979).
\bibitem{swen82} {\sc R. H. Swendsen}, ``Monte Carlo
Renormalization'', 
in {\sl Real-space Renormalization}, {\sl eds. T. W. Burkhardt and J.
M. J. van Leeuwen}, Springer (1982).

\bibitem{berk} {\sc N. A. Berker} and {S. Ostlund}, {\sl J. Phys. C}
{\bf 12}, 4961 (1979).
\bibitem{cal} {\sc D. Callaway} and {M. Schick}, {\sl Phys. Rev. B}
{\bf 23}, 3494 (1980).
\bibitem{dun} {\sc L. Dunfield} and {J. Noolandi}, {\sl Phys. Rev. B}
{\bf 22}, 4430 (1980).
\bibitem{cal} {\sc D. Callaway} and {M. Schick}, {\sl Phys. Rev. B}
{\bf 20}, 3494 (1980).


\end{thebibliography}
\end{document}

