НОУ ІНТУЇТ | лекція | Паралельні методи матричного множення

1. 7.1. Постановка задачі
2. 7.2. послідовний алгоритм
3. 7.3. Множення матриць при стрічкової схемі поділу даних
4. 7.3.1. визначення подзадач
5. 7.3.2. Виділення інформаційних залежностей

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

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

Множення матриці A розміру mxn і матриці B розміру nxl призводить до отримання матриці С розміру mxl, кожен елемент якої визначається відповідно до виразу:

Як випливає з (7.1), кожен елемент результуючої матриці С є скалярний добуток відповідних рядка матриці A і стовпці матриці B:

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

7.2. послідовний алгоритм

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

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

// Алгоритм 7.1 // Послідовний алгоритм множення матриць double MatrixA [Size] [Size]; double MatrixB [Size] [Size]; double MatrixC [Size] [Size]; int i, j, k; ... for (i = 0; i <Size; i ++) {for (j = 0; j <Size; j ++) {MatrixC [i] [j] = 0; for (k = 0; k <Size; k ++) {MatrixC [i] [j] = MatrixC [i] [j] + MatrixA [i] [k] * MatrixB [k] [j]; }}}

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

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

Оскільки кожен елемент результуючої матриці є скалярний добуток рядка і стовпця вихідних матриць, то для обчислення всіх елементів матриці С розміром nxn необхідно виконати n2x (2n-1) скалярних операцій і затратити час

де є час виконання однієї елементарної скалярної операції.

7.3. Множення матриць при стрічкової схемі поділу даних

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

7.3.1. визначення подзадач

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

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

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

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

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

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

Можлива проста схема організації необхідної послідовності передач стовпців матриці В між подзадачами полягає в поданні топології інформаційних зв'язків подзадач у вигляді кільцевої структури. У цьому випадку на кожній ітерації подзадача i, 0 <= i <n, буде передавати свій стовпець матриці В подзадаче з номером i + 1 (відповідно до кільцевої структурою подзадача n-1 передає свої дані подзадаче з номером 0) - див. Мал. 7.2 . Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечено - в кожній подзадаче черзі виявляться всі стовпці матриці В.

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

Загальна схема передачі даних для першого паралельного алгоритму матричного множення при стрічкової схемі поділу даних

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

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

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

Загальна схема передачі даних для другого паралельного алгоритми матричного множення при стрічкової схемі поділу даних