Национальный Исследовательский Университет

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Институт автоматики и вычислительной техники

Кафедра прикладной математики

Лабораторная работа № 1

Умножение двух матриц

методом статического разделения на полосы

Курс «Параллельные системы и параллельные вычисления»

Выполнил

студент 5 курса группы А-13-08

Захаров Антон

Преподаватель

Панков Николай Александрович

Постановка задачи

Пусть даны две прямоугольные матрицы и размерности и
соответственно:

Требуется найти матрицу (произведением) размерности :

Для нахождения произведения матриц методом статического разделения на полосы необходимо составить последовательно-параллельную программу на языке C/C++ с применением интерфейса передачи сообщений (MPI, Message Passing Interface), а также исследовать характеристики разработанной программы в зависимости от числа исполнителей.

Последовательный алгоритм решения

Умножение матриц по определению

В соответствии с определением, произведение матриц состоит из всех возможных комбинаций скалярных произведений строк матрицы и столбцов матрицы . Элемент матрицы с индексами (i, j) есть скалярное произведение i-ой строки матрицы и j-го столбца матрицы .

1. for (i = 0; i < m; i++) {

2. for (j = 0; j < q; j++) {

3. C[i][j] = 0;

4. for (k = 0; k < n; k++)

5. C[i][j] += A[i][k] * B[k][j];

6. }

7. }

На первый взгляд это минимальный объем работы, необходимый для перемножения двух матриц. Однако исследователям не удалось доказать минимальность, и в результате они обнаружили другие алгоритмы, умножающие матрицы более эффективно.

Алгоритм Штрассена

Первый алгоритм быстрого умножения матриц был разработан В. Штрассеном в 1969. В основе алгоритма лежит рекурсивное разбиение матриц на блоки. Недостатком данного метода является большая сложность программирования по сравнению со стандартным алгоритмом, численная неустойчивость и большой объём используемой памяти.

Разработано большое количество алгоритмов на основе метода Штрассена, которые улучшают его численную устойчивость и уменьшают объём используемой памяти.

Алгоритм Копперсмита-Винограда

В 1990 Копперсмит и Виноград опубликовали алгоритм, умножающий матрицы со сложностью . Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день алгоритм Копперсмита-Винограда является наиболее асимптотически быстрым, но он эффективен только на очень больших матрицах и поэтому не применяется.

В 2003 Кох и др. рассмотрели в своих работах алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали возможность существования алгоритмов умножения матриц со сложностью .

Параллельный алгоритм решения

В предлагаемой реализации метода статического разделения на полосы исходные матрицы разбиваются на горизонтальные полосы. Получаемые полосы распределяются по процессорам: все полосы одной матрицы, например , распределяются между процессорами, а полосы другой – по мере необходимости передаются на все процессоры. При этом на каждом из имеющегося набора процессоров в каждый конкретный момент времени располагается только по одной полосе матриц и . Перемножение полос (а данная операция может быть выполнена процессорами параллельно) приводит к получению частей (полос) результирующей матрицы , которые затем в совокупности и дадут искомую матрицу.

– полоса матрицы ;

– полоса матрицы ;

– число процессоров.

Результаты вычислительного эксперимента

Матрицы 1 000 × 1 000

Число узлов	Число исполнителей на узле	Общее число исполнителей	Время решения1 (сек)	Ускорение	Память, выделяемая на исполнителях (МБ)
1	1	1	20,214690	1,0000	8,010864
1	2	2	10,491869	1,9267	4,196167
1	3	3	7,293000	2,7718	2,922058
1	4	4	5,630250	3,5904	2,288818
2	4	8	3,340757	6,0509	1,335144
3	4	12	3,329982	6,0705	1,014709
4	4	16	3,322259	6,0846	0,854492
5	4	20	3,241675	6,2359	0,762939
6	4	24	3,025505	6,6814	0,694275
7	4	28	2,846166	7,1024	0,648499
8	4	32	2,766360	7,3073	0,617981
9	4	36	2,656821	7,6086	0,587463
10	4	40	2,636472	7,6673	0,572205
11	4	44	2,495054	8,1019	0,549316
12	4	48	2,478727	8,1553	0,534058
13	4	52	2,453845	8,2380	0,526428
14	4	56	2,275840	8,8823	0,511169
15	4	60	2,214899	9,1267	0,503540
16	4	64	2,193978	9,2137	0,495911

Время

(сек)

Зависимость времени решения задачи от числа исполнителей

Число

исполнителей

Ускорение

Зависимость ускорения параллельного решения от числа исполнителей

Число

исполнителей

Память

(МБ)

Зависимость памяти, выделяемой на исполнителе, от числа исполнителей

Число

исполнителей

Матрицы 10 000 × 10 000

Число узлов	Число исполнителей на узле	Общее число исполнителей	Время решения (сек)	Ускорение	Память, выделяемая на исполнителях (МБ)
1	1	1	15221,21469	1,0000	804,8828
1	2	2	7478,491869	2,0353	419,6167
1	3	3	5281,293000	2,8821	295,2147
1	4	4	3260,630250	4,6682	226,9918
2	4	8	2055,340757	7,4057	133,5144
3	4	12	1675,370241	9,0853	102,4801
4	4	16	1493,322259	10,1929	85,4492
5	4	20	1326,241675	11,4770	76,2939
6	4	24	1251,025505	12,1670	69,4375
7	4	28	1102,846166	13,8018	63,2294
8	4	32	988,766360	15,3941	61,7981
9	4	36	791,656821	19,2270	58,7463
10	4	40	720,636472	21,1219	57,2205
11	4	44	686,495054	22,1724	54,9316
12	4	48	639,478727	23,8025	53,4058
13	4	52	580,453845	26,2230	52,6428
14	4	56	526,275840	28,9225	51,1169
15	4	60	475,214899	32,0302	50,3540
16	4	64	407,754661	37,3293	50,0488

Время