Game of Life

[CornedBee]

I just finished a program for university. It was a challenge where we had to create an implementation of John Conway's Game of Life and make it as fast as possible. Since I found the challenge to be fun and interesting, I'm posting it here for all of you.

The basic rules of the game are explained here:
http://en.wikipedia.org/wiki/Conway's_Game_of_Life

Your objective is to implement a program that runs this simulation as fast as possible. Measure of performance is
a) the number of CPU cycles used and
b) the physical time used. (Mean of three runs.)
The program will be executed for 3000 generations on two different patterns on two different machines. Each result will be given a score relative to the results of my reference implementation. (8 results: two measurements over two starting patterns and two machines) The mean of the score is the final result. Implementations that produce an incorrect result are disqualified. Implementations that need more than two minutes for a run are disqualified, too. I'm not that patient.

The program must be able to read and write a simple textual file format. This file holds two whitespace-separated numbers per line, which form a coordinate pair designating a cell that is alive.

100 24
-24 51

The above specifies that the cell at (100,24) is alive, as is the cell at (-24, 51).
Input to the programs will be given in this format, and the program must produce this format as output (either to stdout or a configurable file name). The order of points is irrelevant; the file will be sorted before any comparison is done.

The machine specifications are:
1)
Intel Core Duo (32-bit instruction set, SSSE3 support, dual core)
1 GB RAM

2)
AMD Athlon64 (64-bit instruction set, SSE2 support, single core)
1 GB RAM

The target compiler is GCC 4.1 or GCC 4.2 (depends on what I'll be using when the contest ends) on a Linux system. There is no need to make it portable to other platforms.
The project must include a simple way of building. You can use GNU autotools/make, SCons, Boost.Build or a custom shell script (Bourne shell or bash). Compilations must be possible with one, at most two, simple commands. (e.g. "./configure; make" or "bjam").
You may use C or C++. If you use C++, you may expect the Boost libraries to be available, both 1.34.1 and 1.35. (Hopefully it will be released by then.)

Implementations based on hashlife are forbidden, sorry. This advanced algorithm is so superior that it would be pointless to compare it against the other possibilities.

This is an optimization challenge. Optimize your algorithms, and optimize your instructions. Every cycle counts.

The contest ends at 0:00, April 21th. Have fun!

I will post a few test input/output files soon.

[mike_g]

Sorry, I havent read through the entire Wikipedia page so maybe I missed this part, but what size are the grid dimensions meant to be?

[tabstop]

Originally Posted by mike_g

Sorry, I havent read through the entire Wikipedia page so maybe I missed this part, but what size are the grid dimensions meant to be?

Why do you assume there are bounds on the grid size?

[Dave_Sinkula]

I'm still waiting for the results of Wireworld.

[jEssYcAt]

Originally Posted by Dave_Sinkula

I'm still waiting for the results of Wireworld.

I think Salem got too busy with work and then just forgot about it, and I have mixed feelings about it... I'm no more than a hobbyist programmer, so I'm a little afraid to hear how bad my entry was. )

Originally Posted by mike_g

Sorry, I havent read through the entire Wikipedia page so maybe I missed this part, but what size are the grid dimensions meant to be?

More important I think is, how large will the patterns be? Shall we assume they might be "of any size", or are you willing to tell us something like "the patterns are 200x100 and 40x60"?

[CornedBee]

There is no actual boundary on the grid size. However, I will run no pattern for more than 3000 generations, and no starting pattern will be larger than a few hundred grid cells in any direction. Because the pattern cannot grow more than one cell per generation, you can assume that it will not grow beyond about 8000 cells in either dimension.

However, I will give out bonus points for solutions that do not use fixed-size grids. I'll just have to think of a fair and balanced way of adding that in.

[jEssYcAt]

When you say you will run no pattern for more than 3,000 generations, are you suggesting that our program needs to have a way to let you choose how many generations it will run, or are we safe to hard-code the program running for 3,000 generations?

And are you going to clock the entire program or are you going to modify the program to add your own timing functions around the update or something (meaning you are only timing the actual calculation of the generations, not loading and saving files)?

I realize the overhead of loading and saving files is probably not going to be a significant bottleneck compared to calculating 3,000 generations of a board that might grow to a couple thousand cells in both directions, but I need to know how pointlessly to tinker with my file io operations.

[CornedBee]

Let me put it this way: in profiling my reference, file I/O is not there. It simply takes up no noticeable amount of time.

That said, the cycle count will clock the entire program. The physical time count will count only the core parts.

And the program must be able to run for a configurable number of steps. Best would be a command line parameter.

[Bubba]

Presumably this has to be in C/C++?

[CornedBee]

You can write it in Fortran if you want; I have that gcc variant too.

The rule is that a GNU toolchain must support the code. So you can write it in pure assembly, too, as long as you use AT&T syntax.

[abachler]

Does it have to be for linux, or will Win32 console variants be allowed also?

[CornedBee]

My test computers run Linux only, sorry. I could run programs under Wine, but
1) I can't compile them, and I don't accept executables and
2) Wine is 32-bit only and
3) you'd probably get a considerable performance penalty from Wine.

However, if you don't have Linux, you could develop using MinGW GCC. I'd be willing to help you in the final stage.

[dwks]

My test computers run Linux only, sorry. I could run programs under Wine, but
1) I can't compile them, and I don't accept executables and
2) Wine is 32-bit only and
3) you'd probably get a considerable performance penalty from Wine.

You could use mingw. It's a Linux package (for Debian, presumably downloadable for other distributions) that apparently lets you compile Win32 executables under Linux.

Or you could wine the compiler. But you're right, of course; performance would be significantly reduced.

[edit] "April 21th"? Oh, and of course it looks interesting. [/edit]

[CornedBee]

Originally Posted by dwks

You could use mingw. It's a Linux package (for Debian, presumably downloadable for other distributions) that apparently lets you compile Win32 executables under Linux.

Yeah, I could do that. But that still prevents me from testing the 64-bit compatibility of the program.

"April 21th"?

Hey, I posted this at 1:30 AM.

[abachler]

Originally Posted by CornedBee

However, if you don't have Linux, you could develop using MinGW GCC. I'd be willing to help you in the final stage.

Well, I was planning on using assembly, multithreading and the GPU. Linux does threads differn't from win32 and im not sure if you have RapidMind installed.