Intel Threading Challenge 2009

Intel Threading Challenge 2009 is an intel contest where you have to implement a multi-threaded solution for a given set of problems using any tech you want (not necessarily from intel) but taking into account the test machine specs. The problems are spawned every two weeks with 19 days to complete the task. There are two phases with six problems to solve. The score in a phase will be the sum of your three best scored submitted solutions. The solution should include a kind of report and of course the source code. You can find here an example of the report and more information about the rules, prizes, etc… here. The contest is managed, or at least it seems so, by Dr. Clay Breshears. As his bio shows, he is a really experienced engineer. Recently, he published a book on parallel programming “The Art of Concurrency: A Thread Monkey’s Guide to Writing Parallel Applications“, which I’m going to buy after I read “Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism“and “The Art of Multiprocessor Programming“. By the way, he made a hell of a fun video about concurrent programming: “A visual guide to key concepts in threaded programming – Common problems and how to solve them

I really don’t have much time but I could enjoy participating in this contest and well, it’s a nice excuse to get my hands on Threading Building Blocks. I’m going to give a try for the next couple of weeks to the first problem (bounded knapsack problem) and I will see if I have fun. Don’t expect any graphics related tests/tech demos in the meantime although I want to show something of the entry development. For the moment, I don’t know exactly what I’m going to show but I will.

One Response to “Intel Threading Challenge 2009”

  1. mdm100 says:

    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 bigger hardware, then the challenges will certainly give you the opportunity to learn and exercise a different set of skills.

    However, in my experience, the challenges were poorly specified,often requiring much 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 chanllenges, such as the Internaltional 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 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, 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 to submit 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. 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 with at least some personal feedback.