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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Особенность этой параллельной формы в том, что 4 процессора
загружены только на первом ярусе, а на последнем ярусе загружен
лишь один процессор.
1.2. Вторая параллельная форма имеет вид:
Данные: 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
.
Ярус 2. a
5
a
6
, a
7
a
8
.
Ярус 3. a
1
a
2
+ a
3
a
4
, a
5
a
6
+ a
7
a
8
.
Ярус 4. (a
1
a
2
+ a
3
a
4
)(a
5
a
6
+ a
7
a
8
).
1.3. Третья параллельная форма такова:
Данные: 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
.
Ярус 2. a
1
a
2
+ a
3
a
4
, a
5
a
6
.
Ярус 3. a
7
a
8
.
Ярус 4. a
5
a
6
+ a
7
a
8
.
Ярус 5. (a
1
a
2
+ a
3
a
4
)(a
5
a
6
+ a
7
a
8
).
Ясно, что высота второй формы 4, третьей формы — 5, а ширина
обеих форм одинакова и равна 2.
Для эффективного распараллеливания процесса стремятся
1) к увеличению загруженности системы процессоров;
2) к отысканию параллельной формы с заданными свойствами.
Пример 2. Рассмотрим вычисление произведения n чисел.
Пусть n = 8. Требуется перемножить числа a
1
, a
2
, a
3
, a
4
, a
5
,
a
6
, a
7
, a
8
.
2.1. Обычная схема последовательного умножения:
Данные a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
.
Ярус 1. a
1
a
2
Ярус 2. (a
1
a
2
)a
3
. . ., . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ярус 7. (a
1
a
2
. . . a
7
)a
8
Высота этой параллельной формы равна 7, ширина равна 1.
2.2. Уменьшение числа ярусов можно добиться с помощью ал-
горитма сдваивания, который состоит в следующем:
Данные 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
4
), (a
5
a
6
)(a
7
a
8
).
Ярус 3. (a
1
a
2
a
3
a
4
)(a
5
a
6
a
7
a
8
).
20

Страницы