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

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

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

(8.1)

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

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

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

А11 А12 … А1к В11 В12 … В1к С11 С12 … С1к

. . . × . . . = . . . (8.2)

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

 

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

(8.3)

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

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

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

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

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

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

Хід роботи:

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

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

3. До звіту внесіть графік залежності часу від розмірів масиву.

 

Таблиця 7.1

Варіанти для виконання лабораторної роботи

№ Варіанта Топологія Число вузлів Латентність
Решітка
Кільце
Повний граф
Решітка
Кільце
Повний граф
Решітка
Кільце
Повний граф
Решітка
Кільце
Повний граф

Контрольні запитання:

1. Поясніть яким чином проводиться паралельне обчислювання матриць.

2. Поясніть на що впливає латентність у обчислюванні множення матриць.

3. Які методи паралельного обчислювання матриць ви знаєте? У чому полягає їх суть.

4. Що таке стрічкова схема обчислювання матриць.

5. Опишіть алгоритми Фокса і Кеннона.

Література.

1. Столлінгс У. «Структурная организация и архитектура компьютерных систем.» М, СПб, Київ, «Вільямс», 2002.

2. Бройдо В.Л. «Вычислительные системы, сети и телекоммуникации.» - С-П: Пітер, 2002.

3. Столінгс В. «Компьютерные системы передачи данных». - С-П: Пітер, 2002.

4. Таненбаум Е. «Компьютерные сети». - С-П: Пітер, 2002.

5. Таненбаум Е. «Архитектура компьютеров». - С-П: Пітер, 2002.