Лекции по параллельным вычислениям. Гергель В.П - 140 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

140
/snw/qT
comm,s
21
2 . (10.9)
После умножения матричных блоков процессоры передают свои блоки
матрицы В предыдущим процессорам по столбцам решетки процессоров. При
этом первые передают свои данные последним процессорам в столбцах решет-
ки. Эти операции могут быть выполнены параллельно, поэтому время на пере-
дачу данных на этом этапе составит:
/snwT
comm,s
22
. (10.10)
Просуммировав соотношения (10.7), (10.8), (10.10), с учетом параметра q
получаем общее время выполнения алгоритма:
./snwqqlogqsnq/nsnq
/snwq/snwqlogq
snq/nsnqT
2
2
22
22
2
22
112
1
12
(10.11)
Напомним, что параметр q определяет размер процессорной решетки и
sq .
Теперь с использованием (10.11) нетрудно записать соотношения для ускоре-
ния и эффективности, аналогичные (10.5), (10.6). Читателям предлагается вы-
полнить это самостоятельно.
10.5 Модифицированный метод умножения матриц
при блочном разделении данных
Для уменьшения затрат на коммуникации применяют модифицирован-
ный алгоритм умножения матриц при блочном разделении данных. Отличие от
рассмотренного выше алгоритма заключается в изменении схемы начального
распределения блоков перемножаемых матриц между подзадачами. Начальное
расположение блоков подбирается так, чтобы блоки можно было перемножать
без дополнительных передач данных, а перемещение блоков между подзадача-
ми в ходе вычислений осуществляется с использованием более простых комму-
никационных операций (алгоритм Кэннона) [3].

Страницы