Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завдання
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=5Б , n2=3П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Коберник Тарас Богданович КІ-44:
Завдання відповідно варіанту задане в таблиці 1.
Таблиця 1 Завдання відповідно варіанту
Розміри матриць
К-сть
процесорів (Р)
Тип початкового
завантаження даних
Співвідношення часових параметрів
N1
N2
N3
120
110
120
8
Завантаження через 1 процесор
tU=10tS=4tP=6tZ=tW
Згідно з таблицею 1 отримаємо такі значення n1,n2,n3:
n1=3П – А = 120; n2=2І – Б = 110; n3=4Б – А = 120;
Отже маємо матрицю А(120*110) та матрицю В(110*120)
Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44, де «nb»- номер букви П.І.Б студента.
Коберник Тарас Богданович КІ-44:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
К
О
Б
Е
Р
Н
И
К
Т
А
Р
А
С
Б
О
Г
Д
А
Н
О
В
И
Ч
3
1
4
2
5
6
7
8
Отримаємо – БНОРАСГД
Для БНОРАСГД отримаємо 35, 134, 250, 93, 27, 82, 74,13. Даний набір чисел записуємо у стовпець і переводимо і двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
035 - 00100011 00100011
134 - 10000110 10000110
250 - 11111010 11011010
093 - 01011101 01001101
027 - 00011011 => 00010011
082 - 01010010 01010010
074 - 01001010 01001000
013 - 00001101 00001100
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує певну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять). 0809350
type=(0+8+0+9+3+5+0)=25 mod 3 + 1 = 2(через один процесор)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k = 7-кількість цифр в номері залікової книжки.
tU=(9 +1)tS=(3 +1)tP=(5 +1)tZ=(0+1)tW
tU=tW; tS=tw/10; tP=tw/4; tZ=tw/6;
Анотація
В даній курсовій роботі розроблена структура перемноження матриці на матрицю на заданій структурі, завантаження матриць відбувається через один процесор. Процесор через який завантажуються дані є основним і він може взаємодіяти одночасно з трьома процесорами. Виконано обчислення часу виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з варіантом. Розроблена функціональна схема для завантаження даних в процесори, обчислення і збору результатів.
Програма до курсової роботи була розроблена в середовищі Microsoft Visual Studio 2010 на мові С++ з використанням бібліотек MPI. В курсовій роботі наведено граф-схеми виконання алгоритму множення двох матриць.
Зміст
Вступ…………………………………………………………………………………..6
1. Теоретичний розділ 8
2. Проектування граф-схеми виконання алгоритму 12
3. Розробка функціональної схеми 18
4. Розрахунковий розділ 22
5. Розробка програми виконання заданої функції (алгоритму) 29
Висновок
Список використаної літератури
Додатки
Вступ
Внаслідок повсякденного використання обчислювальної техніки бурхливо розвивається напрям числового моделювання (англ. numerical simulation). Числове моделювання, є проміжним елементом між аналітичними методами вивчення і фізичними експериментами. Зростання кількості завдань, для вирішення яких необхідно використовувати паралельні обчислення, обумовлено:
- можливістю вивчати явища, які є або надто складними для дослідження аналітичними методами, або занадто дорогими або небезпечними для експериментального вивчення;
- швидким зростанням складності об'єктів моделювання (ускладнення і збільшення систем);
- виникненням необхідності вирішення завдань, для яких необхідно проведення аналізу складної поведінки (наприклад, умов переходу, до так званого, детермінованому хаосу);
- необхідністю управління складними промисловими і технологічними процесами в режимі реального часу і в умовах невизначеності;
- зростанням кількості завдань, для вирішення яких необхідно обробляти гігантські обсяги інформації (наприклад, 3D моделювання);
При цьому, використання паралельних і кластерних систем, дозволяє значно зменшити вартість процесу наукового і технологічного пошуку.
Створити програму для виконання якої будуть задіяні всі ресурси суперкомп'ютера не завжди можливо. При розробці паралельної програми для розподіленої системи мало розбити програму на паралельні потоки. Для ефективного використання ресурсів необхідно забезпечити рівномірне завантаження кожного з вузлів кластера, що в свою чергу означає, що всі потоки програми повинні виконати приблизно однаковий обсяг обчислень.
Отримання високої ефективності виконання програм ускладнює використання паралельних систем. Відповідно до звіту Міжвідомчої комісії з розвитку надпотужних обчислень США ефективність сучасних (2004 р.) паралельних систем в середньому становить менше 10%.
Домінуюче положення при розробці паралельних програм для паралельних систем займає стандарт MPI (англ. Message Passing Interface). Програма, розроблена в моделі передачі повідомлень, може бути представлена інформаційним графом, вершинам якого відповідають паралельні гілки програми, а ребрам комунікаційні зв'язки між ними. Це можна використовувати для диспетчеризації завдань та їх обчислювальних потоків. Враховуючи гетерогенність обчислювальних ресурсів і середовищ передачі даних у кластері, можна здійснити розподіл обчислювальних потоків (гілок) з обчислювальних вузлів так, щоб мінімізувати накладні витрати на обмін даними між потоками і вирівняти обчислювальне навантаження між вузлами.
Теоретичний розділ
Множення матриці A розміру m x n і матриці B розміру n x k призводить до отримання матриці С розміру m x k, кожен елемент якої визначається відповідно до виразом:
(1.1)
Як випливає з (1.1), кожен елемент результуючої матриці С є скалярний добуток відповідних рядка матриці A та стовпця матриці B (1.2):
(1.2)
Цей алгоритм передбачає виконання m x n x k операцій множення і стільки ж операцій додавання елементів вихідних матриць. При множенні квадратних матриць розміру n x n кількість виконаних операцій має порядок O (n3). Відомі послідовні алгоритми множення матриць, що мають меншу обчислювальної складністю (наприклад, алгоритм Страса (Strassen's algorithm)), але ці алгоритми вимагають великих зусиль для їх освоєння. Також можна припустити, що всі матриці є квадратними і мають розмір n x n.
Для виконання всіх необхідних обчислень базової підзадачі повинні бути доступні один з рядків матриці A і всі стовпці матриці B. Просте вирішення цієї проблеми - дублювання матриці B у всіх підзадача - є, як правило, неприйнятним в силу великих витрат пам'яті для зберігання даних. Тому організація обчислень повинна бути побудована таким чином, щоб в кожний поточний момент часу підзадачі містили лише частину даних, необхідних для проведення розрахунків, а доступ до решти даних забезпечувався б за допомогою передачі даних між процесорами.
Для обчислення одного рядка матриці С необхідно, щоб у кожній підзадачі містилася рядок матриці А і був забезпечений доступ до всіх стовпцях матриці B. Можливі способи організації паралельних обчислень полягають у наступному.
Алгоритм являє собою ітераційну процедуру, кількість ітерацій якої збігається з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному стовпцю матриці В. При виконанні ітерації проводиться скалярний множення містяться в підзадача рядків і стовпців, що призводить до отримання відповідних елементів результуючої матриці С. Після завершення обчислень в кінці кожної ітерації стовпці матриці В повинні бути передані між підзадачами з тим, щоб у кожній підзадачі виявилися нові стовпці матриці В і могли бути обчислені нові елементи матриці C. При цьому дана передача стовпців між підзадачами повинна бути організована таким чином, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно опинилися всі стовпці матриці В.
Можлива проста схема організації необхідної послідовності передач стовпців матриці В між підзадачами полягає в представленні топології інформаційних зв'язків підзадач у вигляді кільцевої структури. У цьому випадку на кожній ітерації підзадача i, 0 <= i <n, буде передавати свій стовпець матриці В підзадачі з номером i+1 (відповідно до кільцевою структурою підзадача n-1 передає свої дані підзадачі з номером 0) - див рис . 1.1 . Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечено - в кожній підзадачі черзі виявляться всі стовпці матриці В.
На рис. 1.1 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців (n = 4). На початку обчислень в кожній підзадачі i, 0 <= i <n, розташовуються i-й рядок матриці A і i-й стовпець матриці B. В результаті їх перемножування підзадача отримує елемент c ii результуючої матриці С. Далі підзадачі здійснюють обмін стовпцями, в ході якого кожна підзадача передає свій стовпець матриці B наступної підзадачі відповідно до кільцевою структурою інформаційних взаємодій. Далі виконання описаних дій повторюється до завершення всіх ітерацій паралельного алгоритму.
Рис. 1.1. Загальна схема передачі даних для першого паралельного алгоритму матричного множення при стрічкової схемою розділення даних
При розглянутому способі розділення даних для виконання операції матричного множення потрібно забезпечити послідовне одержання в підзадачах всіх рядків матриці B, поелементне множення даних і підсумовування знову одержуваних значень з раніше обчисленими результатами. Організація необхідної послідовності передач рядків матриці B між підзадачами також може бути виконана з використанням кільцевої структури інформаційних зв'язків (рис. 1.2 ).
На рис. 1.2 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців (n = 4). На початку обчислень в кожній підзадачі i, 0 <= i <n, розташовуються i-е рядки матриці A і B. матриці В результаті їх перемножування підзадача визначає i-й рядок часткових результатів шуканої матриці C. Далі підзадачі здійснюють обмін рядками, в ході якого кожна підзадача передає свій рядок матриці B наступної підзадачі відповідно до кільцевою структурою інформаційних взаємодій. Далі виконання описаних дій повторюється до завершення всіх ітерацій паралельного алгоритму.
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай tu, ts, і tp час операцій, відповідно, множення, додавання і пересилання одного числа між сусідніми процесорами. Тоді загальний час виконання операцій множення: U = (N1*N3*N2)*tu, загальний час виконання операцій додавань: S = (N1*N3*(N2-1)*ts, загальний час виконання операцій пересилань даних по всіх процесорах: P = (N3*N2)*(p-1)*tp. Загальний час обчислень визначимо як T = (U+S+P)/p.
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам'ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами - 1.
Рефлективна пам'ять. При необхідності організувати зв'язок між кількома обчислювальними пристроями, в кожне з них вставляється мережна карта з 2-х портової рефлективної пам'яттю. Кожному пристрою виділяється певна адресний простір в пам'яті мережевої карти. Для об'єднання карт використовується кільцева топологія.
При запису одним пристроєм даних в свою область пам'яті на мережеву карту, дані копіюються в цю ж область пам'яті на всіх інших мережевих картах. Інші пристрої зчитують передані їм дані з області пам'яті відведеної для обміну даними з пристроєм № 1 своєї мережевої карти. Т.ч. обмін даними для пристроїв абсолютно прозорий і зводиться до операцій читання-запису з пам'яті. Мережева карта для пристрою виглядає як просто область пам'яті.
Для забезпечення можливості одночасного читання-запису з однієї області пам'яті використовується спеціальна 2-х портова пам'ять.
Проектування граф-схеми виконання алгоритму
Алгоритм перемноження матриць на багатопроцесорній структурі складається з декількох етапів:
визначення зв’язків між процесорами, на яких будуть перемножуватись матриці;
розбиття матриць на частини і розсилання кожному процесору його підматриці;
обчислення результату;
збереження результату.
На рис. 2.1. наведена граф-схема зв’язків між процесорами заданої структури. Дана граф-схема дозволяє визначити комунікації між процесорами. При розробці алгоритму множення матриць комунікації відіграють важливу роль. Від зв’язків між процесорами залежить алгоритм розсилання даних, збору і обміну підматрицею Ві при перемноженні матриць.
Рис.2.1. Граф 8-процесорної системи.
Наступним кроком є спосіб розбиття даних між процесорами. Від даного кроку залежить рівномірність навантаження кожного процесора і час простою при різному навантажені. На рис. 2.2 наведено схему розбиття матриць А і В між процесорами. Як видно з схеми навантаження буде рівномірне, так як кожен процесор отримає підматриці рівного розміру.
Рис.2.2. Розбиття матриці між процесорами.
Можна розглянути два варіанти реалізації множення на даній структурі:
повільніший, але більш простіший в реалізації метод, при якому один процесор може одночасно тільки приймати або тільки передавати інформацію.
швидший, але важчий в реалізації метод коли 1 процесор може і приймати і передавати дані одночасно.
Метод 1.
Завантаження даних відбувається через 1 процесор. Вибраний процесор. №7 – через нього буде здійснюватися доступ до пам’яті. Даний процесор може приймати або пересилати дані одночасно не більше, ніж трьом процесорам. Всі інші процесори можуть одночасно тільки приймати або тільки передавати дані одному процесору. Початкове завантаження даних відбувається за схемою рис 2.3:
Рис.2.3. Завантаження даних.
Передача даних з 5-го на 4-тий і 8-мий процесори, а також з 2-го на 6-тий і 1-ший відбувається послідовно, так як 2 і 5 процесори можуть одночасно обмінюватись даними тільки з одним процесором.
Згідно з рис. 2.3 завантаження відбувається наступним чином:
Крок 1: Процесор 7 завантажує підматриці для процесорів 3 і 4
Крок 2: Процесор 7 передає процесорам 2 і 5 підматриці для процесорів 3 і 4 відповідно.
Крок 3: Процесор 7 завантажує дані для процесорів 1 і 8;
Процесор 2 передає дані для 3 процесора процесору 1.
Процесор 5 передає 4-му процесору його підматриці.
Крок 4: Процесор 7 передає дані для 1 і 8 процесорів 2 і 5 процесорам.
Процесор 1 передає 3-му процесору його підматриці.
Крок 5: Процесор 7 завантажує дані для 6 і 5 процесорів.
Процесор 2 передає дані для 1 процесора процесору 1.
Процесор 5 передає дані для 8 процесора процесору 8.
Крок 6: Процесор 7 передає дані для 6 і 5 процесорів 2 і 5 процесорам.
Крок 7: Процесор 7 завантажує дані для процесора 2.
Процесор 2 передає дані для 6 процесора процесору 6.
Крок 8: Процесор 7 передає дані для процесора 2.
Крок 9: Процесор 7 завантажує дані для процесора 7.
На кожному з ярусів для обчислення часу завантаження вибирається операція, яка буде виконуватись найдовше. Збір даних і збереження в пам'ять відбувається за схемою рис. 2.4:
Рис.2.4. Вивантаження даних.
Згідно з рис. 2.4 збереження даних в пам'ять відбувається за 7 роки:
Крок 1: Процесори 1, 8, 6 передають свої результати процесорам 3,5,4 відповідно.
Процесор 7 зберігає свій результат в пам'ять.
Крок 2: Процесори 3,5,2 передають свої дані процесору 7
Крок 3: Процесор 4 передає процесору 2 свій результат.
Процесор 7 зберігає в пам'ять результати процесорів 3,5,2.
Крок 4: процесори 3,5,2 передають процесору 7 дані процесорів 1,8,4
Крок 5: процесор 7 зберігає в пам'ять результати процесорів 1,8,4.
Процесор 4 передає процесору 2 результат процесора 6.
Крок 6: процесор 2 передає результат процесора 6 процесору 7.
Крок 7: процесор 7 зберігає результат процесора 6 в пам'ять.
В даній структурі зв’язків від процесорами можна виділити кільце, тому обмін підматрицею Ві при перемноженні матриць буде виконуватись по вибраному кільцю, яке зображене на рис.2.5:
Рис.2.5. Вибраний кільцевий маршрут передачі підматриць В при множенні
Передача відбувається за 2 кроки:
Крок 1:
1 -> 3, 7->5; 8->6; 4->2;
Крок 2:
3 -> 7, 5->8; 6->4; 2->1;
Де 1-8 – це номери процесорів, а -> вказує від якого до якого процесора відбувається пересилання підматриць B.
Метод 2.
Завантаження і вивантаження даних відбувається через 1 процесор. Вибраний процесор №7 – через нього буде здійснюватися доступ до пам’яті. Одночасно процесор 7 може обмінюватись інформацією з трьома іншими процесорами. Також він має власну пам'ять достатню для розміщення матриці А і матриці В.
Всі інші процесори можуть одночасно приймати від одного процесора дані і передавати іншому. Ці процесори мають власну пам'ять достатню для розміщення підматриць Аi і Вi, які вони будуть перемножувати, місце для результату множення (підматриці розмірністю 15х120) і місце для можливості тимчасового збереження ще одного екземпляру підматриці В іншого процесора.
Виділення додаткової пам’яті для зберігання додаткового екземпляра результату іншого процесора зроблено для того, щоб обмін підматрицею В відбувався паралельно.
Розповсюдження даних між процесорами відбувається за схемою Рис. 2.3.
Передача даних з 5-го на 4-тий і 8-мий процесори, а також з 2-го на 6-тий і 1-ший відбувається послідовно, так як 2 і 5 процесори можуть одночасно обмінюватись даними тільки з одним процесором.
За даною схемою завантаження матриці в процесори відбувається за 5 кроків:
Крок 1. В процесор 7 завантажуються з пам’яті підматриці A3 B3,A4 B4
Крок 2. Процесор 7 передає підматриці A3 B3 процесору 2.
Процесор 7 передає підматриці A4 B4, процесору 5.
Процесор 7 завантажує підматриці A1 B1,A8 B8 з пам’яті.
Крок 3. Процесор 2 передає підматриці A3 B3 процесору 1.
Процесор 5 передає процесору 4 підматрицю A4 B4.
Процесор 7 передає процесору 2 підматрицю A1 B1
Процесор 7 передає процесору 5 підматрицю A8 B8
Процесор 7 завантажує підматриці A5 B5, і A6 B6
Крок 4. Процесор 1 передає процесору 3 підматрицю A3 B3
Процесор 2 передає процесору 1 підматрицю A1 B1
Процесор 5 передає процесору 8 підматриці A8 B8
Процесор 7 передає процесору 5 підматрицю A5 B5
Процесор 7 передає процесору 2 підматрицю A6 B6
Процесор 7 завантажує підматриці A2 B2
Крок 5. Процесор 2 передає процесору 6 підматрицю A6 B6
Процесор 7 передає процесору 2 підматрицю A2 B2
Процесор 7 завантажує підматриці A7 B7
Всі дані завантажені.
На кожному з ярусів для обчислення часу завантаження вибирається операція, яка буде виконуватись найдовше.
Збір даних і збереження в пам'ять відбувається за схемою рис. 2.4
Збереження даних в пам'ять відбувається за 4 роки:
Крок 1 Процесор 7 зберігає результат свого множення в пам'ять.
Процесори 3, 5, 2 передають свої результати процесору 7.
Процесор 1 передає свої результати процесору 3.
Процесор 8 передає свої результати процесору 5.
Процесор 4 передає свої результати процесору 2.
Процесор 6 передає свої результати процесору 4.
Крок 2 Процесор 7 зберігає результати процесорів 2,5,3 в пам’ять.
Процесори 3, 5, 2 передають відповідно результати процесорів 1,8,4 процесору 7.
Процесор 4 передає результат процесора 6 процесору 2.
Крок 3 Процесор 7 зберігає результати процесорів 1,8,4 в пам’ять.
Процесор 2 передає результати процесора 6 процесору 7.
Крок 4 Процесор 7 зберігає в пам'ять результати процесора 6.
В даній структурі зв’язків від процесорами можна виділити кільце, тому обмін підматрицею Ві при перемноженні матриць буде виконуватись по вибраному кільцю, яке зображене на рис.2.5.
Розробка функціональної схеми
Функціональна схема розроблена для другого методу за яким кожен процесор може одночасно приймати і передавати дані:
Рис. 3.1.Частина функціональної схеми, яка відповідає за завантаження даних.
Згідно з схемою рис. 3.1 дані поступово завантажуються і передаються через один процесор, в даному випадку це процесор №7. Процесор 7 через процесори 5 і 2 пересилає підматриці на кожен процесор. В схемі зображені блоки завантаження і пересилання даних. Кожен блок відповідно до часу потрібного для його виконання має відповідні розміри. Весь процес завантаження розділений на п’ять рівнів, кожен рівень синхронізується до операції, яка найдовше виконується.
Рис. 3.2.Частина функціональної схеми, яка відповідає за перемноження матриць.
Відповідно до схеми рис. 3.2 відбувається перемноження матриці А на матрицю В на структурі з 8-ми процесорів. Розмір блоків відповідає часу потрібному для виконання вказаної операції. Процес перемноження складається з 8-ми рівнів перемноження і з 7-ми рівнів пересилання даних. Дана схема складається з блоків множення і блоків пересилання даних.
Рис. 3.3.Частина функціональної схеми, яка відповідає за вивантаження результатів.
За схемою рис. 3.3 процес вивантаження складається з чотирьох рівнів. На кожному рівні синхронізація відбувається згідно блоку, який виконується найдовше. В даній схемі присутні блоки двох типів: пересилання результату і вивантаження в пам'ять. Розміри блоків вказані відповідно до часу який потрібний для їх виконання.
Розрахунковий розділ
Для процесорних елементів визначимо такі розміри підматриць:
A1- A8 = n1*n2 = 15*110; B1-B8 = n2*n3 = 110*15;
Де n1, n2, n3 – розміри підматриць.
k – кількість підматриць, які одночасно завантажуються або пересилаються.
р – кількість процесорів.
tU=(9 +1)tS=(3 +1)tP=(5 +1)tZ=(0+1)tW
tU=tW; tS=tw/10; tP=tw/4; tZ=tw/6
Обчислення для методу за яким один процесор в один час може тільки приймати або тільки передавати дані.
Загальний час виконання операцій завантаження рівний найдовшій операції на кожному кроці і відповідають рис. 2.3 і опису до нього.
Крок 1:
Процесор завантажує частину даних.
Ткz1=k*((n1*n2)+(n2*n3))tz =2*((15*110) + (110*15))tz = 3300 + 3300 = 6600tz = =6600tw/6 = 1100tw
Крок 2:
Процесор передає завантажені дані.
Ткz2=((n1*n2)+(n2*n3))tp=((15*110) + (110*15))tp = 1650+1650=3300tp= =3300tw/4 =825tw
Крок 3:
Процесор завантажує частину даних.
Ткz3=k*((n1*n2)+(n2*n3))tz =2*((15*110) + (110*15))tz = 3300+3300=6600tz = =6600tw/6 = 1100tw
Крок 4:
Процесор передає завантажені дані.
Ткz4=((n1*n2)+(n2*n3))tp=((15*110)+(110*15))tp=1650+1650=3300tp=3300tw/4= 825tw
Крок 5:
Процесор завантажує частину даних.
Ткz5=k*((n1*n2)+(n2*n3))tz =2*((15*110) + (110*15))tz = 3300+3300=6600tz = =6600tw/6 = 1100tw
Крок 6:
Процесор передає завантажені дані.
Ткz6=((n1*n2)+(n2*n3))tp=((15*110) + (110*15))tp = 1650+1650=3300tp= =3300tw/4 = 825tw
Крок 7:
Передача даних по заданій структурі.
Ткz7=((n1*n2)+(n2*n3))tp= ((15*110) + (110*15))tp = 1650+1650=3300tp = =3300tw/4 = 825tw
Крок 8:
Передача даних по заданій структурі.
Ткz8=((n1*n2)+(n2*n3))tp=((15*110)+ (110*15))tp= 1650+1650=3300tp=3300tw/4 = 825tw
Крок 9:
Ткz9=(n1*n2+n2*n3)tz =(15*110 + 110*15)tz = 1650 + 1650 = 3300tz =3300tw/6 = =550tw
Z = Ткz1+ Ткz2+ Ткz3+ Ткz4+ Ткz5+Ткz6+Ткz7+Ткz8+Ткz9= 5*825+3*1100+550= 4125+3300 +550= 7975tw
Після завантаження даних відбувається обробка даних, яка включає в себе 8 циклів операцій множення і додавання та 7 пересилань.
U = (n1*n3*n2)*tu
S = (n1*n3*(n2-1))*ts
P = (n3*n2)*(p1-1)*2*tp
Загальний час множення: U = (120*120*110)*tu = 1584000tu = 1584000tw;
Додавання: S = (120*120*109)*ts = 1569600ts=156960tw;
Пересилання :
Так як пересилання відбуваються за 2 кроки, то загальний час пересилань збільшується в двічі, пересилання виконуються 7 разів:
P = (120*110)*7*2*tp=184800tp=184800tw/4 =46200tw;
Загальний час виконання операцій вивантаження дорівнює сумі найдовших операцій на кожному кроці і відповідає рис. 2.4 і опису до нього.
Крок 1:
Вивантаження даних з процесора в пам’ять:
Ткw1=n1*n3*p*tw=15*15*8tw = 1800tw
Крок 2:
Передача даних між процесорами:
Ткw2=n1*n3*p*tp=(15*15*8)tp = 1800tp=1800tw/4 = 450tw
Крок 3:
Вивантаження даних з процесора в пам’ять:
Ткw3=k*n1*n3*p*tw=3*(15*15*8) = 5400tw
Крок 4:
Передача даних між процесорами:
Ткw4=n1*n3*p*tp=(15*15*8)tp = 1800tp=1800tw/4 = 450tw
Крок 5:
Вивантаження даних з процесора в пам’ять:
Ткw5=k*n1*n3*p*tw=3*(15*15*8) = 5400tw
Крок 6:
Передача даних між процесорами:
Ткw6=n1*n3*p*tp=(15*15*8)tp = 1800tp=1800tw/4 = 450tw
Крок 7:
Вивантаження даних з процесора в пам’ять:
Ткw7=n1*n3*p*tw=15*15*8*tw = 1800tw
Загальний час вивантаження – W = Tкw1 + Tкw2 +Tкw3 + Tкw4 + Tкw5 + Tкw6 + Tкw7 = 3*450tw+2*5400tw + 2*1800tw= 15750tw
Загальний час виконання множення матриць:
T = Z + (U + S + P)/p1 + W = (7975+(1584000+156960+46200)/8+15750)tw =
= 247020tw
Для порівняння обчислимо умовний час виконання послідовного алгоритму:
Час завантаження і час вивантаження будуть такими ж як і в паралельному алгоритмі без пересилань:
Zпос = (N1*N2+N2*N3)tz=(120*110 + 110* 120)tz = 26400tz = 26400tw/6. = 4400tw
Wпос = (N1*N2+N2*N3)tw=(120*110 + 110* 120)tw =.26400tw
Пересилань ніяких не буде, тому час пересилання Pпос = 0.
Час множення буде рівним:
Uпос = (N1*N2*N3) * tU = (120*120*110)*tu = 1584000tu = 1584000tw
Час додавання буде рівним:
Sпос = (N1*N2*N3) * tS = (120*120*109)*ts = 1569600ts=156960tw
Tпос = Zпос + Uпос + Sпос + Wпос = ( 4400 + 1584000 + 156960 + 26400) * tw = 1771760 * tw
Час виконання послідовного алгоритму перемноження однакових матриць на одному процесорі приблизно в 1771760/247020 ≈ 7,17 раз більший, ніж паралельного алгоритму.
Для характеристики алгоритму визначимо коефіцієнт К, який характеризує відсоток послідовних обчислень. Послідовні обчислення характеризуються тим, що в конкретний момент часу працює тільки 1 процесор. В нашому випадку він буде рівний:
K = (Tkz1 + Tkz8+ Tkw7) / T = (1100 + 825 + 1800) / 247020 ≈ 0,015 = 1,5%.
Також порахуємо ефективність паралельного алгоритму. Ефективність визначається, як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
E = TПОС / (T * p1) = 1771760/(247020*8) ≈ 0,897.
Обчислення для методу, в якому дозволяється одночасно приймати і передавати підматриці між процесорами, дані одчислення відповідають розробленій функціональній схемі.
Загальний час виконання операцій завантаження рівний найдовшій операції на кожному кроці.
Крок 1:
Ткz1=k*(n1*n2+n2*n3)tz=2*(15*110 + 110*15)tz = 3300+3300=6600tz=6600tw/6 = 1100tw
Крок 2:
Так як час завантаження є менший, ніж час пересилання, але об’єм завантаження є більший, найдовшою операцією є час завантаження
Ткz2=k*(n1*n2+n2*n3)tz=2*(15*110 +110*15)tz=3300+3300=6600tz=6600tw/6 = 1100tw
Крок 3:
Час завантаження підматриць для 2-х процесорів на даному кроці є найбільшим
Ткz3=k*(n1*n2+n2*n3)tz=2*(15*110+110*15) = 3300+3300=6600tz=6600tw/6 = 1100tw
Крок 4:
Так як час пересилання підматриць для одного процесора є більший за час завантаження підматриць для 1 процесора, то береться час пересилання.
Ткz4=(n1*n2+n2*n3)tP=(15*110+110*15)tP = 3300tP = 3300tw/4 = 825tw
Крок 5:
Найбільший час на даному кроці – час пересилання підматриць для одного процесора
Ткz5=(n1*n2+n2*n3)tP=(15*110+110*15)tP = 3300tP = 3300tw/4 = 825tw
Z = Tкz1 + Tкz2 + Tкz3+ Tкz4 + Tкz5= 1100+1100+1100+825+825 = 4950tw.
Після завантаження даних відбувається обробка даних, яка включає в себе 8 циклів операцій множення і додавання та 7 пересилань.
U = (n1*n3*n2)*tu
S = (n1*n3*(n2-1))*ts
P = (n3*n2)*(p1-1)*tp
Загальний час множення: U = (120*120*110)*tu = 1584000tu = 1584000tw;
Додавання: S = (120*120*109)*ts = 1569600ts=156960tw;
Пересилання : P = (120*110)*7*tp=92400tp=92400tw/4 =23100tw;
Загальний час виконання операцій вивантаження дорівнює сумі найдовших операцій на кожному кроці.
Крок 1:
Вивантаження даних з процесора в пам’ять:
Ткw1=n1*n3*p*tw=15*15*8* tw= 1800tw
Крок 2:
Вивантаження даних з процесора в пам’ять:
Ткw2=k*n1*n3*p*tw=3*15*15*8* tw = 5400tw
Крок 3:
Вивантаження даних з процесора в пам’ять:
Ткw3=k*n1*n3*p*tw=3*15*15*8* tw = 5400tw
Крок 4:
Вивантаження даних з процесора в пам’ять:
Ткw4=n1*n3*p*tw=15*15*8* tw = 1800tw
Загальний час вивантаження – W = Tкw1 + Tкw2 +Tкw3+ Tкw4 = 1800tw+5400tw+5400tw + 1800tw= 14400tw
Загальний час виконання множення матриць:
T = Z + (U + S + P)/p1 + W = (4950+(1584000+156960+23100)/8+14400)tw =
= 239857,5tw
Час послідовного множення буде аналогічним, як і для методу 1.
Час виконання послідовного алгоритму перемноження однакових матриць на одному процесорі приблизно в 1771760/239857,5 ≈ 7,39 раз більший, ніж паралельного алгоритму.
Для характеристики алгоритму визначимо коефіцієнт К, який характеризує відсоток послідовних обчислень. В нашому випадку він буде рівний:
K = (Tkz1 + Tkw4) / T = (1100 + 1800) / 239857,5 ≈ 0,012 = 1,2%.
Також порахуємо ефективність паралельного алгоритму. Ефективність визначається, як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
E = TПОС / (T * p1) = 1771760/(239857,5*8) ≈ 0,923.
Розробка програми виконання заданої функції (алгоритму)
Першим кроком розробки програми для виконання заданої функції є розробка блок схеми алгоритму.
Рис. 5.
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора