At 06:50 PM 1/23/2008 +0000, Anselm Hook wrote:
If you have a large cellular automata; such as say conways-life (or
something with perhaps a few more bits per pixel) - what is an efficient way
to represent this in memory?...speed is critical since the data-set may be
large. ...
Michael Abrash organized a contest to optimize Life back in the days of the
386/486. The solution he reports in his "Graphics Programming Black Book"
is impressive and may provide some inspiration. See chapters 18 and 19 at
http://www.byte.com/abrash/ . You're not going to adopt this method
directly, but it suggests some ways to achieve enormous speed. Chapter 18
has some general advice about the process of going about optimizing your CA
code.
As the question suggests and an earlier respondent noted, an efficient
memory representation of the CA state can be the key. I wouldn't expect
measures that are appropriate for Life (such as glider detection or sparse
matrix representation) to be effective for a CA of a watershed,
though. For a large grid, you will achieve a lot if you can get the whole
thing into RAM in some form or another, no matter how heavily
compressed. I would be inclined to look first at stuffing contiguous
groups of cells into machine words and forgetting about any other kind of
in-RAM compression. E.g., with 8 or fewer values per cell, you can
represent any state of a three-by-three block in a 32 bit word and still
have five bits left over for additional information. That gives you
upwards of eight billion cells to play with in a 4 GB machine. You could
then tile the RAM and apply a solution like Abrash's winner, tile by
tile. That should be amenable to heavy parallelization, too. Have you
checked out NVidia's CUDA?
Best,
Bill Huber
Quantitative Decisions
_______________________________________________
Geowanking mailing list
[email protected]
http://lists.burri.to/mailman/listinfo/geowanking
