Why is parallel execution slower than sequential for this code?

Question

#pragma omp parallel
{
 for (i=1; i<1024; i++)
  #pragma omp for
  for (j=1; j<1024; j++)
   A[i][j] = 2*A[i-1][j];
}

I'm using 12 threads to execute this code. Any suggestions what I must do to speed up?

What is the type of A? Most likely, you're doing so little work in each thread (about 85 additions) that the cost of distributing the work is far greater than the cost of the actual calculation. If you're not doing at least tens-of-thousands of operations in each thread, you're unlikely to benefit from parallelism. — pburka
Are you sure that the code you posted is really what you want to do? You probably forgot a 'for' after the 'parallel' - what you posted will execute the same loop on all threads. This would very easily explain why this code is slower than the serial version... — Spock

Leeor Leeor · Accepted Answer · 2013-10-06T19:05:22

Assuming A's type is smaller than 64Bytes, trying to parallelize the inner loop this way would most likely cause you to have false sharing in cache lines.

Say A is an aligned array of 4-byte ints, you would have A[i][0] through A[i][15] in the same cache line. This means that all 12 threads would attempt to read the line simultaneously, each for the part it needs, this may have resulted in having the line shared between the multiple cores if you left it at that, but you also try to write is back, leading each core to attempt to take ownership on the line in order to modify it.

CPU caches are usually based on MESI based protocols, making a store attempt issue a read-for-ownership that would invalidate the line in each other core except the requester. Issuing 12 parallel (or rather 6 if you have 6 core * 2 threads each) would result in a race where the first one winning the line may very well have it preempted from him by a snoop before it even had a chance to modify it (although that's not likely). The result is quite messy, and may take a while before the line travels to each core in its turn, gets modified, and then snooped out by another core. This recurred for each of the next consecutive groups of 16 elements (again, assuming int).

What you might do is:

make sure that each individual thread is working on its own cacheline, but adding an internal loop that runs over the required number of elements per line, and parallelizing the loops that skips over this number of elements.

This however would prevent you from reaching the full potential of the CPU as you lose the spatial locality and the streaming property of your code. Instead, you may:

Parallelize the outer loop so that each thread works over a few lines, thereby allowing it to own the entire consecutive stream of memory. However, since you need ordering between the lines, you may have to do a little tweaking here (for e.g. a transpose).

There's still a downside here, since if a thread encounters too many streams it might loose track of them. A third approach is, therefore -

Tile the array - break it into sets of, say, 48 lines, distribute them between the threads so that each runs on a few full lines (the transpose trick still applies here, btw), and then continue to the next group

Why is parallel execution slower than sequential for this code?

2 Answers