Final problem in Intel Threading Challenge

The last stage of the Intel Threading Challenge has begun and the final problem announced. While problem #5 is still live until tomorrow, problem #6 “Maximum Independence Set” provides another opportunity to win a prize from Intel and stack up some more points towards the grand prize for highest total cumulative points.

The Maximum Independence Set problem requires developers to write a threaded program to find a maximum independent set of an input graph. Naturally, the time required to execute the program will play a role in the scoring.

Entries for this final phase are due by 20th November. Winners of the competition so far have been announced on the winner’s page.

2 Responses

  1. I’ve tried the challenges. On the surface they seem intriguing and entertaining. And it’s fair to say that if your normal day job doesn’t take you deeply into multithreading, particularly threading that scales with more cores, then the challenges will certainly give you the opportunity to learn and exercise a different set of skills.

    In my experience, the challenges were poorly specified,o ften requiring elaboration and explanation before contestants could start work on a solution. The judges could learn a good deal about concise and effective specification from other programming challenges, such as the International Olympiad in Informatics.

    The test data used to exercise the solutions were often toy cases, and trivial compared to the bounds set in the problem. For example, in some challenges, the bounds were set to 2^31. Implementing a solution to such bounds is of course non-trivial. The judges should set realistic bounds that reflect the test instances that are used to test each solution. Otherwise, implementing a efficient solution is purely guesswork on the size of the test instances used. A contestant can hope that only test small cases are used and optimize for that, or go for the larger cases and suffer because the same optimizations don’t apply, and then loose out because only small sized test cases are used.

    I didn’t start the challenges until phase 2, where the majority of challenges in this phase were NP complete or NP-hard problems, with only 2 of the 6 challenges having polynomial solutions (matrix multiplication and convex hull.). To my mind, the effectiveness of algorithms for the NP class of problems often has little to do with threading and often more about luck. Typically the solution involves pruning some form of search tree and it is just luck if you choose to prune from the “right” point to arrive at the solution quickest. (For instance, the SAT problem in phase 1, the judges struggled to find a satisfactory set of test cases that produced timely results for a majority of solutions. The effectiveness really depended upon the direction of attack rather than use of threading.)

    My final gripe about the Intel Threading Challenge is that the problems were tough enough to require many hours to implement a solution and provide a decent write up (often from 30-60 hours), yet competitors do not get to know their own personal score. This seems little to ask given the effort involved in producing a solution. Yet competitors are expected to be satisfied with a few paragraphs of write up in the challenge forum where the distribution of points is given and the winner announced.

    I think threading is an interesting challenge. In practice, if your code is mostly runs server-side, then you probably do not need to worry about it, since concurrent requests will typically provide the parallel work needed to keeps all cores busy. However, for desktop code, becoming au fait with multithreading is almost inevitable. For anyone wanting to test their mettle on threading, I hope other competitions surface that offer fairer challenges that are well specified and provide personal feedback to each contestant.

  2. Thank you for the detailed feedback. We’ve read, discussed and are committed to continuing to improve the Intel Threading Challenge to make it the best that it can be. Please keep the feedback coming.

    Regards,
    Aaron Tersteeg
    Parallel Programming Community Manager
    Intel Corp.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: