Параллельные операции в массиве с зависимостью

Question

Мне нужна помощь для решения этой проблемы, у меня есть код с операциями, выполняемыми над предыдущим элементом массива, и мне нужно распараллеливать, используя задачи openmp, однако я знаю, как удалить эту зависимость. Мой учитель говорит, что в этом случае не интересно использовать зависимость (in, out). Как бы мне удалить то, что зависело от этого тогда?

void sum_sequential(float a[N]) {
        a[0] = 1.0;

    for (int i = 1; i < N; i++)
        a[i] = 2 * a[i-1] + 1;
}

Answer 1

Вы совершенно правы, что существует зависимость от данных. Значение, которое нужно вычислить для каждого элемента, выражается в терминах значения, ранее вычисленного для предыдущего элемента, поэтому этот алгоритм по своей сути является последовательным. Нет никакого практического преимущества в его распараллеливании, поскольку успешная работа с зависимостями не оставляет места для параллелизма.

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