使用 OpenMP 应用基于任务的并行性

Question

我有以下代码，我正在尝试使用 OpenMP 对其进行并行化处理。

int ncip(int dim, double R){
int n, r = (int)floor(R);

if (dim == 1) return 1 + 2*r; 

#pragma omp task shared(n, dim)
n = ncip(dim-1, R); // last coord 0

for(int i=1; i<=r; ++i){   
    #pragma omp task shared(n, dim)
    n += 2*ncip(dim-1, sqrt(R*R - i*i) ); // last coord +- i

}
return n;
}

由于递归调用，我需要应用基于任务的并行性，但我的计算没有显示任何加速。我究竟做错了什么？有什么建议可以帮助加快计算速度吗？

Answer 1

并行不是免费的，因此，不管一个简单的 pragma 看起来多么天真，例如#pragma omp task，它的成本很高，因为它隐藏了创建和同步线程、分配和排队任务等的整个逻辑。只有在计算强度和多线程本身的开销之间找到平衡，和问题的大小（更不用说多线程的副作用，如错误共享等），您将观察到积极的 (>1) 加速。

另外，请记住线程的数量总是有限的。一旦你已经为每个线程创建了足够的工作负载，不要试图通过添加额外的工作共享结构来提升你的代码——一个线程不能神奇地分成两个独立的指令流。也就是说，如果您有一个已经并行的最顶层循环，并且它有足够的迭代次数来保持所有可用线程忙碌，那么您将无法尝试提取嵌套并行性。

话虽如此，除非您可以使用其他一些技术，例如记住部分结果或完全删除递归，否则只需使用一个最顶层的并行循环和一个缩减子句来确保线程安全地访问共享变量：

#pragma omp parallel for reduction(+:n)
for (int i = 1; i <= r; ++i)
{
    n = n + (2 * ncip(dim-1, sqrt(R*R - i*i)));
}

然后是一个简单的顺序函数：

int ncip(int dim, double R)
{
    int n, r = (int)floor(R);

    if (dim == 1)
    {
        return 1 + 2*r; 
    }

    n = ncip(dim-1, R);

    for (int i = 1; i <= r; ++i)
    {   
        n = n + (2 * ncip(dim-1, sqrt(R*R - i*i)));
    }

    return n;
}

DEMO

使用 OpenMP 应用基于任务的并行性

Applying task based parallelism using OpenMP

c++

openmp