Parallel version of loop not faster than serial version

Question

I'm writing a program in C++ to perform a simulation of particular system. For each timestep, the biggest part of the execution is taking up by a single loop. Fortunately this is embarassingly parallel, so I decided to use Boost Threads to parallelize it (I'm running on a 2 core machine). I would expect at speedup close to 2 times the serial version, since there is no locking. However I am finding that there is no speedup at all.

I implemented the parallel version of the loop as follows:

• Wake up the two threads (they are blocked on a barrier).

• Each thread then performs the following:

  • Atomically fetch and increment a global counter.
  • Retrieve the particle with that index.
  • Perform the computation on that particle, storing the result in a separate array
  • Wait on a job finished barrier

• The main thread waits on the job finished barrier.

I used this approach since it should provide good load balancing (since each computation may take differing amounts of time). I am really curious as to what could possibly cause this slowdown. I always read that atomic variables are fast, but now I'm starting to wonder whether they have their performance costs.

If anybody has some ideas what to look for or any hints I would really appreciate it. I've been bashing my head on it for a week, and profiling has not revealed much.

EDIT: Problem solved! I'm going to detail how I solved this problem. I used gprof again, but this time compiled without the optimization flag (-O3). Immediately, the profiler indicated that I was spending an incredible amount of time in the function which performs the computation on each individual particle: much more than in the serial version.

This function is virtual and accessed polymorphically. I changed the code to access it directly rather than through the vtable and voila' the parallel version produced a speedup of nearly 2! The same change on the serial version had little effect.

I'm not sure why this is so, and would be interested if anyone knows!

Thanks to all the posters. You all helped to some extent and it will be very difficult to accept one answer.

Answer 1

Perform the computation on that particle, storing the result in a separate array

How heavy are computations?

• Generally speaking atomic counter may cost hundreds of clock cycles and it is quite important to see that you do not only increment counters.
• Also try to see how much job each thread does - do they cooperate well (i.e. on each cycle each proceeds about half of particle).
• Try to subdivide the job to bigger chunks then single particle (let's say 100 particles and so on).
• See how much job is done outside of threads.

Honestly... it looks like what are you talking about is a bug.