Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць на кільцевій структурі
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет "Львівська політехніка"
Кафедра ЕОМ
/
Курсова робота
з дисципліни
"Паралельні та розподілені обчислення"
на тему
" Паралельне виконання операцій множення матриць на кільцевій структурі "
Варіант №10
Завдання
Розробити структуру та описати процедуру перемноження матриці А (розмірністю n1*n2) на матрицю В (розмірністю n2*n3)а кільцевій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці.
№ вар
Розміри матриці
К-ть
процесорів
Тип початкового
завантаження даних
Співвідношення часових параметрів
N1
N2
N3
10
220
620
90
4
1
tU = 17tS = 4tP =8tZ = 8tW
Примітка:
1*- завантаження початкових даних в процесори через один з них;
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
У варіантах 1-12 процесори можуть тільки послідовно записувати чи читати дані.
Збір даних у варіантах 7-12 проводиться по одному напрямку ( по кільцю)
Анотація
В даній курсовій роботі розроблена структура перемноження матриці на матрицю на кільцевій структурі, завантаження початкових даних в процесори відбувається через один з них. Розміри матриць згідно із варіантом. Також пораховано час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з варіанту.
Курсова робота виконана у середовищі Microsoft Visual Studio 2010 на мові С з використанням бібліотек MPI і має консольний інтерфейс. В курсовій наведено граф-схеми виконання алгоритму множення двох матриць на кільцевій структурі .
Annotation
In this course work was developed the structure of multiplying the matrix by a matrix of ring structure, loading the initial data processors by one of them. Dimensions of matrices according to the task. Also calculated the performance of the algorithm, the percentage of sequential algorithm and the efficiency of the algorithm for the values according to the task Course work is done in Microsoft Visual Studio 2010 on language C with MPI libraries and has a console interface. In the course work there are graph-schemes of algorithm for multiplying two matrices ring structure.
ЗМІСТ
Вступ 6
1. Теоретичний розділ 7
2. Аналіз (розробка) граф-схеми виконання заданої функції 10
3. Розробка функціональної схеми 13
4. Розрахунковий розділ 16
5. Розробка програми 20
Висновки 23
Використана література 24
Додаток (Лістинг програми) 25
Вступ
На даний час є досить широке застосування паралельних алгоритмів. Паралельні алгоритми використовуються для розв’язання таких задач: множення матриці на матрицю, задача Діріхле, розв’язання систем лінійних алгебраїчних рівнянь (СЛАР) методом Гауса і методом простої ітерації та інші. Ефективність паралельної обробки залежить як від продуктивності комп’ютерів, так і від розмірів і структури пам’яті, пропускної здатності каналів зв’язку, використаних мов програмування, компіляторів, операційних систем, чисельних методів та інших математичних досліджень.
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач лінійної алгебри, наприклад ітераційних методів розв’язання систем лінійних рівнянь і т.п.
При розробці паралельних алгоритмів розв’язання складних науково-технічних задач принциповим моментом являється аналіз ефективності використання паралелізму, що полягає зазвичай в оцінці отримуваного прискорення процесу обчислень (скорочення часу вирішення задачі). Формування подібних оцінок прискорення може здійснюватися стосовно вибраного обчислювального алгоритму (оцінка ефективності розпаралелювання конкретного алгоритму). Інший важливий підхід полягає в побудові оцінок максимально можливого прискорення процесу вирішення задачі конкретного типу (оцінка ефективності паралельного способу вирішення задачі).
1. Теоретичний розділ
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач. Для їх реалізації використовуються різні алгоритми та різні структури. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один з процесорів, завантаження даних безпосередньо кожним процесором з розподіленої пам'яті. Якщо завантаження даних здійснюється через один з процесорів, то дані зчитуються цим процесором з пам'яті, розрізаються на частини, які розсилаються іншим процесорам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана в окрему пам'ять, потім кожен процесор безпосередньо зчитує з пам'яті призначений для нього файл.
Алгоритм перемноження матриці на матрицю на кільцевій структурі
Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, смуги записані в пам'ять. Матриця результатів повертається в нульовий процес.
Реалізація алгоритму виконується на кільці з p1 процесорів. Матриці розрізані як наведено на рис. 1.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. scatter A 2. scatter B
/ /7. Збір результатів у С
Рис. 1.2 Стадії обчислень добутку матриць на кільцевій структурі
Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами.
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай tu, ts, і tp час операцій, відповідно, множення, додавання і пересилання одного числа між сусідніми процесорами. Тоді загальний час виконання операцій множення: U = (n1*n2)*(n3*n2)*tu, загальний час виконання операцій додавань: S = (n1*n2)*(n3*(n2-1))*ts, загальний час виконання операцій пересилань даних по всіх процесорах: P = (n3*n2)*(p1-1)*tp.
Загальний час обчислень визначимо як T = (U+S+P)/p1. Відношення часу "обчислень без обмінів" до загального часу обчислень: K = (U+S)/(U+S+P).
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам'ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами - 1.
2. Аналіз (розробка) граф-схеми виконання заданої функції
Згідно завдання потрібно розробити алгоритм перемноження матриці на матрицю на кільцевій структурі із завантаження початкових даних в процесори через один з них. Така структура дозволяє проводити множення над окремими частинами матриць паралельно.
На рис. 2.1 наведено результат розробки граф-схеми виконання алгоритму перемноження двох матриць на кільцевій структурі із завантаження початкових даних в процесори через один з них.
Рис. 2.1. Граф-схема виконання алгоритму множення двох матриць на кільцевій структурі із завантаження початкових даних в процесори через один з них.
Блок 1 означає початок роботи. Блок 2 це пам’ять де містяться матриці.
Початкові дані зчитуються потім розділяються на кількість процесорів(блок 3,4) кожна підматриця для окремого процесора записується у окрему пам’ять(тобто один великий масив ділиться на N менших масивів ). Далі 5 ,6,7 це виконання множення, блок 8 вивід частин результату. Для кінцевого визначення результату необхідно виконати кількість циклів множення рівну кількості процесорів в системі. Тобто, кожен процесор в кінці зчитує з наступного по ходу нову підматрицю та її розміри. Після завершення останнього циклу множення, яке проходить паралельно на кожному процесорі, починається заключна послідовна фаза обчислення добутку, а саме вивантаження часткових результатів . На рисунку 2.2 наведено граф-схему покрокового виконання алгоритму.
Для матриць та і Р процесорів розміри підматриць та визначаються так:
для А та для В обчислюємо
де, та – ціла частина від ділення, та – залишки.
Перші підматриці матриці А матимуть кількість рядків , решту – рядків. Для матриці В, відповідно, , , стовпців.
Рис.2.2 Граф-схема покрокового виконання алгоритму.
3. Розробка функціональної схеми
Функціональні схеми множення матриці на матрицю наведені на рис. 3.1 та 3.2, причому на рис. 3.2 наведена схема покрокового виконання заданого алгоритму. На рис. 3.2 в крайній лівій колонці наведені етапи виконання алгоритму на чотирьох процесорах.
Спочатку кожен з процесорів послідовно зчитує свої підматриці та з окремої пам’яті, після чого система запускається на виконання. Всі процесори, повністю виконавши задане їм множення, відсилають результати у пам’ять по черзі відповідно до свого рангу. Остаточний результат множення матриць буде записано в пам'ять.
Визначимо розміри підматриць Аі та Ві для кожного з процесорів.
,,
,
Рис. 3.1 Граф-схема перемноження матриці
Рис. 3.2. Граф-схема покрокового виконання заданого алгоритму
4. Розрахунковий розділ
Для процесорних елементів визначимо такі розміри підматриць:
А0-3[55, 620], B0-1[620, 22], B2-3[620, 22].
Оскільки кожен процесор завантажує дані зідно із завданням записує ічитає дані паралельно то будуть такі розрахунки.
Отже в даному випадку час завантаження:
29.03.2013 10:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора