Избавление от зависимости от данных

Question

У меня есть этот код:

for(i=0; i<size; i++) 
{ 
    d[i] = d[i-1] + v[i]; 
} 

Когда я делаю параллельную обработку для этого цикла, у меня есть зависимость данных и интервал инициации становятся 2 Значения у меня есть: интервал

инициации : 2

|load v[i-1]|load d[i-2]| add |store d[i-1]| 
|   |   | load v[i]|load d[i-1] |  add | store d[i] | 

Я не хочу останавливаться между ними.

инициирования интервала: 1

|load v[i-1]|load d[i-2]| add |store d[i-1]| 
|   |load v[i] |load d[i-1]|  add | store d[i] | 

Это невозможно, так как d [I-1] не сохраняется.

Как сделать интервал инициализации равным 1, изменив код?

Answer 1

Вы не можете уменьшить этот пробел.

Также это (разворачивание цикла) не является наиболее эффективным способом параллельной обработки для этого типа цикла. Ваш цикл выглядит как операция префикса. Для префикс-суммы доступны быстрые параллельные алгоритмы и реализации. Например, this question