Составители:
Рубрика:
ибо при t 6= 1 из основного логарифмического тождества вытекает
соотношение log
a
t/ log
b
t = log
a
b.
§ 2. Распараллеливание умножения
матрицы на вектор
Здесь используем заглавные буквы для обозначения векто-
ров и матриц и малые буквы для их компонент. Пусть X =
(x
1
, . . . , x
n
)
T
, Y = (y
1
, . . . , y
n
)
T
— n-мерные векторы, A = (a
ij
)
n
i,j=1
— квадратная матрица порядка n. Предположим, что Y = AX, т.е.
y
i
=
n
X
j=1
a
ij
x
j
. (2.1)
Теорема 2.1. Для вычисления произведения квадратной
матрицы порядка n на вектор можно построить параллельную
форму высоты dlog
2
ne + 1 и ширины n
2
.
Д о к а з а т е л ь с т в о. За первый такт работы с n
2
процессо-
рами можно получить n
2
произведений a
ij
x
j
, т.е. все требуемые
произведения. Все суммы (2.1) можно получать параллельно, ис-
пользуя схему сдваивания (для этого на втором такте потребуется
n · dn/2e процессоров, а на следующих тактах число используемых
процессоров будет уменьшаться). Для вычисления сумм согласно
теореме 8.1 главы 1 потребуется dlog
2
ne тактов. Итак, общее тре-
буемое количество тактов равно dlog
2
ne + 1. Теорема доказана.
§ 3. Распараллеливание перемножения матриц
Теорема 3.1. Для перемножения двух квадратных мат-
риц порядка n можно построить параллельную форму высоты
dlog
2
ne + 1 и ширины n
3
.
Д о к а з а т е л ь с т в о. Умножение матрицы порядка n на
вектор можно представить в виде параллельной формы высоты
dlog
2
ne + 1 и ширины n
2
. Поскольку умножение квадратных мат-
риц можно рассматривать, как произведение первой матрицы на
столбцы второй (а этих столбцов n), то при наличии n
3
процессоров
можно умножение матриц на упомянутые столбцы осуществлять
параллельно. Это приведет к параллельной форме той же высоты,
но с шириной в n раз больше. Теорема доказана.
28
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »
