Finding minimal element in array, and its index

Question

With OpenMP 3.1, it is possible to have a reduction clause with min:

double m;
#pragma omp parallel for reduction(min:m)
for (int i=0;i< n; i++){ 
  if (a[i]*2 < m) {
    m = a[i] * 2;
} 
return m;

Suppose I also need the index of the minimal element; is there a way to use the reduction clause for this? I believe the alternative is writing the reduction manually using nowait and critical.

Answer 1

Suppose I also need the index of the minimal element; is there a way to use the reduction clause for this?

Unfortunately, no. the list of possible reductions in OpenMP is very … small. In particular, min and max are the only “higher-level” functions and they aren’t customisable. At all.

I have to admit that I don’t like OpenMP’s approach to reductions, precisely because it’s not extensible in the slightest, it is designed only to work on special cases. Granted, those are interesting special cases but it’s still fundamentally a bad approach.

For such operations, you need to implement the reduction yourself by accumulating thread-local results into thread-local variables and combining them at the end.

The easiest way of doing this (and indeed quite close to how OpenMP implements reductions) is to have an array with elements for each thread, and using omp_get_thread_num() to access an element. Note however that this will lead to a performance degradation due to false sharing if the elements in the array share a cache line. To mitigate this, pad the array:

struct min_element_t {
    double min_val;
    size_t min_index;
};

size_t const CACHE_LINE_SIZE = 1024; // for example.
std::vector<min_element_t> mins(threadnum * CACHE_LINE_SIZE);

#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    size_t const index = omp_get_thread_num() * CACHE_LINE_SIZE;
    // operate on mins[index] …
}