What's the best solution for an embarrassingly parallel problem?

Question

Sorry for the vague topic question, but I'm working on some academic video processing routines. The algorithms are written in MATLAB, and while it's fine for development purposes, it processed a video at about 60spf, or around .0166fps. Needless to say, this wont be sufficient for demos and such, so my summer job is to convert the routine to something that will run drastically faster.

I have rewritten the slowest portion of the code for CUDA, nvidia's GPGPU solution. However, there is also a large portion of the code that seems to be better done on the CPU, as it is relatively serial. The problem is, the machine I was given has 2 Xeon processors, with 8 logical cores total, and it seems to be a shame to bottleneck the GPU code by coding only for single core. The video conversion process is functional in that each frame does not depend on other frames, so I was thinking some kind of asynchronous queue/stream would best.

Here lies my question: what would be the best way to achieve this type of parallelism with the best ratio of effort to speed yield?

Some of the solutions I've looked at are OpenMP, .net TPL, and just simple pthreads.

I only have basic exposure to asynchronous programming, so I would rather use a library or something rather than mess around with mutexes and barriers and shoot myself in the foot multiple times. I don't mind learning, because that's one of my goals for this summer, but at the same time, parallelism is hard. However, if the speed difference is actually very noticeable, I'm willing to pull my hair out for a couple weeks. :P

Thanks in advance.

Answer 1

If maximizing effort to yield is your goal, I would recommend looking at the TPL in .NET. This is probably the simplest way to implement this. Depending on what your code is doing, you could either form a pipeline or just even use Parallel.For (or ForEach) on each "frame".

That being said, if you want to stick to native, non-managed code, a good option might be Microsoft's new Parallel Patterns Library or Intel's Threading Building Blocks. They both have similar constructs to the new TPL, especially for data parallelism, and would make this fairly easy to parallelize, as long as "each frame does not depend on other frames" remains true.

Answer 2

My advice would be to approach this in a step-wise fashion.

1. First, prove that you have a functional non-MATLAB implementation. This is non-trivial and, frankly, I think you should plan on spending 100% of your brain cycles getting correctness first before you think about performance.

2. Partition your solution: prove that you can take the routine that you think is decoupled from the rest of the implementation and isolate it syntactically from the rest of the code. For example, if you were talking about a ray tracer, you could take the math that result from a single view point shooting a ray through a single pixel into the common environment. This is also non-trivial as it will require you to think about what is actually common (e.g., the geometry of the environment, texture maps, etc.) and what is specific to a unique situation (e.g., ray from eye to pixel). Performance profiling is your friend here.

3. Identify the syntax of the libraries or frameworks that you are interested in that will be required to create threads / processes in parallel, launch them and join their results after completion. Note: you'll need to have mutual exclusion on shared data, etc. For example, in Java world, this would be java.util.concurrency.

4. Try creating two (only two) threads to partition your work in half. Write benchmarks that allow you to measure your initial solution, the solution for N=2 threads and profile the hell out of the results.

5. Only then should you even think about further parallelization.

If you follow steps like these, you'll (a) succeed at your actual task (port from MATLAB), (b) have something that works to some known performance metrics and (c) have a clear path forward if you'd like to further exploit parallization opportunities.