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

Запропоновано алгоритм розв’язування часткової узагальненої алгебраїчної проблеми власних значень зі стрічковими симетричними матрицями на комп’ютерах гібридної архітектури. Приведено результати апробації алгоритму на персональному суперкомп’ютері гібридної архітектури Інпарком_pg....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Хіміч, О.М., Попов, О.В., Баранов, А.Ю., Чистяков, О.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/113023
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць / О.М. Хіміч, О.В. Попов, А.Ю. Баранов, О.В. Чистяков // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 86-94. — Бібліогр.: 10 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-113023
record_format	dspace
spelling	irk-123456789-1130232017-02-01T03:02:37Z Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць Хіміч, О.М. Попов, О.В. Баранов, А.Ю. Чистяков, О.В. Запропоновано алгоритм розв’язування часткової узагальненої алгебраїчної проблеми власних значень зі стрічковими симетричними матрицями на комп’ютерах гібридної архітектури. Приведено результати апробації алгоритму на персональному суперкомп’ютері гібридної архітектури Інпарком_pg. Предложен алгоритм решения частичной обобщенной алгебраической проблемы собственных значений с ленточными симметричными матрицами на компьютерах гибридной архитектуры. Приведены результаты апробации алгоритма на персональном суперкомпьютере гибридной архитектуры Инпарком_pg. This paper proposes an algorithm for solving partial generalized algebraic eigenvalue problem with band symmetric matrices on hybrid computers. The results of testing of the algorithm on a personal hybrid supercomputer Inparkom_pg are shown. 2016 Article Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць / О.М. Хіміч, О.В. Попов, А.Ю. Баранов, О.В. Чистяков // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 86-94. — Бібліогр.: 10 назв. — укр. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/113023 519.6 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Запропоновано алгоритм розв’язування часткової узагальненої алгебраїчної проблеми власних значень зі стрічковими симетричними матрицями на комп’ютерах гібридної архітектури. Приведено результати апробації алгоритму на персональному суперкомп’ютері гібридної архітектури Інпарком_pg.
format	Article
author	Хіміч, О.М. Попов, О.В. Баранов, А.Ю. Чистяков, О.В.
spellingShingle	Хіміч, О.М. Попов, О.В. Баранов, А.Ю. Чистяков, О.В. Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць Теорія оптимальних рішень
author_facet	Хіміч, О.М. Попов, О.В. Баранов, А.Ю. Чистяков, О.В.
author_sort	Хіміч, О.М.
title	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць
title_short	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць
title_full	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць
title_fullStr	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць
title_full_unstemmed	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць
title_sort	гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
url	http://dspace.nbuv.gov.ua/handle/123456789/113023
citation_txt	Гібридний алгоритм роз`язування задач на власні значення для стрічкових матриць / О.М. Хіміч, О.В. Попов, А.Ю. Баранов, О.В. Чистяков // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 86-94. — Бібліогр.: 10 назв. — укр.
series	Теорія оптимальних рішень
work_keys_str_mv	AT hímíčom gíbridnijalgoritmrozâzuvannâzadačnavlasníznačennâdlâstríčkovihmatricʹ AT popovov gíbridnijalgoritmrozâzuvannâzadačnavlasníznačennâdlâstríčkovihmatricʹ AT baranovaû gíbridnijalgoritmrozâzuvannâzadačnavlasníznačennâdlâstríčkovihmatricʹ AT čistâkovov gíbridnijalgoritmrozâzuvannâzadačnavlasníznačennâdlâstríčkovihmatricʹ
first_indexed	2025-07-08T05:03:56Z
last_indexed	2025-07-08T05:03:56Z
_version_	1837053811161563136
fulltext	86 Теорія оптимальних рішень. 2016 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Запропоновано алгоритм розв’язу- вання часткової узагальненої алге- браїчної проблеми власних значень зі стрічковими симетричними матрицями на комп’ютерах гіб- ридної архітектури. Приведено результати апробації алгоритму на персональному суперком- п’ютері гібридної архітектури Інпарком_pg. © О.М. Хіміч, О.В. Попов, А.Ю. Баранов, О.В. Чистяков, 2016 УДК 519.6 О.М. ХІМІЧ, О.В. ПОПОВ, А.Ю. БАРАНОВ, О.В. ЧИСТЯКОВ ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЗАДАЧ НА ВЛАСНІ ЗНАЧЕННЯ ДЛЯ СТРІЧКОВИХ МАТРИЦЬ Вступ. Велика кількість наукових та прак- тичних задач, зокрема при дослідженні стійкості конструкцій, розрахунку динаміки напружено-деформованого стану об’єктів різної природи та інші, зводяться до розв’я- зання часткової узагальненої алгебраїчної проблеми власних значень з симетричними стрічковими додатно-означеними матрицями великих розмірів. Важливою особливістю таких задач лінійної алгебри, які виникають при дискре- тизації, є те, що кількість ненульових елементів матриць складає kn , де nk  , а n – порядок матриці, тобто матриці є розрідженими [1, 2]. Структура розрідженої матриці визначається нумерацією невідомих задачі і часто є стрічковою, блочно-діаго- нальною з обрамленням, профільною і тому подібне. В даній статті розглядаються симе- тричні додатно-означені стрічкові матриці. Для розв’язування алгебраїчної проблеми власних значень зі стрічковою структурою матриць великих розмірів виникає необхід- ність створення нових алгоритмів, які забез- печують підвищення ефективності обчислень на комп’ютерах гібридної архітектури, тобто багатоядерних процесорах (CPU) з графіч- ними прискорювачами (GPU). Постановка задачі. Алгебраїчна пробле- ма власних значень (АПВЗ) полягає у зна- ходженні таких чисел , при яких існують відмінні від нульового розв’язки системи лінійних алгебраїчних рівнянь (СЛАР): ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЗАДАЧ НА ВЛАСНІ ЗНАЧЕННЯ … Теорія оптимальних рішень. 2016 87 Ax = λBx, A, B  Mn × n, x  Cn, λ  C, (1) де Mn × n – множина квадратних матриць порядку n. Числа  називаються власними значеннями задачі (1), а вектори x – власними векторами цієї задачі. Задача (1) називається узагальненою проблемою власних значень. Якщо B – одинична матриця n-го порядку (тобто B ≡ In), то задача Ax = λx (2) називається стандартною проблемою власних значень, а числа  та вектори x називаються відповідно власними значеннями та власними векторами матриці A. Можуть розглядатися такі задачі на власні значення:  повна проблема власних значень – знайти всі власні значення і всі власні вектори;  часткова проблема власних значень – знайти одне або декілька власних значень та відповідних їм векторів або лише власні значення (всі або декілька). Тут розглядається гібридний алгоритм методу ітерацій на підпросторі розв’язування часткової узагальненої проблеми власних значень (знаходження кількох найменших власних значень та відповідних власних векторів) для стрічкових симетричних додатно-означених матриць A та В. Також вважатимемо, що напівширина стрічки матриці A та матриці В рівні. Гібридний алгоритм методу ітерацій на підпросторі. Метод ітерацій на підпросторі є узагальненням методу обернених ітерацій і полягає в побудові послідовності підпросторів Et (t = 1, 2, ...), яка збігається до підпростору E∞, що містить шукані власні вектори. В методі ітерацій на підпросторі на t-й ітерації обчислюється орто- нормований базис підпростору Et та, якщо досягнута збіжність, визначаються шукані власні пари [1, 3]. Декомпозиція стрічкових симетричних матриць. Ефективність методів розв’язування великих АПВЗ (використання оперативної пам’яті та часу розв’язування) зі стрічковими матрицями у великій мірі залежить від ефектив- них способів зберігання, використання та обробки стрічкових матриць [4, 5]. Розподіл між процесами багатоядерного комп’ютера матриць A та B такий: елементи (головної діагоналі та піддіагональні) стрічкових симетричних матриць задачі повинні бути розподілені між процесами відповідно одномірної блочно-циклічної схеми, за якою процес з логічним номером r оперує з елемен- тами рядків матриці з номерами sI + 1,…, sI + s, а процес з номером r + 1 − з елементами рядків з номерами s(I + 1) + 1,…, s(I + 1) + s. Гібридний алгоритм методу ітерацій на підпросторі. Розв’язування АПВЗ зі стрічковими симетричними матрицями гібридним алгоритмом, що розгляда- ється, зводиться до виконання для t = 1, 2, … таких підзадач [1, 3]:  розв’язування системи рівнянь з матрицею A (розв’язується кожним процесом, використовуючи попередньо факторизовану матрицю): AXt = Yt1; (3) О.М. ХІМІЧ, О.В. ПОПОВ, А.Ю. БАРАНОВ, О.В. ЧИСТЯКОВ 88 Теорія оптимальних рішень. 2016  обчислення проекції матриці А на підпростір Et (виконується на GPU): t Τ tt Τ tt AXXYXA  1 ; (4)  обчислення прямокутної матриці (виконується з використанням GPU): Wt = BXt; (5)  обчислення проекції матриці B на підпростір Et (виконується з вико- ристанням GPU): t Τ tt Τ tt BXXWXB  ; (6)  розв’язування проблеми власних значень для проекцій (розв’язується кожним процесом незалежно): At Zt = Bt Zt Λt ; (7)  обчислення наступного наближення (за рахунок розподіленості даних між процесами, операції виконуються паралельно на CPU): Yt = WtZt; (8)  перевірка умов закінчення ітераційного процесу: ( ) ( 1) ( ) t t i i t i       (i = 1, 2, … , r). (9) Якщо умови (9) виконуються після t ітерацій, то наближенням розв’язку задач (1) або (2) є: 1 ,* t i i   ( ) X* = Xt+1Zt+1 (i = 1, 2, … , r). Тут, як і в (9), мається на увазі, що власні значення упорядковані за зростанням 0 < 1  2  …  r  … . Як відомо (див., наприклад [1]), ітераційний процес збігається лінійно, причому швидкість збіжності i визначається відношенням i /q+1, де q  розмір підпростору Et, що ітерується. Тому, чим більше значення q, тим за меншу кількість ітерацій буде досягнута точність наближень, але при цьому збільшується обсяг обчислень на кожній ітерації. З практики [1] рекомендується вибирати  82min  r,rq . Результатом роботи гібридного алгоритму ітерацій на підпросторі є:  обчислені власні значення λi, розташовані у кожному процесі в порядку зростання;  матриця власних векторів, відповідних обчисленим власним значенням (елементи цієї матриці розподілені між процесами відповідно до одномірної блоч- но-циклічної схеми, яка співпадає зі схемою розподілу елементів матриць A та B). Слід відзначити, що в підзадачах (3) та (5) беруть участь матриці вихідної задачі (1). Обсяг обчислень в кожній з цих підзадач на порядок або більше перевищує обсяг обчислень у інших підзадачах. Отже, ефективність гібридного алгоритму методу ітерацій на підпросторі визначається ефективним виконанням на гібридному комп’ютері підзадач (3) та (5). На ефективність гібридних алго- ритмів лінійної алгебри у значній мірі впливає розподіл матриць між ядрами CPU та графічними процесорами, а також виконання обмінів даними між ними. Розглянемо детально як вирішуються ці проблеми в гібридному плитковому ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЗАДАЧ НА ВЛАСНІ ЗНАЧЕННЯ … Теорія оптимальних рішень. 2016 89 алгоритмі розв’язування підзадачі (3) на основі LLT-розвинення (факторизація методом Холецького) для комп’ютерів з одним та декількома графічними про- цесорами [6, 7]. Гібридний плитковий алгоритм LLT-розвинення. Розв’язуємо систему лінійних рівнянь: ,Ax b (10) де матриця A – стрічкова додатно-означена, n – порядок матриці, m – напівши- рина стрічки матриці. Розв’язання системи (10) полягає в розв’язанні підзадач: трикутне розвинення матриці системи: TLLA  , (11) та розв’язання двох СЛАР з трикутними матрицями: bLy  , (12) yxLT  . (13) Розіб’ємо стрічкову матрицю A на вертикальні прямокутні плитки [6]. Оскільки матриця симетрична, то доцільно зберігати тільки нижній її трикутник, що дає можливість оптимізувати обсяг пам’яті, який необхідний для реалізації алгоритму, а також зменшити кількість виконуваних арифметичних операцій. Крім того, таке розбиття даних дає можливість більш ефективно використовувати кеші CPU та GPU, а також високоефективні функції cuBLAS для виконання матрично-векторних операцій. Іншою важливою особливістю плиткового розбиття даних є те, що на кожному кроці блочного алгоритму Холецького потрібно мати в пам’яті тільки wm / плиток, де w – ширина плитки, які будуть розташовані послідовно за плиткою з провідним блоком. Таким чином, така декомпозиція даних дає можливість на кожному кроці алгоритму копіювати в пам’ять GPU лише одну додаткову плитку. Введемо деякі позначення, які будуть потрібні для опису алгоритму трикутного розвинення (схематично показано на рисунку):  iPb – діагональний блок плитки з номером i ;  ,i jPu – підматриця плитки i , що починається з рядка j w ;  ,i jPs – квадратна підматриця плитки i , що починається з рядка .j w Гібридний плитковий алгоритм LLT-розвинення для гібридних комп’ютерів з одним GPU. При реалізації цього алгоритму використовуються три основні операції: 1) факторизація щільної симетричної додатно-означеної матриці. В даному алгоритмі ця операція буде використовуватися для факторизації діагонального блоку плитки iPb ; 2) розв’язування СЛАР з трикутною матрицею. Використовується для розв’язування рівняння 1,ii PuPbX  ; 3) обчислення добутку двох матриць. Використовується для оновлення плиток матриці системи, які розташовані за плиткою з провідним блоком: ,0 ,0 , ,( ) .T i j i j i j i jPu Pu Pu Ps    (14) О.М. ХІМІЧ, О.В. ПОПОВ, А.Ю. БАРАНОВ, О.В. ЧИСТЯКОВ 90 Теорія оптимальних рішень. 2016 РИСУНОК. Декомпозиція даних Для виконання перших двох операцій, на i -му кроці алгоритму, потрібно використовувати лише дані, які знаходяться в i -й плитці. Для операції добутку двох матриць, окрім i -ї плитки, також використовуються плитки, які розташо- вуються послідовно за i -ю плиткою. Отже, кількість плиток, які використову- ються на i -му кроці алгоритму дорівнює wm / . На кожному наступному кроці в пам’ять GPU потрібно копіювати одну додаткову плитку. Доцільно виконувати копіювання плитки, яка буде потрібна на наступному кроці, одночасно з виконанням операції добутку двох матриць. Таким чином, можна досягти більшої ефективності алгоритму. Для того, щоб на кожному кроці не виділяти додаткову пам’ять для наступної плитки, потрібно на початку роботи алгоритму виділити пам’ять для зберігання 1/ wm плитки. На кожно- му кроці wm / плиток будуть використовуватися для обчислень, а наступна плитка буде копіюватися у вільну ділянку пам’яті. Це дає можливість значно зменшити використання пам’яті GPU у порівнянні з алгоритмами, коли вся матриця зберігається на GPU. Програмну реалізацію гібридного алгоритму розіб’ємо на два етапи: на пер- шому (підготовчому) етапі виконується початкова ініціалізація, на другому – обчислюється трикутне розвинення матриці системи. Підготовчий етап: 1) ініціалізація cuBLAS; 2) створення двох екземплярів cudaStream_t: cudaCopyStream, cudaCalculateStream; 3) потік cudaCalculateStream використовується як основний потік cuBLAS; 4) виділення пам’яті для 1/ wm плитки на GPU. Вказівник на цю пам’ять gpuTilesMemory; 5) копіювання перших wm / плиток в пам’ять GPU. Варто зазначити, що доцільним є виділення однієї ділянки пам’яті для збе- реження 1w/m плиток в GPU, що дає можливість швидше виділити всю необхідну пам’ять. ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЗАДАЧ НА ВЛАСНІ ЗНАЧЕННЯ … Теорія оптимальних рішень. 2016 91 На другому етапі, для кожного 1,..., /i n w виконуємо наступні кроки алгоритму: 1) факторизація діагонального блоку i -ї плитки iPb . Результат записується в ;iPb 2) перетворення на GPU нижньої частини плитки ,1iPu за формулою 1 ,1 ,1 *( ) .i i iPu Pu Pb  Використовується функція cublasDtrsm; 3) асинхронне копіювання у потоці cudaCopyStream і-ї плитки в пам’ять CPU; 4) асинхронне копіювання плитки, котра буде потрібна на наступному кроці в gpuTilesMemory, використовуючи cudaCopyStream; 5) виконати цикл по j від 1 доки виконується нерівність [ ];j w len i  на кожній ітерації виконати перетворення (14), використовуючи функцію cublasDgemm; 6) синхронізація потоку cudaCopyStream та збереження i -ї плитки на CPU; 7) синхронізація основного потоку cuBLAS – cudaCalculateStream. Після виконання всіх кроків алгоритму отримаємо нижню трикутну матри- цю, для якої справджується формула (6) другого етапу. Реалізація гібридного плиткового алгоритму LLT-розвинення для гібридних комп’ютерів з декількома GPU. Нехай кількість доступних GPU для реалізації алгоритму дорівнює numGPU . В цьому випадку i -ту плитку матриці буде обробляти GPU з номером modnumGPUi (нумерація GPU з 0). Нові версії CUDA дають можливість використовувати один CPU для роботи з усіма доступними GPU. Оскільки основна частина обчислень виконується на GPU, то будемо використовувати один CPU потік. Як і в попередньому випадку, розіб’ємо реалізацію алгоритму на два етапи. На підготовчому етапі виконуються такі операції: 1) ініціалізація cuBLAS для кожного GPU; 2) створення екземплярів cudaStream_t для кожного GPU, а також їх запис в масиви: cudaCopyStreamArr[], cudaCalculateStreamArr[]; 3) встановлення основних потоків для доступних GPU; 4) виділення пам’яті для 1 numGPU n w   плиток у кожному GPU; 5) копіювання перших wm / плиток у пам’ять відповідних GPU. На другому етапі для кожного 1... /i n w продовжуємо виконувати такі кроки алгоритму: 1) виклик функції cudaSetDevice( numGPUimod ). Таким чином поточним GPU стає той, в якому зберігається і-та плитка; О.М. ХІМІЧ, О.В. ПОПОВ, А.Ю. БАРАНОВ, О.В. ЧИСТЯКОВ 92 Теорія оптимальних рішень. 2016 2) перетворення на GPU нижньої частини плитки 1,iPu за формулою 1 ,1 ,1 ( ) .i i iPu Pu Pb   Використовується функція cublasDtrsm; 3) асинхронне копіювання у потоці cudaCopyStreamArr[ modnumGPUi ] i -ї плитки в пам’ять CPU; 4) встановлення поточним GPU, в якому має зберігатися плитка, що буде потрібна на наступному кроці. Копіювання цієї плитки у пам’ять відповідного GPU, використовуючи cudaCopyStreamArr; 5) копіювання i -ї плитки в пам’ять всіх інших GPU; 6) виконання циклу по j від 1 доки виконується нерівність [ ]j w len i  , на кожній ітерації виконати перетворення (14), використовуючи функцію cublasDgemm. Перед викликом cublasDgemm потрібно встановити GPU з номером ( )modnumGPU,i j як поточний; 7) синхронізація потоків cudaCopyStreamArr та збереження i -ї плитки на CPU; 8) синхронізація основних потоків cuBLAS за допомогою cudaCalculateStreamArr. Після виконання всіх кроків алгоритму отримаємо нижню трикутну матри- цю, для якої справджується формула (6) другого етапу. Розв’язання трикутних систем. Кількість операцій при розв’язанні трикут- них систем (12), (13) виконується значно менше, ніж при трикутному розвиненні матриці системи. Ці підзадачі ефективно можна реалізувати на CPU, викори- стовуючи відповідні програми з бібліотеки Intel MKL [8]. Експериментальне дослідження ефективності гібридного алгоритму ітерацій на підпросторі. На основі запропонованого гібридного алгоритму ітерацій на підпросторі було створено програму для комп’ютера гібридної архітектури, використовуючи для розпаралелювання обчислень між ядрами CPU системи MPI, а для виконання обчислень на GPU – технологію CUDA. Проведено апробацію розробленого гібридного алгоритму на інтелекту- альному персональному суперкомп’ютері гібридної архітектури Інпарком_pg (1 обчислювальний вузол, 2 процесори Xeon 5606, 2 GPU Tesla K40) на різних задачах, наприклад, використовувалася узагальнена АПВЗ: ,Ax Bx  матриці A і B отримано при дискретизації методом кінцевих елементів задачі на власні значення для оператора Лапласа в прямокутнику, одна сторона якого закріплена [9]. В таблиці приведено порівняльні часові характеристики розв’язування трьох задач на власні значення для оператора Лапласа паралельним блочно-цик- лічним та гібридним алгоритмами ітерацій на підпросторі на Інпарком_pg при використанні різної кількості процесів (ядер) на CPU та процесорів GPU, а саме: задача 1 – n = 811 801, m = 901; задача 2 – n = 1 002 001, m = 1 001; задача 3 – n = 1 442 401, m = 1 201. Тут n – порядок матриці, m – на півширина стрічки. ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ЗАДАЧ НА ВЛАСНІ ЗНАЧЕННЯ … Теорія оптимальних рішень. 2016 93 ТАБЛИЦЯ. Порівняння часу (сек) розв’язування АПВЗ паралельним та гібридним алгоритмами ітерацій на підпросторі Задача Паралельний алгоритм Гібридний алгоритм 1 CPU 4 CPU 8 CPU 4CPU + 1 GPU 8 CPU + 2 GPU 1 1311,4 452,6 225,8 209,6 147,7 2 2420,8 1480,5 632,8 386,8 298,5 3 3224,1 1752,8 942,8 502,1 359,5 З таблиці ми бачимо, що час розв’язування задач за розробленим гібридним алгоритмом методу ітерацій на підпросторі значно менший у порівнянні з часом розв’язування цих задач за допомогою блочно-циклічного алгоритму. Зокрема, використовуючи один GPU було досягнуто прискорення в 6 – 8 раз у порівнянні з послідовною версією (1 CPU), а використовуючи 2 GPU отримано прискорення в 7 − 9 раз. При розв’язуванні задач гібридним алгоритмом з використанням одного GPU отримано прискорення в 1,25 раз у порівнянні з часом розв’я- зування паралельним блочно-циклічним алгоритмом на восьми процесах, а при використанні двох GPU – в 1,4 раз. Розроблений гібридний алгоритм добре масштабується та показує пропорційне зменшення часу розв’язування. Висновки. Запропоновано гібридний алгоритм методу ітерацій на підпро- сторі для стрічкових матриць, який забезпечує високу ефективність розпара- лелювання на GPU, враховує структуру стрічкової матриці, оптимізує викори- стання пам’яті GPU. Подальші дослідження доцільно направити на розробку алгоритму для гра- фічних прискорювачів архітектури Kepler [10] та CUDA 7.5, зокрема викори- стання можливості динамічного паралелізму, безпосереднього обміну даними між GPU без участі центрального процесора, а також забезпечити врахування архітектурних особливостей центрального процесора, використовуючи бібліо- теку обчислювальної математики Intel MKL. А.Н. Химич, А.В. Попов, А.Ю. Баранов, А.В. Чистяков ГИБРИДНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ НА СОБСТВЕННЫЕ ЗНАЧЕНИЯ ДЛЯ ЛЕНТОЧНЫХ МАТРИЦ Предложен алгоритм решения частичной обобщенной алгебраической проблемы собственных значений с ленточными симметричными матрицами на компьютерах гибридной архитектуры. Приведены результаты апробации алгоритма на персональном суперкомпью- тере гибридной архитектуры Инпарком_pg. A.N. Khimich, A.V. Popov, А.Y. Baranov, A.V. Chystyakov HYBRID ALGORITHM FOR SOLVING EIGENVALUES PROBLEM FOR BAND MATRICES This paper proposes an algorithm for solving partial generalized algebraic eigenvalue problem with band symmetric matrices on hybrid computers. The results of testing of the algorithm on a personal hybrid supercomputer Inparkom_pg are shown. О.М. ХІМІЧ, О.В. ПОПОВ, А.Ю. БАРАНОВ, О.В. ЧИСТЯКОВ 94 Теорія оптимальних рішень. 2016 1. Бате К., Вилсон Е.Л. Численные методы анализа и метод конечных элементов. – М.: Стройиздат, 1982. – 447 с. 2. Химич А.Н., Молчанов И.Н., Попов А.В., Чистякова Т.В., Яковлев М.Ф. Параллельные алгоритмы решения задач вычислительной математики. – Киев: Наук. думка, 2008. – 247 с. 3. Парлет Б. Симметричная проблема собственных значений. – М.: Мир, 1983. – 318 с. 4. Попов А.В., Химич А.Н. Параллельный алгоритм решения системы линейных алгебра- ических уравнений с ленточной симметричной матрицей // Компьютерная математика. – 2005. – № 2. – С. 52 − 59. 5. Уилкинсон Дж.Х., Райнш К. Справочник алгоритмов на языке Алгол. Линейная алгебра. – М.: Машиностроение, 1976. – 389 с. 6. Buttari A., Langou J., Kurzak J., Dongarra J. A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures. // Parallel Computing. – 2009. – Vol. 35, Issue 1. – P. 38. – 53. 7. Хіміч О.М., Баранов А.Ю. Гібридний алгоритм розв’язування лінійних систем зі стрічковими матрицями прямими методами // Компьютерная математика. – 2013. – Вып. 2. – С. 80 – 87. 8. Math Kernel Library (Intel (R) MKL) Documentation // https://software.intel.com/en-s/intel-mkl 9. Молчанов И.Н., Попов А.В, Химич А.Н. Алгоритм решения частичной проблемы собствен- ных значений для больших профильных матриц // Кибернетика и системный анализ. – 1992. – № 2. – С. 141 – 147. 10. Вычислительная архитектура NVIDIA Kepler высокопроизводительные вычисления NVIDIA // http://www.nvidia.com/object/nvidia-kepler.html Одержано 20.04.2016 http://www.irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?Z21ID=&I21DBN=UJRN&P21DBN=UJRN&S21STN=1&S21REF=10&S21FMT=JUU_all&C21COM=S&S21CNR=20&S21P01=0&S21P02=0&S21P03=IJ=&S21COLORTERMS=1&S21STR=%D0%9669780 https://software.intel.com/en-s/intel-mkl http://www.nvidia.com/object/nvidia-kepler.html

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

Репозитарії

Схожі ресурси