Fast Hardware Simulation

[akash...@gmail.com]

I'm planning to implement a massively parallel simulator of game of life on digital circuits for my class project. I have an FPGA with 6-million logic gates (effectively). I'm guessing the simulation would naively yield 1 million to 1 billion steps/sec and the grid will be somewhere between 100x100 to 1000x1000. I'm not quite happy with the grid size but I'll be thinking about how to trade in size for some overhead in speed.

I think GOL is really awesome but I don't know a lot about it (and I just joined the forum). So what I am trying to understand is:

1) What similar work others have done, and what are the fastest simulation speeds/sizes for cutting edge software (and maybe hardware if others have worked on the same veins).

2) What cool patterns could I run with this? Something to show non-enthusiasts how awesome GOL/CA is. I'm looking at some kind of semi-useful (possibly numerical) computation and demonstrating how fast it runs. (for example I saw that someone has a pattern that produces fibonacci numbers encoded within gliders every 2100 steps, please point me to more of such awesome things).

3) What other cellular automata could I play around with this? It is actually easy to implement different circuit designs on it because it is all automated, so I am planning to experiment quite a bit with my kit.

[Frank Buss]

akash...@gmail.com wrote:
> I'm planning to implement a massively parallel simulator of game of
> life on digital circuits for my class project. I have an FPGA with
> 6-million logic gates (effectively). I'm guessing the simulation
> would naively yield 1 million to 1 billion steps/sec and the grid
> will be somewhere between 100x100 to 1000x1000. I'm not quite happy
> with the grid size but I'll be thinking about how to trade in size
> for some overhead in speed.

Nice.

> I think GOL is really awesome but I don't know a lot about it (and I
> just joined the forum). So what I am trying to understand is:

It's a usenet newsgroup, not a forum.

> 1) What similar work others have done, and what are the fastest
> simulation speeds/sizes for cutting edge software (and maybe hardware
> if others have worked on the same veins).

Hashlife is the best implementation which I know for Game Of Life:
http://en.wikipedia.org/wiki/Hashlife
It needs logarithmic space and time instead of the usual linear calculation.

> 2) What cool patterns could I run with this? Something to show
> non-enthusiasts how awesome GOL/CA is. I'm looking at some kind of
> semi-useful (possibly numerical) computation and demonstrating how
> fast it runs. (for example I saw that someone has a pattern that
> produces fibonacci numbers encoded within gliders every 2100 steps,
> please point me to more of such awesome things).

Not Game of Life, but another CA:

http://en.wikipedia.org/wiki/Von_Neumann_universal_constructor

I've played with CAs, too:

http://www.frank-buss.de/automaton/

Interesting might be "The Virtual cellular automaton", with which you
could build some useful calculation. And I really like the Rabbits
patterns in my Game of Life Applet: very minimal start pattern, but
complex behaviour. Can you build a longer running CA with some minimal
start pattern?

> 3) What other cellular automata could I play around with this? It is
> actually easy to implement different circuit designs on it because it
> is all automated, so I am planning to experiment quite a bit with my
> kit.

The CA FAQ has a lot more information:

http://cafaq.com

--
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss