使用 OpenMP 任务指令计算 PI

Question

我需要并行化计算数字 π 的代码，使用 π 的 Leibniz 公式和 OpenMP 任务指令。

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;
}

但是顺序执行要快得多。（Seq.时间：0.3 s，Par.时间：87 s）

第二个想法是增加一个任务的粒度并减少任务的数量，其中一个从 0 do 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）。

在这一点上，我开始认为使用任务指令不可能加快速度，但同样，我做错了什么或者有什么方法可以重组问题以使其变得更好表演？谢谢

编辑：迄今为止最好的功能：

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 秒标准杆。时间：4秒

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);
    }
}

您可以通过使用单个循环 for 为该循环的每次迭代执行偶数和奇数计算来进一步改进它。

您不需要从循环 private 中生成 'i'，在 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.

使用 OpenMP 任务指令计算 PI

Calculate PI using OpenMP task directive

c

parallel-processing

multithreading

pi

openmp