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

Міністерство освіти і науки, молоді та спорту України

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

 

 

Кафедра ЕОМ

 

 

 

 

 

 

 

 

 

Курсова робота

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

на тему:

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

 

 

Виконав:

ст. гр. КІ-44

Демкович О.П.

Прийняв:

Грицик І.В.

 

 

 

Львів – 2013

Завдання

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

N1 = 60, N2 = 208,  N3 = 325

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

Співвідношення часових  параметрів	Пояснення
tu = 6*tw	час виконання однієї операції множення
ts = 3/5*tw	час виконання однієї операції сумування
tp = 3/5tw	час виконання однієї операції пересилання  даних між процесорами
tz = tw	час виконання операції завантаження одних даних
tW	час виконання операції вивантаження одних даних

 

 

                Таблиця 2. Матриця зв’язків між процесорами

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

 

Type = ( _i)mod3 + 1

z = 1009955 (номер залікової книжки)

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

 

Анотація

В даній курсовій роботі розроблено алгоритм паралельного множення двох матриць з розмірами 60х208 і 208х325 з завантаженням даних з розподіленої пам’яттю. В процесі виконання роботи виділено такі етапи:

• проектування граф-схеми виконання алгоритму (визначення зв’язків між процесорами, визначення кільця для обміну даними, граф-схема виконання алгоритму множення двох матриць з розподіленою пам’яттю);
• розробка функціональної схеми;
• розрахункова частина (розрахунок ефективності, часу виконання алгоритму, відсотка послідовної частини алгоритму та ін.);
• програмна реалізація, яка включає в себе алгоритм роботи програми, його граф-схему та сам код програми.

Програма написана на мові Java з використанням багатопотоковості і має консольний інтерфейс. Після завершення всіх етапів роботи, було зроблено висновки, аналіз отриманих критеріїв продуктивності виконання поставленої задачі.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Annotation

In this course work parallel algorithm multiplying two matrices with dimensions 210h56 56h251 and downloading data from a distributed memory. In carrying out the work allocated to the following stages:

- Designing a graph-scheme of algorithm (define connections between processors, the definition of the ring to exchange data, the graph-scheme of the algorithm of multiplication of two matrices with distributed memory);

- Development of a functional circuit;

- Part of the settlement (calculation of efficiency, since the algorithm, a consistent percentage of the algorithm, etc..)

- Software implementation, which includes the algorithm of the program, its graph schema and the code of the program.

The program is written in Java using multithreading and has a console interface. After completion of all phases of work, was made conclusions, analysis of the performance criteria of the task.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Зміст

Вступ 1. Теоретичний розділ 2. Проектування граф-схеми виконання алгоритму 2.1. Зв’язки між процесорами 2.2. Пересилання даних по кільцю 2.3. Граф-схема виконання алгоритму 3. Розробка функціональної схеми 4. Розрахунковий розділ 4. 1. Послідовне виконання 4. 2. Паралельне виконання 5. Розробка програми 6. Результат виконання програми Висновки Список використаної літератури Додаток А. Лістинг програми

6 7 8 8 8 9 12 15 15 16 20 22 23 24 25

 

 

 

 

 

 

 

 

 

 

 

 

Вступ

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

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

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

 

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

Паралельна система складається  з певної кількості процесорів та модулів пам’яті. В даному випадку це структура з 8 процесорів та спільна пам’ять.

Множення матриці на матрицю  або матриці на вектор є базовими мікроопераціями різних задач. Для їх реалізації використовують різні алгоритми та різні структури.

Для вирішення цієї задачі використовується алгоритм, при якому матриця А  розбивається на 8 горизонтальних смуг, а матриця В – на 8 вертикальних, в такому разі матриця результату буде складатись з 8 горизонтальних смуг (рис.1.1) 

Рис. 1.1 Розбиття матриць

 

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

 

2. Проектування граф-схеми виконання алгоритму

2.1.   Зв’язки між процесорами

Для ефективної роботи паралельної  системи було побудовано схему пересилань даних та граф зв’язків між процесорами, їх опис, який наведений на рис. 2.1.

Рис. 2.1. Граф зв’язків між процесорами

 

2.   Пересилання даних по кільцю

Оскільки стоїть задача розпаралелити  виконання перемноження матриць, то доцільно використовувати обмін даними по кільцевій структурі, що забезпечує роботу з мінімальними затримками. Граф пересилання даних між процесорами на кільцевій структурі зображений на рис. 2.2.

Пересилання між процесорами виконується  у такому порядку:

P1 →P3→P5→P4→P7→P6→P8→P2

Рис. 2.2. Граф пересилання даних між процесорами на кільцевій структурі

 

3.   Граф-схема виконання алгоритму

На початку роботи алгоритму  кожен процесорний елемент зчитує початкові дані, тобто підматриці А та В, які були завантажені з розподіленої пам’яті. Відбувається множення підматриць. Після закінчення цієї операції відбувається обмін даними підматриці В між процесорами по кільцевій структурі, яка вже була наведена на рис. 2.2. Так відбувається доти, доки підматриця В не буде перемножена на всі підматриці А.

Далі відбувається поетапне виведення часткових результатів, тобто підматриць C і збір загального результату, тобто виведення матриці С у повному вигляді.

На рис. 2.3. наведена граф-схема виконання алгоритму множення двох матриць з розподіленою пам’яттю в загальному випадку.

Рис. 2.3.  Граф-схема виконання алгоритму множення двох матриць з розподіленою пам’яттю.

 

Для матриць А[N1,N2] та B[N2,N3] і Р процесорів розміри підматриць Аі та Ві визначаються так.

Для А та для В обчислюємо

           

            ,

де С_1А та С_1В – ціла частина від ділення,  С_2А та С_2В - залишки.

Перші (Р - С_2А) підматриці матриці А матимуть кількість рядків С_1А, решту – (С_1А + 1) рядків. Для матриці В, відповідно, (Р - С_2В), С_1В, (С_1В + 1) стовпців.

Визначимо розміри підматриць Аі та Ві для кожного з процесорів.

,

,

Розбиття матриці А на горизонтальні  стрічки і матриці B на вертикальні  стрічки наведено на рис. 2.4.

                   A B

          208        325

A1                                      7

A2 7

A3 7

A4 7

A5 8

A6 8

A7 8

A8 8

 

B1             40

B2             40

B3             40

B4             41

B5             41

B6             41

B7             41

B8             41

 

 

60  208 

Рис. 2.4. Розбиття матриць A і B на підматриці.

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Розробка функціональної схеми 

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

Відразу після запуску кожен  з процесорів паралельно з іншими зчитує початкові дані із своєї окремої  пам'яті.

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