----- Original Message ----- From: "Richard Schroeppel" <rcs@CS.Arizona.EDU> To: <math-fun@mailman.xmission.com> Sent: Friday, April 11, 2003 10:44 PM Subject: [math-fun] cellular automata soup experiments [snip]
One possible "practical" consequence is that big random Life patterns can be subdivided and run on many parallel machines, with an overlapping margin of perhaps 2000 cells, for many time steps, and only modest synchronization effort.
If you have two adjacent swaths, you can give them identical margins of say 2000 cells. After 1000 generations, half of each margin could be bad, so you overwrite the bad halves of both margins. This assures that no matter how fast effects travel, the whole image will always be correct. The margin correction step might be faster than the neighborhood process itself. I used to do exactly this on the Binary Image Processor in 1975, but the swaths were 36 bits wide minus an 8-bit margin on each side. I updated margins every fourth step. We were computing I would guess about 5 neighborhoods per microsecond including overhead. Of course that was using one processor, not many, but the principle is the same. We were among the first experimenters with Life. Unfortunately we were supposed to be developing a product so we couldn't compete with Gosper and MIT at finding new phenomena (ignoring any difference in talent). Steve Gray