Лабораторная работа 1 (Умножение двух матриц методом статического разделения на полосы (Захаров))

Посмотреть архив целиком

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

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

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

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

Лабораторная работа № 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








Время

(сек)

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

Число

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


Ускорение

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

Число

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


Память

(МБ)

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

Число

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


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


Число
узлов

Число
исполнителей
на узле

Общее число исполнителей

Время
решения
(сек)

Относительное ускорение

Память,
выделяемая на исполнителях
(МБ)

6

4

24

8105,025505

1,0000

1529,2968

7

4

28

7519,846166

1,0778

1257,7002

8

4

32

6720,766360

1,2060

1059,2882

9

4

36

6011,656821

1,3482

937,9508

10

4

40

5329,636472

1,5207

781,0864

11

4

44

4902,495054

1,6532

614,8806

12

4

48

4360,478727

1,8587

512,6952

13

4

52

3971,453845

2,0408

457,7634

14

4

56

3520,275840

2,3024

416,6250

15

4

60

3027,190033

2,6774

379,3764

16

4

64

2650,754661

3,0576

370,7886


Случайные файлы

Файл
9058-1.rtf
5029-1.rtf
27838.rtf
33203.rtf
183076.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.