Про алгоритм методу найменших квадратів для розв’язування лінійних систем на гібридних комп’ютерах

Розглядається гібридний алгоритм методу найменших квадратів на основі сингулярного (SVD) розвинення матриці для розв’язування СЛАР з матрицями довільного рангу на багатоядерних комп’ютерах з графічними процесорами....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
Hauptverfasser:	Хіміч, О.М., Ніколаєвська, О.А., Чистякова, Т.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schriftenreihe:	Компьютерная математика
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/168425
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:	Про алгоритм методу найменших квадратів для розв’язування лінійних систем на гібридних комп’ютерах / О.М. Хіміч, О.А. Ніколаєвська, Т.В. Чистякова // Компьютерная математика. — 2016. — № 2. — С. 120-128. — Бібліогр.: 5 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-168425
record_format	dspace
spelling	irk-123456789-1684252020-05-02T01:28:21Z Про алгоритм методу найменших квадратів для розв’язування лінійних систем на гібридних комп’ютерах Хіміч, О.М. Ніколаєвська, О.А. Чистякова, Т.В. Розглядається гібридний алгоритм методу найменших квадратів на основі сингулярного (SVD) розвинення матриці для розв’язування СЛАР з матрицями довільного рангу на багатоядерних комп’ютерах з графічними процесорами. Рассматривается гибридный алгоритм метода наименьших квадратов на основе сингулярного (SVD) разложения матрицы для решения СЛАУ с матрицами произвольного ранга на многоядерных компьютерах с графическими процессорами. The hybrid algorithm of the least squares method based on SVD of a matrix for solving linear systems with matrices of arbitrary rank on multicore computers with GPUs is considered. 2016 Article Про алгоритм методу найменших квадратів для розв’язування лінійних систем на гібридних комп’ютерах / О.М. Хіміч, О.А. Ніколаєвська, Т.В. Чистякова // Компьютерная математика. — 2016. — № 2. — С. 120-128. — Бібліогр.: 5 назв. — укр. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/168425 519.6 uk Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Розглядається гібридний алгоритм методу найменших квадратів на основі сингулярного (SVD) розвинення матриці для розв’язування СЛАР з матрицями довільного рангу на багатоядерних комп’ютерах з графічними процесорами.
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/168425
citation_txt	Про алгоритм методу найменших квадратів для розв’язування лінійних систем на гібридних комп’ютерах / О.М. Хіміч, О.А. Ніколаєвська, Т.В. Чистякова // Компьютерная математика. — 2016. — № 2. — С. 120-128. — Бібліогр.: 5 назв. — укр.
series	Компьютерная математика
work_keys_str_mv	AT hímíčom proalgoritmmetodunajmenšihkvadratívdlârozvâzuvannâlíníjnihsistemnagíbridnihkompûterah AT níkolaêvsʹkaoa proalgoritmmetodunajmenšihkvadratívdlârozvâzuvannâlíníjnihsistemnagíbridnihkompûterah AT čistâkovatv proalgoritmmetodunajmenšihkvadratívdlârozvâzuvannâlíníjnihsistemnagíbridnihkompûterah
first_indexed	2025-07-15T03:12:39Z
last_indexed	2025-07-15T03:12:39Z
_version_	1837680988397764608
fulltext	120 Компьютерная математика. 2016, № 2 Розглядається гібридний алгоритм методу найменших квадратів на основі сингулярного (SVD) розви- нення матриці для розв’язування СЛАР з матрицями довільного рангу на багатоядерних комп’ю- терах з графічними процесорами.  О.М. Хіміч, О.А. Ніколаєвська, Т.В. Чистякова, 2016 УДК 519.6 О.М. ХІМІЧ, О.А. НІКОЛАЄВСЬКА, Т.В. ЧИСТЯКОВА ПРО АЛГОРИТМ МЕТОДУ НАЙМЕНШИХ КВАДРАТІВ ДЛЯ РОЗВ’ЯЗУВАННЯ ЛІНІЙНИХ СИСТЕМ НА ГІБРИДНИХ КОМП’ЮТЕРАХ Вступ. Математичне моделювання процесів та явищ в різних предметних областях часто зводиться до розв’язування систем лінійних алгебраїчних рівнянь (СЛАР) великих розмі- рів. На сьогоднішній день ця проблема вирі- шується використанням гібридних комп’юте- рів, які поєднують MIMD- і SIMD-архітек- тури, тобто реалізуються обчислення на ба- гатоядерних комп’ютерах (CPU) з приско- ренням на графічних процесорах (GPU) [1]. Проте величезний розрив між високою про- дуктивністю графічних процесорів і повіль- ними комунікаційними зв’язками між CPU і GPU, а також принциповими архітектурни- ми відмінностями цих обчислювальних при- строїв, значно ускладнює розробку ефектив- них гібридних алгоритмів. Тільки за умови правильного використання обчислювальних ресурсів можна створити ефективні гібридні алгоритми розв’язування СЛАР. Під ефек- тивним алгоритмом розв’язування задачі ро- зуміється алгоритм, який дозволяє отримати достовірний розв’язок з мінімальним вико- ристанням ресурсів комп’ютера − процес о- рів, пам’яті, часу. Як відомо, комп’ютерна модель задачі має завжди наближений щодо вихідної задачі характер або через похибку вихідних даних, або через похибку отримання (вводу) число- вих даних про задачу в комп’ютері [2]. Тому властивості лінійної системи, яку доводиться розв’язувати на комп’ютері, можуть відріз- нятися від властивостей математичної задачі. Виникає необхідність створення алгоритму розв’язування СЛАР з апріорі невизначени- ми властивостями та матрицями великих ро- змірів. ПРО АЛГОРИТМ МЕТОДУ НАЙМЕНШИХ КВАДРАТІВ ДЛЯ ... Компьютерная математика. 2016, № 2 121 В роботі розглядається алгоритм методу найменших квадратів на основі сингулярного (SVD) розвинення матриць для розв’язування СЛАР з матрицями довільного рангу на комп’ютерах гібридної архітектури. 1. Архітектурні особливості CPU і GPU, які впливають на ефективність гібридного алгоритму розв’язування СЛАР [3]. Комп’ютер MIMD-архітек- тури, який входить до складу гібридної архітектури, складається з обчислюваль- них вузлів, кожен з яких може мати декілька багатоядерних процесорів та свою локальну пам’ять, що розподіляється між цими процесорами. На кожному ядрі процесора виконується один потік послідовних інструкцій. Кожен процесор має доступ тільки до локальної пам’яті свого вузла. Обчислювальні вузли об’єд- нуються між собою деяким комунікаційним середовищем, тому міжпроцесорні операції за тривалістю виконання значно перевершують арифметичні операції. Отже, необхідно передбачити найбільш ефективну топологію міжпроцесорних зв’язків та рівномірне завантаження процесорів. Графічний процесор влаштований принципово інакше. Множина великої кількості потоків команд виконується одночасно, забезпечуючи масовий парале- лізм обчислень та їх високу швидкодію на GPU. Причому ніяких накладних вит- рат у графічному процесорі немає. Використати обчислювальні можливості GPU у повній мірі можна лише в тому випадку, коли задача розпаралелюється на сот- ні виконуючих потоків, тобто коли одна і та ж послідовність математичних опе- рацій застосовується до великого обсягу даних. Наприклад, виконання матрич- но-матрично та матрично-векторних операції доцільно виконувати на GPU. GPU відрізняється від CPU також за принципами доступу до пам’яті. На GPU є 6 видів пам’яті, кожна з яких має своє призначення. Доцільно враховува- ти призначення кожного виду пам’яті при здійсненні комунікаційних зв’язків між CPU і GPU, які є надто повільними у порівнянні з виконанням обчислень. Виникає необхідність розподілу задачі на окремі підзадачі з метою визна- чення: пріоритетів підзадач, на CPU чи GPU їх краще реалізовувати за часом виконання, які підзадачі можна виконати паралельно, в якій послідовності їх треба виконувати тощо. 2. Постановка задачі. Розглянемо задачу розв’язування СЛАР з виродже- ною квадратною або прямокутною матрицею у загальному випадку довільного рангу за допомогою гібридного паралельного алгоритму методу найменших квадратів на основі SVD розвинення матриці [2]. При введенні несумісної у загальному випадку СЛАР з точно заданими вихідними даними (математична модель з точно заданими вихідними даними): ,Ax b , ,m n n mA R x R b R   (1) в комп’ютері отримуємо систему з наближеними даними (машинна модель з наближеними даними): bxА  , ,ААА  bbb  . (2) Будемо вважати, що для похибок елементів матриці та правої частини вико- нуються наступні співвідношення: , .A bA A b b      О.М. ХІМІЧ, О.А. НІКОЛАЄВСЬКА, Т.В. ЧИСТЯКОВА Компьютерная математика. 2016, № 2122 Тут і в подальшому, якщо не обумовлено додатково, використовуються евклідова векторна та підпорядкована їй спектральна матрична норми. Властивості машинної моделі задачі можуть відрізнятися від властивостей вихідної задачі, оскільки елементи матриці та правих частин в комп’ютері ма- ють наближений характер. Тобто задача, яку необхідно розв’язати в комп’ютері, – це задача з апріорі невідомими властивостями, отже необхідно спочатку дослі- дити її властивості. Фундаментальну роль при дослідженні задачі найменших квадратів відіграє визначення повноти рангу в межах машинної точності та пов- ноти рангу в межах завдання вихідних даних, а також визначення ефективного рангу матриці (  -рангу). Комп’ютерний алгоритм дослідження повноти рангу зводиться до перевірки двох співвідношень: 11.0 1.0, ( )h A   (3) ( ) 1,Ah A  (4) де  AAAh )( – число обумовленості матриці .A Перша умова (3), яка виконується в арифметиці з плаваючою комою, озна- чає, що матриця має повний ранг у межах машинної точності, а друга (4) – що вона є повного рангу також у межах точності задання вихідних даних. Таку машинну задачу слід розглядати як коректно поставлену в межах точ- ності задання вихідних даних. Ефективний ранг матриці визначає номер стійкої проекції нормального псевдорозв’язку задачі найменших квадратів з наближеними вихідними даними. Ця проекція апроксимує або нормальний псевдорозв’язок або його проекцію. Отже, для знаходження  -рангу необхідно знайти величину r, яка дорівнює найбільшому значенню i, для якого виконується нерівність: 1, i    0, 1,2...,i i   де i – сингулярні числа матриці А. 3. Алгоритм методу найменших квадратів на основі сингулярного роз- винення матриці. В загальному випадку задача розв’язування СЛАР з матри- цею довільного рангу є некоректною, а система в багатьох випадках – несуміс- ною. Для таких СЛАР можна отримати розв’язок методом найменших квадратів (псевдорозв’язок), який для сумісної і коректної задачі збігається з класичним розв’язком [2]: A = UV T, (5) яке виконується за допомогою послідовності двосторонніх ортогональних пере- творень Хаусхолдера та QR-алгоритма з неявним зсувом. Узагальнений розв’язок отримується за формулами: # #( ), ,Tx V c c U b   (6) де Σ# – псевдообернена матриця сингулярних чисел. ПРО АЛГОРИТМ МЕТОДУ НАЙМЕНШИХ КВАДРАТІВ ДЛЯ ... Компьютерная математика. 2016, № 2 123 При обчисленні за допомогою сингулярного розвинення (5) псевдорозв’язку (6) СЛАР з прямокутною матрицею довільного рангу розміру m×n (m ≥ n) можна виділити п’ять підзадач: 1) приведення вихідної матриці до верхньої дводіагональної форми        0 )0( )1( J A n , де (0)J – квадратна верхня дводіагональна матриця порядку n, в якій відмінні від нуля лише елементи (0) (0) , , 1, ;k k k kj j  2) сингулярне розвинення верхньої дводіагональної матриці (0) ,J тобто приведення J (0) до діагональної матриці ; 3) формування матриці правих сингулярних векторів V; 4) формування матриці (вектора) c з (6); 5) обчислення псевдорозв’язку (6). Для приведення прямокутної матриці A(0) розміру m1×n1 (m1 = max{m, n}, n1 = min{m, n}, A(0) ≡ A, якщо m ≥ n, або A(0) ≡ AT, якщо m < n), до верхньої дво- діагональної форми можна використати алгоритм Хаусхолдера. При цьому не- обхідно виконати 1 1n  двосторонніх елементарних перетворень відображення: A(i) = P(i)A(i-1)Q(i) (i = 1, 2,..., n11), (7) де ортогональні матриці P(i) = I + siuiui T, Q(i) = I + tivivi T, а вектори ui, vi та множ- ники si, ti визначаються так, щоб для кожного i = 1, 2,..., 1 1n  виконувались умови: siui Tui = tivi Tvi = 2, (8) 0)()(  i j,k i k,j aa (k = i+1,…, m1; j = i+2,…, n1). (9) Двосторонні перетворення (7) з умовами (8), (9) можна записати наступним чином: A(i) = A(i1) + ui.yi T + zivi T, (i = 1, 2,…, n1), (10) де  Ti i,m i i,ii i i,ii aadau )1()1( 1 )1( ,,,,0,,0      , vi = gi – fi+1ei+1, yi = wi + civi, zi = ti xi – ciui, )1(1  iT i T i ii T i Aew sd g , wi T = siui TA(i1), xi = A(i1)vi, i i i,ii ad )(sign )1(  , iiii gf )(sign 1,1   (11) ci = 0,5tiwi Tvi,   12)1(   iads i- i,iii ,   12 11    ii,iii gft  ,     m ij i i,ja 2)1(2i ,  22 , 1 , n i i j j i g      ei – одиничний орт. Таким чином, на кожному кроці (для кожного i) модифікується розташована в правому нижньому кутку підматриця розміру (m i + 1) × (n  i + 1), за вико- О.М. ХІМІЧ, О.А. НІКОЛАЄВСЬКА, Т.В. ЧИСТЯКОВА Компьютерная математика. 2016, № 2124 нанням умов (8), (9), а елементи )(i i,ii ad  та )( 11 i i,ii af   є відповідно діагональним та позадіагональним елементами дводіагональної матриці (0).J Для сингулярного розвинення верхньої дводіагональної матриці J(0) за син- гулярними числами використовується QR-алгоритм з неявним зсувом. Цей алго- ритм полягає у побудові послідовності верхніх дводіагональних матриць J(0), J(1), …, J(N ), …, які збігаються до діагональної матриці . Перехід від J(k–1) до J(k) виконується за допомогою серії двосторонніх плоских обертань Гівенса: J (k) = S(k)TJ(k  1)T (k), (12) де )()( 3 )( 2 )( k n kkk SSSS  , )()( 3 )( 2 )( k n kkk TTTT  , а )()( , k j k j TS – елементарні матриці плоских обертань. В результаті отримуємо сингулярне розвинення дводіаго- нальної матриці: THGJ  ~)0( ,  NJ~ , (13) G = S(1)S(2)…S(N ), H = T(1)T(2)…T(N ). (14) Формування матриці правих (або лівих) сингулярних векторів проводиться шляхом накопичення елементарних перетворень відображення: Q = Q(1)Q(2)··· Q(n1) або P = P(1)P(2)··· P(n1) (15) та обертань (14). Тоді наближеними правими сингулярними векторами вихідної матриці є стовпчики матриці V = QH, а лівими – стовпчики матриці U = PG. Аналогічним чином проводиться формування матриці (вектора) c з (4) – спочатку у відповідності з формулами: b(i) = P(i)b(i1) (m ≥ n) або b(i) = Q(i)b(i1) (m < n), (16) i = 1, 2, …, n11, формується b(n1) або b(m1), а потім обчислюється: c = GTb(n1) або c = HTb(m1). (17) Одночасно з обчисленням матриці J(0) за формулою (14) формується прямо- кутна матриця (вектор) b(n  1) (або b(m  1), якщо m < n). Формулу (16) для i = 1, 2, …, min(m, n) 1 можна записати наступним чином: b(i) = b(i1) + uihi T, hi T = siui T b(i1) (m ≥ n) (18) або b(i) = b(i1) + vihi T, hi T = tivi T b(i1) (m < n). (19) Тобто, для кожного i модифікується нижня підматриця розміру (mi+1)×q. Формування матриці елементарних перетворень відображень Q з (15) можна виконати так: Q(i) = Q(k)Q(i1) ≡ Q(i1) + vkxk T (i = 1, 2,…, n1), (20) де Q(0) ≡ I, Q ≡ Q(n1),   k T ikk vQtx 1 ,   1 1,1   kkkk vft (21) вектор відображення vk визначено в (11), )0( 1,1   kkk jf – наддіагональний елемент дводіагональної матриці J(0) (k = ni). Формування матриці елементарних перетворень відображення P з (15), яка обчислюється при m < n, проводиться аналогічно. ПРО АЛГОРИТМ МЕТОДУ НАЙМЕНШИХ КВАДРАТІВ ДЛЯ ... Компьютерная математика. 2016, № 2 125 4. Гібридний паралельний алгоритм Хаусхолдера зведення прямокутної матриці до верхньої дводіагональної форми на комп’ютерній архітектурі з декількома CPU та GPU. При реалізації гібридного паралельного алгоритму Хаусхолдера для зведення прямокутної матриці A(0) розміру m×n до верхньої дводіагональної форми A(n  1) застосовується стрічково-циклічний розподіл матриці СЛАР між процесами CPU, за яким процесу з логічним номером 1k послідовно розподіляються елементи рядків з номерами ...,2,, pkpkk  , де pk ...,,2,1 , p – кількість процесів, що використовується. Розпаралелювання на CPU виконується за допомогою MPI-функцій. При такому розташуванні матриці на процесах простій процесорів (ядер) CPU буде мінімальний, адже обчислення в кожному з них відбуватимуться майже до кінця модифікації матриці . Отже, такий підхід забезпечить рівномірне завантаження (балансу- вання) процесів. Зрозуміло, що необхідно передбачити виконання обчислень на процесах таким чином, щоб наявність інформаційних зв’язків (комунікацій- них взаємодій) між ними була мінімальною. 4.1. Алгоритм Хаусхолдера на гібридних комп’ютерах з декількома CPU та GPU складається з виконання для i = 1, 2,…, n1 послідовності таких підзадач: 1) для знаходження значення φ i та вектора wi з (11) дані пересилаються з CPU на GPU і кожним процесом обчислюються масиви останніх n i+1 та q еле- ментів векторів часткових сум добутків транспонованого i-го вектор-стовпчика матриці A(i  1) на прямокутні матриці (відповідно) A(i – 1) та b(i  1), елементи яких розподілені по процесах за стрічково-циклічнію схемою; 2) мультизбірка реалізується провідним процесом на CPU (в якому розта- шовані i-ті рядки прямокутних матриць) векторів добутків транспонованого i-го вектор-стопчика матриці A(i – 1) на прямокутні матриці A(i  1) та b(i  1) з обчисле- них кожним процесом векторів часткових сум; 3) за допомогою операції мультирозсилки масив елементів ( 1) ( 1) 1, , ,i i i,i i,ia a    ( 1), i i,na  i-го рядка матриці, останні n i + 1 та q елементів векторів добутків тра- нспонованого i-го вектор-стовпчика матриці A(i  1) на прямокутні матриці A(i  1) та b(i  1) розсилаються всім процесам для обчислення на відповідних GPU; 4) одночасно всіма процесами обчислюються значення φ i та )(i i,ii ad  з (11), формується лівий вектор відображення ui та після цього обчислюється значення si з (11), а потім формуються останні n i елементів векторів wi та gi у відпо- відності з (11) та вектор hi при m ≥ n; 5) одночасно всіма процесами обчислюються значення ψi та )( 11 i i,ii af   з (11), формується правий вектор відображення vi, а після цього обчислюється значення ti та ci і потім формуються останні n i елементів вектора yi; 6) кожним процесом у відповідності зі стрічково-циклічною схемою розпо- ділення прямокутних матриць та з формулами (11) обчислюються останні m i елементів векторів xi та zi, а також вектор hi з (19) при m < n; О.М. ХІМІЧ, О.А. НІКОЛАЄВСЬКА, Т.В. ЧИСТЯКОВА Компьютерная математика. 2016, № 2126 7) кожним процесом, у відповідності зі стрічково-циклічною схемою роз- поділення прямокутних матриць, виконується модифікація (10) розташованої в правому нижньому кутку підматриці розміру (m i) × (n i) матриці A(i  1), а також модифікація (18) або (19) нижньої підматриці розміру (n i + 1) × q матриці b(i  1). Після виконання всіх цих операцій на GPU результати обчислень переси- лаються на CPU у провідний процес і для всіх i = 1, 2,…, n  1 усім процесам має бути розісланий елемент )1( n n,na . Таким чином, в результаті виконання всіх операцій алгоритму кожним про- цесом будуть сформовані два n-мірних масиви діагональних та наддіагональних елементів дводіагональної матриці J(0). В даному алгоритмі реалізація обчислень на GPU здійснюється за допомо- гою технології CUDA. Через те, що на гібридних комп’ютерах дуже повільні зв’язки між CPU та GPU, матриці та вектори в алгоритмі розподілені таким чи- ном, щоб за один раз переслати всі необхідні масиви на глобальну пам’ять GPU, виконати з ними необхідні матрично-векторні операції, розпаралелюючи на GPU, і отримані результати переслати на CPU. Оскільки на GPU обчислення розпаралелюються на дуже велику кількість потоків, це дає можливість ефекти- вно виконати матрично-векторні операції з великою кількістю даних, забезпе- чуючи при цьому високу швидкодію. Крім того, швидкодію операцій можна пі- двищити застосовуючи відповідні функції бібліотеки CUBLAS [4]. Пересилка блоків матриць між CPU виконується за допомогою MPI-функцій. Матрично-векторні операції виконуються на GPU при викорис- танні відповідних функцій бібліотеки CUBLAS. 4.2. Паралельний QR-алгоритм. Всі діагональні та наддіагональні елемен- ти верхньої дводіагональної матриці J(0) зберігаються в кожному процесі. Також в кожному процесі зберігаються всі обчислені наближені сингулярні числа. Оскільки окреме (елементарне) плоске обертання, яке використовується при обчисленні матриць сингулярних векторів (14), складається з попарних перетво- рень лише двох елементів (належать стовпчикам, що модифікуються) кожного рядка, а параметри плоского обертання обчислюються кожним процесом, то елементи матриці сингулярних векторів, що формується, та матриці cT з (17) ро- зподіляються за стрічково-циклічною схемою. В цьому випадку потреби в обмінах даними між процесами при формуванні цих матриць немає. Для виконання паралельного QR-алгоритму на кожній ітерації s = 1, 2, … виконуються такі операції:  одночасно кожним процесом, без обмінів даними між ними, обчислюєть- ся значення зрушення ks, послідовно для j = 1, 2, …, ns < n формуються матриці плоских обертань )()( , s j s j TS та модифікується дводіагональна матриця J(s  1) у відповідності з (12); ПРО АЛГОРИТМ МЕТОДУ НАЙМЕНШИХ КВАДРАТІВ ДЛЯ ... Компьютерная математика. 2016, № 2 127  одночасно кожним процесом, без обмінів даними, у відповідності зі схе- мою розподілення модифікуються елементи матриці сингулярних векторів, що формується, та матриці cT з (17);  одночасно кожним процесом, без обмінів даними, перевіряється умова досягнення заданої точності обчислення чергового наближеного сингулярного значення. Після цього результати обчислень збираються в одному процесі на CPU. 5. Експериментальне дослідження гібридного алгоритму. Проведено до- слідження ефективності гібридного алгоритму для розв’язування СЛАР з виродженими матрицями різного порядку та при використанні різної кількості CPU та GPU на комп’ютері Інпарком_g гібридної архітектури [5] (рисунок). На графіку видно, що розроблений гібридний алгоритм добре масштабова- ний, тобто зі збільшенням кількості процесів прискорення обчислень зростає, для великих порядків матриці найкраще прискорення досягається при викорис- танні 8 процесів. У перспективі можливе покращення алгоритму завдяки дина- мічному розпаралелюванню обчислень між процесорами GPU, яке дає можли- вість пересилати дані безпосередньо від одного GPU до іншого GPU, оминаючи CPU. Така можливість реалізується при використанні версій CUDA 5 та вище на гібридних комп’ютерах з графічними процесорами на базі архітектури NVIDIA Kepler. РИСУНОК. Залежність прискорення від кількості процесів та порядку матриці розв’язування задачі гібридним алгоритмом SVD на Інпарком_g О.М. ХІМІЧ, О.А. НІКОЛАЄВСЬКА, Т.В. ЧИСТЯКОВА Компьютерная математика. 2016, № 2128 А.Н. Химич, Е.А. Николаевская, Т.В. Чистякова ОБ АЛГОРИТМЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ ДЛЯ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ НА ГИБРИДНЫХ КОМПЬЮТЕРАХ Рассматривается гибридный алгоритм метода наименьших квадратов на основе сингулярного (SVD) разложения матрицы для решения СЛАУ с матрицами произвольного ранга на много- ядерных компьютерах с графическими процессорами. A.N. Khimich, E.A. Nikolaevskaya, T.V. Chistyakova ABOUT THE METHOD OF LEAST SQUARES ALGORITHM FOR SOLVING LINEAR SYSTEMS ON HYBRID COMPUTERS The hybrid algorithm of the least squares method based on SVD of a matrix for solving linear systems with matrices of arbitrary rank on multicore computers with GPUs is considered. 1. Боресков А.В., Харламов А.А. Основы работы с технологией CUDA.  М.: Пресс, 2010. С. 232. 2. Молчанов И.Н. Машинные методы решения прикладных задач. Алгебра, приближение функций. Київ: Наук. думка, 1987. 288 с. 3. Химич А.Н., Молчанов И.Н., Попов А.В. и др. Параллельные алгоритмы решения задач вычислительной математики. Київ: Наук. думка, 2008. 248 c. 4. CUBLAS: http://www.nvidia.com.ua/object/tesla-gpu-accelerated-libraries-cublas-ru.html 5. Молчанов И.М., Мова В.И. Интеллектуальные параллельные компьютеры на графиче- ских процессорах для решения научно-технических задач. Праці Міжнародної мо- лодіжної математичної школи «Питання оптимізації обчислень (ПОО-XXXVII). Київ: Інститут кібернетики імені В.М. Глушкова НАН України, 2011. С. 121 – 122. Одержано 11.10.2016 Про авторів: Хіміч Олександр Миколайович, доктор фізико-математичних наук, профессор, член-кор. НАН України, завідуючий відділом Інституту кібернетики імені В.М. Глушкова НАН України, Е-mail: khimich505@gmail.com Ніколаєвська Олена Анатоліївна, кандидат фізико-математичних наук, науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України, Е-mail: elena_nea@ukr.net Чистякова Тамара Василівна, кандидат фізико-математичних наук, старший науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України. Е-mail: tamara.chistjakova@gmail.com

Про алгоритм методу найменших квадратів для розв’язування лінійних систем на гібридних комп’ютерах

Institution

Ähnliche Einträge