Fast LIFE (was: Re: summing 9-cell neighborhoods)
mark kramer
1> The other optimization in my system is the update method. I keep a list
1> of actions that will happen in the next generation ....
1> Cells are kept in a hash table (with each bucket being a linked list), so
1> lookups are fairly fast, and since the algorithm only updates the parts
1> of the board that are actually changing, it wastes no time examining either
1> empty space or inactive (i.e. stable) parts of the board. It also reclaims
1> memory as it goes, so you can (for example) set a glider going, and it will
1> go forever with constant (small, ~18 cells) memory usage.
In article <96...@bloom-beacon.MIT.EDU>, ta...@athena.mit.edu (Michael Zehr) writes:
2> The fastest algorithms I know of for sparse life use lists of active
2> cells. but given a sparse life board, it *might* be faster to keep a
2> list of active "areas" and use a method similar to mine on each active
^^^^^^^^^^^^^^^^^^^^^^
2> "area." the trick would be to keep area management to a minimum. (for
2> example, when do you split an area into two separate areas?) note that
^^^^^^^^^^^^^^^^^^^^^^^^^
2> the method of incrementing the neighbor count for all cells in the
2> neighborhood of a new-born requires 8 memory access per new-born.
2>
2> and for life, there are other speed hacks you can use. (example -- have
2> one item in your active list indicate that there is a glider at x,y in
2> stage z. ....
2>
2> as someone pointed out, optimizations are highly dependant on the
2> particular CA. my ideas were specifically for fixed-size CAs in which
2> most cells were active in a given generation.
When I was a student, I wrote a lot of LIFE-programs (my father told me all
about LIFE when I was 12 :-) ).
Only after years I came to an idea like the first one above, but it did
not work out satisfactorily, because of the large overhead on _every_
reference to a cell.
The only reason I used that approach was the low baud-rate of our
terminals at the time. By using the active list it was easy to update only
changed locations.
BTW: Of course the rules were parametrised, so any totalistic
2-dimensional 9-neighbourhood CA could be run.
I have often considered the idea to keep track of active regions, but
splitting and joining(!!) them seems to cost too much overhead.
So, if intelligent methods fail, why not use a dumb method?
Split the (infinite) field into fixed sized blocks of say KxK cells.
Each block may be considered a finite CA with external boundary
conditions. For updating the cells _in_ the block all available tricks can
be used; to reduce work at the boundaries use overlapping boundaries and
"communicate" changes to neighbouring blocks.
Now use method #1 above to keep track of active _blocks_ instead of
_cells_. The larger K is, the more efficient is bookkeeping, but also the
less efficient is memory usage. The optimal choice of K depends on your
system and the particular CA-rule.
However, the system has a very special kind of influence on performance.
Consider a paged memory system; then the best choices of K are such that
the blocks use exactly an integral number of pages each.
I used this method with K=16 on a general purpose time-sharing system.
On a special purpose and/or personal system a further speedup may be
obtained by intelligent prepaging (e.g. when visiting blocks row by row).
For sparse CA the overhead is small (for LIFE with K=16 approx. 40% of
cells in active blocks are active); for dense CA even smaller.
Furthermore this method does not rely on any properties of the particular
CA-rule (what is special about gliders, traffic lights etc. to keep track
of them seperately?)
--
Mark R. Kramer, Department of Computer Science, University of Utrecht
Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
Phone: +31 - 30 - 531937 | UUCP : ...!hp4nl!ruuinf!kramer
| INTERNET: kra...@cs.ruu.nl
Dave Hiebeler
>Split the (infinite) field into fixed sized blocks of say KxK cells.
>
>Each block may be considered a finite CA with external boundary
>conditions. For updating the cells _in_ the block all available tricks can
>be used; to reduce work at the boundaries use overlapping boundaries and
>"communicate" changes to neighbouring blocks.
>Mark R. Kramer, Department of Computer Science, University of Utrecht
This is exactly the method I used to run CA programs on our
32-node Intel Hypercube. I split up the grid into 32 horizontal slices,
each slice is N cells wide, and N/32 high (assume N divisible by 32,
although the program works even if that is not the case).
During each step, each node updates its strip, and then sends the
new top row to its neighbor above, and its bottom row to its neighbor
below, and receives a new row from each of those neighbors.
I didn't do much to optimize, so if one slice always gets updated
faster than the rest, then that node will do a lot of waiting, to
get its new boundaries from its neighbors. I suppose it might be
useful at times to have some bit of dynamic shuffling, where if one
node seems to be waiting a lot, a neighbor "gives it a row" so to
speak. That would take some overhead, so perhaps applying that
trick every 100 steps or so wouldn't be too bad. Or maybe just
taking some precautions when setting up the division scheme for
a particular cellular automaton might be good enough in other
cases, depending on how dynamic and non-homogeneous the behavior
over the grid will be.
----
Dave Hiebeler Internet: hieb...@cs.rpi.edu (preferred address)
Computer Science Dept. hieb...@itsgw.rpi.edu
Amos Eaton Bldg. Bitnet: user...@rpitsmts.bitnet
Rensselaer Polytechnic Inst. / Troy, NY 12180-3590