Yes memory access patterns seem to be the most common bottleneck for most parallel code. I was implementing a parallel version of quick sort recently and I have similar stories to tell. Optimize the code to avoid cache misses frequently and you end up getting a near optimal speedup.