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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

121
q
l
n
), матрицу A можно представить в виде набора прямоугольных блоков
следующим образом:
q,pA...,pA,pA
..........
q,A...,A,A
A
21
12111
,
где
j,iA — блок матрицы, состоящий из элементов:
j,ia...j,iaj,ia
..........
j,ia...j,iaj,ia
j,iA
l,K,K,K
l,,,
21
12111
.
При блочном разбиении целесообразна топология системы в виде решетки
из p строк и q столбцов. При этом вычислительный процесс следует организо-
вать так, чтобы соседние в структуре решетки процессоры обрабатывали смеж-
ные блоки исходной матрицы. Для блочной схемы может быть применено так-
же циклическое чередование строк и столбцов.
9.4 Умножение матрицы на вектор, разделение по строкам
В данном случае умножение m×n-матрицы на n×1-вектор сводится к вы-
числению m скалярных произведений векторов длины n. Каждое такое произ-
ведение требует n операций умножения и
операций сложения. Таким об-
разом, вычислительная сложность последовательного алгоритма составит
12
1
nmT , а в случае квадратной n×n-матрицы
12
1
nnT . (9.14)
Если умножение n×n-матрицы выполняется параллельно (см. рис. 9.3), за
каждым процессором закрепляется не более
s
m n s
(9.15)
строк, где
*
– здесь и далее означает операцию округления до целого в боль-
шую сторону. Количество процессоров, за которыми будет закреплено меньше
чем
s
m строк, определяется конкретными значениями n и s.

Страницы