The winner for the Phase 2 portion of the 2009 Intel Threading Challenge Contest has been announced. Go to the contest website for details. For this contest, we broke up the problems into two Phases. The first phase had 6 problems and ran 13 weeks from 06 APR to 03 JUL; the second phase also had 6 problems to solve in 13 weeks from 24 AUG to 20 NOV. The description of the twelve problems is still available on the contest main page if you are curious about what the problems were.
I served as primary judge and problem coordinator. In total, there were 148 program entries (49 on Linux, 99 on Windows) during those 26 weeks, with many entries in C, C++, and C#. There was a smattering of Java, Cilk++, Erlang, and Haskell, too. Besides the application to solve the posed problems, this contest required a write-up describing how the entrant had parallelized their code, what problems they encountered, and how they were solved.
Each problem was given a 19-day time frame for a solution to be submitted. With the compressed schedule, the first and last weeks of problems were overlapped with the previous problem and the next one. For that reason, we only counted the top three problems submitted by each contestant in a Phase to determine the overall winner in each Phase.
Many of the problems posed were NP-Complete. This meant that, in most cases, the solution code needed to (potentially) search through the entire solution space. If contestants found a good, parallel solution space algorithm, many of the other problems could be solved with this base algorithm. It should be a matter of recasting the solution checking computation and supporting data structures to the specific problem. Some problem dependent heuristics to trim the search space could also be applied. Unfortunately, there weren't many contestants that stuck around to solve more than one or two problems. Thus, code re-use like this would not have been much of a benefit.
Even so, the judges were surprised by the depth of knowledge and resourcefulness of many contestants. One particular instance was demonstrated in the Knight's Tour (Problem #2, Phase 2) solutions. Rather than compute and enumerate each full length path, some applications only went to the halfway point. Then, using the fact that the knight had to return to the start square, the ends of the half tours were matched up and counted. I smacked myself in the forehead after I read the first code write-up that used this technique. (I'm sure it would have occurred to me eventually, but up to that point it hadn't even been a glimmer in my mind.)
Without the points directly awarded to use Intel tools (as we had in the previous Threading Challenge contest), there were very few entries that used Intel Threading Building Blocks (TBB). We thought that the use of the TBB hash map would have been a good solution for finding the next possible city to be visited in the Travelling Baseball Fan problem (#4, Phase 2). Some may have tested TBB solutions and found them to not be as fast as some other solution or simply ran out of time and were unable to submit them. It's impossible to say.
Contestants came from all over the world. The countries with the bulk of entrants were Russia, China, India, and the US. Each problem statement was translated to Mandarin and Russian, which required a lot of time and effort of Intel folks in those countries to coordinate and ensure things were posted on time. I appreciate the efforts of these unsung heroes for their work behind the scenes. Without them, the contest would not have been as successful as it turned out to be.
I want to express my thanks to each and every one of the contestants in both phases of this contest. I am very pleased with the camraderie expressed in the problem forums during the contest (that was still a cut-throat competition). I hope everyone participating learned some new things and some new techniques for parallel programming. At the very least, I hope everyone was able to have some fun programming solutions to some of the "classic" problems from computer science.