Slashdot Mirror
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."
Sounds rather typical for russian stuff. I used to live there 12 years ago. Most things, like household items like irons and mixers weren't very pretty, but they were definitely were solid and lasted years and years. Some were even left from the previous generation.
I also remember seeing a magazine explaining the construction of an electric razor, and being able to buy all the components it was made of in a shop. Now unfortunately things seem to have "modernized" though, and all the crap that is produced now is becoming common there.
It's even kind of sad. If previously it was possible to have something working for 10 years without failing, now we have to replace things like mixers and vacuum cleaners very often.
Wasn't the NASA program created by a genetic algorithm? It's bad style yes, but fairly decent for an automated programmer.
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/030
>
> 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
cpeterso
Another nice modern variant on the coreware there is found at IBM called RoboCode.
You write Java robots that battle each other by controlling movement, gun turret and radar turret. A great way to learn Java, be mentally stimulated and is entertaining to watch.