Cellular Automata FAQ

[Non-Java version]

Cellular automata software

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand this node
What general-purpose CA simulators are available?
Contributions by:
  • Russell Inman <inman@ceti.csustan.edu>
  • H.H. Chou <hhchou@cs.umd.edu>
  • Dana Eckart <dana@rucs.faculty.cs.runet.edu>
  • Andy Wakelin <mctaww@uk.ac.dct>
  • Harold McIntosh <mcintosh@redvax1.dgsca.unam.mx>
  • Rudy Rucker <rucker@sjsumcs.SJSU.EDU>
  • Ken Karakotsios <karakots@apple.com>
  • Simone Maggi <magi@c700-2.sm.dsi.unimi.it>
  • Dino Cule <cule@ee.umanitoba.ca>

Expand this node
Expand this node
What simulators for the Game of Life are available?
Go to the Game of Life FAQ
Expand this node
Expand this node
How can I make CA simulations run fast?
Contributions by:
  • Rudy Rucker <rucker@sjsumcs.SJSU.EDU>
  • Richard Ottolini <stgprao@st.unocal.COM>
  • J Dana Eckart <dana@rucs.faculty.cs.runet.edu>
See Tim Tyler's site on Cellular automata optimisation.

I can think of four main tricks for making a CA program run fast.

  1. Lookup table. Generally a cell takes on a NewC value which is computed on the basis of info in the cell's neighborhood. Try to find a way to pack the neighborhood info bitwise into a nabecode number. Then use nabecode as an index into a lookup table. Thus NewC = lookup[nabecode]. You precompute the lookup values for all possible nabecodes before running the CA. Lookups can be saved, as Walker and I did in CA LAB.

  2. Pointer swap. To run a CA, you need two buffers, one for the current world of cells, and one for the updated world of cells. After the update, *don't* copy the updated world onto the current world. Just swap the pointers to world and new world.

  3. The flywheel. In stepping through the cells of the CA, you repeatedly compute a cell's nabecode, then compute the nabecode of the next cell over, and so on. Because the neighborhoods overlap, a lot of the info in the next cell's nabecode is the same as in the old cell's nabecode. Try to arrange nabecode so that you can left shift out the old info and OR in the new info.

  4. Assembly language. A 2D VGA CA is going to have about 300K cells. That means you are going to assemble nabecodes and lookup the NewC values about 300K times per screen. This means that your inner loop for flywheeling the nabecode must be as efficient as possible. If you can write this in assembly language, and keep an eye on the listed ``clocks'' per instruction, you can shave off a few clocks here and there, which really adds up when done 300K times.

If the rule set is known to lead to sparse configurations, e.g. Life Game with a small initial pattern, then one can use sparse matrix tricks. That is, to just compute in the vicinity of occupied cells. Generally these do not compile as efficiently as a full matrix method, because there is more indirect address and branches. However, one could include both a sparse and full matrix method in the same program, then convert when the cross-over density is reached.

Tips for periodic boundary conditions

There are two basic methods:

1) coding for faster modulo arithmetic; and 2) using a larger array and copying the boundary cells between iterations. The brute force method of doing modulo arithmetic on index variable, x, for a range of 0..63 in C is (x+offset)%64 whereas on some architectures (e.g. some Sun Sparcstations) it is actually faster to do

register int tmp=x+offset;

tmp>63 ? tmp-64 : tmp

if offset is positive and similarly if it is negative. Still better, if the range is a power of 2, might be


when offset is positive and


when offset is negative.

Expand this node
Expand this node
What other CA software is available?
There's a list of some other software here.

Expand this node
Expand this node
Wilhelm Hasselbring. CELIP: A cellular language for imaging processin. Parallel Computing, 14:99-109, 1990.

D. Hiebeler. A brief review of CA packages. Physica D, 45:463, 1990.

Hans B. Sieburg and Oliver K. Clay. Cellular automata as algebraic systems. Complex Systems, 5(6):575-602, December 1991.

Friedhelm Seutter. CEPROL: A cellular programming language. Parallel Computing, 2(327-333):327-333, 1985.

Tommaso Toffoli and Norman Margolus. Cellular Automata Machines. MIT Press, London, 1987.