c++ - 使用openMP并行获取最小元素的索引

Question

我试着写这段代码

float* theArray; // the array to find the minimum value
int   index, i;
float thisValue, min;

index    = 0;
min = theArray[0];
#pragma omp parallel for reduction(min:min_dist)
for (i=1; i<size; i++) {
    thisValue = theArray[i];
    if (thisValue < min)

    { /* find the min and its array index */

        min = thisValue;

        index    = i;
    }
}
return(index);

但是这个没有输出正确的答案。似乎 min 没问题，但正确的索引已被线程破坏。

我也尝试了一些网上和这里提供的方法(外循环使用parallel for，最终比较使用critical)，但这导致速度下降而不是加速。

我应该怎么做才能使最小值及其索引都正确？谢谢!

Answer 1

我不知道一个优雅的人想要做一个最小化并保存一个索引。我通过找到每个线程的局部最小值和索引，然后找到关键部分中的全局最小值和索引来做到这一点。

index = 0;
min = theArray[0];
#pragma omp parallel
{
    int index_local = index;
    float min_local = min;  
    #pragma omp for nowait
    for (i = 1; i < size; i++) {        
        if (theArray[i] < min_local) {
            min_local = theArray[i];
            index_local = i;
        }
    }
    #pragma omp critical 
    {
        if (min_local < min) {
            min = min_local;
            index = index_local;
        }
    }
}

使用 OpenMP 4.0 可以使用用户定义的缩减。用户定义的最小减少量可以这样定义

struct Compare { float val; sizt_t index; };    
#pragma omp declare reduction(minimum : struct Compare : omp_out = omp_in.val < omp_out.val ? omp_in : omp_out)

那么归约可以这样进行

struct Compare min; 
min.val = theArray[0]; 
min.index = 0;
#pragma omp parallel for reduction(minimum:min)
for(int i = 1; i<size; i++) {
    if(theArray[i]<min.val) { 
        min.val = a[i];
        min.index = i;
    }
}

适用于 C 和 C++。除了简化代码之外，用户定义的缩减还有其他优势。有多种算法可以进行归约。例如，合并可以在 O(number of threads) 或 O(Log(number of threads)) 中完成。我给出的第一个解决方案是在 O 中完成的(线程数) 但是，使用用户定义的缩减让 OpenMP 选择算法。