Высокопроизводительные вычисления на кластерах. Беликов Д.А - 82 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

82
5 МАТРИЧНЫЕ ВЫЧИСЛЕНИЯ
Задача матричного умножения требует для своего решения вы-
полнения большого количества арифметических операций.
Пусть
, ,
A B C
– квадратные матрицы
n n
,
C AB
. Тогда ком-
поненты матрицы
C
рассчитываются по следующей формуле:
1
n
ij ik kj
k
,
, 1,...,
i j n
. (5.1)
Из (5.1) видно, что для вычисления одного элемента матрицы
C
необходимо
n
умножений и
n
сложений. Учитывая общее количе-
ство таких элементов, можно сосчитать, что операция умножения
матриц потребует выполнения
3
n
скалярных умножений и
3
n
сло-
жений на обычном последовательном компьютере:
3
1
nttT
addmult
.
Произведение матриц может рассматриваться как
2
n
независи-
мых скалярных произведений либо как
n
независимых произведе-
ний матрицы на вектор. В каждом случае используются различные
алгоритмы.
5.1 Способы повышения производительности умножения
матриц
Производительность умножения матриц может быть улучшена
путем изменения порядка циклов
ijk
в (5.1). Каждый язык про-
граммирования характеризуется различным способом хранения в
памяти компьютера элементов массивов. На Фортране элементы
матриц располагаются последовательно в памяти по столбцам, т.е.
11 21 1 12 22 2 13
, ,..., , , ,..., , ,...,
n n nn
a a a a a a a a
. Размещаемые в кэш-памяти
элементы матриц
, ,
A B C
эффективно используются, когда доступ к
ним или их модификация в алгоритме умножения матриц осуществ-
ляется последовательно с переходом к соседней ячейке памяти.
Кроме того, при последовательной выборке данных увеличивается
эффективность использования кэш-памяти. Поэтому порядок следо-

Страницы