Распараллелить с omp atomic

Question

Интересно, эквивалентны ли эти два цикла по производительности, если a является глобальным int, а M a 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;
}

Для двухъядерного процессора результат:

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
• Результат openmp неверен при использовании без reduction или atomic

Подробности:

Скомпилировано с gcc 8.2.1 с опцией -Wall -O3 -mtune=native -march=native -fopenmp на tio machine , с использованием двух ядер процессора Xeon E5-2650 v4.