Теория распараллеливания и синхронизация. Демьянович Ю.К - 69 стр.

UptoLike

Составители:

Рубрика:

Рис. 4. Иллюстрация распараллеливания префиксных вычислений

Пусть i — идентификатор процесса, barrier(i) — точка син-

хронизации, old[n] — массив, гд е сохраняется старое значение.

int a[n], s[n], old[n]; # предполагается, что массив a[n]

# инициализирован

process Sum[i = 0 to n − 1] {

int d = 1;

s[i] = a[i];

barrier(i); # I барьер

while (d < n) {

old[i] = s[i]; # сохранение старых значений

barrier(i); # II барьер



(i − d) >= 0



s[i] = old[i − d] + s[i];

barrier(i); # III барьер

d = d + d; # удваивание расстояния

}

Замечание. Барьеры здесь необходимы для устранения взаимного

влияния:

I барьер: элементы s[i] должны быть проинициализированы до

начала выполнения программы;