OpenMP Директива сокращения ручной работы

Question

Я работаю над факториальной функцией.Я должен написать его параллельную версию, используя OpenMP.

double sequentialFactorial(const int N) {
    double result = 1;
    for(int i = 1; i <= N; i++) {
        result *= i;
    }
    return result;
}

Хорошо известно, что этот алгоритм может быть эффективно распараллелен с использованием техники сокращения.

Мне известно о существовании предложения reduction ( стандарт §§ 2.15.3.6).

double parallelAutomaticFactorial(const int N) {
    double result = 1;
    #pragma omp parallel for reduction(*:result)
    for (int i=1; i <= N; i++) 
        result *= i;
    return result;
}

Однако я хочу попробовать реализоватьТехника сокращения "ручной работы".

double parallelHandmadeFactorial(const int N) {

    // maximum number of threads
    const int N_THREADS = omp_get_max_threads();

    // table of partial results
    double* partial = new double[N_THREADS];
    for(int i = 0; i < N_THREADS; i++) {
        partial[i] = 1;
    }

    // reduction tecnique
    #pragma omp parallel for
    for(int i = 1; i <= N; i++) {
        int thread_index = omp_get_thread_num();
        partial[thread_index] *= i;
    }

    // fold results
    double result = 1;
    for(int i = 0; i < N_THREADS; i++) {
        result *= partial[i];
    }

    delete partial;

    return result;
}

Я ожидаю, что производительность двух последних фрагментов будет очень схожей и лучше, чем в первом.Тем не менее, средняя производительность составляет:

Sequential Factorial          3500 ms
Parallel Handmade Factorial   6100 ms
Parallel Automatic Factorial   600 ms

Я что-то упустил?

---

Благодаря @Gilles и @PW этот код работает, как и ожидалось

double parallelNoWaitFactorial(const int N) {

    double result = 1;

    #pragma omp parallel
    {
        double my_local_result = 1;

        // removing nowait does not change the performance
        #pragma omp for nowait
        for(int i = 1; i <= N; i++)
            my_local_result *= i;

        #pragma omp atomic
        result *= my_local_result;
    }

    return result;
}

Answer 1

Если элементы массива совместно используют строку кэша, это приводит к ложному совместному использованию , что в дальнейшем приводит к снижению производительности.

Чтобы избежать этого:

• Используйте личную переменную double partial вместо double массива partial.
• Используйте результат partial каждого потока, чтобы вычислить окончательный result в критической области
• Этот конечный result должен быть переменной, не являющейся частной для параллельной области.

Критическая область будет выглядеть так:

#pragma omp critical
    result *= partial;