Обновление массива из 1000000 элементов параллельно

Question

Это вопрос, который задан в предыдущем экзамене.

Рассмотрим следующий фрагмент кода C:

int i, array[1000000]; 
array[0] = 0; 
for (i = 1; i < 1000000; i++) 
array[i] = array[i-1] + 3; 

Можем ли мы просто запустить 1000000. заявление обновление массива в цикл параллельно? Если нет, измените оператор обновления так, чтобы он мог работать параллельно и все равно производить то же окончательное содержимое массива .

Я понимаю, что невозможно просто запустить 1 000 000 операторов обновления массива в цикле for параллельно. Только способы, которые мне приходят в голову, - использовать рекурсию, которая не параллельна, и использовать 1000000 потоков, что не является отличной идеей.

Итак, есть ли другой способ сделать это параллельно с очень небольшими заявлениями на обновление? Мы можем использовать openMPI или openCL

Редактировать: Это не вопрос домашней работы, но я думаю, что это было задано как домашнее задание в какой-то школе. Это из прошлой экзаменационной работы. Я загрузил его here

Answer 1

Проблема в том, что вы не можете распараллелить этот цикл, но не только с двумя потоками, так как каждая итерация зависит от предыдущего.

Ваш алгоритм производит:

array[0] = 0; 
array[1] = 3; 
array[2] = 6; 
... 

Таким образом, вы можете написать заявление обновления таким образом, что каждая итерация не зависит от предыдущего:

int i, array[1000000]; 
array[0] = 0; 
for (i = 1; i < 1000000; i++) 
    array[i] = 3*i; 

В этом случае вы удалили зависимость данных, и вы можете легко распараллелить цикл (например, с помощью OpenMP или MPI).