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."
The only winning move is not to play. How about a nice game of chess?
I couldn't resist!
An article where SOVIET RUSSIA *and* beowulf jokes are on topic. What's next? A Natalie Portman interview?
I've often been told my programs require more cpu, allocate more memory, and take more time than any other coder on the team. If I can scale up my special skillz to more than one processor at a time, I might have a chance here.
Anyone remember Core Wars?
It should not read like that it should be.
since a craftsmanly Russian program defeated a sophisticated program created by a genetic algorithm from NASA.See (from NS):
"The final battle saw Wenig's program - created using genetic algorithms - take on a program designed by a computing student from Moscow State University."
A subtle, but important difference. Now if the prgrams were actually evolving in the Gridwars game that would be interesting, as it would be similar(ish) to my project.
*Dreams of a day they put an edit queue on slashdot*
Rogue: oh no! a 'C' is chasing my @! majick missle! majick missle! arghhll...
This is not the first time something craftmanslike can beat something sofisticated. Even thought the following examples are strictly hardware, the general idea is the same.
Take, for instace the T34 vs the Tiger. The Tiger was one of the most sofisticated - if not the most sofisticated - tanks in production at the time, but were drowned by hordes of the more craftmanlike and easily manufactured T34.The battle between a simple, craftmanlike approach and sofistication was once again seen in the early sixties, in the race to get a man into space. The russians fielded the Vostok, a design born more out of solid craftmanship than anything else. It's very simplicity was a strenght, allowing it to undertake missions up to five days long, while the american attemt at a longdurationflight in the highly sofisicated Mercury lasted just under a day and a half, leaving Gordon Cooper in a virtualy dead capsule (having to eyeball his attitude thru the windown and manualy fire the retros). Granted, one reason the US had to go for sofisication is that their rockets simply couldn't lift as much as russian rockets... but whereas derivatives of the Vostok still flies (as unmanned recoverable satelites), the line that breed the Mercury is dead.
Sofistication is well and good, but many times a less sofisticated but better crafted designs / programs can outperform it. Sofistication for it's own sake is usually not worth the tradeoffs.
Everything in the world is controlled by a small, evil group to which, unfortunately, no one you know belongs.
NASA decided that the astronauts needed a writing utensil to take notes during space missions. NASA spend a large amount of money to develop the zero G ballpoint pen.
This is an urban legend.
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