OpenMP collapse parallel for with parallel max-reduction?

Question

I have the following nested loops that I want to collapse into one for parallelization. Unfortunately the inner loop is a max-reduction rather than standard for loop thus collapse(2) directive apparently can't be used here. Is there any way to collapse these two loops anyway? Thanks!

(note that s is the number of sublists and n is the length of each sublist and suppose n >> s)

    #pragma omp parallel for default(shared) private(i,j)
    for (i=0; i<n; i++) {
        rank[i] = 0;
        for (j=0; j<s; j++)
            if (rank[i] < sublistrank[j][i])
                rank[i] = sublistrank[j][i]; 
    }

Answer 1

In this code the best idea is not to parallelize the inner loop at all, but make sure it is properly vectorized. The inner loop does not access the memory continuously, which prevents vectorization and results in a poor cache utilization. You should rewrite your entire code to ensure continuous memory access (e.g. change the order of indices and use sublistrank[i][j] instead of sublistrank[j][i]).

If also beneficial to use a temporary variable for comparisons and assign it to rank[i] after the loop.

Another comment is that always use your variables in their minimum required scope, it also helps the compiler to create more optimized code. Putting it together your code should look like something like this (assuming you use unsigned int for rank and loop variables)

#pragma omp parallel for default(none) shared(sublistrank, rank)
    for (unsigned int i=0; i<n; i++) {
        unsigned int max=0;
        for (unsigned int j=0; j<s; j++)
            if (max < sublistrank[i][j])
                max = sublistrank[i][j]; 
        rank[i]=max;
    }

I have compared your code and this code on CompilerExporer. You can see that the compiler is able to vectorize it, but not the old one.

Note also that if n is small, the parallel overhead may be bigger than the benefit of parallelization.