OpenMP: Алгоритм суммирования префиксов

Question

Я пытаюсь реализовать алгоритм суммирования префиксов в C, используя OpenMP, и я застрял.

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

int main(int argc, char* argv[])
{
    int p = 5;
    int X[5] = { 1, 5, 4, 2, 3 };
    int* Y = (int*)malloc(p * sizeof(int));

    for (int i = 0; i < p; i++)
        printf("%d ", X[i]);
    printf("\n");

    Y[0] = X[0];

    int i;
    #pragma omp parallel for num_threads(4)
    for (i = 1; i < p; i++)
        Y[i] = X[i - 1] + X[i];

    int k = 2;
    while (k < p)
    {
        int i;
        #pragma omp parallel for
        for (i = k; i < p; i++)
            Y[i] = Y[i - k] + Y[i];
        k += k;
    }

    for (int i = 0; i < p; i++)
        printf("%d ", Y[i]);
    printf("\n");

    system("pause");
    return 0;
}

Что должен делать этот код?

Ввод числа в X,
вывод числа (префиксы) в Y
и число равно p.

X = 1, 5, 4, 2, 3

Стадия I.

Y[0] = X[0];

Y[0] = 1

Этап II.

int i;
#pragma omp parallel for num_threads(4)
for (i = 1; i < p; i++)
    Y[i] = X[i - 1] + X[i];

Пример:

Y[1] = X[0] + X[1] = 6
Y[2] = X[1] + X[2] = 9
Y[2] = X[2] + X[3] = 6
Y[4] = X[3] + X[4] = 5

Стадия III. (где я застрял)

int k = 2;
while (k < p)
{
    int i;
    #pragma omp parallel for
    for (i = k; i < p; i++)
        Y[i] = Y[i - k] + Y[i];
    k += k;
}

Пример:

k = 2
Y[2] = Y[0] + Y[2] = 1 + 9 = 10
Y[3] = Y[1] + Y[3] = 6 + 6 = 12
Y[4] = Y[2] + Y[4] = 10 + 5 = 15

Над10 + 5 = 15 должно быть 9 + 5 = 14, но Y[2] был перезаписан другим потоком.Я хочу использовать это Y[2], что было до запуска цикла for.

Пример:

k = 4
Y[4] = Y[0] + Y[4] = 1 + 15 = 16

Результат: 1, 6, 10, 12, 16. Ожидаемый хороший результат: 1, 6, 10, 12, 15.

Answer 1

Над 10 + 5 = 15 должно быть 9 + 5 = 14, но Y[2] был перезаписан другим потоком.Я хочу использовать это Y[2] то, что было до запуска цикла for.

С OpenMP вам всегда нужно учитывать, является ли ваш код правильным для последовательного случая с одним потоком, потому что

1. На самом деле он может работать таким образом, и
2. Если он некорректен поочередно, то он практически наверняка также неверен как параллельная программа.

Ваш код неверен серийно.Похоже, вы могли бы это исправить, запустив проблемный цикл в обратном направлении, от i = p - 1 до k, но на самом деле этого недостаточно для параллельной работы.

Похоже, что ваша лучшая ставка заключается в накопленииваши частичные результаты в другой массив, чем содержит результаты предыдущего цикла.Например, вы можете переключаться между X и Y в качестве источника данных и результата, с небольшим указателем на смазку итеративных колес.Или вы можете сделать это немного проще, используя 2D-массив вместо отдельных X и Y.

Answer 2

ОБНОВЛЕНИЕ для Стадии III.

int num_threads = 8;
int k = 2;
while (k < p)
{
    #pragma omp parallel for ordered num_threads(k < num_threads ? 1 : num_threads)
    for (i = p - 1; i >= k; i--)
    {
        Y[i] = Y[i - k] + Y[i];
    }
    k += k;
}

Код выше решил мою проблему. Теперь он работает параллельно, кроме первых нескольких раундов.