c++ - OpenMP 初学者 - 圈内问题

Question

我是 OpenMP 的初学者，我正在尝试并行化以下函数:

void calc(double *x, int *l[N], int d[N], double *z){

    #pragma omp parallel for
    for(int i=0; i<N; i++){

        double tmp = d[i]>0 ? ((double) z[i] / d[i]) : ((double) z[i] / N);

        for(int j=0; j<d[i]; j++)
            x[l[i][j]] += tmp;

    }

}

但对于 N=100000，顺序时间大约为 50 秒，如果有 2 个或更多线程，它会长达几分钟。

L 指针数组随机包含 1 到 30 个元素(由 d 数组中的相应位置给出)并且元素在 0 到 N 之间变化，所以我知道我有一个负载平衡问题但是如果我有一个引导或动态调度(甚至自动)的时间更糟。

我也知道问题显然出在对 x 数组的访问中，因为它没有被连续访问，但是有没有办法解决这个问题并在这个函数中有某种加速？

提前致谢!

Answer 1

假设您有能力使用一些额外的空间来完成它，您可能可以加快速度。

基本思想是为每个线程创建一个单独的求和数组，然后当它们全部完成后，将这些单独拷贝中的相应元素相加，最后将该结果的每个元素添加到原始 x。

只要 x 相当小，这可能是非常合理的。如果 x 可能真的很大，它可能会很快变得不实用。鉴于 L 显然只有大约 30 个元素，听起来 x 可能也被限制在大约 30 个元素(无论如何在运行这段代码时实际上可以使用) .如果这是正确的，那么每个线程都有一个单独的拷贝应该不会造成重大问题。