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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

86
! записываем с
ij
из быстрой памяти в медленную
end do
end do
Выполним подсчет числа обмена данными между основной и
кэш-памятью. Для передачи элементов матрицы
A
потребуется
2
n
обращений,
B
–
3
n
,
C
–
2
n
. В итоге получим
3 2
1
3
n n
обра-
щений.
Теперь покажем, что подход, основанный на блочных скалярных
произведениях (5.2), приводит к более эффективному использова-
нию кэш-памяти. Рассмотрим блочную версию матричного умно-
жения:
do i = 1, N
do j = 1, N
! считываем блок C
ij
в быструю память
do k = 1, N
! считываем блок A
ik
в быструю память
! считываем блок B
kj
в быструю память
c(i, j) = c(i, j)+a(i, k)*b(k, j)
end do
! записываем C
ij
из быстрой памяти в медленную
end do
end do
По этому алгоритму число передаваемых данных будет следую-
щим: для матрицы
A
–
3 2 2 2
( / )
N n N Nn
, для матрицы
B
– также
2
Nn
, а для чтения и записи блоков матрицы
C
–
2 2 2 2
( / )
N n N n
.
Всего получается
2 2
2
2 1 2
N n Nn
обращений к быстрой
кэш-памяти. Поэтому чтобы минимизировать число обращений,
нужно взять как можно меньшее значение
N
. Но
N
подчиняется
ограничению, что
2 2
3 /
M n N
, которое означает, что в кэш-
памяти может разместиться по одному блоку матриц
, ,
A B C
. Отсю-
да получаем
3 /
N n M
и
3
2
2 3 /
n M
. Тогда отношение
1 2
/ / 2 3
M , и видно, что блочные скалярные произведе-
ния имеют решительное преимущество. Продемонстрируем это на

Страницы