Умножение двух матриц методом блочного сдвига
.docxНациональный Исследовательский Университет
МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
Институт автоматики и вычислительной техники
Кафедра прикладной математики
Лабораторная работа № 1
Умножение двух матриц
методом блочного сдвига
Выполнила
Студентка А-13-09
Шорникова Дарья
Преподаватель
Панков Николай Александрович
Москва, 2013 г.
Постановка задачи
Пусть даны две прямоугольные матрицы и размерности и соответственно:
Требуется найти матрицу (произведением) размерности :
Для нахождения произведения матриц методом статического разделения на полосы необходимо составить последовательно-параллельную программу на языке C или C++, использующую принципы нитевого распараллеливания, а также исследовать характеристики разработанной программы в зависимости от числа потоков.
Тестирование проводились на компьютере со следующей конфигурацией:
ПРОЦЕССОР Intel Core i7-3720 2.6 Ггц
ОПЕРАТИВНАЯ ПАМЯТЬ 8Gb
ОПЕРАЦИОННАЯ СИСТЕМА Windows 8 Ultimate x64 (SP1)
Последовательный алгоритм решения
Умножение матриц по определению
В соответствии с определением, произведение матриц состоит из всех возможных комбинаций скалярных произведений строк матрицы и столбцов матрицы . Элемент матрицы с индексами (i, j) есть скалярное произведение i-ой строки матрицы и j-го столбца матрицы .
for (i = 0; i < m; i++) {
for (j = 0; j < q; j++) {
C[i][j] = 0;
for (k = 0; k < n; k++)
C[i][j] += A[i][k] * B[k][j];
}
}
Параллельный алгоритм решения
Одним из эффективных методов параллельного решения этой задачи является блочное умножение матриц. Блочными алгоритмами являются алгоритмы Фокса и Кэннона.
В блочном алгоритме матрица представляется в виде набора блоков. В данной лабораторной работе реализован алгоритм Кэннона для квадратных матриц размера n*n.
Для корректной работы блочных алгоритмов необходимо, чтобы количество блоков по горизонтали и вертикали было n/q, где q=√p. То есть, число нитей, используемых в алгоритме, должно являться полным квадратом. Нить вычислений должна иметь доступ к горизонтальной полосе матрицы A и вертикальной полосе матрицы B.
Идея алгоритма Кэннона состоит в минимизации числа пересылок блоков. Добиться этого можно начальным перераспределением блоков в матрицах A и B. Для этого каждая строка матрицы A сдвигается на число блоков влево, равное ее номеру, и столбец матрицы B сдвигается на число блоков вверх, равное его номеру.
Следует помнить, что операции сдвига являются циклическими.
На каждом шаге алгоритма Кэннона происходит перемножение блоков Aij и Bij для получения соответствующего блока Cij с последующим сдвигом строк матрицы A влево и столбцов матрицы B вверх. Цикл повторяется q раз
Перераспределение блоков
Результаты вычислительного эксперимента
Теоритические оценки эффективности алгоритма (обменные взаимодействия между процессами не учитываются, так как они имеют доступ к матрицам, расположенным в общем адресном пространстве)
Максимальное ускорение, которое мы можем получить, равно числу нитей.
По результатам экспериментов время решения является средним арифметическим из 3-х времен решения задачи.
Матрицы 1000 × 1000
Число потоков |
Время решения (сек) |
Ускорение |
1 |
8.594 |
1 |
2 |
4.486 |
1.915
|
3 |
3.114 |
2.759
|
4 |
2.496 |
3.443
|
5 |
2.188 |
3.927
|
6 |
2.039 |
4.214
|
7 |
1.922 |
4.471 |
8 |
2.001 |
4.294
|
9 |
2.002 |
4.292 |
Матрицы 2500 × 2500
Число потоков |
Время решения (сек) |
Ускорение |
1 |
189.236 |
1 |
2 |
91.910 |
2,058
|
3 |
62.453 |
3,031
|
4 |
52.713 |
3,589
|
5 |
45.910 |
4,121
|
6 |
41.549 |
4,554
|
7 |
38.144 |
4,961
|
8 |
39.321 |
4,812
|
9 |
39.532 |
4,786
|
Матрицы 20 000 × 20 000
Число потоков |
Время решения (сек) |
Ускорение |
1 |
6005,4665 |
1,0000 |
2 |
3401,2681 |
1,7657 |
3 |
2375,1655 |
2,5284 |
4 |
1820,5416 |
3,2987 |
5 |
1873,0987 |
3,2062 |
6 |
1891,9394 |
3,1742 |
7 |
1873,6492 |
3,2052 |
8 |
1831,9423 |
3,2782 |
9 |
1951,0563 |
3,0781 |
10 |
2089,2749 |
2,8744 |
11 |
2116,7367 |
2,8371 |
12 |
2085,5324 |
2,8796 |
Время
(сек)
Число
потоков
Ускорение
Число
потоков
Приложение. Код программы.