Gridwars Parallel Programming Challenge

Peter_Pork writes "New Scientist has an article about GridWars, a challenging new game that runs on large clusters of computers. Programs fight each other for supremacy in terms of the number of processors they control, and the main point of the contest is to develop better parallel algorithms. It seems a nice idea: have fun while you improve the state-of-the-art in cluster computing. The result of the last contest was somewhat of an upset, since a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA."

Comments

Re:bad programming

[cpeterso]

People are noting that NASA's program was created using genetic algorithms, but there is nothing preventing the use a data table to store the genetically evolving data. In fact, that might be a much better host because the evolving data is located in a single section of data.

Anyways, the table lookup is NOT necessarily faster than huge switch statement. The table lookup requires the data table to be loaded. If the table is large and has poor reference locality, then your program could end up thrashing the processor cache. The switch statement(s), however, can compute the jumps without loading stuff from the data segment (and flooding the processor cache).

And Linus Torvalds seems to agree with me: http://www.ussg.iu.edu/hypermail/linux/kernel/0304 .3/1367.html


>
> gcc 3.4 will have a __builtin_ctz function which can be used for this.
> It will emit special instructions on CPUs that support it (i386, Alpha
> EV67), and use a lookup table on others, which is very boring, but
> also faster.

Classic mistake. Lookup tables are only faster in benchmarks, they are
almost always slower in real life. You only need to miss in the cache
_once_ on the lookup to lose all the time you won on the previous one
hundred calls.

"Small and simple" is almost always better than the alternatives. I
suspect that's one reason why older versions of gcc often generate code
that actually runs faster than newer versions: the newer versions _look_
like they do a better job, but..

Linus