Search for the minimum element in the 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 a minimal element; is there any way to use the reduction clause for this? I believe the alternative writes down the abbreviation manually with nowait and critical .

Answer 1

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

Unfortunately not. the list of possible abbreviations in OpenMP is very ... small. In particular, min and max are the only "higher level" functions and are customizable. For everyone.

I must admit that I do not like the OpenMPs approach to abbreviations, precisely because it does not expand in the slightest degree, it is intended only for work in special cases. Of course, these are interesting special cases, but still a fundamentally bad approach.

For such operations, you need to implement the abbreviation yourself by copying the local stream results into local stream variables and combining them at the end.

The easiest way to do this (and even very close to how OpenMP implements abbreviations) is to have an array with elements for each thread and use omp_get_thread_num() to access the element. Note, however, that this will lead to performance degradation due to a false exchange if the elements of the array share the cache line. To reduce this, apply an 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] … }