Паралельне виконання операцій множення матриць

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Національний університет  «Львівська політехніка»

 

Кафедра ЕОМ

 

КУРСОВА РОБОТА

з дисципліни:

«Паралельні та розподілені обчислення»

на тему:

«Паралельне виконання  операцій множення матриць»

 

                                     Виконав:

Ст. гр. КІ - 45

Гончаренко О.С.

Прийняв:

Грицик І.В.

 

 

 

Львів – 2014

 

Завдання

Розробити схему та описати  процедуру перемноження матриці А (розмірністю N1*N2) на матрицю В (розмірністю N2*N3) на структурі з восьми процесорів. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
Г	О	Н	Ч	А	Р	Е	К	О	О	Л	Е	К	С	А	Н	Д	Р	С	Е	Р	Г	І
	3	8		4	5	7	1	2		6

 

N1 = 190

N2 =88

N3 = 149

Таблиця 1.  Часові параметри

 

Співвідношення часових  параметрів	Пояснення
tu=2tz	час виконання однієї операції множення
tS=1/5tZ	час виконання однієї операції сумування
tP =1/3tZ	час виконання однієї операції пересилання даних між процесорами
tz	час виконання операції завантаження одних даних
tW=1/5tz	час виконання операції вивантаження одних даних

 

Таблиця 2. Кодування букв

К	О	Н	Р	Е	Л	С	Ч
47	250	134	93	171	212	82	49
2F	FA	86	5D	AB	D4	52	31

 

 

 

 

                Таблиця 3. Матриця суміжності

	1	2	3	4	5	6	7	8
1	0	0	1	0	1	1	1	1
2	1	0	1	1	1	0	1	0
3	1	0	0	0	0	1	1	0
4	0	1	0	0	1	1	0	1
5	1	0	1	0	0	0	1	1
6	1	1	0	1	0	0	0	0
7	0	1	0	1	0	0	0	0
8	0	0	1	1	0	0	0	0

 

 

Type = ( _i)mod3 + 1

Z= 1109519.

Type = 3 Розподілена пам'ять.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Анотація

В даній курсовій роботі проведено розробку програмної реалізації восьми процесорної паралельної системи зі розподіленою пам’яттю, яка виконує множення двох матриць розмірами А(190*88) та В(88*149). Також наводяться числові значення характеристик даної системи таких як ефективність, коефіцієнт відношення часу виконання паралельної частини програми і часу виконання всієї програми. Проведено також порівняння даного алгоритму з простим послідовним за такими основним ознаками, як час виконання однакової задачі на різних алгоритмах, ефективність.

Алгоритм виконання множення 2-ох матриць реалізований на С++ з консольним інтерфейсом, та з використанням MPI.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Annotation

In this course work developed program of eight parallel processor system with distributed memory, which performs multiplication with dimensions А(190*88) and В(88*149). There are numerical values ​​of the characteristics of the system such as efficiency, the ratio of the execution time of the parallel program and the execution time of parallel applications and runtime. Comparing this algorithm with a simple serial to such basic functions as performing the same task on different performance algorithms. 
          Multiplication algorithm of two matrices implemented in C + + with a console interface, and using MPI.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Зміст

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вступ.

Паралельні обчислювальні  системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій.

Паралельні алгоритми досить важливі  з огляду на постійне вдосконалення  багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму.

Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу. Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому необхідно, щоб завдання, що розв'язується було сегментоване — розділене на підзадачі, що можуть обчислюватися паралельно. При цьому для розподілених обчислень доводиться також враховувати можливу відмінність в обчислювальних ресурсах, які будуть доступні для розрахунку різних підзадач. Проте, не кожне завдання можна «розпаралелити» і прискорити його розв'язання за допомогою розподілених обчислень.

1. Теоретичний розділ.

 

Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу  навантаження між декількома обчислювальними  пристроями. Цими «обчислювальними пристроями»  можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів, об’єднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер.

Паралельна модель програмування  сильно відрізняється від звичайної  – послідовної. Існують дві моделі паралельного програмування: модель паралелізму даних і модель паралелізму задач. Модель паралелізму даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізаму задач передбачає розбиття основної задачі на самостійні підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: MPI (Message Passing Interface) і PVM (Parallel Virtual Machine).

При множенні  матриць А(mxn) і В(nxl) отримаємо матрицю С(), кожен елемент якої визначається відповідно до виразу:

     (1.1)  

                   

Як випливає з даної формули, кожен елемент результуючої матриці С є скалярний добуток відповідних рядка матриці A та стовпця матриці B: 
Цей алгоритм передбачає виконання mxnxl операцій множення і mx(2n-1)xl операцій додавання елементів вихідних матриць. 

         Послідовний алгоритм множення матриць видається трьома вкладеними циклами: 
Алгоритм 1.Послідовний алгоритм множення двох квадратних матриць 
for (i = 0; i <n; i + +) { 
  for (j = 0; j <l; j + +) { 
    MatrixC [i] [j] = 0; 
    for (k = 0; k <m; k + +) { 
      MatrixC [i] [j] = MatrixC [i] [j] + MatrixA [i] [k] * MatrixB [k] [j]; 
    } 
  } 
}

Цей алгоритм є ітеративним  і орієнтований на послідовне обчислення рядків матриці С. Дійсно, при виконанні однієї ітерації зовнішнього циклу (циклу за змінною i) обчислюється один рядок результуючої матриці (Рис. 1.1).

 

 
Рис. 1.1.Обчислення одного рядка результуючої матриці

На першій ітерації циклу  за змінною i використовується перший рядок матриці A і всі стовпці матриці B для того, щоб обчислити елементи першого рядка результуючої матриці С.

Оскільки кожен елемент результуючої матриці є скалярний добуток  рядка та стовпця вихідних матриць, то для обчислення всіх елементів  матриці з розміром nxl необхідно виконати n*(2n-1)*l скалярних операцій .

З визначення операції матричного множення випливає, що обчислення усіх елементів матриці С може бути виконано незалежно один від одного. Як результат, можливий підхід для організації паралельних обчислень полягає у використанні в якості базової підзадачі процедури визначення одного елемента результуючої матриці С. Для проведення всіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і одному стовпцю матриці В.

Для обчислення одного рядка  матриці С необхідно, щоб у  кожній підзадачі містилася рядок  матриці А і був забезпечений доступ до всіх стовпцях матриці B. Можливі способи організації паралельних обчислень полягають у наступному. 
Алгоритм являє собою ітераційну процедуру, кількість ітерацій якої збігається з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному стовпцю матриці В. При виконанні ітерації проводиться скалярне множення, що призводить до отримання відповідних елементів результуючої матриці С. Після завершення обчислень в кінці кожної ітерації стовпці матриці В повинні бути передані між підзадачами з тим, щоб у кожній підзадачі виявилися нові стовпці матриці В і могли бути обчислені нові елементи матриці C. При цьому дана передача стовпців між підзадачами повинна бути організована таким чином, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно опинилися всі стовпці матриці В. 
Можлива проста схема організації необхідної послідовності передач стовпців матриці В між підзадачами полягає в представленні топології інформаційних зв'язків підзадач у вигляді кільцевої структури. У цьому випадку на кожній ітерації підзадача i, 0 <= i <n, буде передавати свій стовпець матриці В підзадачі з номером i +1 - Рис. 1.2. Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечена в кожній підзадачі по черзі опиняться всі стовпці матриці В.