Развертывание петли для достижения параллелизма - PullRequest
Новая
       13

Развертывание петли для достижения параллелизма

0 голосов
/ 12 марта 2012

Во время лекции мой профессор дал нам следующий цикл: 

for (int i = 0; i < 100; i++) {
    a[i] = a[i] + b[i];
    b[i + 1] = c[i] + d[i];
}

Он указал на зависимость между итерациями цикла, потому что строка три устанавливает значение, которое используется в следующей итерации в строке 2 (устанавливает b[i+1], который становится b[i] в следующей итерации).Поэтому мы не можем запускать каждую итерацию цикла параллельно.

Затем он дал нам развернутую версию: 

a[1] = a[1] + b[1];
for (int i = 0; i < 98; i++) {
    b[i+1] = c[i] + d[i];
    a[i+1] = a[i] + b[i];
}
b[99] = c[99] + d[99];

Он утверждает, что теперь каждая итерация цикла может быть запущена впараллельно.Проблема, которую я вижу, состоит в том, что в строке 3 задается, что станет b[i] в следующей итерации в строке 4, и поэтому мы все еще не можем выполнять каждую итерацию параллельно.

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

1 Ответ

1 голос
/ 12 марта 2012

Полагаю, вы ошиблись, записав развернутую версию, которую дал ваш профессор.Чтобы быть эквивалентным первому алгоритму, он должен выглядеть следующим образом: 

a[0] = a[0] + b[0];
for (int i=0 ; i<99 ; ++i) {
    b[i+1] = c[i] + d[i];
    a[i+1] = a[i+1] + b[i+1];
}
b[100] = c[100] + d[100];

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

...