6.4.4 PRSHParallel Remote Shell

8.3.2 Example: A One-dimensional Cellular Automaton
In the examples above, the order of the elements and the way in which they are assigned to processors was unimportant, so it was possible to do all communication using collective reductions, scans, broadcasts, etc. Now we consider an example in which the placement of data is meaningful, requiring us to use point-to-point communication routines. One-dimensional cellular automata (CA) are simple dynamical systems that can display surprisingly complex behavior. A CA with half-width hw is an array of values with an update rule that says the next value in location i depends only on the previous values in locations (i-hw, ...,  , ...i+hw). For simplicity, we consider finite CA with periodic boundary conditions, i.e., the location indices are computed modulo ncells, the number of cells in the array.
A wide variety of cellular automata have been studied. The values may be integers, or they may be restricted to a finite alphabet of size A. If A=2, the values are bits, and it is often possible to pack them very tightly and perform updates very rapidly. The update rule may be an arbitrary function of the 2hw+1 input values. Special cases include linear functions and functions like "parity" which count the number of values of a particular type in the input domain. Program 8.11 shows some code from a simple sequential CA implementation designed to work with arbitrary functions of fairly small alphabets (each value must fit in a single unsigned char, i.e., A 256).
typedef struct ca_s{ 
  unsigned char *state; /* size ncells */ 
  int A; 
  int hw; 
  int ncells; 
  unsigned char *old; /* size ncells + 2*hw */ 
  /* other fields that control updateRule */ 
} CA_t; 
Program 8.10: Structure definition for a 1-D cellular automaton with update rule implemented in Program 8.11.
The two distinct operations in the procedure CAiterate are important. The first operation, CAcopystate involves copying the contents of the state array to the old array so that we can write the new values into state. The second phase then computes the new state based on values in old. Notice that periodic boundary conditions are imposed by padding the old array on both ends by hw values, copied from the opposite end of state, as illustrated in Figure 8.1. Thus, when the new value of, e.g., state [0] is evaluated, updateRule uses values old[-hw] through

 



How to Build a Beowulf
How to Build a Beowulf: A Guide to the Implementation and Application of PC Clusters (Scientific and Engineering Computation)
ISBN: 026269218X
EAN: 2147483647
Year: 1999
Pages: 134

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net