使用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是正常的,但正确的索引已被线程破坏.

我也尝试过在互联网和这里提供的一些方法(使用并行用于外部循环并使用关键进行最终比较)但这会导致速度下降而不是加速.

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

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(number of threads)是使用用户定义的缩减,让我们的OpenMP选择算法.

Answer 2

因为您不仅要尝试找到最小值 ( reduction(min:___))，还要保留索引，因此需要使检查变得至关重要。这会显着减慢循环速度（如报告所述）。一般来说，请确保有足够的工作，这样您就不会像这个问题一样遇到开销。另一种方法是让每个线程找到最小值及其索引，并将它们保存到一个唯一的变量中，并让主线程对它们进行最终检查，如以下程序所示。

#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include <omp.h>

using std::cout;
using std::vector;

void initializeVector(vector<double>& v)
{
    std::mt19937 generator(time(NULL));
    std::uniform_real_distribution<double> dis(0.0, 1.0);
    v.resize(100000000);
    for(int i = 0; i < v.size(); i++)
    {
        v[i] = dis(generator);
    }
}

int main()
{
    vector<double> vec;
    initializeVector(vec);

    float minVal = vec[0];
    int minInd = 0;

    int startTime = clock();

    for(int i = 1; i < vec.size(); i++)
    {
        if(vec[i] < minVal)
        {
            minVal = vec[i];
            minInd = i;
        }

    }

    int elapsedTime1 = clock() - startTime;

    // Change the number of threads accordingly
    vector<float> threadRes(4, std::numeric_limits<float>::max());
    vector<int>   threadInd(4);

    startTime = clock();
#pragma omp parallel for
    for(int i = 0; i < vec.size(); i++)
    {
        {
            if(vec[i] < threadRes[omp_get_thread_num()])
            {
                threadRes[omp_get_thread_num()] = vec[i];
                threadInd[omp_get_thread_num()] = i;
            }
        }

    }

    float minVal2 = threadRes[0];
    int minInd2 = threadInd[0];

    for(int i = 1; i < threadRes.size(); i++)
    {
        if(threadRes[i] < minVal2)
        {
            minVal2 = threadRes[i];
            minInd2 = threadInd[i];
        }
    }

    int elapsedTime2 = clock() - startTime;

    cout << "Min " << minVal << " at " << minInd << " took " << elapsedTime1 << std::endl;
    cout << "Min " << minVal2 << " at " << minInd2 << " took " << elapsedTime2 << std::endl;
}

请注意，在进行优化且循环中无需执行任何其他操作的情况下，串行版本似乎仍然占据主导地位。关闭优化后，OMP 占据上风。

PS你写的reduction(min:min_dist)，然后继续使用 min 而不是min_dist。