OMP - 减少到基于另一个值的值

Question

我正在尝试并行化一个简单的算法来找到旅行商问题的合适解决方案。

设path为对应于城市的整数数组。在每次尝试中，选择 path 数组的两个随机索引进行切换。此开关影响到前后节点的距离，总共 4 个距离。如果采用它们的总和，我们可以推断出我们执行的切换是否产生了比旧路径更好或更差的路径。在前一种情况下，开关被保留，我们可以进行下一次尝试。

并行化此算法的一个想法是同时尝试 N 不同的切换，并执行生成最短路径的切换。到目前为止我的代码如下：

float switchCities(){

    int switchCandidates[NUM_THREADS][2];
    float minDist;

    #pragma omp parallel for reduction(*need help here*)
    for(int i=0; i<NUM_THREADS; i++){

        //selecting 2 random candidates excluding the first and last
        switchCandidates[i][0] = rand() % (N-1) + 1;
        switchCandidates[i][1] = rand() % (N-1) + 1;

        float oldDist = localDist(switchCandidates[i][0], switchCandidates[i][1]);
        float newDist = localSwitchedDist(switchCandidates[i][0], switchCandidates[i][1]);

        if(newDist >= oldDist){
            newDist = FLT_MAX;
        }

    }

    //perform the switch
    ....

    return minDist;
}

通过将无效开关距离设置为某个较大的数字，我可以将距离减小到最小值，但是我对路径本身比距离更感兴趣。是否可以执行减少，以便我最终得到导致最小距离的索引 i？

Answer 1

使用共享向量保存信息，然后让单个线程使用该向量找出最佳选择：

float switchCities(){

    int switchCandidates[NUM_THREADS][2];
    float minDist;

    std::vector<std::pair<float,int> > best(omp_get_max_threads(), std::make_pair<float,int>(9e999999, -1));

    #pragma omp parallel for
    for(int i=0; i<NUM_THREADS; i++){
        //selecting 2 random candidates excluding the first and last
        switchCandidates[i][0] = rand() % (N-1) + 1;
        switchCandidates[i][1] = rand() % (N-1) + 1;

        float oldDist = localDist(switchCandidates[i][0], switchCandidates[i][1]);
        float newDist = localSwitchedDist(switchCandidates[i][0], switchCandidates[i][1]);

        auto &my_best = best.at(omp_get_thread_num());
        if(newDist >= my_best.first){
            my_best.first = newDist;
            my_best.second = i;
        }
    }

    //have one thread look at the `best` vector and find the best value here

    return minDist;
}

OMP - 减少到基于另一个值的值

OMP - Reduce to a value based on another value

c

parallel-processing

openmp

reduction