Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 21 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

Д о к а з а т е л ь с т в о почти очевидно. В случае, когда n не яв-
ляется степенью двойки, найдем k так, чтобы 2
k−2
< n < 2
k
, и
дополним произведение 2
k
− n сомножителями, равными единице.
Далее строим параллельную форму, соответствующую схеме сдва-
ивания, и подсчитываем высоту и ширину этой формы.
Аналогичным образом применяется схема сдваивания к сумме
n чисел; в результате получается следующее утверждение.
Теорема 8.2. Высота параллельной формы сложения n чисел,
соответствующей схеме сдваивания, равна dlog
2
ne, а ее ширина
не превосходит dn/2e.
Д о к а з а т е л ь с т в о аналогично доказательству теоремы 8.1 (в
случае, когда n не является степенью двойки, добавляем в сумму
соответствующее число нулевых слагаемых).
Пусть теперь требуется найти не только произведение n чисел
a
1
, a
2
, a
3
, . . . , a
n
, но и все последовательные произведения
a
1
, a
1
a
2
, a
1
a
2
a
3
, . . . , a
1
a
2
. . . a
n−1
.
Эта задача по схеме сдваивания реализуется очень эффективно.
Продемонстрируем это на примере восьми сомножителей (n = 8);
на следующей ниже схеме искомые произведения подчеркнуты.
Данные: a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
Ярус 1. a
1
a
2
, a
3
a
4
, a
5
a
6
, a
7
a
8
.
Ярус 2. (a
1
a
2
)a
3
(a
1
a
2
)(a
3
a
4
), (a
5
a
6
)a
7
a
5
a
6
a
7
a
8
.
Ярус 3. (a
1
a
2
a
3
a
4
)a
5
(a
1
a
2
a
3
a
4
)(a
5
a
6
)
(a
1
a
2
a
3
a
4
)(a
5
a
6
a
7
) (a
1
a
2
a
3
a
4
)(a
5
a
6
a
7
a
8
).
Здесь высота h = 3, ширина w = 4, и имеется полная загруз-
ка процессоров, однако, некоторые результаты "лишние" в том
смысле, что в окончательном ответе они не нужны (последнее —
достаточно типичное свойство параллельных алгоритмов).
Нетрудно реализовать эту схему для произвольного числа n
сомножителей, дополнив их в случае, когда n не является степенью
двойки, необходимым числом единиц. Эта схема тоже называется
схемой сдваивания (для последовательных произведений). Высота
и ширина этой схемы такая, как указано в теореме 8.1.
Отметим две особенности параллельных алгоритмов.
1. Ряд алгоритмов имеет очень много "лишних" операций.
2. Разные схемы параллельных алгоритмов реализуют разные
алгоритмы, хотя формально (ввиду ассоциативности и коммутатив-
22

Страницы