Можно ли распараллелить оба следующих цикла?

Question

do i=2, n-1
   y(i) = y(i+1)
end do

do i=2, n-1
   y(i) = y(i+1) - y(i-1)
end do

Привет, мне интересно, можно ли распараллелить оба этих цикла? Кажется, что часть y(i+1) делает это невозможным. Потому что это зависит от значения, которое еще не сгенерировано.

Answer 1

В обоих случаях у вас есть так называемая «зависимость, переносимая циклом»

do i=2, n-1    
    y(i) = y(i+1) - y(i-1) 
end do

Расчет для y (i) зависит от y (i +/- 1), поскольку в параллельном цикле вы не можете гарантироватьпорядок, в котором будет выполняться i, y (i + 1), возможно, уже был обновлен до его нового значения до вычисления y (i).Хуже того, y (i + 1) может обновляться в одном потоке, в то время как другой поток пытается прочитать то, что может быть поврежденным значением (поскольку его данные обновляются только наполовину. В любом случае вы получитенеправильные ответы.

Лучшее решение здесь - иметь доступный для записи и доступный для записи массив

do i=2, n-1    
    yNew(i) = yOld(i+1) - yOld(i-1) 
end do
swap(yOld, yNew)

Теперь ваша проблема исчезнет, ​​поскольку массив y не обновляется параллельным циклом. Если ваш язык поддерживаетуказатели, которые вы можете легко поменять местами новые / старые массивы, поддерживая указатели на них и просто меняя указатели. Единственным дополнительным расходом является то, что вам нужно хранить дополнительную копию ваших данных как копию только для чтения, чтобы цикл мог ссылаться на нее.

Answer 2

Конечно, вы можете.

Вам просто нужно написать это так, чтобы каждая параллельная задача не «наступала» на память какой-либо другой задачи.

Во втором случаеЭто было бы сложно, но я уверен, что это возможно, если подумать достаточно.

Answer 3

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

for all i in [2, n-2] in parallel do
   y'(i) = y(i+1)
end do

Если вы хотите использовать только два блока параллельного выполнения, вам потребуется хранилище для одного элемента массива:

e = y(n/2)
for all i in [0, 1] in parallel do
   for j in [1, n/2 - 1] do
      y(i*n/2 + j) = (y(i*n/2 + j)
   end do
end do
y(n/2 - 1) = e

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

Второй цикл не может быть распараллелен, поскольку вы должны вычислить y (i-1)вычислить у (я).Ни за что.Это не проблема для первого цикла, так как все значения, которые в конечном итоге читаются, гарантированно будут иметь правильное значение перед началом цикла.Не так во втором!

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

Answer 4

Если y является массивом (он выглядит как функция, но тогда вы назначаете вызов функции), то часть y (i + 1) уже существует, хотя все еще проблематично для распараллеливания.