找到最近对时的OpenMP竞争条件

Question

我正在做一个任务，找到两个不相交的集合A和B之间最接近的一对。我正在使用OpenMP并行化算法的递归，但我遇到了一些数据竞争。我是OpenMP的新手，所以我认为它与错误的私有/共享变量有关。我把完整的算法放在下面：

float OMPParticleSim::efficient_closest_pair(int n, vector<Particle> & p, vector<Particle> & q)
{
// brute force
if(n <= 3) {
    float m = numeric_limits<float>::max();

    for(int i = 0; i < n - 2; i++) {
        for(int j = i + 1; j < n - 1; j++) {
            if((set_A.find(p[i].id) != set_A.end() && set_A.find(p[j].id) != set_A.end()) || (set_B.find(p[i].id) != set_B.end() && set_B.find(p[j].id) != set_B.end())) {
                continue;
            }

            float distsq = pow(p[i].x - p[j].x, 2) + pow(p[i].y - p[j].y, 2) + pow(p[i].z - p[j].z, 2);
            pair<pair<Particle, Particle>, float> pa = make_pair(make_pair(p[i], p[j]), sqrt(distsq));

            #pragma omp critical
            insert(pa);

            m = min(m, distsq);
        }
    }

    return sqrt(m);
}

// copy first ceil(n/2) points of p to pl
vector<Particle> pl;
int ceiling = ceil(n/2);

for(int i = 0; i < ceiling; i++) {
    pl.push_back(p[i]);
}

// copy first ceil(n/2) points of q to ql
vector<Particle> ql;

for(int i = 0; i < ceiling; i++) {
    ql.push_back(q[i]);
}

// copy remaining floor(n/2) points of p to pr
vector<Particle> pr;

for(int i = ceiling; i < p.size(); i++) {
    pr.push_back(p[i]);
}

// copy remaining floor(n/2) points of q to qr
vector<Particle> qr;

for(int i = ceiling; i < q.size(); i++) {
    qr.push_back(p[i]);
}

float dl, dr, d;

#pragma omp task firstprivate(pl, ql, p, q, n) private(dl) shared(closest_pairs)
dl = efficient_closest_pair(ceil(n / 2), pl, ql);

#pragma omp task firstprivate(pl, ql, p, q, n) private(dr) shared(closest_pairs)
dr = efficient_closest_pair(ceil(n / 2), pr, qr);

#pragma omp taskwait
d = min(dl, dr);

float m = p[ceil(n / 2) - 1].x;
vector<Particle> s;

for(int i = 0; i < q.size(); i++) {
    if(fabs(q[i].x - m) < d) {
        s.push_back(Particle(q[i]));
    }
}

int num = s.size();
float dminsq = d * d;

for (int i = 0; i < num - 2; i++) {
    int k = i + 1;

    while(k <= num - 1 && pow(s[k].y - s[i].y, 2) < dminsq) {
        if((set_A.find(s[i].id) != set_A.end() && set_A.find(s[k].id) != set_A.end()) || (set_B.find(s[i].id) != set_B.end() && set_B.find(s[k].id) != set_B.end())) {
            k++;
            continue;
        }

        float dist = pow(s[k].x - s[i].x, 2) + pow(s[k].y - s[i].y, 2) + pow(s[k].z - s[i].z, 2);
        pair<pair<Particle, Particle>, float> pa = make_pair(make_pair(s[i], s[k]), sqrt(dist));

        #pragma omp critical
        insert(pa);

        dminsq = min(dist, dminsq);
        k++;
    }
}

return sqrt(dminsq);
}

insert方法如下所示：

void OMPParticleSim::insert(pair<pair<Particle, Particle>, float> & pair) {
    if(closest_pairs.size() == 0) {
        closest_pairs.push_back(pair);
        return;
    }

    for(int i = 0; i < closest_pairs.size(); ++i) {
        if(closest_pairs[i].second > pair.second) {
            closest_pairs.insert(closest_pairs.begin() + i, 1, pair);
            break;
        }
    }

    if(closest_pairs.size() > k) {
        closest_pairs.pop_back();
    }
}

并行区域的起点在这里：

void OMPParticleSim::do_closest_pair(int num_threads) {
    vector<Particle> p = set;

    // presort on x
    sort(p.begin(), p.end(), sortxomp);

    vector<Particle> q = p;

    // presort on y
    sort(q.begin(), q.end(), sortyomp);
    float cp;

    #pragma omp parallel num_threads(num_threads) 
    {
        #pragma omp single 
        {
            cp = efficient_closest_pair(set.size(), p, q);
        }
    }

    sort(closest_pairs.begin(), closest_pairs.end(), sortpairsomp);
}

所有结果都存储在nearest_pairs列表中并输出到文件中。我知道存在数据竞争的原因是因为某些粒子ID是负数（所有粒子ID都是正数），并且多次运行程序会导致将不同的值写入文件。任何帮助都会很棒！

Answer 1

错误是dl和dr应该在任务之间共享。