Intel Threading Challenge: the convex hull challenge begins

The new puzzle for the Intel Threading Challenge has been announced. The goal is to find the convex hull of a set of points within a three dimensional space. I’d not seen this exercise before, so it took me a moment to visualise it, but the convex hull is basically the smallest 3D shape that can enclose all the points. There’s more mathematical information on the convex hull here, including some helpful illustrations, and this page on convex polyhedrons might also prove helpful.

You have until Friday 6 November to submit your solution (code, and write-up), and you can find full details (and sample input data) at the Intel Threading Challenge website. It goes without saying that your code should make optimal use of threading. This challenge is all about computation, and the input and output are both text based, so you don’t need any fancy 3D graphics skills.

Now a new puzzle has been announced, the solution to an old puzzle has also been released. Akki provided the winning solution to the graph colouring problem. The solution included several compromises in the interests of increasing performance. These included creating a copy of the graph for each thread, which carries a higher cost in memory; and accessing a shared variable which is rarely updated without synchronisation, which can negatively affect accuracy. Comparing the threaded code to a brute force sequential program shows a massive speed improvement. Execution time was cut from 41.73s to 0.42s with four threads.

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: