Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури
У роботі пропонуються модифікований метод та алгоритм розв’язування систем нелінійних рівнянь (СНР) для комп’ютерів MIMD-архітектури. Наведені часи розв’язування СНР різних порядків, визначені коефіцієнти прискорення та ефективності використання запропонованого методу. В работе предлагаются модифици...
Gespeichert in:
| Veröffentlicht in: | Математичні машини і системи |
|---|---|
| Datum: | 2014 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84444 |
| 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: | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури / М.Ф. Яковлєв, А.Н. Нестеренко, В.М. Бруснікін // Математичні машини і системи. — 2014. — № 4. — 12-17. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860245698153283584 |
|---|---|
| author | Яковлєв, М.Ф. Нестеренко, А.Н. Бруснікін, В.М. |
| author_facet | Яковлєв, М.Ф. Нестеренко, А.Н. Бруснікін, В.М. |
| citation_txt | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури / М.Ф. Яковлєв, А.Н. Нестеренко, В.М. Бруснікін // Математичні машини і системи. — 2014. — № 4. — 12-17. — Бібліогр.: 4 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | У роботі пропонуються модифікований метод та алгоритм розв’язування систем нелінійних рівнянь (СНР) для комп’ютерів MIMD-архітектури. Наведені часи розв’язування СНР різних порядків, визначені коефіцієнти прискорення та ефективності використання запропонованого методу.
В работе предлагаются модифицированный метод и алгоритм решения систем нелинейных уравнений (СНУ) для компьютеров MIMD-архитектуры. Приведены времена решения СНУ разных порядков, определены коэффициенты ускорения и эффективности использования предложенного метода.
The paper deals both with modified method and algorithm intended for the solving of non-linear systems (NLS) for MIMD-architecture computers. Times required for the solving of NLSs of various orders are given; acceleration and efficiency coefficients for the proposed method are determined, as well.
|
| first_indexed | 2025-12-07T18:35:48Z |
| format | Article |
| fulltext |
12 © Яковлєв М.Ф., Нестеренко А.Н., Бруснікін В.М., 2014
ISSN 1028-9763. Математичні машини і системи, 2014, № 4
УДК 519.6
М.Ф. ЯКОВЛЄВ*, А.Н. НЕСТЕРЕНКО**, В.М. БРУСНІКІН*
ПРОБЛЕМИ ЕФЕКТИВНОГО РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ
РІВНЯНЬ НА БАГАТОПРОЦЕСОРНИХ КОМП’ЮТЕРАХ MIMD-АРХІТЕКТУРИ
*
Інститут проблем математичних машин і систем НАН України, Київ, Україна
**
Інститут кібернетики імені В.М. Глушкова НАН України, Київ, Україна
Анотація. У роботі пропонуються модифікований метод та алгоритм розв’язування систем не-
лінійних рівнянь (СНР) для комп’ютерів MIMD-архітектури. Наведені часи розв’язування СНР різ-
них порядків, визначені коефіцієнти прискорення та ефективності використання запропонованого
методу.
Ключові слова: комп’ютери MIMD-архітектури, системи нелінійних рівнянь, модифікований іте-
раційний метод, ефективність розпаралелювання.
Аннотация. В работе предлагаются модифицированный метод и алгоритм решения систем не-
линейных уравнений (СНУ) для компьютеров MIMD-архитектуры. Приведены времена решения
СНУ разных порядков, определены коэффициенты ускорения и эффективности использования
предложенного метода.
Ключевые слова: компьютеры MIMD-архитектуры, системы нелинейных уравнений, модифици-
рованный итерационный метод, эффективность распараллеливания.
Abstract. The paper deals both with modified method and algorithm intended for the solving of non-linear
systems (NLS) for MIMD-architecture computers. Times required for the solving of NLSs of various
orders are given; acceleration and efficiency coefficients for the proposed method are determined, as well.
Keywords: MIMD-architecture computers, system of non-linear equations, modified iterative method,
parallelization efficiency.
1. Вступ
На практиці досить часто доводиться розв’язувати рівняння з частинними похідними. Для
цього методом скінченних різниць або скінченних елементів їх зводять до систем неліній-
них рівнянь зі стрічковою матрицею Якобі (частіш за все блочно тридіагональною або
блочно п’ятидіагональною). Отже, сьогодні виникає потреба у створенні методів, націле-
них на швидке та ефективне розв’язування таких систем.
Основні алгоритми розв’язування систем нелінійних рівнянь (СНР) [1, 2] вимагають
обчислення наближеного значення матриці Якобі системи та розв’язування системи ліній-
них алгебраїчних рівнянь (СЛАР). На розв’язування СЛАР або знаходження оберненої ма-
триці витрачається значний час. Цей час можна суттєво скоротити, якщо при обчисленні
елементів матриці Якобі і при розв’язуванні СЛАР або знаходженні оберненої матриці ви-
конання всіх арифметичних операцій розпаралелити на вибрану кількість процесів. Розпа-
ралелювання всіх обчислень реалізуються на багатоядерному комп'ютері MIMD-
архітектури. Кількість процесів для обчислень обирається автоматично, виходячи з вимог
рівномірної завантаженості процесорів, оптимізації та синхронізації кількості обмінів ін-
формацією між процесорами [3].
У цій роботі пропонується чисельний модифікований алгоритм, спрямований на
скорочення часу розв’язування СЛАР.
2. Постановка задач з наближеними вихідними даними для систем нелінійних рів-
нянь
Нехай дана система n нелінійних рівнянь:
ISSN 1028-9763. Математичні машини і системи, 2014, № 4 13
( ) 0=xf , (1)
де ( ) ( ) ( ) ( )( ) Tn xfxfxfxf ,,, 21
…= − n -вимірна вектор-функція, а ( ) Tnxxxx ,,, 21
…= −
n -вимірний вектор, причому ( ) 0f x = є деяким наближенням до точної системи нелі-
нійних рівнянь ( ) 0xϕ = , і для цих вектор-функцій виконується нерівність
( ) ( ) δ≤ϕ− uuf (2)
на будь-якому n -вимірному векторі u . Для розв’язування задачі (1) задається початкове
наближення 0x та визначається область ( ){ }nibxaD iii ,,2,1 …=≤≤= , в якій шука-
ється розв’язок, і необхідна точність ε отримання наближення до розв’язку системи. При
цьому початкове наближення належить визначеній області Dx ∈0 . Верхнім індексом у
формулах позначені номери компонент векторів, а нижнім − номери ітерацій.
Якщо
n
ji
j
i
x
f
H
1, =
∂
∂= − матриця Якобі системи (1) (або деяке наближення до неї),
то ітераційний процес методу Ньютона знаходження розв’язку при заданому початковому
наближенні записується у вигляді
( )kkk xfwH −= , (3)
де kkk xxw −= +1 − поправка, k =0, 1, ... – номер ітерації і kkk wxx +=+1 . Як видно з фо-
рмули (3), на кожній ітерації необхідно розв’язувати систему лінійних алгебраїчних рів-
нянь, обчислюючи значення вектор-функції і матрицю Якобі.
У випадку стрічкової матриці Якобі матриця представляється у блочному вигляді:
=
− pppp HH
HH
HHH
HH
xH
,1
3331
232221
1211
0
00
0
00
)(
…
⋱…
⋯
…
…
.
Відповідно до представлення матриці Якобі у блочному вигляді представляються
вектор правої частини та вектор невідомих:
=
pf
f
f
xf
⋮
2
1
)( ,
=
p
k
k
k
k
x
x
x
x
⋮
2
1
.
3. Модифікований метод Ньютона
Модифікований метод Ньютона можна записати у такому вигляді:
( ) ( ) 0)( 2
1
212111
1
11 =−++− −+ kkkkk xxHxfxxH ,
14 ISSN 1028-9763. Математичні машини і системи, 2014, № 4
( ) ( ) ( ) 0)( 3
1
3231
1
121222
1
22 =−+−++− −−+ kkkkkkk xxHxxHxfxxH ,
. . . . . . . . . . . . . (4)
( ) ( ) ( ) 0
1
11 =−++− ∑
≠
=
−+
p
ij
j
j
k
j
k
ij
k
ii
k
i
k
ii xxHxfxxH .
. . . . . . . . . . . . .
( ) ( ) ( ) 01
1
1,1
1 =−++− −
−
−−
+
p
k
p
k
pp
k
pp
k
p
k
pp xxHxfxxH
При цьому наступне наближення обчислюється за формулами:
( )( ))( 2
1
212111111
1 −
−
+ −+−= kkkkk xxHxfHxx ,
( ) ( )( ))( 3
1
3231
1
121212222
1 −−
−
+ −+−+−= kkkkkkk xxHxxHxfHxx ,
. . . . . . . . . . . . . (5)
( ) ( )
−+−= ∑
≠
=
−
−
+
p
ij
j
j
k
j
k
ij
k
iiii
k
i
k xxHxfHxx
1
1
1
1 ,
. . . . . . . . . . . . .
( ) ( )( )1
1
1,11
1
−
−
−−−
+ −+−= p
k
p
k
pp
k
pppp
k
p
k xxHxfHxx .
Якщо позначити в загальному вигляді матрицю G:
[ ]2,1
,011 HG = ,
[ ]1,1, ,0, +−= iiiiii HHG , i=2,3,…., p-1,
[ ]0,1, −= pppp HG ,
то для збіжності ітераційного процесу, тобто для того, щоб поправка прямувала до нуля,
необхідно виконання нерівності
1max
1
1
<
−
≤≤
iiii
pi
GH .
Паралельний алгоритм наведеного методу на MIMD-комп’ютері з використанням p
процесів реалізується за такою обчислюваною схемою:
• Проводиться автоматичний розподіл обчислення значень компонент вектор-
функції системи нелінійних рівнянь на p блоків, який виконується таким чином: обчислю-
ється відношення q
p
n =
, де a – ціла частина числа a , n – порядок системи рівнянь.
Обчислюється величина ( ) nqps −+= 1 ; тоді останні s процесів будуть обробляти блоки
по m q= рівнянь, а перші p s− процесів – блоки по ( )1m q= + -ому рівнянню.
• У кожному з p процесорних елементів обчислюються по m компонент вектор-
функції ( )0xf .
ISSN 1028-9763. Математичні машини і системи, 2014, № 4 15
• У кожному з p процесорних елементів обчислюється відповідний діагональний
блок матриці Якобі ( )0xH ii розміру mm× .
• Для модифікованого методу Ньютона замість СЛАР, заданих формулою (3),
розв’язується СЛАР, задана формулою (4), відносно похибки kkk xxw −= +1 з викорис-
танням, наприклад, паралельного варіанта методу Гауса.
• Обчислюються відповідні компоненти наступного наближення до розв’язку 1+kx
за формулами (5). Потім у кожному з p процесів збираються отримані частини компонент
вектора наближеного розв’язку, обчислюються компоненти вектор-функції ( )1+kxf і пере-
віряються умови закінчення ітераційного процесу.
Обчислення похибки отриманого наближення розв’язку системи з наближеними да-
ними відносно точного розв’язку системи з точними даними проводиться за формулою [4]
δ+ε≤− −1
kk Hxx ,
де x − точний розв’язок точної системи рівнянь. Зауважимо, що у кожному з p процесів
обчислюються відповідні блоки матриці Якобі kH та обернені до них 1−
kH .
4. Порівняння звичайного та модифікованого методів Ньютона
Нижче наведено порівняння часів розв’язку системи нелінійних рівнянь зі стрічковою мат-
рицею Якобі звичайним та модифікованим методами на багатоядерних комп’ютерах з ви-
користанням p процесів.
У наведеній нижче таблиці представлені часи розв’язування системи нелінійних рі-
внянь:
( ) ,0,01223 1 ==+−− + ixxx iii
( ) ,2,,2,1,01223 11 −==+−−− −+ nixxxx iiii
…
( ) ,1,0123 1 −==+−− − nixxx iii
Починаючи з початкового наближення, 1−=ix в області { },iii bxaD ≤≤=
1,,2,1,0 −= ni … , при n = 4000 та n = 6000, it=100, eps=1×10-10, del=1×10-10,
ia = -1000,
ib =1000. У стовпчику під номером «1» подані часи розв’язування нелінійної системи мо-
дифікованим методом Ньютона, а у стовпчику під номером «2» − звичайним методом.
Таблиця 1. Часи розв’язування СНР
n = 4000 n = 6000
np 1 2 1 2
1 395,38 385,69 1220,25 1223,67
2 185,40 277,19 603,58 828,00
3 55,11 212,42 204,06 619,52
4 20,80 178,45 76,03 533,95
5 8,56 159,04 36,28 468,79
6 4,89 144,20 19,46 420,18
7 3,12 135,39 11,42 392,36
8 2,08 127,34 7,02 367,75
16 ISSN 1028-9763. Математичні машини і системи, 2014, № 4
З табл. 1 видно, що використання модифікованого методу Ньютона суттєво скоро-
чує час розв’язування задачі. Коефіцієнти прискорення (рис. 1) та ефективності (рис. 2) для
даної СНР 6000 порядку представлені на наступних діаграмах.
0
20
40
60
80
100
120
140
160
180
200
1 2 3 4 5 6 7 8
Кількість процесів
К
о
е
ф
іц
іє
н
т
п
р
и
с
к
о
р
е
н
н
я
Модифікований
метод Ньютона
Стандартний метод
Ньютона
0
5
10
15
20
25
1 2 3 4 5 6 7 8
Кількість процесів
К
о
е
ф
іц
іє
н
т
е
ф
е
к
ти
в
н
о
с
ті
Модифікований
метод Ньютона
Стандартний
метод Ньютона
Рис. 1. Коефіцієнт прискорення Рис. 2. Коефіцієнт ефективності
0
200
400
600
800
1000
1200
1400
1600
16 18 20 22 24 26 28 30 32
кількість процесів
ч
а
с
р
о
зв
'я
зу
в
а
н
н
я
С
Н
Р
n=20000
n=30000
n=40000
n=50000
Рис. 3. Часи розв’язування СНР різних порядків
Отримана ефективність (в %)
(
np
S
E
p
p = ) відображена на діаграмі
(рис. 2).
Отже, з діаграми видно, що зі збі-
льшенням кількості процесів, використа-
них для знаходження розв’язку задачі, ко-
ефіцієнт ефективності збільшується для
модифікованого методу, в той час як для
стандартного – дещо зменшується.
Іншою важливою особливістю за-
пропонованого методу є зменшення обсягу
пам’яті, необхідної для реалізації алгорит-
му, що дає можливість розв’язувати СНР більш високих порядків. На графіку (рис. 3)
представлені часи розв’язування наведеної вище системи нелінійних рівнянь при
n = 20000, 30000, 40000 та 50000 на кількості процесів від 16 до 32.
Зі збільшенням порядку системи швидкість зменшення часу розв’язування від кіль-
кості процесів зростає.
У подальшому будуть розглянуті реалізації паралельного алгоритму на багатоядер-
ному комп’ютері з графічними прискорювачами.
5. Висновки
Модифікований метод Ньютона скорочує час розв’язування задачі та вимагає меншого
об’єму пам’яті. Зі збільшенням кількості процесів, використаних для знаходження
розв’язку задачі, коефіцієнт ефективності збільшується для модифікованого методу. Мо-
дифікований метод легко масштабується на різну кількість процесів.
СПИСОК ЛІТЕРАТУРИ
1. Параллельные алгоритмы решения задач вычислительной математики / [Химич А.Н., Молчанов
И.Н., Попов А.В. и др.]. − Киев: Наукова думка, 2008. − 248 с.
ISSN 1028-9763. Математичні машини і системи, 2014, № 4 17
2. Яковлев М.Ф. Особливості розв’язування систем нелінійних та диференціальних рівнянь на па-
ралельних комп’ютерах / М.Ф. Яковлев, Т.О. Герасимова, А.Н. Нестеренко // Питання оптимізації
обчислень (ПОО – XXXV): праці міжнар. симпозіуму. – Київ: Інститут кібернетики ім. В.М. Глуш-
кова НАН України, 2009. – Т. 2. – С. 435 – 439.
3. Численное программное обеспечение интеллектуального MIMD-компьютера Инпарком /
А.Н. Химич, И.Н. Молчанов, В.И. Мова [и др.]. − Киев: Наукова думка, 2007. − 216 с.
4. Нестеренко А.Н. Некоторые вопросы решения систем нелинейных уравнений на многопроцес-
сорных вычислительных системах с распределенной памятью / А.Н. Нестеренко, А.Н. Химич,
М.Ф. Яковлев // Вестник компьютерных и информационных технологий. − 2006. − № 10. − С. 54 –
56.
Стаття надійшла до редакції 19.08.2014
|
| id | nasplib_isofts_kiev_ua-123456789-84444 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T18:35:48Z |
| publishDate | 2014 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Яковлєв, М.Ф. Нестеренко, А.Н. Бруснікін, В.М. 2015-07-08T13:00:23Z 2015-07-08T13:00:23Z 2014 Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури / М.Ф. Яковлєв, А.Н. Нестеренко, В.М. Бруснікін // Математичні машини і системи. — 2014. — № 4. — 12-17. — Бібліогр.: 4 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/84444 519.6 У роботі пропонуються модифікований метод та алгоритм розв’язування систем нелінійних рівнянь (СНР) для комп’ютерів MIMD-архітектури. Наведені часи розв’язування СНР різних порядків, визначені коефіцієнти прискорення та ефективності використання запропонованого методу. В работе предлагаются модифицированный метод и алгоритм решения систем нелинейных уравнений (СНУ) для компьютеров MIMD-архитектуры. Приведены времена решения СНУ разных порядков, определены коэффициенты ускорения и эффективности использования предложенного метода. The paper deals both with modified method and algorithm intended for the solving of non-linear systems (NLS) for MIMD-architecture computers. Times required for the solving of NLSs of various orders are given; acceleration and efficiency coefficients for the proposed method are determined, as well. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури Проблемы эффективного решения нелинейных уравнений на многопроцессорных компьютерах MIMD-архитектуры Problems of effective solution of system of nonlinear equations on MIMD-architecture multiprocessor computers Article published earlier |
| spellingShingle | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури Яковлєв, М.Ф. Нестеренко, А.Н. Бруснікін, В.М. Обчислювальні системи |
| title | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури |
| title_alt | Проблемы эффективного решения нелинейных уравнений на многопроцессорных компьютерах MIMD-архитектуры Problems of effective solution of system of nonlinear equations on MIMD-architecture multiprocessor computers |
| title_full | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури |
| title_fullStr | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури |
| title_full_unstemmed | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури |
| title_short | Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури |
| title_sort | проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах mimd-архітектури |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84444 |
| work_keys_str_mv | AT âkovlêvmf problemiefektivnogorozvâzuvannâsistemnelíníinihrívnânʹnabagatoprocesornihkompûterahmimdarhítekturi AT nesterenkoan problemiefektivnogorozvâzuvannâsistemnelíníinihrívnânʹnabagatoprocesornihkompûterahmimdarhítekturi AT brusníkínvm problemiefektivnogorozvâzuvannâsistemnelíníinihrívnânʹnabagatoprocesornihkompûterahmimdarhítekturi AT âkovlêvmf problemyéffektivnogorešeniânelineinyhuravneniinamnogoprocessornyhkompʹûterahmimdarhitektury AT nesterenkoan problemyéffektivnogorešeniânelineinyhuravneniinamnogoprocessornyhkompʹûterahmimdarhitektury AT brusníkínvm problemyéffektivnogorešeniânelineinyhuravneniinamnogoprocessornyhkompʹûterahmimdarhitektury AT âkovlêvmf problemsofeffectivesolutionofsystemofnonlinearequationsonmimdarchitecturemultiprocessorcomputers AT nesterenkoan problemsofeffectivesolutionofsystemofnonlinearequationsonmimdarchitecturemultiprocessorcomputers AT brusníkínvm problemsofeffectivesolutionofsystemofnonlinearequationsonmimdarchitecturemultiprocessorcomputers |