Why is Having More Threads than Cores Faster?

Question

I've implemented a version of PageRank in a multithreaded version. I'm running it on a 4-core Q6600. When I run it set to create 4 threads, I get:

real    6.968s
user   26.020s
sys     0.050s

When I run with 128 threads I get:

real    0.545s
user    1.330s
sys     0.040s

This makes no sense to me. The basic algorithm is a sum-reduce:

1. All threads sum a subset of the input;
2. Synchronize;
3. Each thread then accumulates part of the results from the other threads;
4. The main thread sums an intermediate value from all the threads and then determines whether to continue.

Profiling hasn't helped. I'm not sure what data would be helpful to understand my code - please just ask.

It really has me puzzled.

Answer 1

Deliberately creating more threads than processors is a standard technique used to make use of "spare cycles" where a thread is blocked waiting for something, whether that's I/O, a mutex, or something else by providing some other useful work for the processor to do.

If your threads are doing I/O then this is a strong contender for the speed-up: as each thread blocks waiting for the I/O, the processor can run the other threads until they too block for I/O, hopefully by which time the data for the first thread is ready, and so forth.

Another possible cause of the speed up is that your threads are experiencing false sharing. If you have two threads writing data to different values on the same cache line (e.g. adjacent elements of an array) then this will block the CPU whilst the cache line is transferred back and forth. By adding more threads you decrease the likelihood that they are operating on adjacent elements, and thus reduce the chance of false sharing. You can easily test this by adding extra padding to your data elements so they are each at least 64 bytes in size (the typical cache line size). If your 4-thread code speeds up, this was the problem.