Гібридний алгоритм факторизації стрічкових несиметричних матриць

Гібридний алгоритм факторизації стрічкових несиметричних матриць

Запропоновано алгоритм факторизації стрічкових несиметричних матриць на комп’ютерах гібридної архітектури. Проведено апробацію алгоритму на суперкомп’ютерах СКІТ-4 та Інпарком....

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2015
1. Verfasser: Баранов, А.Ю.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schriftenreihe:Теорія оптимальних рішень
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/112392
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:Гібридний алгоритм факторизації стрічкових несиметричних матриць / А.Ю. Баранов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015.. — С. 22-28. — Бібліогр.: 8 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-112392
record_format dspace
spelling irk-123456789-1123922017-01-21T21:49:59Z Гібридний алгоритм факторизації стрічкових несиметричних матриць Баранов, А.Ю. Запропоновано алгоритм факторизації стрічкових несиметричних матриць на комп’ютерах гібридної архітектури. Проведено апробацію алгоритму на суперкомп’ютерах СКІТ-4 та Інпарком. Предложен алгоритм факторизации ленточных несимметричных матриц на компьютерах гибридной архитектуры. Алгоритм апробирован на суперкомпьютерах СКИТ-4 и Инпарком. An algorithm for factorization of band nonsymmetric matrices using hybrid computers is considered. The results of testing of the algorithm on supercomputers Inparcom and SCIT-4 are presented. 2015 Article Гібридний алгоритм факторизації стрічкових несиметричних матриць / А.Ю. Баранов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015.. — С. 22-28. — Бібліогр.: 8 назв. — укр. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/112392 519.6 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
description Запропоновано алгоритм факторизації стрічкових несиметричних матриць на комп’ютерах гібридної архітектури. Проведено апробацію алгоритму на суперкомп’ютерах СКІТ-4 та Інпарком.
format Article
author Баранов, А.Ю.
spellingShingle Баранов, А.Ю.
Гібридний алгоритм факторизації стрічкових несиметричних матриць
Теорія оптимальних рішень
author_facet Баранов, А.Ю.
author_sort Баранов, А.Ю.
title Гібридний алгоритм факторизації стрічкових несиметричних матриць
title_short Гібридний алгоритм факторизації стрічкових несиметричних матриць
title_full Гібридний алгоритм факторизації стрічкових несиметричних матриць
title_fullStr Гібридний алгоритм факторизації стрічкових несиметричних матриць
title_full_unstemmed Гібридний алгоритм факторизації стрічкових несиметричних матриць
title_sort гібридний алгоритм факторизації стрічкових несиметричних матриць
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2015
url http://dspace.nbuv.gov.ua/handle/123456789/112392
citation_txt Гібридний алгоритм факторизації стрічкових несиметричних матриць / А.Ю. Баранов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015.. — С. 22-28. — Бібліогр.: 8 назв. — укр.
series Теорія оптимальних рішень
work_keys_str_mv AT baranovaû gíbridnijalgoritmfaktorizacíístríčkovihnesimetričnihmatricʹ
first_indexed 2025-07-08T03:50:52Z
last_indexed 2025-07-08T03:50:52Z
_version_ 1837049213516513280
fulltext 22 Теорія оптимальних рішень. 2015 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Запропоновано алгоритм факто- ризації стрічкових несиметричних матриць на комп’ютерах гібрид- ної архітектури. Проведено апро- бацію алгоритму на суперкомп’ю- терах СКІТ-4 та Інпарком.  А.Ю. Баранов, 2015 УДК 519.6 А.Ю. БАРАНОВ ГІБРИДНИЙ АЛГОРИТМ ФАКТОРИЗАЦІЇ СТРІЧКОВИХ НЕСИМЕТРИЧНИХ МАТРИЦЬ Вступ. При чисельному розв’язанні задач у багатьох випадках виникає необхідність роз- в’язувати систему лінійних алгебраїчних рів- нянь (СЛАР). Наприклад, задачі лінійної алгебри виникають при дискретизації крайо- вих задач чи задач на власні значення проекційно-різницевим методом (скінченних елементів, скінченних різниць). Також, при використанні методів математичного програ- мування, ітераційних методів розв’язання нелінійних задач часто на кожній ітерації розв’язується СЛАР. Важливою особливістю задач лінійної ал- гебри, які виникають при дискретизації, являється те, що кількість ненульових еле- ментів матриць таких задач складає kn , де nk  , а n – порядок матриці, тобто матриці є розрідженими [1]. Структура роз- рідженої матриці визначається нумерацією невідомих задач і часто є стрічковою, блочно-діагональною з обрамленням, про- фільною і тому подібне. В даній статі роз- глядаються несиметричні матриці стрічкової структури. Іншою важливою особливістю є великий порядок матриці СЛАР – до десятків мільйо- нів. Це зумовлюється бажанням викори- стовувати більш точні дискретні моделі, що дає можливість отримувати наближені роз- в’язки більш близькі до розв’язків вихідних задач, враховувати локальні особливості даного процесу чи явища. Актуальним на сучасному етапі є ство- рення ефективних паралельних алгоритмів для комп’ютерів гібридної (MIMD, SIMD) архітектури. ГІБРИДНИЙ АЛГОРИТМ ФАКТОРИЗАЦІЇ … Теорія оптимальних рішень. 2015 23 Постановка задачі. Розглянемо систему лінійних алгебраїчних рівнянь: ,Ax b (1) де матриця A – стрічкова несиметрична, n – порядок матриці ,A 1k  кількість нижніх діагоналей, 2k – кількість верхніх діагоналей. Найбільш ефективним прямим методом розв’язання такої задачі є, як відомо, метод Гаусса [2]. Розв’язання системи (1) полягає у розв’язанні підзадач: трикутне розвинення матриці системи, розв’язання двох СЛАР з трикутними матрицями: ,A PLU (2) ,Ly b (3) .Ux y (4) Послідовний алгоритм факторизації. У роботі [3] показно, що кількість верхніх діагоналей матриці U дорівнює 21 kk  . Тому, для опису алгоритму будемо розглядати матрицю A з 21 kk  верхніми діагоналями. Нехай порядок стрічкової несиметричної матриці A дорівнює ,n pb 1 , 1 2 ,k lb k k ub   де b це деяке наперед задане натуральне число. Розіб’ємо матрицю A на квадратні блоки: 11 12 13 1(1 ) 21 22 23 2(1 ) 2(2 ) 31 32 ( 1)2( 1)1 ( 2)2 ( 1)( 1) ( 1) ( 1) 0 0 0 0 0 0 0 0 0 0 u u u ll l p p p p p p pp A A A A A A A A A A A AA A A A A A                                        Переходимо до опису алгоритму. Для кожного pi ,1 треба виконати такі кроки: 1) виконати факторизацію прямокутної матриці, елементами якої є блоки ( 1 ( 2) ,, , , , ,ii i i i i q iA A A A  де min( , ),q i l p  використовуючи алгоритм Гаусса для щільних матриць: А.Ю. БАРАНОВ 24 Теорія оптимальних рішень. 2015 ii qi ii i qi ii U L L P A A                       . (5) 2) перестановка рядків у тих підматрицях, де це необхідно, використо- вуючи матрицю iP ; 3) знаходження матриць ( 1) ( 2), , , ,i i i i irU U U  де ),min( puir  за формулою:    iriiiiirii AALUU  )1( 1 )1(     ; (6) 4) оновлення матриць jtA , де 1,j i q  та 1,t i r  за формулою: itjijtjt ULAA  . (7) Після виконання всіх кроків алгоритму отримуємо трикутне розвинення вихідної матриці. Гібридний алгоритм факторизації. Розглянемо алгоритм факторизації несиметричної стрічкової матриці для гібридних комп’ютерів з графічними прискорювачами. Такі алгоритми потребують копіювання даних з пам’яті CPU до пам’яті GPU та навпаки. Сучасні GPU мають можливість одночасно викону- вати копіювання даних та операції обчислення. Також, обсяг глобальної пам’яті GPU є меншим за пам’ять CPU. Тому, доцільним є створення гібридних алго- ритмів, які будуть оптимально використовувати пам’ять GPU, використо- вуватимуть можливість одночасно виконувати обчислення та копіювання даних. Нехай кількість доступних графічних прискорювачів дорівнює .g На i -му кроці послідовного алгоритму факторизації нам потрібні тільки блоки, які знаходяться в i -му стовпчику, та в u стовпчиках, що слідують за ним. При цьому, в кожному стовпчику знаходиться найбільше 1u l  блоків. Таким чином, на кожному кроці алгоритму, достатньо зберігати в GPU тільки ці блоки. Переходимо до опису гібридного алгоритму факторизації. Блоки матриці ,A що знаходяться на GPU, будемо позначати використовуючи верхній індекс .d Будемо виконувати операцію з п. 1 послідовного алгоритму на CPU, всі інші операції доцільно виконувати на GPU. Перед початком роботи алгоритму, виконується копіювання блоків матриці ,A що знаходяться в перших 1u стовпчиках, у пам’ять GPU. При цьому, блоки які знаходяться в стовпчику з номером t копіюються в GPU з номером ( 1)mod .t g Для кожного pi ,1 треба виконати наступні кроки: 1) копіювання діагонального блоку d iiА та блоків що знаходяться нижче його в стовпчику :i ( 1) ( 2) ,, , ,d d d i i i i q iA A A  у пам’ять CPU; ГІБРИДНИЙ АЛГОРИТМ ФАКТОРИЗАЦІЇ … Теорія оптимальних рішень. 2015 25 2) факторизації прямокутної матриці, елементами якої є блоки ( 1) ( 2) ,, , , ,ii i i i i q iA A A A  за формулою (5); 3) копіювання отриманих на попередньому кроці блоків , , ,ii qiL L ,iiU iP у пам’ять всіх GPU; 4) у кожному GPU виконується перестановка рядків у тих блоках, де це необхідно, використовуючи матриці ;d iP 5) обчислення блоків ( 1) ( 2 ) , , , , i i i i ir d d dU U U   де ),min( puir  за формулою:       1 ( 1) ( 1) .d d d d d i i ir ii i i irU U L A A    (8) Оскільки кожний GPU має свою копію блоку d iiL , а всі інші члени формули (8) знаходяться в одному стовпчику, то обчислення на цьому кроці можуть здійснюватися одночасно всіма GPU; 6) модифікація блоків ,d jtA де 1,j i q  та 1,t i r  за формулою: .d d d d jt jt jt itA A L U  (9) Кожний GPU має свою копію блоку ,d jiL а блоки d jtA та d itU знаходяться в одній колонці, а отже і в пам’яті одного GPU. Тому обчислення на цьому кроці можуть здійснюватися одночасно всіма GPU; 7) якщо 2 ,i u p   то копіюємо блоки матриці в стовпчику 2i u  у пам’ять GPU з номером ( 1)mod .i u g  Реалізація гібридного алгоритму. При реалізації гібридного алгоритму, доцільно використовувати функції з бібліотеки cuBLAS [4]. Для обрахунків за формулою (8) доцільно використовувати функцію cublasDtrsm, а для формули (9) – cublasDgemm. Для факторизації щільної прямокутної матриці на CPU доцільно використовувати високопродуктивну функцію з бібліотеки Intel MKL [5]. На i -му кроці, оновлення блоків із стовпчика 1,i  за формулою (9), слід виконувати в спеціально виділеному потоці cudaStream_t. Оскільки CUDA має можливість асинхронного запуску функцій на GPU, то використання спеціального потоку для оновлення блоків у стовпчику 1,i  дає можливість почати факторизацію за формулою (5) на 1i -му кроці одночасно з виконанням обчислень за формулою (9) на i -му кроці. Таким чином, одночасно виконую- ться обчислення на CPU та GPU. Також слід зазначити, що даний алгортим може бути реалізований як на одновузлових комп’ютерах з декількома GPU (використовуючи POSIX Threads, OpenMP тощо), так і на багатовузлових комп’ютерах, використовуючи MPI. А.Ю. БАРАНОВ 26 Теорія оптимальних рішень. 2015 Експериментальне дослідження ефективності гібридного алгоритму. Запропонований паралельний алгоритм реалізовано на комп'ютерах з гібрид- ною (MIMD, SIMD) архітектурою: комп’ютері з графічними прискорювачами Інпарком (Tesla M2090, 2 CPU Intel(R) Xeon(R) E5606 @ 2.13GHz) [6], та СКІТ-4 (Tesla M2050, 4 CPU Intel(R) Xeon(R) X5675 @ 3.07GHz) [7]. В чисельних експериментах використовувалися матриці порядку 100000. На рис. 1 показано залежність часу факторизації матриці від напівширини плитки для різних значень ширини блоку ,b експерименти проведені на комп’ютері СКІТ-4. На рис. 1, а використовується 2 GPU, а на рис. 1, б використовується 3 GPU. 0 2 4 6 8 10 12 14 16 1000 2000 3000 4000 Напівширина стрічки а Ч а с ф а к т о р и з а ц ії м а т р и ц і, с е к . 64 96 128 192 0 2 4 6 8 10 12 1000 2000 3000 4000 Напівширина стрічки б Ч а с ф а к т о р и з а ц ії м а т р и ц і, с е к . 64 96 128 196 РИС. 1. Залежність часу факторизації матриці від напівширини стрічки для різних розмірів блоку на комп’ютері СКІТ-4 На рис. 2 показано залежність часу факторизації матриці від напівширини плитки для різних значень ширини блоку ,b експерименти проведені на комп’ю- тері Інпарком. На рис. 2, а використовується 1 GPU, а на рис. 2, б використо- вується 2 GPU. На рис. 3, а показано прискорення алгоритму факторизації матриці в залежності від напівширини стрічки для двох GPU; експерименти проводились на комп’ютері СКІТ-4. На рис. 3, б показано прискорення алгоритму факторизації матриці для двох та трьох GPU; експерименти проводились на комп’ютері Інпарком. У цих експериментах вибирався оптимальний порядок блоку b в залежності від напівширини стрічки матриці. ГІБРИДНИЙ АЛГОРИТМ ФАКТОРИЗАЦІЇ … Теорія оптимальних рішень. 2015 27 0 5 10 15 20 25 1000 2000 3000 4000 Напівширина стрічки а Ч а с ф а к т о р и з а ц ії м а т р и ц і, с е к . 64 96 128 192 0 2 4 6 8 10 12 14 16 18 20 1000 2000 3000 4000 Напівширина стрічки б Ч а с ф а к т о р и з а ц ії м а т р и ц і, с е к . 64 96 128 192 РИС. 2. Залежність часу факторизації матриці від напівширини стрічки для різних розмірів блоку на комп’ютері Інпарком 0 0,5 1 1,5 2 2,5 3 1000 2000 3000 4000 Напівширина стрічки П р и с к о р е н н я 2 GPU 3 GPU а б РИС. 3. Прискорення алгоритму факторизації матриці в залежності від напівширини стрічки на комп’ютерах: а – Інпарком та б – СКІТ-4 1,25 1,3 1,35 1,4 1,45 1,5 1000 2000 3000 4000 Напівширина стрічки Прискорення 2 GPU А.Ю. БАРАНОВ 28 Теорія оптимальних рішень. 2015 Висновки. Запропоновано алгоритм факторизації стрічкових несиметрич- них матриць, який забезпечує високу ефективність розпаралелювання на GPU, враховує структуру стрічкової матриці, оптимізує використання пам’яті GPU. Експериментально проведено дослідження вибору оптимального розміру шири- ни плиток, на які розбивається вихідна матриця. Подальші дослідження доцільно направити на розробку алгоритмів для гра- фічних прискорювачів архітектури Kepler [8], зокрема використання можливості динамічного паралелізму. А.Ю. Баранов ГИБРИДНЫЙ АЛГОРИТМ ФАКТОРИЗАЦИИ ЛЕНТОЧНЫХ НЕССИМЕТРИЧЕСКИХ МАТРИЦ Предложен алгоритм факторизации ленточных несимметричных матриц на компьютерах гибридной архитектуры. Алгоритм апробирован на суперкомпьютерах СКИТ-4 и Инпарком. A.Y. Baranov HYBRID ALGORITHM FOR FACTORIZATION OF BAND NONSYMMETRIC MATRICES An algorithm for factorization of band nonsymmetric matrices using hybrid computers is considered. The results of testing of the algorithm on supercomputers Inparcom and SCIT-4 are presented. 1. Химич А.Н., Попов А.В., Полянко В.В. Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры // Кибернетика и системный анализ. – 2011. – 47, № 6. – С. 159 – 174. 2. Уилкинсон Дж.Х., Райнш К. Справочник алгоритмов на языке Алгол // Линейная алгебра. – М.: Машиностроение, 1976. – 389 с. 3. Gene H., Golub and Charles F. Van Loan. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA. 4. https://developer.nvidia.com/cuBLAS 5. http://software.intel.com/en-us/intel-mkl. 6. Химич А.Н., Молчанов И.Н., Мова В.И. и др. Численное программное обеспечение MIMD-компьютера Инпарком. – Киев: Наук. думка, 2007. – 222 с. 7. http://icybcluster.org.ua 8. http://www.nvidia.com/object/nvidia-kepler.html Одержано 27.01.2015 https://developer.nvidia.com/cuBLAS http://software.intel.com/en-us/intel-mkl http://www.nvidia.com/object/nvidia-kepler.html

Ähnliche Einträge