Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури
В роботі для комп’ютерів гібридної архітектури з багатоядерними та графічними процесорами запропоновано паралельний блочно-циклічний алгоритм двосторонніх перетворень Хаусхолдера. Наведено результати тестування та дослідження як (масштабованості, прискорення тощо) алгоритм в залежності від його пара...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут програмних систем НАН України
2014
|
| Schriftenreihe: | Проблеми програмування |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/113220 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури / О.В. Попов, О.В. Рудич // Проблеми програмування. — 2014. — № 2-3. — С. 99-106. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-113220 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1132202025-02-23T17:48:06Z Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури Block algorithm for Householder transformations for hybrid architecture computers Попов, О.В. Рудич, О.В. Паралельне програмування. Розподілені системи і мережі В роботі для комп’ютерів гібридної архітектури з багатоядерними та графічними процесорами запропоновано паралельний блочно-циклічний алгоритм двосторонніх перетворень Хаусхолдера. Наведено результати тестування та дослідження як (масштабованості, прискорення тощо) алгоритм в залежності від його параметрів та параметрів матриці, що перетворюються. A parallel block cyclic algorithm for two-sided Householder transformations for hybrid architecture computers with multi-core and graphic processors is dealt with in the paper. Results of testing are presented together with investigation of algorithm’s characteristics (scalability, acceleration) depending both on its parameters and parameters of matrix being transformed. 2014 Article Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури / О.В. Попов, О.В. Рудич // Проблеми програмування. — 2014. — № 2-3. — С. 99-106. — Бібліогр.: 6 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/113220 519.61 uk Проблеми програмування application/pdf Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Паралельне програмування. Розподілені системи і мережі Паралельне програмування. Розподілені системи і мережі |
| spellingShingle |
Паралельне програмування. Розподілені системи і мережі Паралельне програмування. Розподілені системи і мережі Попов, О.В. Рудич, О.В. Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури Проблеми програмування |
| description |
В роботі для комп’ютерів гібридної архітектури з багатоядерними та графічними процесорами запропоновано паралельний блочно-циклічний алгоритм двосторонніх перетворень Хаусхолдера. Наведено результати тестування та дослідження як (масштабованості, прискорення тощо) алгоритм в залежності від його параметрів та параметрів матриці, що перетворюються. |
| format |
Article |
| author |
Попов, О.В. Рудич, О.В. |
| author_facet |
Попов, О.В. Рудич, О.В. |
| author_sort |
Попов, О.В. |
| title |
Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури |
| title_short |
Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури |
| title_full |
Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури |
| title_fullStr |
Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури |
| title_full_unstemmed |
Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури |
| title_sort |
блочний алгоритм перетворень хаусхолдера для комп’ютерів гібридної архітектури |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2014 |
| topic_facet |
Паралельне програмування. Розподілені системи і мережі |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/113220 |
| citation_txt |
Блочний алгоритм перетворень Хаусхолдера для комп’ютерів гібридної архітектури / О.В. Попов, О.В. Рудич // Проблеми програмування. — 2014. — № 2-3. — С. 99-106. — Бібліогр.: 6 назв. — укр. |
| series |
Проблеми програмування |
| work_keys_str_mv |
AT popovov bločnijalgoritmperetvorenʹhausholderadlâkompûterívgíbridnoíarhítekturi AT rudičov bločnijalgoritmperetvorenʹhausholderadlâkompûterívgíbridnoíarhítekturi AT popovov blockalgorithmforhouseholdertransformationsforhybridarchitecturecomputers AT rudičov blockalgorithmforhouseholdertransformationsforhybridarchitecturecomputers |
| first_indexed |
2025-11-24T04:15:12Z |
| last_indexed |
2025-11-24T04:15:12Z |
| _version_ |
1849643721842229248 |
| fulltext |
Паралельне програмування. Розподілені системи і мережі
© О.В. Попов, О.В. Рудич, 2014
ISSN 1727-4907. Проблеми програмування. 2014. № 2–3. Спеціальний випуск 99
УДК 519.61
БЛОЧНИЙ АЛГОРИТМ ПЕРЕТВОРЕНЬ ХАУСХОЛДЕРА
ДЛЯ КОМП’ЮТЕРІВ ГІБРИДНОЇ АРХІТЕКТУРИ
О.В. Попов, О.В. Рудич
Інститут кібернетики імені В.М. Глушкова НАН України,
03680, Київ, проспект Академіка Глушкова, 40.
Тел.: (044) 526 6088,
alex50popov@gmail.com, olgar2006@ukr.net
В роботі для комп’ютерів гібридної архітектури з багатоядерними та графічними процесорами запропоновано паралельний блочно -
циклічний алгоритм двосторонніх перетворень Хаусхолдера. Наведено результати тестування та дослідження як (масштабованості,
прискорення тощо) алгоритм в залежності від його параметрів та параметрів матриці, що перетворюються.
A parallel block cyclic algorithm for two-sided Householder transformations for hybrid architecture computers with multi-core and graphic
processors is dealt with in the paper. Results of testing are presented together with investigation of algorithm’s characteristics (scalability,
acceleration) depending both on its parameters and parameters of matrix being transformed.
Вступ
Перетворення Хаусхолдера (ортогональні перетворення віддзеркалення) досить широко використову-
ються при розв’язуванні багатьох задач лінійної алгебри: на власні значення матриць, сингулярного розвинення
матриць, знаходження узагальнених розв’язків систем лінійних алгебраїчних рівнянь методом найменших ква-
дратів тощо. Такі перетворення дозволяють замінити вихідні задачі більш простими. Наприклад, обчислення
власних значень довільної матриці зводиться до обчислення власних значень тридіагональної матриці або син-
гулярне розвинення довільної прямокутної матриці – до сингулярного розвинення дводіагональної матриці.
Тому першим етапом знаходження розв’язків таких задач може бути зведення вихідної матриці задачі до дво-
або тридіагональної матриці, до верхньої форми Хесенберга (для квадратних матриць порядку n), до верхньої
дводіагональної форми
0
)0(J
J (для прямокутних mn матриць, m ≥ n), де J (0) – квадратна верхня дводіа-
гональна матриця порядку n, в якій відмінні від нуля лише елементи
)0(
1,
)0(
, , kkkk jj .
Для виконання вказаних вище зведень необхідно n2 двосторонніх (або односторонніх) елементарних
перетворень віддзеркалення. А загальна кількість арифметичних операцій складає [1] O(n3) для квадратних ма-
триць порядку n або O(mn2) для прямокутних mn матриць. Тому, починаючи з n = O(103), виконання цих зве-
день на персональному комп’ютері потребує досить багато часу.
Скорочення часу розрахунків досягається за рахунок зростання продуктивності комп’ютерів, яке базу-
ється на використанні комп’ютерів з багатьма процесорними пристроями, зокрема з багатоядерними процесо-
рами та розпаралелюванні обчислень. В цих комп’ютерах реалізується, як правило, MIMD-архітектура (архіте-
ктура з множинним потоком команд і даних) з розподіленою пам’яттю. Прискорення обчислень можна досягти
також шляхом використання графічних процесорів (GPU), на яких реалізується SIMD-архітектура паралельних
обчислень, для виконання великих обсягів однорідних арифметичних операцій. Майбутнє обчислювальної тех-
ніки в найближчій перспективі, на наш погляд, це комп’ютери гібридної архітектури, які поєднують MIMD- і
SIMD-архітектури, тобто обчислення на багатоядерних комп’ютерах з використанням GPU для прискоренням
обчислень (див. [2]).
В цій роботі на прикладі задачі зведення щільної симетричної матриці до тридіагональної симетричної
матриці розглядається реалізація перетворень Хаусхолдера на комп’ютерах гібридної архітектури.
Постановка та метод розв’язування задачі
Розглянемо задачу зведення щільної симетричної матриці A порядку n до тридіагональної симетричної
матриці T, тобто задачу обчислення розвинення
THTHA , (1)
де матриця перетворень H така, що
1 HHT
.
Введемо позначення:
n
ji
k
ji
k
cC 1,
)(
,
)(
}{ , AA )0(
, TA n )2(
, HH n )2(
, nIH )0( , nI – одинична
матриця, di ti,i, ei+1 ti+1,i, e1 0, ijaaa
i
nj
i
ij
i
j
T)(
,
)(
2,
)(
,,,0,,0 , T)()(
2
)(
1
)(
,,,,0,,0 i
n
i
i
i
i
i
uuuu ,
T)()(
2
)(
1
)(
,,,,1,0,,0 i
n
i
i
i
i
i
vvvv , T)()(
2
1
1
)(
,,,,0,,0 i
n
i
ii
i
hheh
.
mailto:alex50popov@gmail.com
mailto:olgar2006@ukr.net
Паралельне програмування. Розподілені системи і мережі
100
Для розвинення (1) можна використати n2 двосторонніх ортогональних перетворень віддзеркалення
(Хаусхолдера)
)()1()()( iiii
PAPA
, 2,)( i
T
i
T
ii
i xxxxIP , i = 1, 2,…, n2, (2)
де вектори xi вибираються з умов 0
)(
,
)(
,
i
ik
i
ki aa (k = i +2, …, n),
)1(
,
i
iii ad . Виходячи з цих умов, маємо
.,)(sign
,),,,2(,
2
1
2)1(
,
2
)1(2)1(
1,
)(
1,1
1
)1(
1,
)(
1
)1(
,
)()(
)(
n
ik
i
ki
i
iii
i
ii
i
iii
i
i
ii
i
i
i
ki
i
k
i
ii
aaaae
eaunikauu
u
x
(3)
Тоді, визначивши наступним чином вектор v(i)
)()()( i
i
ii
ucwv ,
)()( i
i
i
gbw , )()(
2
iii
i uw
b
c
T
, )()1()( iii
uAg , 1)(
11
i
iii ueb , (4)
двосторонні перетворення (2) можна записати у вигляді дворангової модифікації
TT )()()()()1()( iiiiii uvvuAA
(i = 1, 2,…, n2). (5)
Отже, на кожному кроці (для кожного i) модифікується нижня права квадратна підматриця порядку ni
матриці A(i1). При виконанні перетворень (5) враховується симетричність вихідної матриці А і всіх матриць A(i).
Аналогічно використовуються двосторонні перетворення Хаусхолдера для зведення QJPA прямокут-
ної mn (m ≥ n) матриці A до верхньої дводіагональної форми J. В цьому випадку кожне двостороне перетво-
рення можна записати у вигляді такої дворангової модифікації
TT )()()()()1()( iiiiii vzyuAA (i = 1, 2,…, n2). (6)
Тут вектори )(iu , )(iv , )(iy , )(iz з умов та формул аналогічних попередньому випадку (див. [3]).
Використовуючи односторонні перетворення Хаусхолдера, можна сформувати матрицю перетворень з H
(1): )1()()( iki HPH (k = n-i-1, i = 1, 2,…, n2, H(0) In, H
(n-2) H). Кожне таке перетворення можна записати
у вигляді однорангової модифікації
T)()()1()( kkii zuHH . За аналогічними формулами формуються матриці
перетворень Хаусхолдера для зведення прямокутної матриці до верхньої дводіагональної форми тощо.
Блочний алгоритм зведення щільної симетричної матриці до тридіагональної симетричної матри-
ці. На ефективність комп’ютерної реалізації алгоритмів зведення матриць, які використовують перетворення
Хаусхолдера, істотний вплив має організація роботи з оперативною пам'яттю. В сучасних процесорах ця па-
м'ять має складну архітектуру, причому швидкість звернення (запису або читання) до оперативної пам'яті різ-
них рівнів суттєво відрізняється. В той же час при одно- або дворангових модифікаціях матриць доводиться
досить часто звертатися до найповільнішої основної оперативної пам'яті, що призводить до суттєвого збіль-
шення часу обчислень. Цю проблему можна вирішити шляхом модифікації алгоритму – використання блочного
виконання перетворень відзеркалення [3, 4].
В блочній версії алгоритму зведення щільної симетричної матриці до тридіагональної форми перетво-
рення матриці виконуються так:
Ts
I
s
I
Ts
I
s
I
sIsIs UVVUAA
)()()()()()( (I = 1, 2, …, N-1), (7)
де N = (n+s3)/s (значення a дорівнює цілій частині числа а), s – розмір блоку, останній N-й блок має роз-
мір sN+2 (sN -1 – дорівнює залишку від ділення n3 на s) і модифікується за формулою
Ts
N
s
N
Ts
N
s
N
sNsn NNNN UVVUAA
)()()()()()2( , (8)
а прямокутні матриці
)()(
,
q
K
q
K VU формуються наступним чином:
;,,
,,,
)()1()()1((1)
)()1()()1((1)
rqKqr
K
r
K
qKq
K
rqKqr
K
r
K
qKq
K
vVVvV
uUUuU
(9)
тут r = 2, …, q, q = s, якщо K = 1, 2, …, N-1, і q = sN, якщо K = N.
Паралельне програмування. Розподілені системи і мережі
101
Вектор віддзеркалення u(i) і вектор v(i) (i = Is–s+r) визначаються за формулами (3), (4). Причому добуток
A(i1)u(i) (тобто вектор v(i)) обчислюється за формулами (r > 1)
,,,
)()1()()1()1()1()()()()1(
iTr
Ir
iTr
Irr
r
Ir
r
I
isIsii uVyuUxxVyUuAuA (10)
а елементи i-х рядка та стовпчика матриці A(i1) за наступними формулами (k = i+1, …, n)
,,2
)1()1()1()1()(
,
)1(
,
)1(
,
)1()1(
,
)(
,
)1(
,
TTT
r
i,I
r
k,I
r
i,I
r
k,I
sIs
ki
i
ik
i
ki
r
i,I
r
Ii
sIs
ii
i
ii UVVUaaaVUaa (11)
де
)1()1(
, ,
r
j,I
r
Ij VU j-й рядок матриць )1()1(
,
r
I
r
I VU відповідно. Причому в цих обчисленнях використовується
наступне представлення матриці A(Is–s+r) (r = 1, 2, …, s–1):
Tr
I
r
I
Tr
I
r
I
sIsrsIs UVVUAA
)()()()()()(
. (12)
Так само дворангову модифікацію (6) можна замінити 2s-ранговою
Ts
I
s
I
Ts
I
s
I
sIsIs VZYUAA
)()()()()()( , (13)
де прямокутні матриці
)()()()(
,,,
q
K
q
K
q
K
q
K ZYVU формуються за формулами аналогічними формулам (9)–(11) (див.
[3]). Головним тут є використання представлення виду (12), формули аналогічні (10) для обчислення добутків
матриці )1( iA або матриці A(i-1/2) на вектор та формули аналогічні (11) для обчислення елементів i-го рядка мат-
риці )1( iA та i-го стовпчика матриці A(i1/2). Аналогічним чином однорангові модифікації можна замінити
s-ранговими.
Паралельні алгоритми
При зведенні щільної симетричної матриці до тридіагональної необхідно взяти до уваги, що обчислення
за формулами (7), (8) та (11), враховуючи симетричність, сумарно вимагають виконання по )(
3
2 23 snOn ари-
фметичних операцій з плаваючою комою, водночас як для всіх інших обчислень необхідно )( 2snO арифметич-
них операцій. Для несиметричних матриць або, якщо не враховувати симетричність матриці, то кількість ариф-
метичних операцій збільшується майже вдвічі. Тому для обчислень за формулами (7), (8) та (10) доцільно вико-
ристати графічні процесорні пристрої (GPU) та враховувати симетричність матриці. Але при використанні ба-
гатопроцесорного комп’ютера елементи симетричної матриці розподіляються між процесорними пристроями
так, що в пам’яті кожного з них зберігається тільки підматриця цієї матриці, яка (як правило) буде несиметрич-
ною. Тому для використання симетричності матриці обчислення за формулами (7) та (10) необхідно організува-
ти спеціальним чином, врахувавши розбиття на блоки. Далі на рис. 1 показано розбиття на блоки симетричної
матриць )(IsA , матриць
)(s
IU (ідентично розбиваються матриці
)(s
IV ) та векторів )(iu (ідентично розбиваються
інші n-вимірні вектори).
Використовуючи позначення рис. 1 та наступні
NI
NI
KI
KI
U
U
U
U
,
1,
1,
*
,
,
NI
NI
KI
KI
V
V
V
V
,
1,
1,
*
,
,
Ni
Ni
Ki
Ki
u
u
u
u
,
1,
1,
*
,
,
)(
,
)(
1,
)(
1,
)(
K
Ni
K
Ni
K
Ki
K
i
g
g
g
g
,
можна формулу (7) розписати так: (K = I, I+1, …, N)
.або
,
)(
1,,
*
,,
*
,
)(
,1
)(
,1
*
,,
*
,,
)(
1,
)(
1,
,,,,
)(
,
)(
,
TIs
KK
T
KIKI
T
KIKI
sIs
KK
Is
KK
T
KIKI
T
KIKI
sIs
KK
Is
KK
T
KIKI
T
KIKI
sIs
KK
Is
KK
AUVVUAAUVVUAA
UVVUAA
(14)
А формули (10) для i
i
i uAg )1( тоді розписуються так: (K = I, I+1, …, N)
.,,
)1(
,
)1(
,
)(
,,,
)(
1,
)(*
,
)(
1,,
)(
,
)(
, r
r
KIr
r
KI
K
IJ
J
KiKiKi
TsIs
KK
K
iKi
sIs
KKKi
sIs
KK
K
Ki xVyUgguAguAuAg
(15)
Паралельне програмування. Розподілені системи і мережі
102
Рис. 1. Розбиття на блоки симетричної матриці
У випадку двосторонніх перетворень прямокутної матриці або односторонніх перетворень матриця A(Is)
розбивається на прямокутні блоки
)(Is
KA (K = I+1, …, N) розміру s(n-Is). Тоді 2s-рангова модифікація або
s-рангова модифікація таких блоків виконуються відповідно за формулами
TIKI
T
IKI
sIs
K
Is
K VZYUAA *
,
*
,
)()(
, TIKI
sIs
K
Is
K ZUHH *
,
)()(
, (16)
де використано позначення ),,()( ,1,
* T
NJ
T
JJ
T
J XXX . Відповідно по аналогії з (15) та (16) записуються фор-
мули обчислення добутку матриці на вектор.
Паралельний алгоритм зведення щільної симетричної матриці до тридіагональної симетричної
матриці. На комп’ютерах гібридної архітектури для зведення симетричної матриці до тридіагональної симет-
ричної матриці доцільно використати блочний алгоритм перетворень Хаусхолдера, оскільки в блочному варіан-
ті наявна велика кількість матрично-матричних і матрично-векторних операцій, які можна виконувати на GPU
за допомогою програмних модулів бібліотеки CUBLAS [5]. Блочний алгоритм також дозволяє зменшити кіль-
кість обмінів даними між процесорними ядрами.
Розпаралелення обчислень на багатоядерних комп’ютерах з графічними процесорами досягається як за
рахунок паралельного виконання розрахунків на різних ядрах, так і за рахунок паралельним обчисленням на
GPU. Крім того слід брати до уваги, що такі комп’ютери гібридної архітектури можуть мати в своєму складі
декілька обчислювальних вузлів, кожен з яких складається з декількох багатоядерних процесорів з
під’єднаними до них GPU. Тому при розробці та реалізації паралельних алгоритмів для цих комп’ютерів слід
розрізняти різні архітектури, зокрема такі: 1 ядро + 1 GPU, m ядер + m GPU на одному вузлі, m ядер + m GPU
на декількох вузлах, причому одне ядро зв’язано з одним GPU. В останніх двох випадках різниця полягає в то-
му, що на одному вузлі може використовуватися спільна пам’ять.
Розподіл даних і результатів. Хоча для виконання перетворень (7)-(11) достатньо елементів головної ді-
агоналі матриці і, наприклад, її верхнього трикутника, все-ж доцільно задавати всі елементи матриці, а модифі-
кувати тільки елементи верхнього трикутника. Для організації паралельних обчислень використовується одно-
вимірна блочна циклічна схема [3] розподілу між процесорними ядрами та між GPU елементів матриць
)(IsA , у
тому числі і вихідної матриці
)0(A . А саме, рядки блоків матриці циклічно розподіляються і зберігаються в
пам’яті ядра та їх копії в глобальній пам’яті відповідного GPU. У випадку використання архітектури
1 ядро + 1 GPU всі елементи матриць
)(IsA зберігаються в пам’яті ядра та в пам’яті GPU.
Результати зведення – діагональні ),...,2,1(, njt jj та позадіагональні )1,...,2,1(,11, njtt jjjj
елементи тридіагональної матриці )2(
1
nAT – обчислюються кожним ядром CPU. Якщо необхідно обчислити
матрицю перетворень H з (1), то на місці елементів верхнього трикутника вихідної матриці у відповідності з їх
розподілом між процесорними пристроями в пам’яті ядер зберігаються ненульові елементи векторів iu .
Для виконання проміжних обчислень, обмінів даними між процесорними ядрами та між ядрами і GPU
кожне ядро використовує робочий масив загальним обсягом (2s+3)n+s+2 слів, а GPU 2 робочі масиви по ns слів
кожний і один з n+2s слів.
Паралельне програмування. Розподілені системи і мережі
103
Алгоритм. З формул (7)–(11) та рис. 1 випливає, що на I-у кроці алгоритму (I = 1, 2, …, N-1, N) можна
виділити наступні підзадачі:
мультирозсилка всім процесорним ядрам та всім GPU I-го (провідного) рядка блоків матриці )( sIsA
(у випадку m ядер + m GPU);
формування кожним ядром, використовуючи GPU, прямокутних матриць )(s
IU , )(s
IV ;
2s-рангова модифікація (7) елементів підматриці порядку n – Is матриці )(IsA відповідно до розподілу
між процесорними ядрами; виконується на GPU.
Формування прямокутних матриць )(s
IU , )(s
IV відповідно до (8)–(11) полягає у тому, що для кожного
i = Is-s+1, …, ks обчислюються вектори iiii vwgu ,,, та значення ряду скалярних величин. Тут доцільно виді-
лити наступні операції або групи операцій:
1) формування вектора iu : якщо використовується архітектура 1 ядро + 1 GPU, то на GPU, а якщо
m ядер + m GPU, то можна виконати на кожному процесорному ядрі з подальшим копіюванням на GPU;
2) формування кожною парою ядро + GPU векторів iii vwg ,, згідно (10), (11), (15). При реалізації цих
операцій доцільно використати GPU, зокрема, застосувавши необхідні програмні модулі CUBLAS, та процесо-
рні ядра при використанні архітектури m ядер + m GPU для мультизбирання вектора i
i
i uAg )1( з обчислених
на GPU згідно (15) часткових сум; при використанні архітектури 1 ядро + 1 GPU всі операції цієї групи доціль-
но виконувати на GPU;
3) при i < Is 2(i-Is+s)-рангова модифікація (i-Is+s+1)-го рядка провідного рядка блоків матриці за фор-
мулою (11), де використовуються вже сформовані частини відповідних прямокутних матриць. Цю підзадачу
можна розпаралелити на GPU з використанням необхідних функцій CUBLAS.
Підзадача з 2s-рангової модифікації (7) за формулами (14) верхнього трикутника підматриці A(Iss) поді-
ляється на 2s-рангові модифікації окремих симетричних діагональних блоків KKA , та 2s-рангові модифікації
окремих наддіагональних прямокутних блоків 1, KKA , що складають підматрицю )( sIsA : Ці
2s-рангові модифікації окремих блоків виконуються на GPU, використовуючи відповідні функції CUBLAS, згі-
дно розподілу елементів матриці між GPU.
При програмній реалізації цього алгоритму можна використовувати можливості, які надаються останні-
ми версіями технології CUDA [6], асинхронних пересилок масивів даних між різними GPU та асинхронного
виконання програмних модулів на GPU, що дозволяє виконувати паралельно обчислення на процесорних ядрах
та на GPU. Ці можливості дозволяють на архітектурі m ядер + m GPU використовувати тільки GPU для форму-
вання векторів iiii vwgu ,,, та підвищити ефективність мультирозсилки I-го (провідного) рядка блоків мат-
риці. Але необхідно брати до уваги, що на деяких гібридних комп’ютерах реалізація програмних засобів остан-
ніх версій CUDA може призводити до суттєвого збільшення часу розв’язування задач.
Для задачі зведення прямокутної матриці до верхньої дводіагональної форми можна запропонувати ана-
логічний паралельний блочно-циклічний алгоритм двосторонніх перетворень Хаусхолдера (13). В цьому алго-
ритмі виділяються три аналогічні підзадачі. При цьому в блочних операціях з під матрицями матриць )( jA не
треба враховувати симетричність і тому використовуються тільки прямокутні блоки.
Паралельний алгоритм накопичення елементарних перетворень віддзеркалення. Аналогічні пара-
лельні алгоритми для комп’ютерів гібридної архітектури можна запропонувати для задач, які згадувались вище
– формування матриць перетворень H, P, Q, зведення прямокутної матриці до верхньої дводіагональної форми
тощо, на основі формул (16). Розглянемо наприклад, задачу накопичення елементарних перетворень віддзерка-
лення, формування матриці перетворень H.
Вихідними даними цієї задачі є результати зведення симетричної матриці до тридіагональної – вектори
віддзеркалення )(ku та скалярні множники kb , k = 1, 2, …, n-2. Елементи векторів віддзеркалення )(ku можуть
зберігатися на місці елементів верхнього трикутника вихідної матриці в пам’яті GPU та за необхідності в
пам’яті багатоядерних процесорів відповідно до їх одновимірного блочного циклічного розподілу. Для збере-
ження скалярних множників kb можна використати тимчасовий (робочий) масив. Результат – матриця H – фо-
рмується на GPU, її елементи розподілено між GPU за тією ж одновимірною блочною циклічною схемою. Для
проміжних обчислень і обмінів даними можна використати ті ж самі робочі масиви, що і в алгоритмі зведення.
Як і в попередньому паралельному алгоритмі зведення симетричної матриці до тридіагональної на I-му
кроці алгоритму (I = 2, …, N-1, N) можна виділити наступні підзадачі:
мультирозсилка всім ядрам та всім GPU елементів прямокутної матриці
)(
1
s
INU
(у випадку використання m ядер + m GPU);
формування кожним ядром, використовуючи GPU, прямокутної матриці
)(s
IZ
(можливе виконання всіх обчислень на GPU);
s-рангова модифікація (16) підматриці
)(IsH відповідно до розподілу між GPU, виконується на GPU.
Паралельне програмування. Розподілені системи і мережі
104
Апробація паралельних алгоритмів
Для досягнення найвищої продуктивності при використанні запропонованих паралельних алгоритмів не-
обхідно, враховуючи параметри задачі, вибрати відповідну архітектуру гібридного комп’ютера, тобто кількість
ядер та GPU, а також розмір блоку. На ці фактори впливають доволі багато чинників, пов’язаних з характерис-
тиками використовуваних програмно-технічних засобів. Тому теоретичне дослідження ефективності паралель-
них алгоритмів для комп’ютерів гібридної архітектури складає великі труднощі і не дає достатньо достовірних
результатів.
На наш погляд більш доцільним є експериментальне дослідження запропонованих алгоритмів на
розв’язуванні ряду тестових задач на конкретному комп’ютері. Таке досліджено для запропонованих алгорит-
мів було проведено на комп’ютері гібридної архітектури Інпарком-G – спільній розробці Інституту кібернетики
імені В.М. Глушкова НАН України та ДНВП "Електронмаш". Цей комп’ютер має в своєму складі 4 обчислюва-
льні вузли. Кожен вузол складається з двох чотириядерних процесорів та двох графічних процесорів.
Чисельні експерименти проводились на обчисленні розвинення (1) щільних симетричних матриць різних
порядків, тобто на обчисленні як тридіагональної матриці T, так і матриці перетворень H, використовуючи пе-
ретворення Хаусхолдера.
Проведені експерименти підтвердили зроблений раніше висновок про доцільність використання в розра-
хунках рівної кількості процесорних ядер та GPU. Це пов’язано з тим, що більшість розрахунків проводиться на
графічних процесорах, а ядра переважно використовуються для обмінів даними. Водночас використання на
кожному вузлі одного ядра та двох GPU не дало відчутних переваг, особливо якщо для обчислень використову-
валось декілька вузлів.
Деякі результати дослідження впливу розмірів блоків на продуктивність комп’ютерів гібридної архітек-
тури на задачах зведення щільних симетричних матриць до тридіагональних, використовуючи перетворення
Хаусхолдера, та обчислення матриць перетвореннь H наведено в табл. 1. Дослідження проводились на однову
вузлі.
Таблиця 1. Час (сек.) виконання перетворень Хаусхолдера для матриць різних порядків в залежності
від розмірів блоків
Розмір
блоку
s
Час (сек.)
n = 6 144 n = 7 000 n = 10 000
1 ядро +
+ 1 GPU
2 ядра +
+ 2 GPU
1 ядро +
+ 1 GPU
2 ядра +
+ 2 GPU
2 ядра +
+ 2 GPU
32 84,090 55,980 119,690 72,419 –
64 58,770 44,760 82,810 61,009 138,306
96 52,800 43,670 73,760 58,212 117,313
112 – – – 58,593 116,671
128 50,830 39,270 70,580 53,610 118,648
144 – – – 60,214 131,105
160 50,930 45,280 70,210 54,179 116,355
176 – – – 61,568 –
192 51,510 46,670 76,110 55,823 130,939
256 53,780 45,560 72,490 66,680 –
320 54,500 50,890 73,220 67,450 –
512 – – – 82,299 –
Наведені результати та результати інших експериментів свідчать, що найвища продуктивність (най-
менший час) досягається при розмірі блоку в межах від 96 до 192. Також ці експерименти показали, що менше
часу витрачається при розмірах блоків кратних 16.
Також було перевірено масштабованість запропонованих паралельних алгоритмів, досліджено продукти-
вність та прискорення.
В табл. 2 показано показники продуктивності обчислень на різних архітектурах, різних середовищах па-
ралельного програмування та двох різних розмірах блоків при виконанні перетворень Хаусхолдера для зведен-
ня щільних симетричних матриць різних порядків n до тридіагональних симетричних матриць. Для порівняння
наведено також продуктивність обчислень без використання графічних процесорів (зауважимо, що в цьому ви-
падку найвища продуктивність досягається при розмірі блоку від 8 до 16).
Паралельне програмування. Розподілені системи і мережі
105
На діаграмах на рис. 2 показано прискорення запропонованих алгоритмів отримані при зведенні матриць
10 000-го та 20 000-го порядків при розмірі блоків 96 та 128 на різній кількості ядер та GPU порівняно
з 1 ядром та 1 GPU.
Як наведені результати, так і результати інших експериментів демонструють ефективність використання
графічних прискорювачів при виконанні блочних перетворень Хаусхолдера. Продуктивність обчислень зростає
із зростанням порядку матриць. Те ж саме стосується прискорення. Це пов’язано з тим, що для менших поряд-
ків присутнє недостатнє завантаження використовуваного обчислювального ресурсу. Тому продуктивність об-
числень незначно збільшується або навіть зменшується (за рахунок накладних витрат) починаючи з деякої кіль-
кості ядер та GPU: для n = 4 096 це 2, для n = 7 000 це 4, для n = 10 000 це 6. Тільки при n > 14 000 наявна масш-
табованість для всього діапазону використовуваних процесорних ядер та GPU. Зауважимо також, що при вико-
ристанні одного вузла дещо вищу продуктивність отримано при розмірі блоків s = 128, а при використанні бі-
льшої кількості вузлів при s = 96.
Таблиця 2. Продуктивність обчислень при виконанні перетворень Хаусхолдера в залежності від порядку n,
розмірів блоків s та використаних програмно-технічних засобів
Кіл-ть Кіл-ть Кіл-ть
s
n = 4 096 n = 7 000 n = 10 000 n = 16 000 n = 20 000 Середовище
розпарале-
лювання вузлів ядер GPU Продуктивність (Gflops.)
1 1 1 96 8,01 11,54 14,42 17,76 18,68
CUDA
1 1 128 8,14 12,06 15,09 19,22 21,09
1 – 128 0,31 0,57
–
1 – 12 0,71 0,87
1 2 2 96 10,30 14,58 18,62 28,05 31,38
MPI+CUDA
2 2 128 8,90 15,48 20,87 28,51 32,45
8 – 128 1,16 1,79
MPI
8 – 12 4,39 5,34 5,02 5,56
2 4 4 96 10,10 16,59 23,06 33,05 37,62
MPI+CUDA
4 4 128 9,34 15,76 23,13 32,81 36,56
16 – 12 8,18 8,25 8,45 MPI
3 6 6 96 10,43 17,83 25,92 42,72 45,04
MPI+CUDA
6 6 128 9,48 16,38 21,96 36,21 39,61
24 – 12 11,53 11,71 11,96 MPI
4 8 8 96 10,69 18,38 25,89 39,79 47,11
MPI+CUDA
8 8 128 9,56 17,04 22,91 36,13 43,04
32 – 12 14,01 14,97 14,41 MPI
0,00
0,25
0,50
0,75
1,00
1,25
1,50
1,75
2,00
2,25
2,50
2,75
s=96 s=128 s=96 s=128
n=10000 n=10000 n=20000 n=20000
П
р
и
с
к
о
р
е
н
н
я
1 ядро
1 GPU
2 ядра
2 GPU
4 ядра
4 GPU
6 ядер
6 GPU
8 ядер
8 GPU
Рис. 2. Прискорення алгоритмів
Паралельне програмування. Розподілені системи і мережі
106
Проведені дослідження засвідчили, що прискорення, а отже і зростання продуктивності наявне при кіль-
кості, яка перевищує 107, елементів підматриці, що обробляється однією парою ядро+GPU. Також, як зазнача-
лось вище, при використанні ресурсу більше одного вузла доцільно використовувати блоки, прядок яких s = 96.
Висновки
В роботі для комп’ютерів з багатоядерними та графічними процесорами (гібридної архітектури) запро-
поновано паралельні блочно-циклічні алгоритми перетворень Хаусхолдера, зокрема, двосторонніх перетворень
для зведення щільної симетричної матриці до тридіагональної. Проведене тестування запропонованих алгорит-
мів засвідчило ефективність використання графічних процесорів для виконання перетворень Хаусхолдера та
правильність вибраних підходів до розробки алгоритмів високопродуктивних обчислень для комп’ютерів гіб-
ридної архітектури. В тому числі:
перехід до блочних версій відповідних методів та алгоритмів розв’язування задач з метою виділення пі-
дзадач з великим обсягом матрично-векторних та матрично-матричних операцій;
виконання матрично-векторних та матрично-матричних операцій на графічних процесорах, використо-
вуючи програмні засоби від розробників технічних засобів;
проведення експериментального дослідження якостей розробленого алгоритму.
Проведені експериментальні дослідження запропонованих алгоритмів на задачах розвинення (1) симет-
ричних матриць різних порядків дозволили визначити обчислювальний ресурс та розміри блоків, достатні для
ефективного розв’язування конкретної задачі на конкретному комп’ютері. Використана для цього методика
може застосовуватися для тестування та дослідження інших алгоритмів високопродуктивних обчислень для
комп’ютерів гібридної архітектури.
1. Уилкинсон Дж.Х., Райнш К. Справочник алгоритмов на языке Алгол. Линейная алгебра. – М.: Машиностроение, 1976. – 389 с.
2. http://www.top500.org
3. Химич А.Н., Молчанов И.Н., Попов А.В., Чистякова Т.В., Яковлев М.Ф. Параллельные алгоритмы решения задач вычислительной ма-
тематики. – К.: Наук. думка, 2008. – 248 с.
4. http://www.netlib.org/ lapack/
5. http://developer.download.nvidia.com/CUBLAS.pdf [Електронний ресурс]
CUBLAS
6. http://developer.nvidia.com/cuda-toolkit-4.0 [Електронний ресурс]
CUDA TOOLKIT 4.0
http://www.top500.org/
http://www.netlib.org/%20lapack/
http://developer.download.nvidia.com/CUBLAS.pdf
http://developer.nvidia.com/cuda-toolkit-4.0
|