How to best optimize this load impbalance and data locality

[ntt2011]

Hi everyone,

I have a specific problem of load imbalance and looking for a solution. I'm a physicist and don't want to reinvent the wheel . If the optimal solution is already known, please help. The serial code is following

Code: Select all

double array[N], sum;

sum = 0.0;
for (i=0; i<N; i++) {
   for (j=0; j<i; j++) {
      sum += array[i] * array[j]
}


as you can see, index i does (i-1) multiplications. So it's longer for higher i. My current solution is interleaving the outer loop with "schedule(static,1)". This helps certainly, but is not perfect, and not enough data locality (index i = N-1 have to read the whole array, possibly thrashes the cache.)

Does anybody knows a better solution to this? thank you

[ftinetti]

Hi,

I usually do something like

Code: Select all

   chunk_size = N / (omp_get_num_threads( ) *chunks_per_thread);
   ... schedule(static,chunk_size)


and test some values for chunks_per_thread. This certainly does not solve the issue:

... and not enough data locality (index i = N-1 have to read the whole array, possibly thrashes the cache.)

but the original code does have it anyway, and OpenMP does not optimize the serial code, it just parallelize it.

HTH,

Fernando.

[MarkB]

Hi again!

It would be possible to improve the locality by doing a 2D block cyclic decomposition of the iteration space, which (I think!) can reduce the amount of data
accessed by a thread from O(N) to O(N/sqrt(p)). You can't achieve this with OpenMP's schedule kinds, however, so you would have to use a parallel region and
compute explicitly what each thread does based on its ID. Before you attempt this, though, it would be worth excluding other overheads: it is worth considering the
affinity of the array with respect to how it was last accessed before this operation, and therefore where it is likely to be cached. Could the overhead of the parallel
region itself be a factor? What is the typical value of N, and how long does the loop nest take to execute on one thread?

Hope that helps,
Mark.

[ntt2011]

Thank you. My N is about 40,000 and it's not simple multiplications like my example, but a much more complicated but invariant work.

I decided to do manual thread load assignment like you said, and tried the folding schedule ( 1 thread doing i and N-i blocks of indices ). I got a nice improvement.