Аналіз ефективності алгоритму Фокса

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ТЕХНОЛОГІЙ ТА ДИЗАЙНУ

КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ПРОЕКТУВАННЯ

Звіт з проектно-технічної практики

Виконав: студент групи БІТ 1-12

Малецький Б. П.

Перевірив: доцент кафедри ІТП

Шрамченко Б. Л.

м. Київ 2015

Завдання на практику

У системі програмування Visual Studio 2010, використовуючи систему паралельного програмування MPI, розробити паралельне застосування для розв'язання наступної задачі: множення матриць за алгоритмом Фокса.

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

Вступ

Будемо вважати, що всі матриці квадратні і мають розмір n x n, кількість блоків по горизонталі і вертикалі однакова і дорівнює q (розмір усіх блоків - k x k, k = n/q). При такій формі даних операцію множення матриць А і B можна представити наступним чином

=

= ,

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

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

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

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

Згідно з алгоритмом Фокса на кожній базовій підзадачі (i, j) розташовуються чотири матричні блоки:

1) блок матриці C;

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

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

алгоритм фокс множення матричний



Рис. 1. Стани блоків в ході обчислень за алгоритмом Фокса.

Метод складається з двох етапів:

1) етап ініціації, на якому кожній підзадачі (I, j) передаються блоки , , і формується нульовий блок ;

2) етап обчислень, на кожній ітерації l, 0 ? 1 < q, якого здійснюються наступні операції:

- для кожного рядка I, 0 ? I < q, блок , підзадачі (I, j) пересилається на всі підзадачі i-го рядка решітки; індекс j, що визначає положення блоку, який пересилається у рядку, обчислюється згідно з виразом

j = (I + 1) mod q;

- отримані в результаті пересилань блоки і кожної підзадачі (I, j) перемножуються, і добуток додається до блоку ;

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

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

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

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

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

Аналіз ефективності алгоритму Фокса

Проведемо аналіз в припущеннях: всі матриці мають розмір n x n, кількість блоків і по горизонталі, і по вертикалі дорівнює q (розмір блоків k ? k, k = n / q), процесори утворюють квадратну решітку, і їх кількість .

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

Загальний аналіз дає ідеальні значення показників. Проведемо детальний аналіз. Складність виконання скалярного множення рядка блока матриці A на стовпець блока матриці B можна оцінити як 2(n / q) - 1. Кількість рядків і стовпців у блоках дорівнює n / q, в результаті трудомісткість операції блочного множення дорівнює при умові . Для додавання блоків потрібно операцій. З урахуванням наведених виразів час виконання обчислювальних операцій алгоритму Фокса оцінюється як

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

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

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

Підсумувавши всі отримані вирази, одержуємо загальний час виконання алгоритму Фокса

Програмна реалізація алгоритму Фокса

Головна функція (main) програми визначає основну логіку роботи алгоритму, послідовно викликаючи необхідні підпрограми. Розглянемо змінні, які використовуються в ній. Перші дві з них (pAMatrix і pBMatrix) - це, відповідно, матриці, які беруть участь в матричному множенні в якості аргументів. Третя змінна pCMatrix - матриця, яка повинна бути отримана в результаті множення. Змінна Size - визначає розмір матриць (припускаємо, що всі матриці квадратні, мають розмірність Size ? Size).

Для збереження матриць використовуються одномірні масиви, в яких матриці зберігаються построково. Таким чином, елемент, розміщений на перетині і-го рядка та і-го стовпця матриці, в одномірному масиві має індекс i * Size + j.

Перед тим як почати виконання паралельного алгоритму слід перевірити, чи являється число доступних процесів повним квадратом:

ProcNum = GridSize ? GridSize.

У випадку, коли ця умова не виконується, виведемо діагностичне повідомлення. Продовжувати виконання програми можна тільки в тому випадку, коли умова виконується.

Назвемо величину GridSize розміром решітки. Ця величина буде використовуватися при розділенні і зборі даних, а також при виконанні ітерацій алгоритму Фокса.

Створення віртуальної декартової топології

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

Для створення декартової топології визначено два масиви: перший DimSize визначає розмірність решітки, а другий Periodic визначає, чи являється решітка періодичною уздовж кожного виміру. Оскільки нам потрібно створити двомірну квадратну решітку, то обидва елементи DimSize визначені наступним чином

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

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

int MPI_Card_coords(MPI_Comm comm, int rank, int ndims, int *coords)

де - comm - комунікатор з топологією решітки,

- rank - ранг процесу, для якого визначаються декартові координати,

- ndims - розмірність решітки,

- coords - декартові координати процесу, що повертає функція.

Глобальна змінна int GridCoords[2] - масив для зберігання координат кожного процесу визначених за допомогою функції MPI_Card_coords.

Для створення комунікаторів для кожного рядка і кожного стовпця процесорної решітки скористаємося функцією з бібліотеки MPI, яка дозволяє розділити решітку на підрешітки:

int MPI_Card_sub(MPI_Comm comm, int *subdims, MPI_Comm *newcomm), де

- comm - вихідний комунікатор з топологією решітки,

- subdims - масив для визначення, які виміри повинні залишитися створеній підрешітці,

- newcomm - створюваний комунікатор з відрешіткою.

Комунікатори для рядка і стовпця також слід оголосити як глобальні (ColComm та RowComm) та розділити вже створений комунікатор GridSize.

Визначення розмірів об'єктів та введення вихідних даних

На наступному етапі розробки програми необхідно задати розмір матриць та виділити пам'ять для зберігання вихідних матриць та їх блоків. Згідно схеми паралельних обчислень (рис. 1) на кожному процесі в кожен момент часу розміщується чотири матричних блоки: два блоки матриці А, блок матриці В і блок матриці С. В головній програмі визначимо змінні для зберігання матричних блоків і розміру цих блоків: int BlockSize, double* pMatrixAblock, double* pAblock, double* pBblock, double* pCblock.

Для визначення розмірів матриць і матричних блоків, виділення пам'яті для їх зберігання і визначення елементів вихідних матриць реалізовано функцію ProcessInitialization.

Завершення процесу обчислень

Для того щоб на кожному етапі розробки програма була завершеною, розроблено функцію ProcessTermination для коректної зупинки процесу обчислень. В ній звільняється пам'ять, виділена динамічно в процесі виконання програми. В якості аргументів передамо цій функції змінні для яких виділялася пам'ять на провідному процесі - pAMatrix, pBMatrix, pCMatrix, pMatrixAblock, pAblock, pBblock, pCblock.

Розподілення даних між процесами

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

Провідний процес - процес з рангом 0, розміщений в лівому верхньому куті процесорної решітки.

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

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

Рис. Перший етап розділення даних

Рис. Другий етап розділення даних

Для блочного розділення матриці між процесами процесорної решітки реалізована функція CheckerboardMatrixScatter. Ця функція приймає в якості аргументів матрицю, яка зберігається на провідному процесі pMatrix, вказівник на буфер збереження матричного блока на кожному з процесів паралельної програми pMatrixBlock, розмір матриці Size і розмір матричного блоку BlockSize.

На першому етапі необхідно розділити матрицю горизонтальними полосами між процесами, що містять нульовий стовпець решітки процесів. Для цього скористаємося функцією MPI_Scatter в рамках комунікатора ColComm. Зазначимо, що в програмі раніше було створено GridSize комунікаторів ColComm. Для того, щоб визначити саме той комунікатор, який відповідає нульовому стовпцю процесорної решітки, скористаємося значеннями, записаними в масиві GridCoords. Функцію MPI_Scatter будемо викликати тільки в тих процесах, у яких значення другої координати рівне 0 (тобто процес розміщеній в нульовому стовпці). Зазначимо, що для тимчасового збереження горизонтальної полоси матриці використовується буфер pMatrixRow.

На другому етапі необхідно розподілити кожен рядок горизонтальної полоси матриці уздовж рядків процесорної решітки. Знову скористаємося функцією MPI_Scatter в рамках комунікатора RowComm. Після виконання цих дій слід звільнити виділену пам'ять.

Для виконання алгоритму Фокса необхідно поблочно розділити матрицю А (блоки матриці зберігаються в змінній pMatrixABlock) і матрицю В (блоки зберігаються в змінній pBlock). Реалізуємо функцію DataDistribution, яка виконує розділення вказаних матриць.

Початок реалізації паралельного алгоритму матричного множення

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

Згідно схеми паралельних обчислень (рис. 1), для виконання матричного множення за допомогою алгоритму Фокса необхідно виконати GridSize ітерацій, кожна з яких складається з виконання трьох дій:

розсилання блоку матриці А по рядку процесорної решітки (для виконання цього кроку реалізовано функцію ABlockCommunication),

виконання множення матричних блоків (для цього реалізована функція SerialResultCalculation)

циклічний зсув блоків матриці В уздовж стовпця процесорної решітки (функція BBlockCommunication).

Тепер розглянемо ці етапи більш детально.

Розсилання блоків матриці А

Отже, на початку кожної ітерації iter алгоритму для кожного рядка процесорної решітки вибирається процес, який буде розсилати свій блок матриці А по процесам відповідного рядка решітки. Номер цього процесу Pivot в рядку визначається в відповідності з виразом

Pivot = (I + iter) mod GridSize

де i - номер рядка процесорної решітки, для якого визначається номер процесу, що розсилається (для кожного процесу номер рядка, в якому він розташований, можна визначити, звернувшись до першого значення масиву GridCoords), а операція mod є операцією підрахунку залишку від ділення. Таким чином, на кожній ітерації, тим що розсилають назначається процес, у якого значення другої координати GridCoords співпадає з Pivot. Після того як номер процесу, що розсилається визначений, необхідно виконати розсилку блока матриці А по рядку. Це робиться за допомогою функції MPI_Bcast в рамках комунікатора RowComm.

Тут нам знадобилося використання додаткового блоку матриці А: перший блок pMatrixAblock зберігає той блок матриці, який був поміщений на даний процес перед початком обчислень, в блок pAblock зберігає той блок матриці, який приймає участь в множенні на даній ітерації алгоритму. Перед виконанням розсилки вміст блока pMatrixBlock копіюється в буфер pAblock, а потім буфер pAblock розсилається на всі процеси рядка.

Циклічний зсув блоків матриці в уздовж стовпців процесорної решітки.

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

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

Для досягнення ефективного і гарантованого одночасного виконання операцій передачі і прийому даних можна скористатися функцією MPI_Sendrecv. Використаємо її для організації циклічного зсуву блоків pBblock матриці B. Кожний процес відправляє повідомлення попередньому процесу того ж стовпця процесорної решітки і приймає повідомлення від наступного процесу. Процес розміщений в нульовому рядку процесорної решітки відправляє свій блок процесу, розміщеному в останньому рядку (рядку під номером GridSize - 1).

Множення матричних блоків

Після того, як блоки матриці А розіслані, необхідно виконати множення блоків pAblock і pBblock, результат цього множення додати до блоку pCblock. Для множення матричних блоків на кожному процесі необхідно виконати послідовний алгоритм матричного множення над матрицями pAblock і pBblock розміру BlockSize?BlockSize і для цього використовується функція SerialResultCalculation.

Функція збору результатів повторяє функцію розподілення вихідних даних, різниця лише в тому, що етапи необхідно виконати зворотному порядку. Спочатку необхідно здійснити збір полоси результуючої матриці з блоків, розташованих на процесорах, що складають стовпець процесорної решітки. Для збору результуючої матриці будемо використовувати функцію MPI_Gather бібліотеки MPI. Ця функція збирає дані із всіх процесів в комунікаторі на одному процесі. Дії, що виконує ця функція, протилежні діям функції MPI_Scatter.

Процедуру збору результуючої матриці С реалізовано в функції ResultCollection.

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

Номер тесту	Розмір матриці	Час роботи для 4 процесів	Час роботи для 9 процесів
1	12	0,000505	0,015954
2	24	0,000739	0,018424
3	72	0,006435	0,060423
4	144	0,032688	0,072813
5	288	0,245135	0,300243
6	432	0,358273	0,516572
7	720	2,999750	2,860021
8	1152	3,578581	3,001812
9	1584	22,225618	25,035123
10	2304	48,064183	47,660679

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

де n - розмір об'єктів, p - кількість процесів, q - розмір процесорної решітки, ? - час виконання одної базової обчислювальної операції, ? - латентність, ? - пропускна здатність мережі передачі даних.



Рис. Графік залежності експериментального і теоретичного часу виконання алгоритму Фокса на чотирьох процесорах.

Висновок

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

Список використаної літератури

Антонов, А.С.Параллельное программирование с использованием технологии MPI: учебное пособие. - М.: Изд-во МГУ, 2004.

Ладогубец, В.В. Параллельные алгоритмы вычислительной математики (курслекций). - К.: АВЕРС, 2006.

Хьюз, К, Хьюз, Т. Параллельное и распределенное программирование на С++. : Пер. с англ. - М.: Издательский дом «Вильямс», 2004.

Размещено на Allbest.ur