ета: Організація багатозадачного режиму обчислення матриць.

Теоретичні відомості

Завдання множення матриці на матрицю, обчислюється співвідношенням:

Для спрощення, будемо розглядати квадратні матриці А і В. Оцінка кількості виконуємих операцій має порядок n³.

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

Інший широко використовуваний підхід для побудови паралельних способів виконання матричного множення, полягає у використанні блокового представлення матриць, при якому початкові матриці A і B і результуюча матриця С, розглядаються у вигляді наборів блоків, як правило квадратного виду деякого розміру m×n. Тоді операцію множення матриць А і В, у блочному виді можливо представити наступним чином(8.2):

А₁₁ А₁₂ … А_1к В₁₁ В₁₂ … В_1к С₁₁ С₁₂ … С_1к

_{... ×... =...} (8.2)

А_к1 А_к2 … А_кк В_к1 В_к2 … В_кк С_к1 С_к2 … С_кк

 

де кожен блок С_ij, матриці С, визначається відповідно до виразу:

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

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

У системі Paralab, реалізовані паралельний алгоритм множення матриць при стрічковій схемі розділення даних і два методи, алгоритм Фокса і Кеннона, для блоково-представлених матриць.

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

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

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