Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами
Розглядається новий гібридний алгоритм розв’язування систем лінійних алгебраїчних рівнянь із стрічковими симетричними додатно визначеними матрицями на комп’ютерах з графічними прискорювачами. Подано результати апробації алгоритму на багатоядерному комп’ютері з графічними прискорювачами Інпарком. Рас...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2013 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84751 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами / О.М. Хіміч, А.Ю. Баранов // Компьютерная математика. — 2013. — № 2. — С. 80-87. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859857392127180800 |
|---|---|
| author | Хіміч, О.М. Баранов, А.Ю. |
| author_facet | Хіміч, О.М. Баранов, А.Ю. |
| citation_txt | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами / О.М. Хіміч, А.Ю. Баранов // Компьютерная математика. — 2013. — № 2. — С. 80-87. — Бібліогр.: 5 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Розглядається новий гібридний алгоритм розв’язування систем лінійних алгебраїчних рівнянь із стрічковими симетричними додатно визначеними матрицями на комп’ютерах з графічними прискорювачами. Подано результати апробації алгоритму на багатоядерному комп’ютері з графічними прискорювачами Інпарком.
Рассматривается новый гибридный алгоритм решения систем линейных алгебраических уравнений с ленточными симметричными положительно определенными матрицами на компьютерах с графическими ускорителями. Представлены результаты апробации алгоритма на многоядерном компьютере с графическими ускорителями Инпарком.
A new hybrid algorithm for solving systems of linear algebraic equations with band symmetric positive definite matrix on computers with GPU is considered. The results of testing of the algorithm on multicore computer Inparcom are presented.
|
| first_indexed | 2025-12-07T15:43:57Z |
| format | Article |
| fulltext |
Компьютерная математика. 2013, № 2 80
Оптимизация
вычислений
Розглядається новий гібридний
алгоритм розв’язування систем
лінійних алгебраїчних рівнянь із
стрічковими симетричними до-
датно визначеними матрицями на
комп’ютерах з графічними при-
скорювачами. Подано результати
апробації алгоритму на багато-
ядерному комп’ютері з графічними
прискорювачами Інпарком.
© О.М. Хіміч, А.Ю. Баранов, 2013
Компьютерная математика. 2013, № 2 81
УДК 519.6
О.М. ХІМІЧ, А.Ю. БАРАНОВ
ГІБРИДНИЙ
АЛГОРИТМ
РОЗВ’ЯЗУВАННЯ
ЛІНІЙНИХ СИСТЕМ
ІЗ СТРІЧКОВИМИ
МАТРИЦЯМИ
ПРЯМИМИ
МЕТОДАМИ
Вступ. При чисельному
розв’язанні задач
у багатьох випадках виникає
необхідність розв’язувати
задачу ( або декілька
підзадач) лінійної алгебри –
систему лінійних алгебра-
їчних рівнянь (СЛАР).
Наприклад, задачі лінійної
алгебри виникають при
дискрети-зації крайових
задач чи задач на власні
значення проекційно-
різницевим методом
(скінченних елементів,
скінченних різниць). Також,
при використанні ітераційних
методів розв’язання
нелінійних задач часто на
кожній ітерації розв’язується
лінеаризована задача –
СЛАР.
Важливою особливістю
задач лінійної алгебри, які
виникають при дискретизації,
являється те, що кількість
ненульових елементів
матриць таких задач складає
kn , де nk << , а n – порядок матриці, тобто
матриці є розрідженими [1]. Структура роз-
рідженої матриці визначається нумерацією
невідомих задач і часто є стрічковою,
блочно-діагональною з обрамленням, про-
фільною і т. п. В даній роботі розглядаються
симетричні додатно визначені матриці
стрічкової структури.
Іншою важливою особливістю є великий
порядок матриця СЛАР – до десятків міль-
йонів. Це зумовлюється бажанням викори-
стовувати більш точні дискретні моделі, що
дає можливість отримувати наближені
розв’язки більш близькі до розв’язків вихід-
них задач, враховувати локальні особливості
даного процесу чи явища.
ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЛІНІЙНИХ СИСТЕМ…
Компьютерная математика. 2013, № 2 81
Розв’язання таких задач потребує значних обчислювальних ресурсів, які за-
безпечуються використанням багатоядерних комп’ютерів. Однак, уже недо-
статньо продуктивності багатоядерних архітектур. Розв’язання проблеми наро-
щування обчислювальних ресурсів лежить у площині використання гібридних
(MIMD, SIMD) архітектур. Пропонується алгоритм розв’язання СЛАР із стріч-
ковими симетричними додатно визначеними матрицями, який використовує
обчислювальні можливості CPU та GPU.
1. Постановка задачі
Розглянемо систему лінійних алгебраїчних рівнянь:
bAx = , (1)
де матриця A – стрічкова симетрична додатно визначена, n – порядок матриці
,A m – напівширина стрічки матриці.
Найбільш ефективним прямим методом розв’язання такої задачі є, як
відомо, метод Холецького [2]. Розв'язання системи (1) полягає у розв’язанні
підзадач: трикутне розвинення матриці системи, розв’язання двох СЛАР
з трикутними матрицями:
* ,TA L L= (2)
,Ly b= (3)
.TL x y= (4)
2. Гібридний алгоритм факторизації Холецького
При розробці програм для гібридних систем важливими етапами реалізації
алгоритму є вибір ефективного способу задання даних та врахування особли-
востей архітектури гібридної системи.
Для систем з багатьма графічними прискорювачами необхідними є операції
обміну даними та синхронізації. Ці операції знижують ефективність алгоритму у
випадку багатьох прискорювачів. Тому, доцільним є створення різних версій
алгоритму для систем з одним та багатьма графічними прискорювачами.
2.1. Декомпозиція даних. При розробці алгоритмів розв’язання задач з
розрідженими матрицями особливе значення має вибір способів задання та
збереження ненульових елементів. Ці способи визначаються структурою
(розміщення ненульових елементів) розрідженої матриці та потребами алго-
ритму розв’язання задачі.
Розіб’ємо стрічкову матрицю на вертикальні прямокутні плитки [3].
Оскільки матриця симетрична, то доцільно зберігати тільки нижню частину
матриці системи, що дає можливість оптимізувати обсяг пам’яті необхідний для
реалізації алгоритму. Також таке розбиття даних дає можливість більш ефек-
тивно використовувати кеші CPU та GPU, з’являється можливість використо-
вувати високоефективні функції cuBLAS. Іншою важливою особливістю такого
задання даних є те, що на кожному кроці блочного алгоритму Холецького
потрібно буде мати в пам’яті тільки wm / плиток, деw – ширина плитки, які
будуть розташовані послідовно за плиткою з ведучим блоком. Таким чином,
така декомпозиція даних дає можливість на кожному кроці алгоритму копіювати
в пам’ять GPU лише одну додаткову плитку.
О.М. ХІМІЧ, А.Ю. БАРАНОВ
Компьютерная математика. 2013, № 2 82
Також введемо деякі позначення, які будуть потрібні для опису алгоритму
трикутного розвинення (схематично показано на рис. 1, б):
• iPb – діагональний блок плитки з номером i ;
• jiPu , – підматриця плитки ,i що починається з рядка wj * ;
• jiPs , – квадратна підматриця плитки ,i що починається з рядка * .j w
а б
РИС. 1. Декомпозиція даних
2.2. Плитковий алгоритм факторизації для гібридних систем з одним
GPU. При реалізації алгоритму Холецького використовуються три основні
операції:
• POTRF – факторизація Холецького щільної матриці. В даному алгоритмі
ця операція буде використовуватися для факторизації діагонального блоку
плитки iPb ;
• TRSM – розв’язування СЛАР з трикутною матрицею. Використовується
для розв’язування рівняння 1,* ii PuPbX = ;
• GEMM – матрично-матрична операція. Використовується для оновлення
плиток матриці системи, які розташовані за плиткою з ведучим блоком:
,0 ,0 , ,*( ) .T
i j i j i j i jPu Pu Pu Ps+ +← − (5)
Для виконання перших двох операцій, на i -му кроці алгоритму, потрібно
використовувати лише дані, які знаходяться в i -й плитці. Для операції GEMM,
окрім i -ї плитки, також використовуються плитки, які розташовуються
послідовно за i -ю плиткою. Отже, кількість плиток, які використовуються на
i -му кроці алгоритму дорівнює wm / . На кожному наступному кроці в пам’ять
GPU потрібно копіювати одну додаткову плитку.
Доцільним є виконувати копіювання плитки, яка буде потрібна на наступ-
ному кроці, одночасно з виконанням операції GEMM. Таким чином, можливо
досягти більшої ефективності алгоритму. Для того, щоб на кожному кроці не
виділяти додаткову пам’ять для наступної плитки, потрібно на початку роботи
ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЛІНІЙНИХ СИСТЕМ…
Компьютерная математика. 2013, № 2 83
алгоритму виділити пам’ять для зберігання 1/ +wm плитки. На кожному кроці
wm / плиток будуть використовуватися для обчислень, а наступна плитка буде
копіюватися на вільний фрагмент пам’яті. Також, значно зменшено викори-
стання пам’яті GPU у порівняння з алгоритмами, коли вся матриця зберігається
на GPU.
Розіб’ємо реалізацію алгоритму на два етапи: на першому – виконується
початкова ініціалізація, на другому – обчислюється трикутне розвинення матри-
ці системи.
Перший етап:
• ініціалізація cuBLAS;
• створення двох екземплярів cudaStream_t: cudaCopyStream,
cudaCalculateStream;
• потік cudaCalculateStream використовується як основний потік cuBLAS;
• виділення пам’яті для 1/ +wm плитки на GPU. Вказівник на цю пам’ять
gpuTilesMemory;
• копіювання перших wm / в плиток пам’ять GPU.
Варто зазначити, що доцільним є виділення одного фрагменту пам’яті для
збереження 1/ +wm плиток в GPU, що дає можливість швидше виділити всю
необхідну пам’ять.
На другому етапі, для кожного 1... , /i n w= виконуємо наступні кроки
алгоритму:
• факторизація діагонального блоку i -ї плитки iPb . Результат записується
в iPb ;
• перетворення на GPU нижньої частини плитки 1,iPu за формулою
1
1,1, )(* −← iii PbPuPu . Використовується функція cublasDtrsm;
• асинхронне копіювання в потоці cudaCopyStream i -ї плитки в пам’ять
CPU;
• асинхронне копіювання плитки, яка потрібна на наступному кроці в
gpuTilesMemory, використовуючи cudaCopyStream;
• виконати цикл по j від 1 доки виконується нерівність ][* ilenwj < ;
на кожній ітерації виконати перетворення (5), використовуючи функцію
cublasDgemm;
• синхронізація потоку cudaCopyStream та збереження i -ї плитки на CPU;
• синхронізація основного потоку cuBLAS – cudaCalculateStream;
Після виконання всіх кроків алгоритму отримаємо нижню трикутну матри-
цю, для якої справджується формула (2).
2.3. Плитковий алгоритм факторизації для гібридних систем з декіль-
кома GPU. Наведемо алгоритм факторизації матриці СЛАР A на комп’ютерах,
де встановлено декілька GPU. Нехай кількість доступних GPU дорівнює
.numGPU У цьому випадку i -ту плитку матриці буде обробляти GPU
О.М. ХІМІЧ, А.Ю. БАРАНОВ
Компьютерная математика. 2013, № 2 84
з номером numGPUi mod (нумерація GPU з 0). При цьому, нові версії CUDA
дають можливість використовувати один CPU для роботи зі всіма доступними
GPU. Оскільки основна частина обчислень виконується на GPU, то будемо
використовувати один CPU потік.
Як і в попередньому випадку розіб’ємо реалізацію алгоритму на два етапи.
На першому етапі виконуються такі операції:
• ініціалізація cuBLAS для кожного GPU;
• створення екземплярів cudaStream_t для кожного GPU, та їх запис у ма-
сиви: cudaCopyStreamArr[], cudaCalculateStreamArr[];
• встановлення основних потоків для доступних GPU;
• виділення пам’яті для 1
*
+
numGPUw
n
плиток у кожному GPU;
• копіювання перших wm / плиток у пам’ять відповідних GPU.
На другому етапі, для кожного 1,..., /i n w= виконуємо наступні кроки
алгоритму:
• виклик функції cudaSetDevice( numGPUi mod ). Таким чином поточним
GPU стає той, в якому зберігається i -та плитка;
• перетворення на GPU нижньої частини плитки 1,iPu за формулою
1
1,1, )(* −← iii PbPuPu . Використовується функція cublasDtrsm;
• асинхронне копіювання в потоці cudaCopyStreamArr[ numGPUi mod ]
i -ї плитки в пам’ять CPU;
• встановлення поточним того GPU, в якому має зберігатися плитка, яка
потрібна на наступному кроці. Копіювання цієї плитки в пам’ять відповідного
GPU, використовуючи cudaCopyStreamArr;
• копіювання i -ї плитки в пам’ять всіх інших GPU;
• виконати цикл по j від 1 доки виконується нерівність ][* ilenwj < ;
на кожній ітерації виконати перетворення (5), використовуючи функцію
cublasDgemm. Перед викликом cublasDgemm потрібно встановити GPU з номе-
ром numGPUji mod)( + як поточний;
• синхронізація потоків cudaCopyStreamArr та збереження i -ї плитки на
CPU;
• синхронізація основних потоків cuBLAS – cudaCalculateStreamArr.
Після виконання всіх кроків алгоритму отримаємо нижню трикутну
матрицю, для якої справджується формула (2).
2.4. Розв’язання трикутних систем. Кількість операцій при розв’язанні
трикутних систем (3, 4) значно менше, чим при трикутному розвиненні матриці
системи. Тому ефективний алгоритм їх розв’язання може бути реалізований на
CPU. Для розв’язання цих систем доцільно використовувати бібліотеку Intel
MKL [4], в якій ефективно реалізовані функції для розв’язання таких систем.
ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЛІНІЙНИХ СИСТЕМ…
Компьютерная математика. 2013, № 2 85
2.5. Експерементальне дослідження ефективності гібридного алгоритму.
На основі запропонованого паралельного алгоритму розроблена програма для
комп’ютера з гібридною (MIMD, SIMD) архітектурою. Апробація програми
проведена на паралельному комп’ютері з графічними прискорювачами Інпар-
ком [5].
На рис. 2, а та б показано залежність часу роботи програми розв’язання
СЛАР від ширини плитки для алгоритму з одним GPU. На рис. 3, а та б показано
залежність часу роботи програми розв’язання СЛАР від ширини плитки для
алгоритму з декількома GPU. З графіків видно, що оптимальний розмір
напівширин стрічки відрізняється для алгоритмів з одним та декількома GPU.
а б
РИС. 2. Залежність часу розв’язання СЛАР від ширини плитки
з різною напівшириною стрічки (1000, 2000) для алгоритму з одним GPU
а б
РИС. 3. Залежність часу розв’язання СЛАР від ширини плитки
з різною напівшириною стрічки (1000, 2000) для алгоритму з двома GPU
О.М. ХІМІЧ, А.Ю. БАРАНОВ
Компьютерная математика. 2013, № 2 86
а б
РИС. 4. Порівняння часу факторизації матриці СЛАР для різної напівширини стрічки
(1000, 2000)
На рис. 4 показано порівняння часу факторизації матриці СЛАР алгорит-
мами з одним та декількома GPU. На рис. 5 – порівняння часу розв’язання СЛАР
використовуючи Intel MKL [4] та описані алгоритми з одним та декількома GPU.
а б
РИС. 5. Порівняння часу розв’язання СЛАР з використанням MKL та алгоритмів
для одного та декількох GPU
Висновки. Для СЛАР із стрічковими симетричними додатно визначеними
матрицями запропоновано алгоритм розв’язання, який забезпечує високу ефек-
тивність розпаралелювання на GPU, враховує структуру стрічкової матриці,
оптимізує використання пам’яті GPU. Також проведено дослідження вибору
оптимального розміру ширини плиток, на які розбивається вихідна матриця.
ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЛІНІЙНИХ СИСТЕМ…
Компьютерная математика. 2013, № 2 87
Подальші дослідження доцільно направити на розробку алгоритмів з
використанням декількох CPU і декількох GPU.
А.Н. Химич, А.Ю. Баранов
ГИБРИДНЫЙ АЛГОРИТМ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ
С ЛЕНТОЧНЫМИ МАТРИЦАМИ ПРЯМЫМ МЕТОДОМ
Рассматривается новый гибридный алгоритм решения систем линейных алгебраических
уравнений с ленточными симметричными положительно определенными матрицами на
компьютерах с графическими ускорителями. Представлены результаты апробации алгоритма
на многоядерном компьютере с графическими ускорителями Инпарком.
O.M. Khimich, A.Y. Baranov
HYBRID ALGORITHM FOR SOLVING LINEAR SYSTEMS WITH TAPE
MATRIX DIRECT METHODS
A new hybrid algorithm for solving systems of linear algebraic equations with band symmetric
positive definite matrix on computers with GPU is considered. The results of testing of the
algorithm on multicore computer Inparcom are presented.
1. Химич А.Н., Попов А.В., Полянко В.В. Алгоритмы параллельных вычислений для задач
линейной алгебры с матрицами нерегулярной структуры // Кибернетика и системный
анализ. – 2011. – 47, № 6. – С. 159–174.
2. Уилкинсон Дж.Х., Райнш К. Справочник алгоритмов на языке Алгол. Линейная алгебра. –
М.: Машиностроение, 1976. – 389 с.
3. Alfredo Buttari, Julien Langou, Jakub Kurzak, and Jack Dongarra. A Class of Parallel Tiled
Linear Algebra Algorithms for Multicore Architectures.Parallel Computing. –2009. – Vol. 35,
N 1. – Р. 38–53.
4. http://software.intel.com/en-us/intel-mkl
5. Химич А.Н., Молчанов И.Н., Мова В.И. и др. Численное программное обеспечение
MIMD-компьютера Инпарком. – Киев: Наукова думка, 2007. – 222 с.
Одержано 15.10.2013
Про авторів:
Хіміч Олександр Миколайович,
доктор фізико-математичних наук,
завідуючий відділом Інституту кібернетики імені В.М. Глушкова НАН України,
Баранов Андрій Юрійович,
аспірант Інституту кібернетики імені В.М. Глушкова НАН України.
|
| id | nasplib_isofts_kiev_ua-123456789-84751 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T15:43:57Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Хіміч, О.М. Баранов, А.Ю. 2015-07-14T15:45:01Z 2015-07-14T15:45:01Z 2013 Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами / О.М. Хіміч, А.Ю. Баранов // Компьютерная математика. — 2013. — № 2. — С. 80-87. — Бібліогр.: 5 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84751 519.6 Розглядається новий гібридний алгоритм розв’язування систем лінійних алгебраїчних рівнянь із стрічковими симетричними додатно визначеними матрицями на комп’ютерах з графічними прискорювачами. Подано результати апробації алгоритму на багатоядерному комп’ютері з графічними прискорювачами Інпарком. Рассматривается новый гибридный алгоритм решения систем линейных алгебраических уравнений с ленточными симметричными положительно определенными матрицами на компьютерах с графическими ускорителями. Представлены результаты апробации алгоритма на многоядерном компьютере с графическими ускорителями Инпарком. A new hybrid algorithm for solving systems of linear algebraic equations with band symmetric positive definite matrix on computers with GPU is considered. The results of testing of the algorithm on multicore computer Inparcom are presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами Гибридный алгоритм решения линейных систем с ленточными матрицами прямым методом Hybrid algorithm for solving linear systems with tape matrix direct methods Article published earlier |
| spellingShingle | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами Хіміч, О.М. Баранов, А.Ю. Оптимизация вычислений |
| title | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами |
| title_alt | Гибридный алгоритм решения линейных систем с ленточными матрицами прямым методом Hybrid algorithm for solving linear systems with tape matrix direct methods |
| title_full | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами |
| title_fullStr | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами |
| title_full_unstemmed | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами |
| title_short | Гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами |
| title_sort | гібридний алгоритм розв’язування лінійних систем із стрічковими матрицями прямими методами |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84751 |
| work_keys_str_mv | AT hímíčom gíbridniialgoritmrozvâzuvannâlíníinihsistemízstríčkovimimatricâmiprâmimimetodami AT baranovaû gíbridniialgoritmrozvâzuvannâlíníinihsistemízstríčkovimimatricâmiprâmimimetodami AT hímíčom gibridnyialgoritmrešeniâlineinyhsistemslentočnymimatricamiprâmymmetodom AT baranovaû gibridnyialgoritmrešeniâlineinyhsistemslentočnymimatricamiprâmymmetodom AT hímíčom hybridalgorithmforsolvinglinearsystemswithtapematrixdirectmethods AT baranovaû hybridalgorithmforsolvinglinearsystemswithtapematrixdirectmethods |