c - 与 omp atomic 并行化

Question

我想知道这两个循环在性能上是否等效，a 是一个全局 int 而 M 是一个 int[]:

#pragma omp for
for (int i = 0; i < N; ++i) {
    #pragma omp atomic
    a += M[i];
}

for (int i = 0; i < N; ++i) {
    a += M[i];
}

换句话说，知道唯一的指令必须是原子的，是否值得将其并行化？ 我个人认为加速第二个循环是不可能的，因为这种行为永远不会同时执行超过一次。

Answer 1

没有同步的循环的问题是结果可能不正确。

为了加快计算速度，您可以使用reduction 子句，这样:

#pragma omp parallel for reduction(+:a)

你可以很容易地对计算产生一些反作用:

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main(void)
{
    long long int setup = 0, sum_atomic = 0, sum_simple = 0, sum_reduc = 0, sum_noomp = 0;
    const int N = 100000;
    int *M = malloc(sizeof *M * N);
    double tick[5];

    for (int i = 0; i < N; ++i) {
        M[i] = i;
    }

    /* setup zone to prevent measuring first parallel zone drawback */
    #pragma omp parallel for 
    for (int i = 0; i < N; ++i) {
        setup += M[i];
    }

    /* using single thread execution */
    tick[0] = omp_get_wtime();
    for (int i = 0; i < N; ++i) {
        sum_noomp += M[i];
    }        

    /* using reduction */
    tick[1] = omp_get_wtime();
    #pragma omp parallel for reduction(+:sum_reduc)
    for (int i = 0; i < N; ++i) {
        sum_reduc += M[i];
    }

    /* using openmp, the wrong way */
    tick[2] = omp_get_wtime();
    #pragma omp parallel for
    for (int i = 0; i < N; ++i) {
        sum_simple += M[i];
    }

    /* using atomic keyword */
    tick[3] = omp_get_wtime();
    #pragma omp parallel for
    for (int i = 0; i < N; ++i) {
        #pragma omp atomic
        sum_atomic += M[i];
    }

    tick[4] = omp_get_wtime();

    printf("noomp:  %lld, in %.0f us\n", sum_noomp,  1000000.*(tick[1]-tick[0]));
    printf("reduc:  %lld, in %.0f us\n", sum_reduc,  1000000.*(tick[2]-tick[1]));
    printf("simple: %lld, in %.0f us\n", sum_simple, 1000000.*(tick[3]-tick[2]));   
    printf("atomic: %lld, in %.0f us\n", sum_atomic, 1000000.*(tick[4]-tick[3]));

    free(M);

    return 0;
}

在双核 CPU 上，结果是:

noomp:  4999950000, in 28 us  -- single thread quite fast 
reduc:  4999950000, in 17 us  -- reduction: twice fast
simple: 2024135316, in 12 us  -- incorrect sum 
atomic: 4999950000, in 3686 us -- atomic kw: slow compared to single thread version

所以:

• 更快的方法是使用 openmp reduction
• openmp 在使用 atomic 时比顺序版本慢
• 在没有 reduction 或 atomic 的情况下使用 openmp 结果是错误的

详细信息:

使用 gcc 8.2.1 在 tio machine 上使用 -Wall -O3 -mtune=native -march=native -fopenmp 选项编译，使用 Xeon CPU E5-2650 v4 的两个内核。