Interesting that on a six core machine there is very little gain after a Degree of Parallelism of 3. The problem does seem highly data parallelizable (is that a word). So why isn't it able to better utilize the 6 cores?
Law of diminishing returns - the associated overhead with additional parallelization starts creeping up on the benefits of said parallelization.The problem is parallelizable, but it might not be a big enough problem to need access to every core in order to achieve maximum performance.
There's also some graph issues here. For example, on the multithreaded one, it takes two seconds on 1 core. Ideal with full use of 6 cores would be (1sec/6~=0.167sec). The points at 6-8 cores are clearly above 0.1 seconds and probably below 0.33, but it's hard to tell.
Most of the literature in parallel (at least, in the parallel compilers space, where I work) plot speedup (http://en.wikipedia.org/wiki/Speedup) versus number of processors instead of seconds versus threads/processors to show how well a given algorithm and implementation scale. Of course, you have to be careful about what you use for the sequential (T_1) baseline, but it's much easier to understand the data in the graphs.
