Составители:
[определение номера партнера j на уровне s];
while (arrive[j] < arrive[i]) skip;
} # этим определяется, что процесс j зашел так же далеко, как i
Здесь не требуется:
1) ожидать переустановки собственного флага;
2) переустанавливать флаг соседа.
Этой схеме свойственнен обычный недостаток программ с воз-
растающими счетчиками: теоретически возможно их переполнение
(на практике это бывает редко).
§13 Распараллеливание префиксных
вычислений
Пусть дан числовой массив a[n]; требуется вычислить сумму пер-
вых i элементов массива и занести ее в элемент s[i] массива s[n],
i = 0, 1, . . . , n−1. Подобные вычисления называются префиксными.
Решение этой задачи может быть р еали зовано программой
s[0] = a[0];
for [i = 1 to n − 1]
s[i] = s[i − 1] + a[i];
Наша задача — дать параллельную версию таких вычислений. Если
бы требовалось вычислить лишь всех элементов, то можно было бы
использовать алгоритм сдваивания; для его реализации при n = 2
k
потребовалось бы k параллельных сложений.
Подобный подход можно использовать и для вычисления всех
префиксов.
Нужный алгоритм имеет следующие этапы:
1) сначала производится присваиван ие s[i] = a[i];
2) далее складываются s[i − 1] и s[i] для i ≥ 1;
3) далее складываются s[i − 2] и s[i] для i ≥ 2;
4) далее складываются s[i − 4] и s[i] для i ≥ 4;
и т.д.
При n = 2
k
описываемый алгоритм реализуется за k так-
тов синхронной параллельной системы. Следующий рисунок ил-
люстрирует работу алгоритма в случае, когда n = 8, а слагаемыми
являются натуральные числа: s[i] = i + 1, i = 0, 1, . . . , 7.
69
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
