c - 使用OpenMP任务指令计算PI

Question

我需要使用OpenMP task指令并行化使用Leibniz公式计算π数量的代码π的代码。
Leibniz formula
因此，我得到了一个顺序代码:

double sequential_execution(long long n)
{
    long long i;
    double factor;
    double sum = 0.0;
    double startTime = omp_get_wtime();

    for (i = 0; i < n; i++) {
        factor = (i % 2 == 0) ? 1.0 : -1.0;
        sum += factor / (2 * i + 1);
    }
    double endTime = omp_get_wtime();
    printf("Sequential execution took %f seconds\n", endTime - startTime);
    sum = 4.0 * sum;
    return sum;
}

我的第一个想法是将for循环的内容捕获为n = 100000000的单个任务:

double parallel_execution(long long n)
{
    long long i=0;
    double factor;
    double sum = 0.0;
    long long index; 
    long squareRootN = ceil(sqrt(n));

    double startTime = omp_get_wtime();
#pragma omp parallel default(none) private(i,factor) shared(n,sum) 
{
    #pragma omp single
    {
        for ( i = 0; i < n; i++) {
            #pragma omp task
            {
                factor = (i % 2 == 0) ? 1.0 : -1.0;
                #pragma omp atomic
                sum += factor / (2 * i + 1);
            }
        }
    }
}
    double endTime = omp_get_wtime();
    printf("Parallel execution took %f seconds\n", endTime - startTime);
    sum = 4.0 * sum;
    return sum;
}

但是顺序执行的方式要快得多(顺序时间:0.3 s，参数时间:87 s)
第二个想法是增加一个任务的粒度并 reduce task 数量，方法是将一个从0开始执行n-1的for循环拆分为两个嵌套循环，每个循环从0执行到sqrt(n)-1。现在，每个任务都有一个从0到sqrt(n)-1的for循环，并且生成了sqrt(n)任务，再次为n = 100000000。

double parallel_execution(long long n)
{
    long long i=0;
    double factor;
    double sum = 0.0;
    long long index; 
    long squareRootN = ceil(sqrt(n));

    double startTime = omp_get_wtime();
#pragma omp parallel default(none) shared(sum,n,squareRootN) private(i,factor,index)
{
    #pragma omp single
    {
        for (i=0;i<squareRootN;i++)
        #pragma omp task
        {
            for (long j=0;j<squareRootN;j++)
            {
                index = i*squareRootN + j;
                if (index > n) break;
                factor = (index % 2 == 0)?1.0 : -1.0; 
                #pragma omp atomic
                sum += factor / (2*index + 1);
            }
        }
    }
}
    double endTime = omp_get_wtime();
    printf("Parallel execution took %f seconds\n", endTime - startTime);
    sum = 4.0 * sum;
    return sum;
}

现在，我得到了更好的时间，但是又比顺序执行要慢得多(Seq:0.3s，Par:11s)。
在这一点上，我开始认为不可能使用Task指令来加快速度，但是再次，我做错了什么吗，还是有某种方法可以重组问题以获得更好的性能？
谢谢
编辑:
迄今为止最好的功能:

double parallel_execution(long long n)
{
    double factor;
    int totalThreads = 0;
    long squareRootN = ceil(sqrt(n));
    double master_sum = 0;
    double *sum;
    double startTime = omp_get_wtime();
#pragma omp parallel default(none) shared(sum,n,squareRootN,totalThreads) private(factor)
{
    #pragma omp single
    {
        totalThreads = omp_get_num_threads();
        sum = (double*)calloc(totalThreads,sizeof(double));
        for (long long i=0;i<squareRootN;i++)
        #pragma omp task
        {
            for (long long j=0;j<squareRootN;j++)
            {
                long long index = i*squareRootN + j;
                if (index > n) break;
                factor = (index % 2 == 0)?1.0 : -1.0; 
                sum[omp_get_thread_num()] += factor / (2*index + 1);
            }
        }
    }
}
    for (int i=0;i<totalThreads;i++) master_sum += sum[i];
    double endTime = omp_get_wtime();
    printf("Parallel execution took %f seconds\n", endTime - startTime);
    master_sum*=4;
    return master_sum;
}

输入大小:n = 1000000000
序号时间:3.19 s
面值时间:4 s

Answer 1

您要负担atomic操作和task creation and management.的开销。使用简化的parallel for进行缩减，可以获得更好的加速效果，即:

#pragma omp parallel default(none) shared(n) reduction( + : sum ) 
for ( i = 0; i < n; i++) {
     double factor = (i % 2 == 0) ? 1.0 : -1.0;
     sum += factor / (2 * i + 1);
}

我们可以通过事先将几率与偶数分开来稍微改善顺序代码:

#pragma omp parallel default(none) shared(n, sum) nowait
{
     #pragma omp for reduction( + : sum ) 
     for (int i = 0; i < n; i+=2 ) {
        sum += 1.0 / (2 * i + 1);
    }
    #pragma omp for reduction( + : sum ) 
    for (int i = 1; i < n; i += 2) {
        sum += -1.0 / (2 * i + 1);
    }
}

您可以通过使用一个循环来对该循环的每次迭代执行偶数和赔率计算来进一步改善它。
您无需从循环'i'中生成private，它将在OpenMP中隐式地成为private。
如果确实需要使用任务，则可以尝试通过在线程之间复制变量sum来最大程度地减少同步开销，并在parallel region的末尾手动减少它(我为简单起见，假设n >= 2和n为even):

double sum[total_threads];

#pragma omp parallel default(none) shared(n, sum)
{
    int threadID = omp_get_thread_num();
    sum[threadID] = 0.0;
    #pragma omp single
    {
        for ( i = 0; i < n; i+=2) {
            #pragma omp task
            {
                sum[threadID] += 1.0 / (2 * i + 1);
                sum[threadID] += -1.0 / (2 * (i + 1) + 1);
            }
        }
    }
  }

double master_sum = 0.0;
for(int i = 0; i < total_threads; i++)
    master_sum += sum[i];

如果您使用的是支持OpenMP C的4.5编译器，则可以使用更复杂的构造函数 taskloop Construct ，并将其与变量reduction的sum结合使用。