Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет "Львівська політехніка"
Кафедра ЕОМ
/
Курсова робота
з дисципліни
"Паралельні та розподілені обчислення"
на тему
"Паралельне виконання операцій множення матриць"
Варіант №16
Завдання
Розробити структуру та описати процедуру перемноження матриці А (розмірністюn1*n2) на матрицю В (розмірністюn2*n3) на заданій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці.
Для визначення варіанту були виконані наступні дії:
визначення розмірів матриць (декодування літер згідно номеру групи):
n1=2П,n2=2Б,n3=1І– КІ-43
Таблиця 1. Порядкові номери літер прізвища, імені та по-батькові
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Р
О
М
А
Н
О
В
С
Ь
К
И
Й
О
Л
Е
К
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
С
А
Н
Д
Р
В
І
Т
А
Л
І
Й
О
В
И
Ч
n1 = О n2 = І n3 = О
Згідно таблиці декодування літер маємо:
N1 = 240 N2 = 176 N3 = 333
Отже, отримаємо такі матриці:
А (240*176) В (176*333)
С (240*333)
для визначення типу пам’яті використовуємо формулу:
(25 mod 3) + 1 = 2 –>завантаження даних через 1 процесор;
для знаходження часових співвідношень використовуємо наступну формулу:
tU=(Zk-3 +1)*tS=(Zk-2 +1)*tP=(Zk-1 +1)*tZ=(Zk+1)*tW
tU = 10tS = 6tP =8tZ = 4tW
Результати декодування літер ПІБ, визначення типу пам’яті та знаходженні часових співвідношень у таблиці 2.
Таблиця 2
№
вар
Розміри матриці
К-ть
процесорів
Тип початкового
завантаження даних
Співвідношення часових параметрів
N1
N2
N3
16
240
176
333
8
2
tU = 10tS = 6tP =8tZ = 4tW
Примітка:
2*- завантаження початкових даних в процесори через один з них;
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
для того, щоб розробити та описати алгоритм множення матриць А*В на структурі, яка задається використовуємо наступний вираз:
14b-8b-1b-3b-9b-2b-11b-5b – КІ-43, де «nb»- номер букви П.І.Б студента
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Р
О
М
А
Н
О
В
С
Ь
К
И
Й
О
Л
Е
К
С
А
Н
Д
Р
3
6
4
8
2
5
7
1
Згідно таблиці кодування букв отримали такий варіант-стовпець:
ЛСРМЬОИН
Л – 21210= 1 1 0 1 0 1 0 02
С – 8210=0 1 0 1 0 0 1 02
Р – 9310= 0 1 0 1 1 1 0 12
М – 4310= 0 0 1 0 1 0 1 12
Ь – 2810=0 0 0 1 1 1 0 02
О – 25010= 1 1 1 1 1 0 1 02
И – 9110= 0 1 0 1 1 0 1 12
Н – 13410= 1 0 0 0 0 1 1 02
В отриманій двійковій матриці одиниці, що розташовані по головній діагоналі замінюємо на 0.
1 1 0 1 0 1 0 0
0 1 0 1 0 0 1 0
0 1 0 1 1 1 0 1
0 0 1 0 1 0 1 1
0 0 0 1 1 1 0 0
1 1 1 1 1 0 1 0
0 1 0 1 1 0 1 1
1 0 0 0 0 1 1 0
(
0 1 0 1 0 1 0 0
0 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1
0 0 1 0 1 0 1 1
0 0 0 1 0 1 0 0
1 1 1 1 1 0 1 0
0 1 0 1 1 0 0 1
1 0 0 0 0 1 1 0 Анотація
В даній курсовій роботі розроблена структура перемноження матриці на матриц, яка складається з 8-ми процесорів; завантаження початкових даних в процесори відбувається через один з них. Розміри матриць задані згідно із варіантом. Також пораховано час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з варіанту.
В курсовій роботі розроблено граф-схему виконання алгоритму множення двох матриць, граф-схему загальної схеми виконання програми та граф-схему покрокового виконання алгоритму. Програмне забезпечення до курсової роботи виконане у середовищі Microsoft Visual Studio 2010 на мові С++ з використанням бібліотек MPI. Програмне забезпечення до курсової роботи має консольний інтерфейс.
Annotation
In this course work was developed the structure of the matrix to matrix multiplication on a matrix consisting of 8 processors, load initial data into the processor takes place through one of them. Matrix size set under option. Also, the algorithm calculated time, the percentage of the sequential algorithm and effectiveness of the algorithm for the values according to embodiment.
In the course work are graph-scheme of the algorithm of multiplication of two matrices, graph-scheme of the overall scheme of the program graph and diagram stepping through the algorithm. Software for course work is done in an environment Microsoft Visual Studio 2010 in C + + using libraries MPI. Software for the course work has a console interface.
Вступ
В наш час розробка паралельних алгоритмів є дуже актуальним питанням і має досить широке застосування у багатьох сферах нашого життя, таких як медицина, автомобілебудування, математика, фізика, астрономія, будівництво тощо. Ефективність паралельної обробки інформації залежить як від продуктивності комп’ютерів, так і від розмірів і структури пам’яті, пропускної здатності каналів зв’язку, використаних алгоритмів.
Для вивчення паралельних алгоритмів найкращим і найпростішим способом є набуття навичок паралельної обробки матриць та векторів.
При розробці паралельних алгоритмів важливим є розв’язання складних науково-технічних задач, в яких принциповим моментом являється аналіз ефективності використання паралелізму, що полягає зазвичай в оцінці отримуваного прискорення процесу обчислень (скорочення часу вирішення задачі). Формування подібних оцінок прискорення може здійснюватися стосовно вибраного обчислювального алгоритму (оцінка ефективності розпаралелення конкретного алгоритму шляхом рівномірного розподілу елементів вхідних матриць на під матриці та розподіл обчислень між процесорами). Інший важливий підхід полягає в побудові оцінок максимально можливого прискорення процесу вирішення задачі конкретного типу (оцінка ефективності паралельного способу вирішення задачі).
//тут зміст
1. Теоретичний розділ
1.1 Особливості перемноження матриці на матрицю
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач лінійної алгебри, наприклад ітераційних методів розв’язання систем лінійних рівнянь і т.п. Тому приведені алгоритми тут можна розглядати як фрагменти в алгоритмах цих методів. Розглянемо три алгоритми множення матриці на матрицю. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один комп'ютер; і завантаження даних безпосередньо кожним комп'ютером з дискової пам'яті. Якщо завантаження даних здійснюється через один комп'ютер, то дані зчитуються цим комп'ютером з дискової пам'яті, розрізаються на частини, які розсилаються іншим комп'ютерам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана на диск у виді окремого файлу зі своїм ім'ям; потім кожен комп'ютер безпосередньо зчитує з диска, призначений для нього файл.
1.2 Алгоритм перемноження матриці на матрицю на кільцевій структурі.
Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, і B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, смуги записані на дискову пам'ять окремими файлами зі своїми іменами і доступні всім комп'ютерам. Матриця результатів повертається в нульовий процес.
Реалізація алгоритму виконується на кільці з p1 комп'ютерів. Матриці розрізані як показане на рис. 2.1: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця результату C розрізана на p1 смуги. Тут передбачається, що в пам'ять кожного комп'ютера завантажується і може знаходитися тільки одна смуга матриці А і одна смуга матриці B.
/
Рис. 1.1 Методи розрізування даних для паралельного алгоритму добутку двох матриць при обчисленні на кільці комп'ютерів. Виділені смуги розташовані в одному комп'ютері
Оскільки за умовою в комп'ютерах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно "прокрутити" по кільцю комп'ютерів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця і відповідна операція множення наведена на рис.1.2 у виді окремого кроку. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отриманий у підматриці(i,j) матриці C.
Обчислення відбувається в такій послідовності.
1. Кожен комп'ютер зчитує з дискової пам’яті відповідну йому смугу матриці А. Нульова смуга повинна зчитуватися нульовим комп'ютером, перша смуга - першим комп'ютером і т.д., остання смуга - зчитується останнім комп'ютером. На рис. 1.2 смуги матриці А і B пронумеровані.
2. Кожен комп'ютер зчитує з дискової пам’яті відповідну йому смугу матриці B. У даному випадку нульова смуга повинна зчитуватися нульовим комп'ютером, перша смуга - першим комп'ютером і т.д., остання смуга - зчитується останнім комп'ютером.
3. Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
4. Обчислювальний крок 2. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів. І т.д.
5. Обчислювальний крок p1-1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
6. Обчислювальний крок p1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
7. Матриця C збирається в нульовому комп'ютері.
Рис. 1.2 Стадії обчислень добутку матриць у кільці комп'ютерів
Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами.
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай tu, ts, і tp час операцій, відповідно, множення, додавання і пересилання одного числа в сусідній комп'ютер. Тоді сумарний час операцій множень дорівнює:
U = (n1*n2)*(n3*n2)*tu, (1.1)
сумарний час операцій додавань дорівнює:
S = (n1*n2)*(n3*(n2-1))*ts (1.2)
сумарний час операцій пересилань даних по всіх комп'ютерах дорівнює:
P = (n3*n2)*(p1-1)*tp (1.3)
Загальний час обчислень визначимо як:
T = (U+S+P)/p1 (1.4)
Відношення часу "обчислень без обмінів" до загального часу обчислень є величина:
K = (U+S)/(U+S+P). (1.5)
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам'ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами - 1. При великих матрицях цим можна знехтувати.
При достатніх ресурсах пам'яті в системі краще використовувати алгоритм, у якому мінімізовані обміни між комп'ютерами в процесі обчислень. Це досягається за рахунок дублювання деяких даних у пам'яті комп'ютерів. У наступних двох алгоритмах використовується цей підхід.
1.3 Особливості використання технології паралельного програмування MessagePassingInterface (MPI).
MPI - бібліотека функцій, яка забезпечує взаємодію паралельних процесів за допомогою механізму передачі повідомлень і не має ніяких засобів для розподілення процесів по обчислювальних вузлах і для запуску їх на виконання. МРІ не містить механізмів динамічного створення і знищення процесів під час виконання програми.
Для ідентифікації наборів процесів вводиться поняття групи і комунікатора.
Процеси об’єднуються в групи, можуть бути вкладені групи. Усередині групи всі процеси понумеровані. З кожною групою асоційований свій комунікатор. Тому при здійсненні пересилок необхідно вказати ідентифікатор групи, усередині якої проводиться це пересилка.
Процедури МРІ:
- ініціалізації та закриття МРІ –процесів;
- реалізації комутаційних операцій типу “точка-точка”;
- реалізації колективних операцій;
- для роботи з групами процесів і комунікаторами;
- для роботи з структурами даних;
- формування топології процесів.
До базових функцій МРІ відносяться:
ініціалізація МРІ;
завершення МРІ;
визначення кількості процесів в області зв’язку;
визначення номеру процесу, який виконується;
передача повідомлень;
приймання повідомлень;
функції відліку часу.
Кожна МРІ – функція характеризується способом виконання.
Локальна функція – виконується всередині процесу, що її викликав. Її завершення не вимагає комунікацій.
Нелокальна функція – для її завершення необхідно виконати МРІ – процедуру іншим процесом.
Глобальна функція – процедуру повинні виконати всі процеси групи. Невиконання цієї умови може привести до “зависання” задачі.
Блокуюча функція – повернення керування з процедури гарантує можливість повторного використання параметрів, які приймали участь у виклику. Ніякої змін в стан процесу, що викликав блокуючий запит до виходу з процедури не може відбуватися.
Неблокуюча функція – повернення з процедури відбувається негайно, без очікування завершення операції. Завершення неблокуючих операцій здійснюється спеціальними функціями.
Операції обміну повідомленнями
Розглянемо: режими обміну, обмін типу “точка-точка”, колективний обмін, способи реалізації моделі передачі повідомлень.
Режими обміну:
В загальному випадку є чотири режими обміну: асинхронний (стандартний), синхронний, з буферизацією, по “готовності”.
Обмін типу “точка-точка” – найпростіша форма обміну повідомленнями, в якій приймають участь тільки два процеси: джерело і адресат. Є кілька різновидностей двохточкового обміну:
синхронний обмін – супроводжується повідомленням про завершення прийому повідомлення;
асинхронний обмін – таким повідомленням не супроводжується;
блокуючі прийом/передача – призупиняють виконання процесу на час приймання повідомлення. Організація блокуючого обміну повідомленнями наведена на рис.1.3;
неблокуючі прийом/передача - виконання процесу продовжується в фоновому режимі, а програма в потрібний момент може запитати підтвердження завершення приймання повідомлення. Організація неблокуючого обміну повідомленнями наведена на рис.1.4.
Неблокуючий обмін вимагає акуратності при виконанні функцій прийому. Оскільки неблокуючий прийом завершується негайно, для системи неважливо, чи прибуло повідомлення до місця призначення чи ні. Переконатися про це можна за допомогою функції перевірки отримання повідомлення. Звичайно виклик таких функцій розміщується в циклі, який повторюється до тих пір, доки функція перевірки не поверне значення “істина” (перевірка отримання пройшла успішно). Після цього можна викликати функцію прийому повідомлення з буферу повідомлень.
Рис.1.3 Блокуючий обмін повідомленнями
Рис.1.4 Неблокуючий обмін повідомленнями
Колективний обмін . В операціях використовуються не два а більше процесів. Різновидностями обміну є:
широкосмугова передача – передача виконується від одного процесу до всіх;
обмін з бар’єром – форма синхронізації роботи процесів, коли обмін повідомленнями проходить тільки після того, як до певної процедури звернулась певна кількість процесів;
операції приведення – вхідними є дані кількох процесів, а результат – одне значення, яке стає доступним всі процесам, які приймали участь в обміні.
Важливою властивістю системи передачі повідомлень є гарантія збереження порядку прийому повідомлень (при відправленні одним процесом іншому кількох повідомлень вони повинні бути прийняті в тій самій послідовності в якій були відправлені). Більшість реалізацій моделі передачі повідомлень забезпечують цю властивість, але не у всіх режимах обміну.
2. Аналіз (розробка) граф-схеми виконання заданої функції
Згідно завдання потрібно розробити алгоритм перемноження матриці на матрицю на кільцевій структурі із завантаження початкових даних в процесори через один з них задається таким виразом:
14b-8b-1b-3b-9b-2b-11b-5b – КІ-43, де «nb»- номер букви П.І.Б студента
Для того, щоб сформувати задану структуру, скористаємось таблицею 2.1, щоб отримати відповідні літери. Після цього розкодуємо їх за допомогою таблиці кодування букв.
Таблиця 2.1 Порядкові номери літер ПІБ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Р
О
М
А
Н
О
В
С
Ь
К
И
Й
О
Л
Е
К
С
А
Н
Д
Р
3
6
4
8
2
5
7
1
Отримали: ЛСРМЬОИН
Згідно отриманих літер формуємо таблицю результатів декодування (табл. 2.2) та матрицю зв’язків (табл. 2.3).
Таблиця 2.2 Результати декодування
Л – 21210= 1 1 0 1 0 1 0 02
С – 8210= 0 1 0 1 0 0 1 02
Р – 9310= 0 1 0 1 1 1 0 12
М – 4310= 0 0 1 0 1 0 1 12
Ь – 2810= 0 0 0 1 1 1 0 02
О – 25010= 1 1 1 1 1 0 1 02
И – 9110= 0 1 0 1 1 0 1 12
Н – 13410= 1 0 0 0 0 1 1 02
Таблиця 2.3 Матриця зв’язків
1
2
3
4
5
6
7
8
1
0
1
0
1
0
1
0
0
2
0
0
0
1
0
0
1
0
3
0
1
0
1
1
1
0
1
4
0
0
1
0
1
0
1
1
5
0
0
0
1
0
1
0
0
6
1
1
1
1
1
0
1
0
7
0
1
0
1
1
0
0
1
8
1
0
0
0
0
1
1
0
На основі даних із таблиці 2.3. будуємо граф з’єднань процесорів:
Рис. 2.1 Граф з’єднань у структурі процесорів
Використання усіх зв’язків між процесорами для вирішення даної задачі – недоцільне, і навіть може призвести до втрати продуктивності. Для реалізації алгоритму перемноження матриць, спершу необхідно вирішити, як саме матриці будуть розподілені між процесорами. Обираємо наступний тип розбиття: матриця А – стрічково-горизонтальне розбиття, матриця В - стрічково-вертикальне розбиття (рис. 2.2).
Рис. 2.2 Результат розбиття матриць
Для отримання часткових результатів на кожному з процесорів, необхідно виконувати пересилання підматриць В між процесорами. Цю дію можна виконувати по певному замкнутому кільцю. Приклад такого кола наведено на Рис.2.3.
Рис. 2.3 Кільце передачі даних між процесорами
Оскільки завантаження початкових даних здійснюється через один процесор, який може одночасно обмінюватися даними із трьома процесорами, то необхідно виділити у структурі (рис. 2.1) певні дерева зв’язків, по яких буде проводитися завантаження початкових даних у процесори і вивантаження часткових результатів у головний процесор.
Рис. 2.4 Дерево завантаження вхідних даних
Рис. 2.5 Дерево вивантаження вхідних даних
Дана структура дозволяє проводити множення над окремими частинами матриць паралельно.
На рис. 2.6 наведено граф-схему виконання алгоритму перемноження двох матриць з завантаженням даних через один процесор.
Рис. 2.6 Граф-схема виконання алгоритму множення двох матриць на кільцевій структурі із завантаження початкових даних в процесори через один з них
На граф-схемі (рис. 2.6) представлено N процесорних елементів (в нашому випадку – 8). Дані завантажуються першим процесором, який має доступ до пам’яті. Він у відповідності із деревом завантаження вхідних даних (рис. 2.4) розсилає дані всім іншим процесорам. Кожен процесор отримує свою частину матриці А та B. Після завершення розсилки даних розпочинається сам процес обчислення, підчас якого обмін між процесорами відбувається по структурі зв’язків за маршрутом, вказаним на рис. 2.3. Процес множення – пересилання повторюється 8 разів. Після виконання останнього перемноження, розпочинається збір результатів. В результаті чого всі процесори у відповідності із деревом вивантаження (рис. 2.5) перешлють часткові результати до першого процесора, який їх складає у повну матрицю-результат і записує у пам’ять.
Рис.2.7 Граф-схема покрокового виконання алгоритму множення двох матриць
3. Розробка функціональної схеми
Виконання всього паралельного алгоритму можна розділити на три блоки: завантаження даних, обчислення і вивантаження.
Підчас завантаження даних із пам’яттю працює лише один процесор. Спочатку процесор 4 завантажує підматриці А5 і В5 і надсилає їх у процесор 3. Потім процесор 3 пересилає під матрицю А5, В5 у процесор 6 і в той же час завантажує підматриці А і В для процесорів 2 (А2, В2), 6 (А6, В6) і 8 (А8, В8). Процесор 4 передає завантажені частини до процесорів 7 (підматриця А2, В2), 3 (підматриця А6, В6) і 8 (підматриця А1, В1), а процесор 6 передає процесору 5 його підматриці. Наступним кроком буде те, що процесори 7, 3 і 8 пересилають процесорам 2, 6 і 1 їхні підматриці, а процесор 4 завантажує підматриці для процесорів 7 (підматриця А7, В7), 3 (підматриця А3, В3) і 8 (підматриця А8,В8). Після цього він передає завантажені підматриці до процесорів, яким вони належать і звільнившись, завантажує підматриці А4 і В4. На цьому процес завантаження завершується і розпочинається процес обчислення.
Процесори перемножують елементи матриць, які були у них попередньо завантаженні і отримують частину результату. Після обчислень відбувається пересилання підматриць В по кільцю 4→3→2→7→8→1→6→5→4. Отже, підматриця В4 пересилається з процесора 4 на процесор 3; підматриця В3 пересилається з процесора 3 на процесор 2; і т.д. Після виконання таких пересилань процесори перемножають свої підматриці А на підматриці В які їм переслали і отримують іще одну частину результату. Такі цикли множення-пересилання повторюються 8 разів. В результаті кожен процесор перемножить свою підматрицю А на кожну підматрицю В і отримає частковий результат.
Після виконання множення і отримання часткових результатів розпочинається збирання результату і його запис в пам’ять. Відповідно до дерева вивантаження, спершу передаються часткові розв’язки від процесорів 5, 2 і 6 до процесора 4, де вони складаються у матрицю С. Із процесорів 8, 3, 1 і 7 часткові розв’язки передаються до процесорів 5, 2 і 6. Часткові розв’язки передаються у процесор 4, у якому після цього вже буде зібрано повний розв’язок, і він розпочне вивантаження матриці С у файл.
Цей процес зображено на функціональній схемі паралельного множення двох матриць із завантаження даних через один процесор (рис.3.1) і на схемі планування обчислень паралельного множення двох матриць із завантаженням даних через один процесор (рис.3.2).
Рис. 3.1 Функціональна схема паралельного множення двох матриць із завантаження даних через один процесор
Як видно із схеми планування обчислень, операції множення і пересилання різних процесорів на етапі обчислення виконуються паралельно на кожному процесорі. Тому час виконання кожного ярусу множення буде рівним найдовшому часу виконання множення і пересилань на ярусі.
На етапі завантаження даних, операції завантаження із пам’яті і передачі від першого процесора даних до першого ярусу дерева завантаження, виконуються послідовно, а операції передачі даних між молодшими ярусами дерева завантаження, і операції читання першим процесором з пам’яті виконуються паралельно.
На етапі збирання результатів операції пересилання від процесорів молодшого яруса дерева вивантаження до процесорів старшого яруса, відбуваються паралельно, так само як вивантаження даних із процесорів першого яруса до головного процесора. Тому час виконання блоку вивантаження буде залежати від часу виконання пересилання даних по найдовшій гілці дерева збору результату (рис. 2.5).
4. Розрахунковий розділ
Для процесорних елементів визначимо такі розміри підматриць:
A1 – A8- 30*176 B1 – B5 – 176*42
B6 – B8 – 176*41
Розбиття матриці А(240x176) на підматриці для кожного процессора
№
Рядків
Стовбців
1
30
176
2
30
176
3
30
176
4
30
176
5
30
176
6
30
176
7
30
176
8
30
176
Розбиття матриці В(176*333) на підматриці для кожного процесора:
№
Рядків
Стовбців
1
176
42
2
176
42
3
176
42
4
176
42
5
176
42
6
176
41
7
176
41
8
176
41
tU = 10tS = 6tP = 8tz = 4tw
tU = 4 * tw
tS = 4/10 * tw
tP = 2/3 * tw
tz = 1/2 * tw
Згідно із завданням, елементи завантажуються через один процесор (type = 2). Вибраний процесор №4. Отже, кількість послідовних операцій завантаження буде рівна числу звертань процесорів до пам’яті.
Nзав = (n1 * n2 + n2 * n3) = 240 * 176 + 176 * 333 = 42240 + 58608 = 100848 – кількість звертань до пам’яті при отриманні обидвох матриць. Звідси, час завантаження матриць:
Tзав = ((n1 * n2 + n2 * n3) * tz = (240 * 176 + 176 * 333) * tz = (42240 + 58608) * tz = 100848 * tz = 50424 * tw
Після того, як дані були завантаженні у один процесор, відбувається «розповсюдження» даних по інших процесорах. Найдовший шлях пересилання даних має вагу 3, найкоротший – 2. Відповідно, час початкового пересилання є:
Tпер = (2 * 30 + 3 * 30 + 2 * 42 + 3 * 41) * 176 * tp = 62832 * tp = 41888 * tw
Процесори готові до роботи, оскільки вони отримали усі необхідні їм дані. Перемноження відбувається «по кільцю», тобто: кожен процесор множить свій рядок на рядок, який приходить до нього (включаючи отримані дані при початковому пересиланні). Виконавши операцію множення, процесор пересилає отриманий раніше рядок наступному процесору, а на вхід отримує новий, який перемножує на «свій» рядок. Таким чином маємо 7 операцій пересилання (коли на вхід процесора приходять дані, які були на початковому розповсюдженню значень, пересилка не виконується) і 8 операцій множення.
Час множення (в найгіршому випадку) на одній ітерації та загальний:
Тмні = N1ч * n2 * N3ч * tu= 30 * 176 * 42 * tu = 221760 * tu = 887040 * tw,
де N1ч – найбільша частина матриці А при розбитті
N3ч – найбільша частина матриці В при розбитті
Тмн = Ttu1 + Ttu2 + ... + Ttu8 = 7096320 * tw
Час додавання (в найгіршому випадку) на одній ітерації та загальний:
Тдоді = N1ч * (n2 - 1) * N3ч* ts = 30 * 175 * 42 * ts = 220500 * ts = 88200 * tw
Тдод = Tts1 + Tts2 + ... + Tts8 = 705600 * tw
Час пересилання (в найгіршому випадку) на одній ітерації (отримання нового рядка та пересилання існуючого)
Тпер.мні = n3ч * N2 * tp = 42 * 176 * tp = 7392 * tp = 4928 * tw
Загальний час пересилання під час процесу множення (в найгіршому випадку) для кількості процесорів p1 = 8:
Тпер.мн. = Tpi * (p1 – 1) * tp = 68992 * tp = 46000 tw
Загальний час пересилання (збору) результатів в процесор 4:
Тзб.рез = (3 * 30 + 3 * 42) * 176 * tp = 38016 * tp = 25344 * tw
Загальний час вивантаження є часом вивантаження одної результуючої матриці С з процесора 4 в пам’ять:
Tвив = n1 * n3 * tw = 240 * 333 * tw= 79920 * tw
Загальний час виконання множення матриць на паралельному алгоритмі, використовуючи дану систему:
Tпар = Tзав + Tпер + Tмн + Tдод + Tпер.мн + Tзб.рез + Tвив = (50424 + 7096320 + 705600 + 46000 + 79920) * tw = 8045496 * tw
Написати, чому я знехтував Т(пер) та Т(зб.рез)
Обрахунок часу виконання послідовного алгоритму множення матриць:
Загальний час множення елементів матриць:
Tпосл.мн = N1 * N2 * N3 * tu = 14065920 * tu = 56263680 tw
Загальний час додавання при обчисленні:
Tпосл.дод = N1 * N3 * (N2 – 1) * ts = 5594400 * tw
Tпос = Tзав + Tпосл.мн + Tпосл.дод + Tвив = 56953464 * tw
Для характеристики алгоритму визначимо коефіцієнт К, який рівний відношенню часу виконання загального алгоритму до часу виконання паралельних операцій.
K = Tпар / (Tпер + Tмн + Tдод + Tпер.мн + Tзб.рез) = 7978264 / (41888 + 7096320 + 705600 + 25344 + 79920) * tw = 1.003
Обрахуємо ефективність алгоритму. Ефективність визначається як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
E = Tпос / (Tпар * P) = 56953464 / (7978264* 8) ≈ 0,892
5. Розробка програми виконання досліджуваної задачі (алгоритму)
5.1. Розробка блок-схеми алгоритму
Першим кроком розробки програми для виконання заданої функції є розробка блок схеми алгоритму.
Рис. 5.1.Блок-схема роботи програми.
Згідно з блок-схемою програма повинна завантажувати дані через один процесор і розсилати їх на всі процесори згідно з вибраним алгоритмом. Після розсилання даних відбувається 8 циклів перемноження матриці. Після того як на кожному процесорі сформується результуючі підматриці всі дані збираються на одному процесорі.
5.2 Вибір середовища
Дана програма написана на мові C++. Для розробки самого паралельного алгоритму множення матриць було обрано шлях використання інтерфейсу передачі повідомлень (МРІ) між процесами, оскільки він має наступні можливості:
створення програм багатопроцесорної обробки інформації;
велика кількість функцій для обміну повідомленнями між процесами;
синхронізація роботи процесів.
MPI - це стандарт на програмний інструментарій для забезпечення зв'язку між гілками паралельного додатка .
MPI розшифровується як "Message passing interface" ("Взаємодія через передачу повідомлень"). Кілька плутає справу той факт , що цей термін вже застосовується по відношенню до апаратної архітектурі ЕОМ. Програмний інструментарій MPI реалізований в тому числі і для ЕОМ з такою архітектурою .
MPI надає програмісту єдиний механізм взаємодії гілок всередині паралельного додатка незалежно від машинної архітектури (однопроцесорні / багатопроцесорні із загальною / роздільною пам'яттю), взаємного розташування гілок (на одному процесорі / на різних ) і API операційної системи.
Програма , що використовує MPI , легше регламентуватиме (звужується простір для здійснення стереотипних помилок паралельного програмування ) і швидше переноситься на інші платформи (в ідеалі , простий перекомпіляцією).
В даний час різними колективами розробників написано кілька програмних пакетів , які відповідають специфікації MPI , зокрема: MPICH , LAM , HPVM і так далі. Вони виступають базовими при перенесенні MPI на нові архітектури ЕОМ.
Мінімально до складу MPI входять: бібліотека програмування (заголовні і бібліотечні файли для мов Сі , Сі + + і Фортран ) і завантажувач додатків.
Опис використаних функцій MPI
В МРІ функціях використовується поняття комунікатор. - це спеціально створений службовий об'єкт, який об'єднує групу процесів і ряд додаткових параметрів (контекст), використовуваних при виконанні операцій передачі даних.
При розробці програмного коду були використані наступні функції бібліотеки МРІ:
int MPI_Init(int *argc, char ***argv), де
argc - вказівник на кількість параметрів командного рядка;
argv - параметри командного рядка.
Використовується для ініціалізації середовища виконання MPI-програми.
int MPI_Finalize(void).
Завершує виконання МРІ програми.
int MPI_Comm_size(MPI_Comm comm, int *size), де
comm - комунікатор, розмір якого визначається;
size - визначена кількість процесів в комунікаторі.
04.06.2014 21:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора