Паралельне виконання операцій множення матриць

 

1.3 Сучасні методи  та інструменти для паралельної  обробки

Багатоядерне програмування  для x86 процесорів складне, і часто  максимальний результат приросту продуктивності досягається при переході від 1 ядра до 4 ядер, та від 4 до 16 ядер. Однак, при  використанні 4 ядер, пропускна здатність  пам'яті стає вузьким місцем для  подальшого зростання продуктивності. Щоб використати переваги паралельних  обчислень графічних процесорів, програмісти можуть просто змінити  вимогливі до продуктивності частини  програми і скористатися сотнями  паралельних ядер GPU. Решта частина  додатка не змінюється, що дозволяє найбільш ефективно використовувати  всі ядра в системі. Запуск функції  на GPU вимагає переписати код цієї функції та реалізувати її паралелізм, потім додати нові виклики функцій, вказавши, які саме функції будуть оброблятись на GPU і які на CPU. Завдяки  цим змінам, вимогливі до продуктивності частини додатку тепер можуть виконуватись значно швидше на GPU.

Універсальні обчислення на графічних процесорах (GPGPU) є методика використання GPU, які зазвичай мають  справу з обчисленнями тільки для  комп'ютерної графіки, виконувати обчислення в додатках, що традиційно обробляються центральними процесорами. Це стало  можливим завдяки включенню програмованих  шейдерних блоків та більш високої  арифметичної точності конвеєрів візуалізації, що дозволило розробникам програмного  забезпечення використовувати потокові процесори задля не-графічних  даних.

CUDA (англ. Compute Unified Device Architecture) - програмно-апаратна архітектура,  яка дозволяє робити обчислення  з використанням графічних процесорів NVIDIA, що підтримують технологію GPGPU (англ. General-Purpose computing on Graphics Processing Units) - обчислення загального призначення  на графічних процесорах. Це архітектура  паралельних обчислень від NVIDIA, що дозволяє істотно збільшити  обчислювальну продуктивність завдяки  використанню GPU (графічних процесорів).

Напрямок обчислень еволюціонує  від «централізованої обробки даних» на центральному процесорі до «спільної  обробки» на CPU і GPU. Для реалізації нової обчислювальної парадигми компанія NVIDIA винайшла архітектуру паралельних обчислень CUDA, на даний момент представлену в графічних процесорах GeForce, ION, Quadro, Tesla і забезпечує необхідну базу розробникам ПЗ.

1.3.1 Технологія NVIDIA® CUDA™

Єдине середовище розробки на C, яка дозволяє програмістам і  розробникам писати програмне забезпечення для вирішення складних обчислювальних завдань за менший час завдяки  багатоядерній обчислювальній потужності графічних процесорів. У світі  вже встановлені мільйони GPU з  підтримкою CUDA, і тисячі програмістів безкоштовно користуються інструментами CUDA для прискорення обчислювальних додатків - від кодування відео  та аудіо до пошуків нафти і  газу, моделювання геному людини, виведення  тривимірних томографічних зображень  і ще цілого ряду обчислювальних завдань  в науково-дослідницькій та прикладній сфері. CUDA SDK дозволяє програмістам реалізовувати  на спеціальному спрощеному діалекті мови програмування С алгоритми, здійснимі на графічних процесорах NVIDIA, і включати спеціальні функції  в текст програми на Cі. CUDA дає  розробникові можливість на свій розсуд організовувати доступ до набору інструкцій графічного прискорювача і управляти  його пам'яттю, організовувати на ньому  складні паралельні обчислення.

 

2.Розробка граф-схеми виконання множення матриць

На основі даних із таблиці 1.3. будуємо граф з’єднань процесорів:

Рис.2.1. Граф з’єднань у структурі процесорів

Використання усіх зв’язків між процесорами для вирішення  даної задачі – недоцільне, і  навіть може призвести до втрати продуктивності, тому найкраще розробити граф кільця передачі даних між процесорами (рис. 2.3). Для реалізації алгоритму перемноження матриць ми вирішили, як матриці розподілені між процесорами. Вибрано наступний тип розбиття: матриця А – стрічково-горизонтальне розбиття, матриця В - стрічково-вертикальне розбиття (рис. 2.2) для зручного множення.

Рис.2.2. Результат розбиття матриць

Для отримання часткових  результатів на кожному з процесорів, необхідно виконувати пересилання  підматриць В між процесорами. Цю дію можна виконувати по певному замкнутому кільцю. Приклад такого кола наведено на Рис.2.3.

Рис.2.3. Кільце передачі даних між процесорами

Оскільки завантаження початкових даних здійснюється через один процесор, який може одночасно обмінюватися даними із трьома процесорами, то необхідно  виділити у структурі (рис. 2.1) певні дерева зв’язків, по яких буде проводитися завантаження початкових даних у процесори (рис. 2.4) і вивантаження часткових результатів у головний процесор (рис. 2.5).

Рис.2.4. Дерево завантаження вхідних даних

Рис.2.5. Дерево вивантаження результату

Дана структура дозволяє проводити множення над окремими частинами матриць паралельно, завдяки чому ми бачимо пришвидшення нашого алгоритму.

На рис. 2.6 наведено граф-схему виконання алгоритму перемноження двох матриць з завантаженням даних через один процесор.

 

 

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

На граф-схемі (рис. 2.6) представлено n процесорних елементів (в нашому випадку – 8). Дані завантажуються першим процесором, який має доступ до пам’яті. Він у відповідності із деревом завантаження вхідних даних (рис. 2.4) розсилає дані всім іншим процесорам. Кожен процесор отримує свою підматрицю А та B. Після завершення розсилки даних розпочинається сам процес обчислення, під час якого обмін між процесорами відбувається по структурі зв’язків за маршрутом, вказаним на рис. 2.3. Процес множення – пересилання підматриці В повторюється 8 разів і множення її на під матриці А. Після виконання останнього перемноження розпочинається збір результатів. В результаті чого всі процесори у відповідності із деревом вивантаження (рис. 2.5) перешлють часткові результати до першого процесора, який їх складає у повну матрицю-результат (матрицю С) і записує її у пам’ять.

 

3. Розробка функціональної схеми

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

Підчас завантаження даних  із пам’яттю працює лише один процесор. Спершу він завантажує підматриці А3 і В3 і надсилає їх у процесор 5. Після цього він завантажує підматриці А і В для процесорів 7, 8 і 6, а в той же час процесор 5 передає підматриці процесора 3 до процесора 7. Процесор 2 передає завантажені частини до процесорів 5, 1 і 4, а процесор 7 передає процесору 3 його підматриці. Доки процесори 5, 1 і 4 пересилають процесорам 7, 8 і 6 їхні підматриці, процесор 2 завантажує підматриці для процесорів 5, 1 і 4. Після цього він передає завантажені підматриці до процесорів, яким вони належать і звільнившись, завантажує підматриці А2 і В2. На цьому процес завантаження завершується і розпочинається процес обчислення.

Процесори перемножують елементи матриць, які були у них попередньо завантаженні і отримують частину  результату. Після обчислень відбувається пересилання підматриць В по кільцю 1→2→5→7→6→3→8→4→1. Отже, підматриця В1 пересилається з процесора 2 на процесор 1; підматриця В5 пересилається з процесора 1 на процесор 8; і т.д. Після виконання таких пересилань процесори перемнужають свої підматриці А на підматриці В які їм переслали і отримують іще одну частину результату. Такі цикли множення-пересилання повторюються 8 разів. В результаті кожен процесор перемножить свою підматрицю А на кожну підматрицю В і отримає частковий результат.

Після виконання множення і отримання часткових результатів  розпочинається збирання результату і  його запис в пам’ять. Відповідно до дерева вивантаження, спершу передаються  часткові розв’язки від процесорів 1, 5 і 7 до процесора 2, де вони складаються у матрицю С. Із процесорів 4, 6 і 3 часткові розв’язки передаються до процесорів 1, 5 і 7. Потім із процесора 8 підматриця С вивантажується у процесор 3, а процесори 1, 5 і 7 вивантажують у процесор 2 наступну групу часткових розв’язків. Частковий розв’язок процесора 8 передається із процесора 3 у процесор 7, і нарешті передається у процесор 2, у якому після цього вже буде зібрано повний розв’язок, і він розпочне вивантаження матриці С у файл.

Цей процес зображено на функціональній схемі паралельного множення двох матриць із завантаження даних через один процесор (рис.3.1) і на схемі планування обчислень паралельного множення двох матриць із завантаженням даних через один процесор (рис.3.2).

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

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

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

 

 

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

 

 

 

Рис. 3.2  Схема планування обчислень при паралельному множенні двох матриць із завантаження даних через один процесор

 

4. Розрахунковий розділ

Для порівняння продуктивності виконання множення при використанні паралельного та послідовного алгоритму, проведемо ряд обчислень.

Множення відбувається наступним  чином: процесори перемножують відповідну підматрицю матрицю А та підматрицю B.

За заданими вхідними даними співвідношення часових параметрів згідно варіанту:

tu=10ts=6tp=5tz=7tw

4.1 Визначення розмірності підматриць

Для процесорних елементів  визначимо такі розміри підматриць:

A1(30,248) – кількість елементів 7440

A2(30,248) – кількість елементів 7440

A3(30,248) – кількість елементів 7440

A4(30,248) – кількість елементів 7440

A5(30,248) – кількість елементів 7440

A6(30,248) – кількість елементів 7440

A7(30,248) – кількість елементів 7440

A8(30,248) – кількість елементів 7440

 

B1(248,8) – кількість елементів 1984

B2(248,8) – кількість елементів 1984

B3(248,8) – кількість елементів 1984

B4(248,8) – кількість елементів 1984

B5(248,8) – кількість елементів 1984

B6(248,9) – кількість елементів 2232

B7(248,9) – кількість елементів 2232

B8(248,9) – кількість елементів 2232

 

 

 

4.2 Розрахунок часу виконання послідовного алгоритму

За заданими вхідними даними виразимо тривалість всіх операцій, які  виконуються, через тривалість операції вивантаження даних tw. І так маємо:

T_u = 7*tw

T_s = 7/10*tw

T_p = 7/6*tw

T_z = 7/5*tw

Час виконання операцій завантаження:

T_z=(n1*n2+n2*n3)*t_z=(240*248+248*67)*t_z=(59520+16616)*t_z=76136*t_z= 
= 106590,4t_w;

Після того, як дані були завантаженні у один процесор, відбувається «розповсюдження» даних по інших процесорах. Найдовший  шлях пересилання даних має вагу 3, найкоротший – 2. Відповідно, час  початкового пересилання є:

T_пер = (2 * 30 + 3 * 30 + 2 * 9 + 3 * 8) * 248 * t_p = 47616 * t_p = 55552 * t_w

Процесори готові до роботи, оскільки вони отримали усі необхідні  їм дані. Перемноження відбувається «по  кільцю», тобто: кожен процесор множить  свій рядок на рядок, який приходить до нього. Виконавши операцію множення, процесор пересилає отриманий раніше рядок наступному процесору, а на вхід отримує новий, який перемножує на «свій» рядок. Таким чином маємо 7 операцій пересилання і 8 операцій множення.

Час множення (в найгіршому випадку)  на одній  ітерації та загальний:

Т_мні = N_1ч * n₂ * N_3ч * t_u= 30 * 248 * 9 * t_u  = 66960 * t_u = 468720 * t_w,

де N_1ч – найбільша частина матриці А при розбитті

    N_3ч – найбільша частина матриці В при розбитті

Т_мн = T_tu1 +  T_tu2 + ... + T_tu8 = 3749760 * t_w

Час додавання (в найгіршому випадку)  на одній  ітерації та загальний:

Т_доді = N_1ч * (n₂ - 1) * N_3ч* t_s = 30 * 247 * 9 * t_s  = 66690 * t_s = 46683  * t_w

Т_дод = T_ts1 +  T_ts2 + ... + T_ts8 = 373464 * t_w

Час пересилання (в найгіршому випадку)  на одній  ітерації (отримання нового рядка  та пересилання існуючого)

Т_{пер.мні} = 2 * N_3ч * n₂ * t_p = 2 * 9 * 248 * t_p = 4464 * t_p = 5208 * t_w

Загальний час  пересилання під час процесу  множення (в найгіршому випадку) для  кількості процесорів p₁ = 8:

Т_пер.мн. = T_pi * (p₁ – 1) * t_p = 42532 * t_w 

Загальний час  пересилання (збору) результатів в  процесор 1:

Т_зб.рез = (3 * 30 + 3 * 9) * 248 * t_p = 29016 * t_p = 33852 * t_w

Загальний час  вивантаження є часом вивантаження одної результуючої матриці С  з процесора 2 в пам’ять:

T_вив = n₁ * n₃ * t_w = 240 * 67 * t_w= 16080 * t_w 

Загальний час  виконання множення матриць на паралельному алгоритмі, використовуючи дану систему:

T_пар = T_зав + T_пер + T_мн + T_дод + T_пер.мн + T_зб.рез  + T_вив = (106590,4 + 55552 + 3749760 + 373464 + 36456 + 33852+ 16080) * t_w = 4355674,4 * t_w

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

Загальний час множення елементів  матриць:

T_{посл.мн} = n₁ * n₂ * n₃ * t_u  =  27914880 * t_w

Загальний час додавання  при обчисленні:

T_{посл.дод} = n₁  * n₃ * (n₂ – 1) * t_s =  2780232* t_w

T_пос  = T_зав + T_{посл.мн} + T_{посл.дод} + T_вив = 30817782,4 * t_w

Для характеристики алгоритму визначимо коефіцієнт К.

K  = T_пар / (T_пер + T_мн + T_дод + T_пер.мн + T_зб.рез) = 4355674,4 / (55552 + 3749760 + 373464 + 36456 + 33852) *  t_w =  1.025

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