Cellular Automaton Algorithm for Real Space Renormalization Group

Michael Biafore

May 28, 1991

Abstract

This is a section of a paper which describes a little more fully the structure of CAM-8.

Contents

List of Figures

1 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 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 bitplanes or layers, as shown in 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 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 ?? we show how the von Neumann neighborhood, consisting simply of a cell and its nearest neighbors is implemented in the CAM-8 architecture Figure 1: The 16 bits, one per bitplane, comprising a single site of the cellular automaton array.

Figure 2: Implementation of the von Neumann neighborhood in CAM-8. The first figure shows the required uniform motion of each bitplane, know as its 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.

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.

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 ??. 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 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 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 Figure 3: 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.

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 module, which consists of 2^{22} = 4, 194, 304 sites, in about .16s. Larger machines, consisting of perhaps 128 modules would contain 1.0737 × 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.

CAM-8 offers a variety of boundary conditions, the most common of which is the completely periodic one, shown in Figure ?? for the case of two dimensions.

Finally, CAM-8 provides a mechanism for measuring the number of occurences of a particular event on each bitplane. An 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 Figure 4: Periodic boundary conditions correspond to toroidal geometry in two dimensions. The actual array contains 4,194,304 lattice sites.

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.

2 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.

2.1 Correlation Function Code

\ 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

2.2 Renormalization Transformation Code

\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

References

[1] S.-k. Ma Phys. Rev. Lett. 37, 461 (1976).

[2] R. H. Swendsen Phys. Rev. Lett. 42, 859 (1979).

[3] R. H. Swendsen, “Monte Carlo Renormalization”, in Real-space Renormalization, eds. T. W. Burkhardt and J. M. J. van Leeuwen, Springer (1982).

[4] N. A. Berker and S. Ostlund, J. Phys. C 12, 4961 (1979).

[5] D. Callaway and M. Schick, Phys. Rev. B 23, 3494 (1980).

[6] L. Dunfield and J. Noolandi, Phys. Rev. B 22, 4430 (1980).

[7] D. Callaway and M. Schick, Phys. Rev. B 20, 3494 (1980).