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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Хіміч, О.М., Чистяков, О.В., Бруснікін, В.М.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут проблем математичних машин і систем НАН України 2015
Schriftenreihe:	Математичні машини і системи
Schlagworte:	Обчислювальні системи
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/113489
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. — № 3. — С. 3-13. — Бібліогр.: 15 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-113489
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1134892025-02-23T20:05:04Z Гібридний алгоритм узагальненого методу спряжених градієнтів для проблеми власних значень з симетричними розрідженими матрицями Гибридный алгоритм обобщенного метода сопряженных градиентов для проблемы собственных значений с симметричными разреженными матрицами Hybrid algorithm of generalized method of conjugate gradients for eigenvalue problem of symmetric sparse matrices Хіміч, О.М. Чистяков, О.В. Бруснікін, В.М. Обчислювальні системи Розглянуто гібридний алгоритм узагальненого методу спряжених градієнтів для розв’язання часткової проблеми власних значень для розріджених симетричних додатно визначених матриць. Досліджено ефективність розробленого гібридного паралельного алгоритму та подано результати апробації алгоритму на комп’ютері гібридної архітектури. Використання графічних процесорів дало змогу значно підвищити швидкодію гібридного алгоритму у порівнянні з послідовною його версією. Рассмотрен гибридный алгоритм обобщенного метода сопряженных градиентов для решения частичной проблемы собственных значений для разреженных симметричных положительно определенных матриц. Исследована эффективность разработанного гибридного параллельного алгоритма и представлены результаты апробации алгоритма на компьютере гибридной архитектуры. Использование графических процессоров позволило значительно повысить быстродействие гибридного алгоритма по сравнению с последовательной его версией. We consider a hybrid algorithm of generalized method of conjugate gradients for solving the partial eigenvalue problem of symmetric sparse positive definite matrices. The efficiency of the developed parallel algorithm and results of its testing on hybrid computer are shown. Using GPUs has allowed to improve significantly the performance of the hybrid algorithm compared to its sequential version. 2015 Article Гібридний алгоритм узагальненого методу спряжених градієнтів для проблеми власних значень з симетричними розрідженими матрицями / О.М. Хіміч, О.В. Чистяков, В.М. Бруснікін // Математичні машини і системи. — 2015. — № 3. — С. 3-13. — Бібліогр.: 15 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/113489 519.6 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	2015
topic_facet	Обчислювальні системи
url	https://nasplib.isofts.kiev.ua/handle/123456789/113489
citation_txt	Гібридний алгоритм узагальненого методу спряжених градієнтів для проблеми власних значень з симетричними розрідженими матрицями / О.М. Хіміч, О.В. Чистяков, В.М. Бруснікін // Математичні машини і системи. — 2015. — № 3. — С. 3-13. — Бібліогр.: 15 назв. — укр.
series	Математичні машини і системи
work_keys_str_mv	AT hímíčom gíbridnijalgoritmuzagalʹnenogometodusprâženihgradíêntívdlâproblemivlasnihznačenʹzsimetričnimirozrídženimimatricâmi AT čistâkovov gíbridnijalgoritmuzagalʹnenogometodusprâženihgradíêntívdlâproblemivlasnihznačenʹzsimetričnimirozrídženimimatricâmi AT brusníkínvm gíbridnijalgoritmuzagalʹnenogometodusprâženihgradíêntívdlâproblemivlasnihznačenʹzsimetričnimirozrídženimimatricâmi AT hímíčom gibridnyjalgoritmobobŝennogometodasoprâžennyhgradientovdlâproblemysobstvennyhznačenijssimmetričnymirazrežennymimatricami AT čistâkovov gibridnyjalgoritmobobŝennogometodasoprâžennyhgradientovdlâproblemysobstvennyhznačenijssimmetričnymirazrežennymimatricami AT brusníkínvm gibridnyjalgoritmobobŝennogometodasoprâžennyhgradientovdlâproblemysobstvennyhznačenijssimmetričnymirazrežennymimatricami AT hímíčom hybridalgorithmofgeneralizedmethodofconjugategradientsforeigenvalueproblemofsymmetricsparsematrices AT čistâkovov hybridalgorithmofgeneralizedmethodofconjugategradientsforeigenvalueproblemofsymmetricsparsematrices AT brusníkínvm hybridalgorithmofgeneralizedmethodofconjugategradientsforeigenvalueproblemofsymmetricsparsematrices
first_indexed	2025-11-24T21:27:00Z
last_indexed	2025-11-24T21:27:00Z
_version_	1849708637310681088
fulltext	© Хіміч О.М., Чистяков О.В., Бруснікін В.М., 2015 3 ISSN 1028-9763. Математичні машини і системи, 2015, № 3 ОБЧИСЛЮВАЛЬНІ СИСТЕМИ УДК 519.6 О.М. ХІМІЧ * , О.В. ЧИСТЯКОВ * , В.М. БРУСНІКІН ** ГІБРИДНИЙ АЛГОРИТМ УЗАГАЛЬНЕНОГО МЕТОДУ СПРЯЖЕНИХ ГРАДІЄНТІВ ДЛЯ ПРОБЛЕМИ ВЛАСНИХ ЗНАЧЕНЬ З СИМЕТРИЧНИМИ РОЗРІДЖЕНИМИ МАТРИЦЯМИ * Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна ** Інститут проблем математичних машин і систем НАН України, Київ, Україна Анотація. Розглянуто гібридний алгоритм узагальненого методу спряжених градієнтів для розв’язання часткової проблеми власних значень для розріджених симетричних додатно визначе- них матриць. Досліджено ефективність розробленого гібридного паралельного алгоритму та по- дано результати апробації алгоритму на комп’ютері гібридної архітектури. Використання гра- фічних процесорів дало змогу значно підвищити швидкодію гібридного алгоритму у порівнянні з послідовною його версією. Ключові слова: комп’ютери гібридної архітектури, алгебраїчна проблема власних значень, розрі- джена матриця, технології програмування CUDA та MPI. Аннотация. Рассмотрен гибридный алгоритм обобщенного метода сопряженных градиентов для решения частичной проблемы собственных значений для разреженных симметричных положи- тельно определенных матриц. Исследована эффективность разработанного гибридного парал- лельного алгоритма и представлены результаты апробации алгоритма на компьютере гибридной архитектуры. Использование графических процессоров позволило значительно повысить быстро- действие гибридного алгоритма по сравнению с последовательной его версией. Ключевые слова: компьютеры гибридной архитектуры, алгебраическая проблема собственных значений, разреженная матрица, технологии программирования CUDA и MPI. Abstract. We consider a hybrid algorithm of generalized method of conjugate gradients for solving the partial eigenvalue problem of symmetric sparse positive definite matrices. The efficiency of the developed parallel algorithm and results of its testing on hybrid computer are shown. Using GPUs has allowed to improve significantly the performance of the hybrid algorithm compared to its sequential version. Keywords: сomputers of hybrid architecture, algebraic problem of eigenvalues, sparse matrix, CUDA and MPI programming technology. 1. Вступ Велика кількість наукових та практичних задач, зокрема, при дослідженні стійкості конс- трукцій, розрахунку динаміки напружено-деформованого стану об’єктів різної природи та ін., зводяться до розв’язання часткової алгебраїчної проблеми власних значень з симетри- чними додатно визначеними матрицями розрідженої структури великої розмірності [1]. Такі задачі можуть бути ефективно розв’язані за допомогою однокрокових та двокрокових ітераційних методів. У статті [2] розглядаються явні та неявні однокрокові ітераційні ме- тоди для часткової проблеми власних значень, серед яких метод найшвидшого спуску, ме- тод обернених ітерацій, степеневий метод та поперемінно-трикутний метод. Також висвіт- лено ряд питань щодо вибору параметрів та передобумовлювачів для підвищення швидко- дії методів, доведено збіжність представлених методів. У роботі [3] розглянуто практичні аспекти розробки високоефективних паралельних однокрокових алгоритмів для MIMD- комп’ютерів та комп’ютерів гібридної архітектури, приведено результати обчислювальних експериментів на інтелектуальній робочій станції гібридної архітектури Інпарком_G. 4 ISSN 1028-9763. Математичні машини і системи, 2015, № 3 У роботах Савинова В.Г. [4, 5] розглядаються двокрокові схеми на прикладі уза- гальненого методу спряжених градієнтів. Для даного методу доводиться збіжність, пода- ються рекомендації щодо вибору ітераційних параметрів, а також пропонується викорис- товувати регуляризатор на основі методу симетричної верхньої релаксації для розв’язання систем лінійних алгебраїчних рівнянь. У прикладному програмному забезпеченні бібліотечного виду Lis (Library of Itera- tive Solvers for Linear Systems) [6] реалізовано паралельні алгоритми для розв’язання на MIMD-комп’ютерах задач на власні значення з розрідженими матрицями з використанням прямих методів, що базуються на методах Крилова, Ланцоша, Арнольді, а також ітерацій- них методів, що базуються на степеневому методі та методі простої ітерації. Бібліотека па- ралельних програм SLEPc (Scalable Library for Eigenvalue Problem) [7] для розв’язування задач на власні значення надає інтерфейси до таких програмних засобів, як ARPACK та BLOPEX. Велика розмірність розріджених матриць у задачах на власні значення, які виника- ють при математичному моделюванні практичних задач, та їх обчислювальна складність потребують використання потужних комп’ютерів для їх розв’язування. Гібридні комп’ютери з багатоядерними процесорами (CPU) та графічними процесорами (GPU − graphics processing units), а також технології GPGPU (General-purpose graphics processing units − GPU загального призначення) дають можливість значно зменшити час розв’язування таких задач. У даній роботі розглядається задача на власні значення: xAx λ , (1) де А – симетрична розріджена додатно визначена матриця порядку n , та x − власне значення і відповідний власний вектор. Для розв’язання алгебраїчної часткової проблеми власних значень для симетричних додатно визначених розріджених матриць на комп’ютерах гібридної архітектури пропону- ється неявний гібридний алгоритм спряжених градієнтів. Досліджено ефективність розро- бленого алгоритму та подано результати його апробації на комп’ютері гібридної архітек- тури. Для знаходження мінімального власного значення використовується узагальнений метод спряжених градієнтів [4]: ....,12,1, ...,,12,1, ,,/ 2 2 1 NNk px px NNkpx pp x k k k k k k k k k k kk k (2) Тут ми маємо ,)()( 1k k kkk pxfxBp ,3,2,1, , )])([,( )])([),()(( ,....;,2,0,0 11 1 1 k pIxAp pIxAxfxB Nk kkk kkkk k k   2 f(x)= A- μ(x)I x / x , , ),( ),( )( xx xAx x ISSN 1028-9763. Математичні машини і системи, 2015, № 3 5 )( kxB – деяка матриця, яка вибирається із умов прискорення збіжності ітераційного проце- су, N – момент відновлення, параметр k може бути вибраний як точка локального міні- муму функціоналу )( kk px . Ітераційний процес закінчується за критерієм .eps )k( )k()k( μ μμ 1 Для узагальненого методу спряжених градієнтів справедлива така теорема [4]. Теорема. Якщо ,),)(( 2 2 2 2 yMyyxBym ,, nRyx Mm0 та N , то ітераційний процес збігається для будь-якого початкового наближення 0x , причому: ,)x( i k k λμlim ,x i k k νlim де ii , νλ – одне із власних значень та відповідний йому влас- ний вектор матриці А. Зазначимо, що при практичній реалізації методу через помилки заокруглення про- цес буде збігатися до 11 νλ , . При створенні ефективного паралельного алгоритму методу спряжених градієнтів необхідно враховувати, що виконання ітерацій методу здійснюється послідовно, тому до- цільно розглядати математичні операції, які можуть бути розпаралелені на кожній ітерації. Аналіз послідовного варіанта алгоритму (2) показує, що найбільш трудомісткими операці- ями (підзадачами) на кожній ітерації за затратами обчислювальних ресурсів і часом вико- нання є множення розрідженої матриці на вектор та розв’язання систем лінійних алгебраї- чних рівнянь (СЛАР) з трикутними матрицями. Саме ці підзадачі і підлягають розпарале- ленню з урахуванням архітектурних особливостей обчислювального середовища гібридно- го комп’ютера. Для ефективного виконання гібридного алгоритму необхідно забезпечувати: • ефективні способи збереження розріджених матриць для виконання матрично- векторних операцій на СPU і GPU; • розв’язування підзадач, які потребують найбільших затрат комп’ютерного часу на GPU; • рівномірне завантаження процесів, що використовуються при розв’язуванні задачі (балансування навантаження); • синхронізацію обмінів між процесами CPU; • мінімізацію обмінів між процесами CPU та між СPU і GPU. 2. Приведенення матриці до блочно-діагонального вигляду з обрамленням З метою підвищення ефективності розв’язання задачі з розрідженими матрицями великих розмірностей була використана ідея попереднього приведення вхідної розрідженої матриці А за допомогою методу паралельних перерізів до блочно-діагональної матриці з обрамлен- ням [8]. Такий підхід дає змогу використовувати більш природний підхід до розпаралелен- ня обчислень на гібридному комп’ютері. Представлення розрідженої матриці у вигляді блочно-діагональної з обрамленням дає можливість ефективно виконувати матрично- векторні операції як на CPU, використовуючи, наприклад, бібліотеку обчислювальної ма- тематики Intel MKL [9], так і на GPU, з використанням бібліотек програм матрично- векторних операцій cuBLAS [10] та cuSPARSE [11]. Схематично матриця, приведена до блочно-діагонального вигляду з обрамленням, має вигляд: 6 ISSN 1028-9763. Математичні машини і системи, 2015, № 3 pp pp T DBBBB BD BD BD BD APPA 1321 11 33 22 11 ... 000 000 0...00 0...00 ~  , де P – матриця перестановок, а блоки iD i iB зберігають розрідженість. Блочно-діагональна матриця може бути представлена як TL ~ L ~ IA ~ , а матриця L ~ є нижньою трикутною блочно-діагональною матрицею з обрамленням. Матриця L ~ складається з трикутних матриць iD ~ на діагоналі та розріджених матриць довільної струк- тури iC ~ в обрамленні, а саме: pp pp D ~ C ~ C ~ C ~ C ~ D ~ D ~ D ~ D ~ pL ~ L ~ L ~ L ~ L ~ L ~ 1321 1 3 2 1 1 3 2 1 0000 0000 0000 0000       . (3) Таким чином, початкова задача зводиться до такої еквівалентної: yyA ~ . 3. Неявний ітераційний гібридний алгоритм методу спряжених градієнтів Для покращання швидкості збіжності ітераційного процесу використовується оператор (регуляризатор)  B x , який можна вибирати на основі методу верхньої симетричної рела- ксації для розв’язання систем лінійних алгебраїчних рівнянь [4]. У цьому випадку: ˆ ˆ ˆ T1 A(x)= (A(x)- μ(x)I)= I - L(x)- L (x) 1- μ(x) , ˆ ˆT -1 -1B(x)=ω(2 -ω)(I -ωL (x)) (I -ωL(x)) , ˆ 1 L(x)= L(x) 1- μ(x) , де – параметр релаксації, )2;1( . З огляду на структуру L̂(x) реалізується такий розподіл блоків (підматриць) L̂(x) по процесах CPU: процеси з номерами pi0 зберігають блоки ˆ iD (x) та ˆ iC (x), а про- цес з номером 1p зберігає блок ˆ iD (x) . Тут p – загальна кількість процесів. ISSN 1028-9763. Математичні машини і системи, 2015, № 3 7 Паралельна реалізація алгоритму в основному визначається блочно-трикутною структурою матриць ˆ iL (x) при розв’язанні системи: ˆ ˆ ,T(I -ωL (x))(I -ωL(x))w= r(x) r(x)=ω(2 -ω)f(x), 1k k kk ppw . Алгоритм розв’язання нижньої трикутної системи T̂(I -ωL (x))y= r зводиться до одночасного та незалежного розв’язування трикутних систем на окремих процесах гібрид- ного комп’ютера з використанням GPU: ˆ q q q(I -ωD (x))y = r , pq1 , та наступного обчислення ˆ q q qy = C (x)y , pq0 , де q – номер процесу. Далі всі процеси надсилають qy~ в останній процес, в якому обчислюється py , розв’язуючи систему ˆ   p-1 p p p q q-1 (I -ωD (x))y = r - y . Аналогічно розв’язується система ˆ(I -ωL(x))w= y , де p -й процес розв’язує сис- тему ˆ p p(I -ωL(x))w = y , а потім розсилає компоненти pw іншим процесам, які незале- жно розв’язують системи ˆˆ Τ q q q p(I -ωL (x))w = y -C (x)w . 4. Оцінки ефективності неявного гібридного алгоритму спряжених градієнтів Розглядаючи розроблений гібридний алгоритм, зазначимо, що основними за складністю арифметичними операціями є множення розрідженої матриці на щільний вектор та розв’язання двох трикутних систем. Для однієї операції множення розрідженої матриці на щільний вектор кількість опе- рацій дорівнює n i iM 1 2 операцій. Для розв’язання однієї трикутної системи справедлива така оцінка складності послідовного алгоритму: n i iiN 1 2 2 операцій. Для визначення оцінок ефективності гібридного алгоритму, в якому всі арифметич- ні операції в основному виконуються на GPU, введемо такі позначення: p – загальна кіль- кість графічних процесів, n – розмірність матриці, i − кількість ненульових елементів в i -му рядку нижньої трикутної матриці, 0k – кількість арифметичних операцій, що вико- нуються на одному GPU одночасно, t – час виконання однієї арифметичної операції на GPU, 0t – час обміну одним блоком між GPU, 1t – час обміну одним блоком між CPU та GPU. Загальний час розсилки даних можна оцінити як plogt 20 . Позначимо 1T – час виконання алгоритму на одному GPU, а pT – алгоритму з вико- ристанням p GPU. Тоді маємо такі наближені співвідношення: 8 ISSN 1028-9763. Математичні машини і системи, 2015, № 3 ,bt)NM( k t qT 1 0 1 2 btptt pk N t pk M qTp 120 00 log, 2 max2 , де q – емпіричний коефіцієнт, що залежить від рівномірності навантаження на обчислюва- льний пристрій, від формату даних, що оброблюються, та архітектурних особливостей об- числювальної системи, )2,1;8,0(q , b – кількість ітерацій. Провівши грубе заокруглення, отримаємо оцінки прискорення та ефективності ал- горитму: ,log, log2 )(2 ,log, 20 001200 01 20 01 ptt pk N pktppktMtp pktpNMt ptt pk N p T T S p p .log, og2 )(2 ,og,1 20 001200 01 20 01 ptt pk N ktplktMt ktNMt pltt pk N p S Ep Отримані оцінки дають змогу стверджувати, що розроблений гібридний алгоритм забезпечує високе прискорення, оскільки наявність у дільниках комунікаційних складових величини 2n сприяє зменшенню частки часу, необхідного на обміни та синхронізацію процесів при великих порядках системи. 5. Особливості програмної реалізації гібридного алгоритму спряжених градієнтів для розв’язування часткової проблеми власних значень з розрідженими матрицями 5.1. Формати збереження розріджених матриць При створенні алгоритмів розв’язування задач з розрідженими матрицями велике значення має вибір способів задання та збереження ненульових елементів. Ці способи визначаються насамперед структурою (розміщенням ненульових елементів) розрідженої матриці, вимо- гами алгоритму, який використовується, а також архітектурою гібридного комп’ютера. Складність ефективної обробки розріджених матриць привела до створення великої кількості форматів їх збереження в комп’ютері, наприклад, CSR (compressed sparse row), CSC (compressed sparse column), COO (coordinate) та ін. Проте не можна рекомендувати єдиний, близький до оптимального, формат зберігання даних. Це у великій мірі залежить від виду розрідженої матриці. У працях багатьох авторів, наприклад [8], проведено аналіз різних форматів збереження розріджених матриць, який показав, що формат CSR, що від- носиться до найбільш універсальних і дозволяє легко реалізувати оптимальний алгоритм множення розрідженої матриці на вектор на CPU, не завжди забезпечує таку продуктив- ність для цієї операції на GPU. У ряді випадків виявляється, що переваги мають модифіко- вані формати, які враховують розрідженість матриці, архітектурні особливості гібридного комп’ютера та організацію пам’яті на GPU. Оскільки розріджені матриці великої розмірності потребують великих об’ємів об- числювальних ресурсів для їх збереження в комп’ютері та витрат часу на їх обробку, ви- никає потреба у виконанні великої кількості додаткових операцій при їх переформатуванні або переіндексації для забезпечення масштабованості обчислювального процесу. Тому був розроблений комбінований формат збереження матриць, що базується на CSR форматі та ISSN 1028-9763. Математичні машини і системи, 2015, № 3 9 враховує особливості представлення блочно-діагональної розрідженої матриці з обрамлен- ням. Схематично комбінований формат представлено на рис. 1. Зі схеми на рис. 1 видно, що блочно-діагональна матриця з обрамленням зберігаєть- ся у class CSR::BD::Matrix у масивах вказівників на діагональні блоки та блоки з обрам- ленням. Тобто кожен блок є окремою підматрицею, збереженою у модифікованому форма- ті CSR (class CSR::Matrix). Такий підхід дозволяє маніпулювати кожним блоком незалежно та забезпечувати можливість розпаралелення обчислень як на MIMD-комп’ютерах, так і на комп’ютерах гі- бридної архітектури. Сlass CSR::BD::Matrix зберігає інформацію про вхідну матрицю class MatrixInfo, а саме: • розмірність матриці, кількість ненульових елементів та її розрідженість; • кількість заданих перерізів при перетворенні матриці; • кількість отриманих блоків у діагоналі та в обрамленні; • характеристики матриці, такі як симетричність, представлення матриці у трикут- ному вигляді та місце розташування трикутника (над чи під головною діагоналлю); • базис матриці (нульовий чи одиничний). Рис. 1. Комбінований формат збереження блочно-діагональної розрідженої матриці з обрамленням У свою чергу class CSR::Matrix зберігає підматриці у модифікованому форматі CSR, тобто поєднує у собі 3- та 4-векторний формат збереження, а саме зберігаються такі масиви: • vector<double>Value – ненульові елементи матриці; • vector<int>Columns – позиція ненульового елемента у рядку; • vector<int>RowIndex – кількість ненульових елементів у кожному рядку; • vector<int>PointerB – кількість ненульових елементів у кожному попередньому рядку; • vector<int>PointerE – кількість ненульових елементів у кожному наступному ряд- ку; matrix_size_type matrix_size; int NZ; double sparsity; int cuts_number; int blocks_in_diagonal; int blocks_in_border; vector <int> block_size; matrix_range_type matrix_range; bool sym_matrix_flag; bool triang_flag; bool lower_block_flag; int matrix_base; class MatrixInfo class CSR::Matrix int Matrix_size; vector<double> Value; vector<int> Columns; vector<int> RowIndex; vector<int> PointerB; vector<int> PointerE; MatrixInfo csr_bd_matrix_info class CSR::BD::Matrix vector<CSR::Matrix> diagonal_blocks vector<CSR::Matrix> border_blocks MatrixInfo csr_bd_matrix_info 10 ISSN 1028-9763. Математичні машини і системи, 2015, № 3 • MatrixInfo csr_bd_matrix_info – містить інформацію про кожну окрему підматрицю та її розташування у блочно-діагональній матриці з обрамленням. Таким чином, отримано уніфікований 5-рядковий формат збереження розрідженої матриці, що дозволяє використовувати відомі високопродуктивні бібліотеки обчислюваль- ної математики. Крім того, якщо у процесі обчислень додаткові масиви не потрібні, то во- ни видаляться автоматично, тим самим досягається більш оптимальне використання опе- ративної пам’яті. Такий формат є ефективним як для використання на CPU, так і на GPU. Він дає змогу, наприклад, застосовувати до блоків матриць в одній і тій же програмі, без прове- дення переіндексації їх елементів, як функції розпаралелення системи MPI, так і програми матрично-векторних операцій з бібліотеки Intel MKL. Тим самим забезпечуються більш ефективне використання обчислювальних ресурсів та висока масштабованість гібридних алгоритмів. Серед переваг обраного формату можна також зазначити прозорий підхід до проведення обчислень, передачі повідомлень між обчислювальними процесами, зменшен- ня витрат часу на розробку, відлагодження та тестування гібридних програм. 5.2. Налаштування гібридних алгоритмів та програм на обчислювальні ресурси гіб- ридного комп’ютера В сучасних гібридних комп’ютерах відмічається постійне оновлення типів обчислюваль- них вузлів та відеокарт, розробляються нові версії систем паралельного програмування MPI та CUDA, а також бібліотек програм обчислювальної математики, наприклад, In- tel MKL, NVidia CuBLAS, CuSparse тощо. Використання найновіших розробок програмно- технічного устаткування сприяє підвищенню ефективності гібридних алгоритмів та про- грам. Тому необхідно передбачити такий спосіб їх розробки, щоб можна було легко вноси- ти відповідні зміни зі змінами в обчислювальних ресурсах гібридного комп’ютера. З цією метою при створенні гібридного алгоритмічно-програмного засобу для розв’язування часткової проблеми власних значень для розріджених матриць ітераційними алгоритмами було використано концепцію «функцій-обгорток» [12]. «Обгортка» (англ. Wrapper) – це функція, яка є проміжною ланкою між прикладними функціями або програ- мами та іншою бібліотекою чи програмним інтерфейсом, а також може модифікувати або узагальнювати інтерфейси прикладних програм. При цьому реалізується модульний прин- цип програмування, який дає можливість при оновленні програмного забезпечення вноси- ти поправки лише в окремі програмні модулі. Комбінований формат збереження блочно- діагональної розрідженої матриці з обрамленням дозволяє ефективно використовувати концепцію «функцій-обгорток». До «обгорток» винесені службові функції для роботи з графічним прискорювачем, наприклад, cusparseCreate(…), cudaMemcpy(…) та ін. Блок-схему функціонального складу розробленого алгоритмічно-програмного засо- бу представлено на рис. 2, до якого входять: • Data structures – модуль, що відповідає за структури збереження даних та їх оброб- ку; • Wrappers function – модуль, в якому реалізовуються «функції-обгортки»; • Hight performance computing libraries – зовнішні високопродуктивні бібліотеки та інтерфейси паралельного програмування; • Statistics functions – модуль, що відповідає за збір, збереження та обробку статис- тичних даних, підвищення ефективності обчислювального процесу, а також за обробку ви- ключних та помилкових ситуацій; • Computing methods functions – модуль, в якому реалізовано обчислювальні алгори- тми (для своєї роботи цей модуль використовує вищенаведені модулі); • External user interface – модуль, що реалізує інтерфейс користувача. ISSN 1028-9763. Математичні машини і системи, 2015, № 3 11 Рис. 2. Блок-схема гібридного алгоритмічно-програмного засобу Такий підхід до розробки гібридного алгоритмічно-програмного засобу дозволяє отримати такі переваги: • розширюваність – за рахунок малої залежності між модулями можна легко дода- вати нові функціональні можливості, наприклад, підтримку нових високопродуктивних бібліотек або структур збереження даних; • зручне налагодження алгоритмічно-програмного засобу на гібридні комп’ютери з різними математичними та технічними характеристиками; • зменшення часу на відлагодження та супровід програмного засобу – відлагоджен- ня модулів відбувається лише один раз і в разі повторного використання повторне тесту- вання не потрібно проводити. 6. Апробація гібридного алгоритму спряжених градієнтів Для експериментального дослідження гібридного алгоритму, що розглядається, було вико- ристано матриці з колекції Флоридського університету [13] (табл. 1). Таблиця 1. Набір тестових матриць з Флоридської колекції розріджених матриць Назва задачі Проблемна область Порядок матриці Кількість ненульових елементів Bmwcra_1 Structural problem 148,770 10,641,602 Bone010 Model reduction problem 986,703 47,851,783 Emila_923 Structural problem 923,136 40,373,538 Обчислювальні експерименти проводилися на інтелектуальній робочій станції гіб- ридної архітектури Інпарком-G [14] з такими технічними характеристиками: чотири вузли з двома 4-ядерними Intel Xeon E5606 процесорами, оперативна пам’ять: 3 Гб на одне фізи- чне обчислювальне ядро. Програми, які реалізують гібридні алгоритми, написано на мові програмування С++ з використанням системи розпаралелювання MPI, бібліотеки Intel MKL для MIMD-комп’ютера, а також технології розпаралелення CUDA та бібліотек програм cuBLAS, cuSPARSE на GPU [15]. У табл. 2 приведено порівняльну характеристику знаходження найменшого власно- го значення на Інпарком-G однокроковим гібридним поперемінно-трикутним алгоритмом [3] та гібридним алгоритмом узагальненого методу спряжених градієнтів при використанні різної кількості ядер CPU та процесорів GPU. Data structures Hight performance computing libraries MKL cuSparse MPI … Wrappers function Statistics functions Computing methods functions External user interface 12 ISSN 1028-9763. Математичні машини і системи, 2015, № 3 Таблиця 2. Порівняльна часова характеристика (сек) гібридних алгоритмів Гібридний алгоритм узагальненого методу спряжених градієнтів Задача CPU CPU + GPU 1 Core 8 Core 16 Core 32 Core 1GPU 2GPU 4 GPU 8 GPU Bone010 155,37 22,32 11,93 8,39 23,29 14,32 7,92 4,52 Bmwcra_1 306,55 43,18 24,48 13,24 43,18 24,27 13,73 8,06 Emilia_923 489,74 69,47 38,08 20,53 66,09 35,28 22,41 13,41 Гібридний алгоритм неявного методу скорішого спуску Bone010 423,80 55,76 31,68 18,00 67,05 29,47 17,86 11,90 Bmwcra_1 820,74 115,27 62,64 34,04 117,41 56,02 30,78 18,76 Emilia_923 1185,52 173,06 90,13 46,94 161,07 77,99 44,31 26,06 З табл. 2 видно, що за неявним гібридним алгоритмом методу спряжених градієнтів на MIMD-комп’ютері найбільше прискорення обчислень при використанні 32 процесів у порівнянні з послідовною версією програми одержано від 18 до 23 разів. Використання одного GPU дає прискорення обчислень в 6,5 – 7,5 разів, а при масштабуванні гібридної системи до восьми GPU − в 34 – 38 разів у порівнянні з послідовною версією програми. За гібридним алгоритмом поперемінно-трикутного методу на MIMD-комп’ютері найбільше прискорення обчислень при використанні 32 процесів у порівнянні з послідов- ною версією програми одержано від 22 до 25 разів. При використанні одного GPU приско- рення обчислень складає 6,3 – 7,3 разів, а при використанні восьми GPU − в 35 – 45 разів у порівнянні з послідовною версією програми. Отже, порівнюючи часи виконання задач при однакових вхідних даних та критеріях закінчення ітераційного процесу двокроковий неявний гібридний алгоритм методу спря- жених градієнтів забезпечує прискорення у 2,0 – 2,8 разів у порівнянні з однокроковим гі- бридним алгоритмом поперемінно-трикутного методу. 7. Висновки Обчислення власних значень та відповідних їм векторів для розріджених матриць великих розмірностей потребують значних обчислювальних ресурсів. У роботі запропоновано ви- сокопродуктивний двокроковий неявний гібридний алгоритм методу спряжених градієнтів для розв’язання алгебраїчної часткової проблеми власних значень для симетричних додат- но визначених розріджених матриць на гібридних комп’ютерах. Створений алгоритм забезпечує суттєве скорочення часу обчислень, тобто відміча- ється пропорціональне зменшення часу розв’язування задачі зі збільшенням кількості про- цесорних ядер MIMD-комп’ютера та кількості графічних прискорювачів на гібридних об- числювальних системах. Програма, що реалізує розроблений гібридний алгоритм, входить до алгоритмічно- програмного забезпечення інтелектуальної робочої станції Інпарком-G і може використо- вуватися для розв’язання науково-технічних задач. СПИСОК ЛІТЕРАТУРИ 1. Приказчиков В.Г. Прототипы итерационных процессов в задаче на собственные значения / В.Г. Приказчиков // Дифференциальные уравнения. – 1980. – Т. 16, № 9. – C. 1688 − 1697. 2. Приказчиков В.Г. Итерационные методы решения задач устойчивости и колебания пластин и оболочек / В.Г. Приказчиков, А.Н. Химич // Прикладная механика. – 1984. – Т. 20, № 1. – C. 88 − 94. ISSN 1028-9763. Математичні машини і системи, 2015, № 3 13 3. Хіміч О.М. Паралельні однокрокові ітераційні методи розв’язання алгебраїчної проблеми влас- них значень для розріджених матриць / О.М. Хіміч, О.В. Чистяков // Компьютерная математика. – 2014. − № 2. – C. 81 − 88. 4. Савинов Г.В. Исследование сходимости одного обобщенного метода сопряженных градиентов для определения экстремальных собственных значений матрицы / Г.В. Савинов // Записки научных семинаров ЛОМИ. – 1980. – Т. 111. – С. 145 – 150. 5. Савинов Г.В. Обобщенный метод сопряженных градиентов для решения линейных систем / Г.В. Савинов // Записки научных семинаров ЛОМИ. – 1978. – Т. 80. – С. 181 – 188. 6. Lis (Library of Iterative Solvers for Linear Systems) [Електронний ресурс] / Akira Nishida. Japan. – Режим доступу: http://www.ssisc.org/lis/index.en.html. 7. SLEPc (Scalable Library for Eigenvalue Problem Computations) [Електронний ресурс] / Universitat Politècnica de València (Spain). – Режим доступу: http://slepc.upv.es. 8. Писсанецки С. Технология разреженных матриц / Писсанецки С. – М.: Мир, 1988. – 411 с. 9. Intel Maths Kernel Library [Електронний ресурс] / Intel. – Режим доступу: http://software.intel.com/en-us/intel-mkl. 10. cuSPARSE (The NVIDIA CUDA Sparse Matrix library) [Електронний ресурс] / NVIDIA. – Режим доступу: http://docs.nvidia.com/cuda/cusparse. 11. cuBLAS (The NVIDIA CUDA Basic Linear Algebra Subroutines) [Електронний ресурс] / NVIDIA. – Режим доступу: http://developer.download.nvidia.com/CUBLAS Library.pdf. 12. Wrapper function [Електронний ресурс] / Olaf Davis. – Режим доступу: http://en.wikipedia.org/wiki/Wrapper_function. 13. The University of Florida Sparse Matrix Collection. [Електронний ресурс] / University of Florida. – Режим доступу: http://www.cise.ufl.edu/research/sparse/matrices. 14. Численное программное обеспечение MIMD-компьютера Инпарком / А.Н. Химич, И.Н. Молча- нов, В.И. Мова [и др.]. – Киев: Наукова думка, 2007. – 222 с. 15. Боресков А.В. Основы работы с технологией CUDA / А.В. Боресков, А.А. Харламов. М.: Пресс, 2010. 232 с. Стаття надійшла до редакції 02.07.2015 http://www.ssisc.org/lis/index.en.html http://slepc.upv.es./ http://software.intel.com/en-us/intel-mkl http://developer.download.nvidia.com/CUBLAS%20Library.pdf

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

Institution

Ähnliche Einträge