Реферат паралельні методи множення матриці на вектор



Скачати 367.44 Kb.
Сторінка1/2
Дата конвертації09.11.2017
Розмір367.44 Kb.
ТипРеферат
  1   2




РЕФЕРАТ
Паралельні методи множення матриці на вектор // Курсова робота // Якубів Петро Степанович // Тернопільський національний технічний університет імені Івана Пулюя, факультет комп'ютерно-інформаційних систем і програмної інженерії, кафедра комп’ютерних наук, група СНм-51 // Тернопіль, 2016 // c. – _ , рис. – _ , табл. – _ , додат. – _ , бібліогр. – _ , креслення - _.
Ключові слова: МАТРИЦЯ, ВЕКТОР, ПАРАЛЕЛЬНІ ОБИЧСЛЕННЯ, GRID.
Метою роботи є: продемонструвати реалізацію множення матриці на векто
ЗМІСТ
Вступ

1 Основний розділ



    1. Постановка задачі

  1. Виконання завдання

2.1 Послідовний алгоритм

2.2 Множення матриць при стрічковій схемі розділення даних

2.2.1 Визначення підзадач

2.2.2 Виділення інформаційних залежностей

2.2.3 Масштабування і розприділення під задач по процесорам

2.2.4 Аналіз ефективності

2.2.5 Результати обчислювальних експериментів

2.3 Алгоритм Фокса множення матриць при блоковому розділенні даних

2.3.1 Визначення під задач

2.3.2 Виділення інформаційних залежностей

2.3.3 Масштабування і розприділення під задач по процесорам

2.3.4 Аналіз ефективності

2.3.5 Результати обчислювальних експериментів

2.4 Алгоритм Кэннона множення матриць при блоковому розділенні даних

2.4.1 Визначення під задач

2.4.2 Виділення інформаційних залежностей

2.4.3 Масштабування і розприділення під задач по процесорам

2.4.4 Аналіз ефективності

2.4.5 Результати обчислювальних експериментів

Висновок

Перелік використаних джерел
ВСТУП
Операція множення матриць є одним із основних завдань матричних обчислень. У даному розділі розглядаються декілька різних паралельних алгоритмів для виконання цієї операції. Два з них засновані на стрічковій схемі розділення даних. Інші два методи використовують блокову схему розділення - це широко відомі алгоритми Фокса(Fox) і Кэннона(Cannon).

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



  • більшу швидкодію;

  • більший обєм оперативної пам’яті;

  • більшу кількість передаючої інформації;

  • опрацювання і збереження великої кількості інформації.

Якщо присутній хоча б один з перерахованих вимог, то використання високопродуктивних обчислень необхідно і виправдано.

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




1 ОСНОВНИЙ РОЗДІЛ
1.1 Постановка задачі
Множення матриці A розміру і матриці B розміру приводить до отримання матриці C розміру , кожен елемент якої визначається відповідно до виразу.

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

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

2 ВИКОНАННЯ ЗАВДАННЯ
2.1 Послідовний алгоритм

матриця інформаційний залежність алгоритм

Послідовний алгоритм множення матриць реалізується трьома вкладеними циклами:
// Алгоритм 1.2

double MatrixA[Size][Size];

double MatrixB[Size][Size];

double MatrixC[Size][Size];

int i,j,k;

...


for (i=0; ifor (j=0; j

MatrixC[i][j] = 0;

for (k=0; k

MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j];

}

}



}
Алгоритм 1.1. Послідовний алгоритм множення двох квадратних матриць.

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

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

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

де це час виконання однієї елементарної скалярної операції.
2.2 Множення матриць при стрічковій схемі розділення даних
Розглянемо два паралельні алгоритми множення матриць, в яких матриці A і B розбиваються на безперервні послідовності рядків або стовпців(смуги).
2.2.1 Визначення підзадач

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

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

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


2.2.2 Виділення інформаційних залежностей

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

1) Перший алгоритм. Алгоритм є ітераційною процедурою, кількість ітерацій якої співпадає з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному стовпцю матриці В. При виконанні ітерації проводиться скалярне множення рядків, що містяться в підзадачах, і стовпців, що призводить до отримання відповідних елементів результуючої матриці С. Після закінчення обчислень у кінці кожної ітерації стовпці матриці В мають бути передані між підзадачами так, щоб у кожній підзадачі опинилися нові стовпці матриці В і могли бути вичислені нові елементи матриці C. При цьому така передача стовпців між підзадачами має бути організована так, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно опинилися усі стовпці матриці В.

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

Представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців(n=4). На початку обчислень в кожній підзадачі , розташовуються -ий рядок матриці A та -ий стовпець матриці B. В результаті їх перемножування підзадача отримує елемент результуючої матриці С. Далі підзадачі здійснюють обмін стовпцями, в ході якого кожна підзадача передає свій стовпець матриці B наступній підзадачі відповідно до кільцевої структури інформаційних взаємодій. Виконання описаних дій повторюється до завершення усіх ітерацій паралельного алгоритму.

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

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

Представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців. На початку обчислень в кожній підзадачі, розташовуються i рядки матриці A і матриці B. В результаті їх перемножування підзадача визначає i-ий рядок часткових результатів шуканої матриці C. Далі підзадачі здійснюють обмін рядками, в ході якого кожна підзадача передає свій рядок матриці B наступній підзадачі відповідно до кільцевої структури інформаційних взаємодій. Далі виконання описаних дій повторюється до завершення усіх ітерацій паралельного алгоритму.


2.2.3 Масштабування і роз приділення під задач по процесорам

Виділені базові підзадачі характеризуються однаковою обчислювальною складністю і рівним об'ємом передаваних даних. У разі, коли розмір матриць виявляється більшим, за число процесорів , базові підзадачі можна збільшити, об'єднавши у рамках однієї підзадачі декілька сусідніх рядків і стовпців перемножуваних матриць. В цьому випадку, початкова матриця A розбивається на ряд горизонтальних смуг, а матриця B представляється у вигляді набору вертикальних(для першого алгоритму) або горизонтальних(для другого алгоритму) смуг. Розмір смуг при цьому слід вибрати рівним k=n/p(при кратно), що дозволить як і раніше забезпечити рівномірність розподілу обчислювального навантаження на процесори, які складають багатопроцесорну обчислювальну систему.

Для розподілу підзадач між процесорами може бути використаний будь-який спосіб, що забезпечує ефективне представлення кільцевої структури інформаційної взаємодії підзадач. Для цього досить, наприклад, щоб підзадачі, що є сусідніми в кільцевій топології, розташовувалися на процесорах, між якими є прямі лінії передачі даних.
2.2.4 Аналіз ефективності

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

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

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

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

З урахуванням числа і тривалості виконуваних операцій час виконання обчислень паралельного алгоритму може бути оцінений таким чином.

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

де α – латентність, β – пропускна здатність мережі, а w – розмір елементу матриці в байтах

Відповідно до отриманих співвідношень загальний час виконання паралельного алгоритму матричного множення визначається наступним вираженням.
2.2.5 Результати обчислювальних експериментів

Експерименти проводилися в обчислювальному кластері на базі процесорів Intel XEON 4 EM64T, 3000 Мгц і мереж Gigabit Ethernet під управлінням операційної системи Microsoft Windows Server 2003 Standart x64 Edition

Для оцінки тривалості базової скалярної операції відбувалося вирішення задачі множення матриць за допомогою послідовного алгоритму і отриманий таким чином час обчислень ділилвся на загальну кількість виконаних операцій, в результаті подібних експериментів для величини було отримано значення 6.4 нс. Експерименти, виконані для визначення параметрів мережі передачі даних, показали значення латентності і пропускної здатності відповідно 130 мкс і 53.29 Мбайт/с. Усі обчислення робилися над числовими значеннями типу double, т. е. величина дорівнює 8 байт.

Результати обчислювальних експериментів приведені в таблиці 2.1. Експерименти виконувалися з використанням двох, чотирьох і восьми процесорів.


Таблиця 2.1. Результати обчислювальних експериментів по дослідженню першого паралельного алгоритму матричного множення при стрічковій схемі розподілу даних

Розмір матриць

Послідовний алгоритм

2 процесори

4 ЦП

8 ЦП










час

Прискорення

час

Прискорення

час

Прискорення

500

0,8752

0,3758

2,3287

0,1535

5,6982

0,0968

9,0371

1000

12,8787

5,4427

2,3662

2,2628

5,6912

0,6998

18,4014

1500

43,4731

20,9503

2,0750

11,0804

3,9234

5,1766

8,3978

2000

103,0561

45,7436

2,2529

21,6001

4,7710

9,4127

10,9485

2500

201,2915

99,5097

2,0228

56,9203

3,5363

18,3303

10,9813

3000

347,8434

171,9232

2,0232

111,9642

3,1067

45,5482

7,6368

Порівняння експериментального часу виконання експерименту і теоретичного часу з формули(1.8) представлені в таблиці 2.2.


Таблиця 2.2. Порівняння експериментального і теоретичного часу виконання першого паралельного алгоритму матричного множення при стрічковій схемі розподілу даннях

Розмір матриць

2 процесори

4 ЦП

8 ЦП










час

Прискорення

час

Прискорення

час

Прискорення

500

0,8243

0,3758

0,4313

0,1535

0,2353

0,0968

1000

6,51822

5,4427

3,3349

2,2628

1,7436

0,6998

1500

21,9137

20,9503

11,1270

11,0804

5,7340

5,1766

2000

51,8429

45,7436

26,2236

21,6001

13,4144

9,4127

2500

101,1377

99,5097

51,0408

56,9203

25,9928

18,3303

3000

174,6301

171,9232

87,9946

111,9642

44,6772

45,5482

З результатів в таблицях можна зробити висновок продуктивності алгоритму.


2.3 Алгоритм Фокса множення матриць при блоковому розділенні даних
При побудові паралельних способів виконання матричного множення разом з розглядом матриць у вигляді наборів рядків і стовпців широко використовується блокове представлення матриць. Виконаємо детальніший розгляд цього способу організації обчислень.
2.3.1 Визначення підзадач

Блокова схема розбиття матриць детально розглянута в попередньому підрозділі. При такому способі розділення даних початкові матриці, і результуюча матриця представляються у вигляді наборів блоків. Для простішого викладу матеріалу матимемо на увазі, що усі матриці є квадратними розміру кількість блоків по горизонталі і вертикалі є однаковою і рівною (тобто розмір усіх блоків рівний). При такому представленні даних операція множення матриць А і B у блоковому виді може бути представлена так.

При блоковому розбитті даних для визначення базових підзадач за основу беруться обчислення, що виконуються над матричними блоками. З урахуванням сказаного визначимо базову підзадачу як процедуру обчислення усіх елементів одного з блоків матриці .

Для виконання усіх необхідних обчислень базовим підзадачам мають бути доступні відповідні набори рядків матриці A і стовпців матриці B. Розміщення усіх необхідних даних в кожній підзадачі неминуче приведе до дублювання і до значного зростання об'єму використовуваної пам'яті. Як результат, обчислення мають бути організовані так, щоб в кожен теперішній момент часу підзадачі містили лише частину необхідних для проведення розрахунків даних, а доступ до іншої частини даних забезпечувався б за допомогою передачі повідомлень. Один з можливих підходів – це алгоритм Фокса(Fox).


2.3.2 Виділення інформаційних залежностей

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

Можливий спосіб організації обчислень за таких умов полягає в застосуванні широко відомого алгоритму Фокса(Fox), - див, наприклад, Fox et al. (1987)Kumar et al. (1994).

Відповідно до алгоритму Фокса в ході обчислень на кожній базовій підзадачі розташовується чотири матричні блоки:



  • блок матриці , що обчислюється підзадачею;

  • блок матриці , що розміщується в підзадачі перед початком обчислень;

  • блоки , матриць і , що отримуються підзадачею в ході виконання обчислень.

Виконання паралельного методу включає:

  • етап ініціалізації, на якому кожній підзадачі передаються блоки , і обнуляються блоки в усіх підзадачах;

  • етап обчислень, у рамках якого на кожній ітерації , здійснюються наступні операції:

  • для кожного рядка , ,блок підзадачі пересилається в усі підзадачі того ж рядка грат; індекс , що визначає положення підзадачі в рядку, обчислюється відповідно до виразу.

де – це операція отримання залишку від цілочисельного ділення;

  • отримані в результати пересилок блоки , кожної під задачі перемножуються і додаються до блоку ;

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


2.3.3 Масштабування і розподіл підзадач по процесорах

У розглянутій схемі паралельних обчислень кількість блоків може змінюватися залежно від вибору розміру блоків. Ці розміри можуть бути підібрані так, щоб загальна кількість базових підзадач співпадала з числом процесорів . Так, наприклад, в найбільш простому випадку, коли число процесорів можна спів ставити з (тобто є повним квадратом) можна вибрати кількість блоків в матрицях по вертикалі і горизонталі рівною. Такий спосіб визначення кількості блоків призводить до того, що об'єм обчислень в кожній підзадачі є однаковим і, тим самим, досягається повне балансування обчислювального навантаження між процесорами. У загальному випадку при довільних кількості процесорів і розмірах матриць балансування обчислень може бути не однаковим, але за належного вибору параметроів може бути оптимізованим.

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


Каталог: uploads -> 877173f1-52e0-4a1f-a4ae-d078558a1aa4
uploads -> Правила прийому до аспірантури та докторантури київського національного університету культури І мистецтв
uploads -> Положення про аспірантуру Миколаївського національного університету імені В. О. Сухомлинського Загальна частина
uploads -> Програма дисципліни «іноземна мова (англійська)»
uploads -> Положення правил прийому до нту "хпі" на 2016 рік правила прийому 2016 Організацію прийому до нту "хпі" та його структурних підрозділів здійснює приймальна комісія правила прийому 2016
uploads -> Програма та методичні вказівки з навчальної дисципліни історія науки І техніки для студентів усіх спеціальностей денної форми навчання
uploads -> Лекція № Тема лекції: Поняття мистецтва як частини культури
uploads -> Афінська держава та стародавня спарта у стародавній історії та культурі людства
uploads -> Київський національний лінгвістичний університет базові навчально-методичні матеріали
uploads -> Освіта осіб з інвалідністю в Україні Тематична національна доповідь Київ -2010 Тематичну національну доповідь «Освіта осіб з інвалідністю в Україні»
877173f1-52e0-4a1f-a4ae-d078558a1aa4 -> Перелік умовних позначень, символів, одиниць, скорочень І термінів

Скачати 367.44 Kb.

Поділіться з Вашими друзьями:
  1   2




База даних захищена авторським правом ©uchika.in.ua 2020
звернутися до адміністрації

    Головна сторінка