Archive for the ‘Contests’ Category

ITC2009: Line Segment Intersection

Saturday, July 4th, 2009

The problem of this contest’s round was to find the intersections within a set of 3d line segments. I found tons of information in google about algorithms solving this problem in 2d. It seems that finding the intersections in a set of 2d line segments is a well known problem of computational geometry. Unfortunately, I didn’t find any algorithm in 3d and I wasn’t sure that converting the 2d algorithms to 3d could give better results than a brute force approach. Taking this into account, I decided to implement a brute force algorithm using a simple line segment intersection test. This approach gave ~800secs in a set of 100.000 line segments. I realized that the tests that were already tested could be skipped, after the modification the algorithm gave ~300secs. At this moment, I removed every instruction of the if intersection test statement (don’t ask why) resulting in a running time of ~6secs. This time was wrong. I was compiling with the optimizations active, so the compiler just removed the call to the intersection test function, giving a double nested loop doing pointer dereferencing. Well, after this little mistake I was ready to think in how to parallelize the algorithm.

As with the previous problem I used Threading Building Blocks as the tool to parallelize the algorithm. I chose to use the parallel_reduce algorithm, after trying to make it with parallel_for. The problem is gathering the results across all the tasks. Parallel_reduce is an easy way of collect results after the tasks completion. The algorithm includes a synchronization method: join. After a task ends the join method is called to merge the results. The parallel approach gave me a time of ~60secs.

I think the speed I got wasn’t that fast to win this round but that’s not my objective. I’m having a lot of fun, I’m learning from other people and I’m learning how to use TBB. Those are my objectives.

ITC2009: Knapsack

Saturday, June 20th, 2009

The 5th problem of the Intel Threading Challenge 2009 Contest is a bounded knapsack  problem with real numbers instead of integers. You can get more information about knapsack problems in “Knapsack Problems: Algorithms and Computer Implementations”, Silvano Martello and Paolo Tooth, which is a free book.  I implemented a classical dynamic programming algorithm using Intel Threading Build Blocks to parallelize it. More information on dynamic programming in “Introduction to Algorithms, Second Edition” .

The approach I took to solve the problem is really naive due time constraints. The problems I found were:

  • Convert a bounded knapsack problem to a 0-1 knapsack problem.
  • Convert real number weights and benefits to integers.
  • Parallelization of the serial algorithm.
  • Memory efficiency.

The serial algorithm is really naive:

  1. Convert the weights and values to integer numbers.
  2. Convert the problem to a 0-1 knapsack problem repeating bounded limit times the items.
  3. Solve 0-1 knapsack problems with a dynamic programming algorithm.
  4. Trace back the items.

As you see this approach is the classical example of dynamic programming you can find in textbooks. Although it has big problems when you try to solve big data.  Repeating the items bounded limit times its a really easy way to convert the problem but needs tons of memory. Multiplying by 100 makes the deal, but it can lead to rounding precision problems. The parallel algorithm is the same but using a “parallel_for” to replace the second for loop of the algorithm.

Well, the solution proposed is very naive, so I don’t expect good results in the contest. Anyway, I enjoyed the problem and I’m already thinking about the next one: “Segment intersection”.