使用OpenMP并行化C++代码,计算实际上并行较慢

Question

我有以下要并行化的代码:

int ncip( int dim, double R)
{   
    int i;
    int r = (int)floor(R);
    if (dim == 1)
    {   
        return 1 + 2*r; 
    }
    int n = ncip(dim-1, R); // last coord 0

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

    return n;
}

当我尝试并行化for循环时,没有openmp运行的程序执行时间是6.956s,我的执行时间大于3分钟(这是因为我自己结束了).在并行化此代码方面我做错了什么？

第二次尝试

    int ncip( int dim, double R)
{   
int i;
int r = (int)floor( R);
if ( dim == 1)
{   return 1 + 2*r; 
}


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

}

return n;

}

Answer 1

你做错了!

(1)变量中有数据竞争n.如果要并行化在同一内存区域中写入的代码,则必须使用缩减(在for中),原子或关键来避免数据危害.

(2)可能你已经启用了嵌套并行,所以每次调用函数时程序都会创建一个新的并行区域ncip.应该是这个主要问题.对于递归函数,我建议你只创建一个并行区域,然后使用pragma omp task.

不要与之并行#pragma omp for并尝试#pragma omp task.看这个例子:

int ncip(int dim, double R){
    ...
    #pragma omp task
    ncip(XX, XX);

    #pragma omp taskwait
    ...
}

int main(int argc, char *argv[]) {
    #pragma omp parallel
    {
        #pragma omp single 
        ncip(XX, XX);
    } 
    return(0); 
}

更新:

//Detailed version (without omp for and data races)
int ncip(int dim, double R){
    int n, r = (int)floor(R);

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

    n = ncip(dim-1, R); // last coord 0

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

            #pragma omp atomic
            n += aux;
        }
    }
    #pragma omp taskwait
    return n;
}

PS:你不会从中获得加速,因为创建任务的开销大于单个任务的工作.您可以做的最好的事情是将此算法重写为迭代版本,然后尝试并行化它.