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

1. 6.2. Постановка задачі В результаті множення матриці А розмірності mxn і вектора b, що складається...
2. 6.4. поділ даних
3. 6.5. Множення матриці на вектор при поділі даних по рядках
4. 6.5.1. Виділення інформаційних залежностей
5. 6.5.2. Масштабування і розподіл подзадач по процесорам
6. 6.5.3. аналіз ефективності

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

В результаті множення матриці А розмірності mxn і вектора b, що складається з n елементів, виходить вектор c розміру m, кожен i -й елемент якого є результат скалярного множення i -го рядка матриці А (позначимо цю строчку ai) і вектора b:

Тим самим отримання результуючого вектора c передбачає повторення m однотипних операцій по множенню рядків матриці A і вектора b. Кожна така операція включає множення елементів рядки матриці і вектора b (n операцій) і подальше підсумовування отриманих творів (n-1 операцій). Загальна кількість необхідних скалярних операцій є величина

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

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

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

// Алгоритм 6.1 // Поcледовательний алгоритм множення матриці на вектор for (i = 0; i <m; i ++) {c [i] = 0; for (j = 0; j <n; j ++) {c [i] + = A [i] [j] * b [j]}}

Матрично-векторне множення - це послідовність обчислення скалярних добутків. Оскільки кожне обчислення скалярного твори векторів довжини n вимагає виконання n операцій множення і n-1 операцій додавання, його трудомісткість порядку O (n). Для виконання матрично-векторного множення необхідно здійснити m операцій обчислення скалярного твори, таким чином, алгоритм має трудомісткість порядку O (mn).

6.4. поділ даних

При виконанні паралельних алгоритмів множення матриці на вектор, крім матриці А, необхідно розділити ще вектор b і вектор результату c. Елементи векторів можна продублювати, тобто скопіювати всі елементи вектора на всі процесори, складові многопроцессорную обчислювальну систему, або розділити між процесорами. При блоковому розбитті вектора з n елементів кожен процесор обробляє безперервну послідовність з k елементів вектора (ми припускаємо, що розмірність вектора n остачі ділиться на число процесорів, тобто n = kxp).

Пояснимо, чому дублювання векторів b і c між процесорами є допустимим рішенням (далі для простоти викладу будемо вважати, що m = n). Вектори b і з складаються з n елементів, тобто містять стільки ж даних, скільки і один рядок або один стовпець матриці. Якщо процесор зберігає рядок або стовпець матриці і поодинокі елементи векторів b і с, то загальне число зберігаються елементів має порядок O (n). Якщо процесор зберігає рядок (стовпець) матриці і все елементи векторів b і с, то загальне число зберігаються елементів також порядку O (n). Таким чином, при дублюванні і при поділі векторів вимоги до обсягу пам'яті з одного класу складності.

6.5. Множення матриці на вектор при поділі даних по рядках

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

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

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

Для об'єднання результатів розрахунку і отримання повного вектора c на кожному з процесорів обчислювальної системи необхідно виконати операцію узагальненого збору даних (див. "Принципи розробки паралельних методів" ), В якій кожен процесор передає свій обчислений елемент вектора c всім іншим процесорам. Цей крок можна виконати, наприклад, з використанням функції MPI_Allgather з бібліотеки MPI.

У загальному вигляді схема інформаційної взаємодії підзадач в ході виконуваних обчислень показана на Мал. 6.2 .

Мал.6.2.

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

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

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

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

6.5.3. аналіз ефективності

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

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

Розглянемо трудомісткість алгоритму множення матриці на вектор. У разі якщо матриця А квадратна (m = n), послідовний алгоритм множення матриці на вектор має складність T1 = n2. У разі паралельних обчислень кожен процесор виробляє множення тільки частини (смуги) матриці A на вектор b, розмір цих смуг дорівнює n / p рядків. При обчисленні скалярного твори одного рядка матриці і вектора необхідно провести n операцій множення і (n-1) операцій додавання. Отже, обчислювальна трудомісткість паралельного алгоритму визначається виразом:

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

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

(Тут і далі операція є округлення до цілого в більшу сторону).

Оцінка трудомісткості операції узагальненого збору даних вже виконувалася в "Принципи розробки паралельних методів" (Див. П. 4.3.4). Як уже зазначалося раніше, дана операція може бути виконана за log2p ітерацій1. На першій ітерації взаємодіючі пари процесорів обмінюються повідомленнями обсягом (W є розмір одного елемента вектора c в байтах), на другій ітерації цей обсяг збільшується вдвічі і виявляється рівним і т.д. Як результат, тривалість виконання операції збору даних при використанні моделі Хокні може бути визначена за допомогою наступного виразу

де - латентність мережі передачі даних, - пропускна здатність мережі. Таким чином, загальний час виконання паралельного алгоритму становить (для спрощення виразу в (6.8) передбачалося, що значення n / p і log2p є цілими).