Об особенностях моделирования линейных динамических систем в многопроцессорных средах
Предложены подходы, позволяющие избегать последовательных участков работы многопроцессорных вычислительных систем. Первый подход основан на предварительном вычислении правых частей неоднородной линейной системы обыкновенных дифференциальных уравнений, второй — на предварительном интерполировании пра...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2007 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101669 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об особенностях моделирования линейных динамических систем в многопроцессорных средах / O.А. Дмитриева // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 63-72. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101669 |
|---|---|
| record_format |
dspace |
| spelling |
Дмитриева, O.А. 2016-06-06T15:50:38Z 2016-06-06T15:50:38Z 2007 Об особенностях моделирования линейных динамических систем в многопроцессорных средах / O.А. Дмитриева // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 63-72. — Бібліогр.: 10 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101669 681.3 Предложены подходы, позволяющие избегать последовательных участков работы многопроцессорных вычислительных систем. Первый подход основан на предварительном вычислении правых частей неоднородной линейной системы обыкновенных дифференциальных уравнений, второй — на предварительном интерполировании правых частей системы с помощью сплайнов. Выявлены соотношения между порядками погрешностей методов численного интегрирования и методов интерполирования, которые позволяют осуществить оптимальный выбор подхода к параллельной реализации решения системы. Запропоновано підходи, що дозволяють уникати послідовних ділянок роботи багатопроцесорних обчислювальних систем. Перший підхід базується на попередньому обчислюванні правих частин неоднорідної лінійної системи звичайних диференціальних рівнянь, другий — на попередній інтерполяції правих частин системи за допомогою сплайнів. Виявлено співвідношення між порядками похибок методів чисельного інтегрування і методів інтерполяції, що дозволяють здійснити оптимальний вибір підходу до паралельної реалізації розв’язування системи. The approaches are proposed which allow to avoid the sequential sections of multiprocessor computer work. The first approach is based on the preliminary computation of right parts of the nonuniform linear system of the ordinary differential equations. The second approach is based on the preliminary interpolation of right parts of the system by splines. The relations between error orders of the numerical integration and interpolation methods are found which permit the optimal choice of the approach to the parallel realization of the system solution. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Вычислительные процессы и системы Об особенностях моделирования линейных динамических систем в многопроцессорных средах On Peculiarities of Linear Dynamic System Simulation in Multiprocessor Media Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах |
| spellingShingle |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах Дмитриева, O.А. Вычислительные процессы и системы |
| title_short |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах |
| title_full |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах |
| title_fullStr |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах |
| title_full_unstemmed |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах |
| title_sort |
об особенностях моделирования линейных динамических систем в многопроцессорных средах |
| author |
Дмитриева, O.А. |
| author_facet |
Дмитриева, O.А. |
| topic |
Вычислительные процессы и системы |
| topic_facet |
Вычислительные процессы и системы |
| publishDate |
2007 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
On Peculiarities of Linear Dynamic System Simulation in Multiprocessor Media |
| description |
Предложены подходы, позволяющие избегать последовательных участков работы многопроцессорных вычислительных систем. Первый подход основан на предварительном вычислении правых частей неоднородной линейной системы обыкновенных дифференциальных уравнений, второй — на предварительном интерполировании правых частей системы с помощью сплайнов. Выявлены соотношения между порядками погрешностей методов численного интегрирования и методов интерполирования, которые позволяют осуществить оптимальный выбор подхода к параллельной реализации решения системы.
Запропоновано підходи, що дозволяють уникати послідовних ділянок роботи багатопроцесорних обчислювальних систем. Перший підхід базується на попередньому обчислюванні правих частин неоднорідної лінійної системи звичайних диференціальних рівнянь, другий — на попередній інтерполяції правих частин системи за допомогою сплайнів. Виявлено співвідношення між порядками похибок методів чисельного інтегрування і методів інтерполяції, що дозволяють здійснити оптимальний вибір підходу до паралельної реалізації розв’язування системи.
The approaches are proposed which allow to avoid the sequential sections of multiprocessor computer work. The first approach is based on the preliminary computation of right parts of the nonuniform linear system of the ordinary differential equations. The second approach is based on the preliminary interpolation of right parts of the system by splines. The relations between error orders of the numerical integration and interpolation methods are found which permit the optimal choice of the approach to the parallel realization of the system solution.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101669 |
| citation_txt |
Об особенностях моделирования линейных динамических систем в многопроцессорных средах / O.А. Дмитриева // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 63-72. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT dmitrievaoa obosobennostâhmodelirovaniâlineinyhdinamičeskihsistemvmnogoprocessornyhsredah AT dmitrievaoa onpeculiaritiesoflineardynamicsystemsimulationinmultiprocessormedia |
| first_indexed |
2025-11-26T06:17:38Z |
| last_indexed |
2025-11-26T06:17:38Z |
| _version_ |
1850615047380795392 |
| fulltext |
ÓÄÊ 681.3
O. À. Äìèòðèåâà, êàíä. òåõí. íàóê
Äîíåöêèé íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò
(Óêðàèíà, 83000, Äîíåöê, óë. Àðòåìà, 58,
òåë.: (062) 3010757, E-mail: dmitriv@r5.dgtu.donetsk.ua)
Îá îñîáåííîñòÿõ ìîäåëèðîâàíèÿ ëèíåéíûõ
äèíàìè÷åñêèõ ñèñòåì â ìíîãîïðîöåññîðíûõ ñðåäàõ
Ïðåäëîæåíû ïîäõîäû, ïîçâîëÿþùèå èçáåãàòü ïîñëåäîâàòåëüíûõ ó÷àñòêîâ ðàáîòû ìíî-
ãîïðîöåññîðíûõ âû÷èñëèòåëüíûõ ñèñòåì. Ïåðâûé ïîäõîä îñíîâàí íà ïðåäâàðèòåëüíîì
âû÷èñëåíèè ïðàâûõ ÷àñòåé íåîäíîðîäíîé ëèíåéíîé ñèñòåìû îáûêíîâåííûõ äèôôåðåí-
öèàëüíûõ óðàâíåíèé, âòîðîé — íà ïðåäâàðèòåëüíîì èíòåðïîëèðîâàíèè ïðàâûõ ÷àñòåé
ñèñòåìû ñ ïîìîùüþ ñïëàéíîâ. Âûÿâëåíû ñîîòíîøåíèÿ ìåæäó ïîðÿäêàìè ïîãðåøíîñòåé
ìåòîäîâ ÷èñëåííîãî èíòåãðèðîâàíèÿ è ìåòîäîâ èíòåðïîëèðîâàíèÿ, êîòîðûå ïîçâîëÿþò
îñóùåñòâèòü îïòèìàëüíûé âûáîð ïîäõîäà ê ïàðàëëåëüíîé ðåàëèçàöèè ðåøåíèÿ ñèñòåìû.
Çàïðîïîíîâàíî ï³äõîäè, ùî äîçâîëÿþòü óíèêàòè ïîñë³äîâíèõ ä³ëÿíîê ðîáîòè áàãàòîïðî-
öåñîðíèõ îá÷èñëþâàëüíèõ ñèñòåì. Ïåðøèé ï³äõ³ä áàçóºòüñÿ íà ïîïåðåäíüîìó îá÷èñëþâàíí³
ïðàâèõ ÷àñòèí íåîäíîð³äíî¿ ë³í³éíî¿ ñèñòåìè çâè÷àéíèõ äèôåðåíö³àëüíèõ ð³âíÿíü, äðóãèé —
íà ïîïåðåäí³é ³íòåðïîëÿö³¿ ïðàâèõ ÷àñòèí ñèñòåìè çà äîïîìîãîþ ñïëàéí³â. Âèÿâëåíî ñï³â-
â³äíîøåííÿ ì³æ ïîðÿäêàìè ïîõèáîê ìåòîä³â ÷èñåëüíîãî ³íòåãðóâàííÿ ³ ìåòîä³â ³íòåðïîëÿö³¿,
ùî äîçâîëÿþòü çä³éñíèòè îïòèìàëüíèé âèá³ð ï³äõîäó äî ïàðàëåëüíî¿ ðåàë³çàö³¿ ðîçâ’ÿçó-
âàííÿ ñèñòåìè.
Ê ë þ ÷ å â û å ñ ë î â à: ïàðàëëåëüíûå âû÷èñëåíèÿ, îáûêíîâåííûå äèôôåðåíöèàëüíûå
óðàâíåíèÿ, íåîäíîðîäíàÿ ñèñòåìà, çàäà÷à ïðèáëèæåíèÿ, èíòåðïîëèðîâàíèå, ñïëàéíû.
Íåîáõîäèìîñòü àäàïòàöèè èçâåñòíûõ ÷èñëåííûõ ìåòîäîâ ðåøåíèÿ ñèñòåì
îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé (ÎÄÓ) â âû÷èñëèòåëüíûõ
ñèñòåìàõ ñ ïàðàëëåëüíîé àðõèòåêòóðîé îáóñëîâëåíà ìíîæåñòâîì îáñòîÿ-
òåëüñòâ, ê êîòîðûì, â ïåðâóþ î÷åðåäü, ñëåäóåò îòíåñòè òîò ôàêò, ÷òî áîëåå
âûñîêàÿ ñêîðîñòü ðåøåíèÿ äîñòèãàåòñÿ â ðåçóëüòàòå ðàöèîíàëüíîé îðãàíè-
çàöèè ðàñïàðàëëåëèâàíèÿ âû÷èñëåíèé. Íåîáõîäèìî òàêæå îòìåòèòü, ÷òî
ìàòåìàòè÷åñêèå ìîäåëè áîëüøèíñòâà íàó÷íûõ è èíæåíåðíûõ çàäà÷ ÷àùå
âñåãî ïðåäñòàâëÿþò ñîáîé ñèñòåìû äèôôåðåíöèàëüíûõ óðàâíåíèé, êàê
îáûêíîâåííûõ, òàê è â ÷àñòíûõ ïðîèçâîäíûõ. Íåñëó÷àéíî â ïîñëåäíèå
ãîäû çíà÷èòåëüíî âîçðîñëî ÷èñëî ðàáîò ïî òåîðèè ïàðàëëåëüíûõ âû÷èñ-
ëåíèé. Îäíàêî ïðèõîäèòñÿ ïðèçíàòü, ÷òî íà ïàðàëëåëüíûõ ìàøèíàõ èñ-
ïîëüçóþòñÿ, ãëàâíûì îáðàçîì, ñòàðûå, õîðîøî èññëåäîâàííûå è ìíîãî-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 63
êðàòíî àïðîáèðîâàííûå ïîñëåäîâàòåëüíûå àëãîðèòìû, êîòîðûå ñïåöèàëü-
íûì îáðàçîì ðåñòðóêòóðèçèðîâàíû [1]. Ðåñòðóêòóðèçàöèÿ àëãîðèòìîâ íà
óðîâíå îòäåëüíûõ îïåðàöèé — ýòî îñíîâíàÿ èäåÿ, êîòîðàÿ â íàñòîÿùåå âðåìÿ
àêòèâíî èñïîëüçóåòñÿ ïðè ñîãëàñîâàíèè ñâîéñòâ ïðîãðàìì è êîìïüþòåðîâ
äëÿ ïîëó÷åíèÿ ìàêñèìàëüíîé ðåàëüíîé ïðîèçâîäèòåëüíîñòè.
Äàííàÿ ðàáîòà ÿâëÿåòñÿ ïðîäîëæåíèåì ðàáîò [2—8], êîòîðûå ïîñâÿ-
ùåíû èññëåäîâàíèþ ïàðàëëåëüíûõ àëãîðèòìîâ ÷èñëåííîãî ðåøåíèÿ ñèñòåì
ÎÄÓ, èñïîëüçóåìûõ äëÿ ìîäåëèðîâàíèÿ ñëîæíûõ äèíàìè÷åñêèõ ñèñòåì ñ
ñîñðåäîòî÷åííûìè ïàðàìåòðàìè. Ïðåäëàãàåìûå àëãîðèòìû îðèåíòèðîâàíû
íà èñïîëüçîâàíèå â ìíîãîïðîöåññîðíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ SIMD
(single instruction stream — multiple data stream) ñòðóêòóðû ñ ðåøåòêîé èëè
ëèíåéêîé ïðîöåññîðíûõ ýëåìåíòîâ. Íàáîð ïðîöåññîðîâ èçâåñòåí äî íà÷àëà
âû÷èñëåíèé è íå ìåíÿåòñÿ â ïðîöåññå ñ÷åòà, ïðè ýòîì êàæäûé ïðîöåñ-
ñîðíûé ýëåìåíò ìîæåò âûïîëíèòü ëþáóþ àðèôìåòè÷åñêóþ îïåðàöèþ çà
îäèí òàêò, âðåìåííûå çàòðàòû, ñâÿçàííûå ñ îáðàùåíèåì ê çàïîìèíàþùåìó
óñòðîéñòâó, îòñóòñòâóþò.
1. Ïîñòàíîâêà çàäà÷è. Ïðåäñòàâèì ìàòåìàòè÷åñêóþ ìîäåëü äèíàìè-
÷åñêîé ñèñòåìû â âèäå ñèñòåìû ÎÄÓ ñ ïîñòîÿííûìè êîýôôèöèåíòàìè è
íà÷àëüíûìè óñëîâèÿìè:
d
dt
A t
x
x f� � ( ), x x( ) ( , ,..., )t x x xm
t
0
0
1
0
2
0 0
� � ,
(1)
ãäå x — âåêòîð íåèçâåñòíûõ ñèãíàëîâ; f (t) —âåêòîð âîçäåéñòâèé, t T�[ , ]0 ;
A — ìàòðèöà êîýôôèöèåíòîâ ñèñòåìû. Çäåñü âû÷èñëåíèå çíà÷åíèÿ âåê-
òîðà íåèçâåñòíûõ x
n�1
íà î÷åðåäíîì øàãå òðåáóåò ïðåäâàðèòåëüíîãî îïðå-
äåëåíèÿ çíà÷åíèé x
n
. Â [3] ðàññìîòðåíû âîïðîñû, ñâÿçàííûå ñ âîçìîæ-
íîñòüþ ïàðàëëåëüíîé ðåàëèçàöèè òàêèõ àëãîðèòìîâ.  ÷àñòíîñòè, åñëè
ñèñòåìà (1) ÿâëÿåòñÿ îäíîðîäíîé, ò.å. f ti ( ) �0, i = 1, 2, ..., m, òî â çàâè-
ñèìîñòè îò âûáðàííîãî ìåòîäà èíòåãðèðîâàíèÿ, ìîæíî èñêàòü ðåøåíèå â
âèäå
x x
n nG�
�
1
,
ãäå G — îïåðàòîð (ìàòðèöà) ïåðåõîäîâ.
Ïîëó÷åííûé îïåðàòîð ïåðåõîäà G, êîòîðûé íåîáõîäèìî îïðåäåëèòü
îäèí ðàç äî íà÷àëà âû÷èñëåíèé, ïîçâîëÿåò âû÷èñëÿòü çíà÷åíèÿ âåêòîðà
íåèçâåñòíûõ ïàðàëëåëüíî [3, 5]. Íàïðèìåð, äëÿ ìåòîäîâ Ðóíãå—Êóòòû,
ýòîò îïåðàòîð, â çàâèñèìîñòè îò òî÷íîñòè ìåòîäà, ìîæåò èìåòü âèä
G E A E
A
E
A
E
A
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
2 3 4
,
O. À. Äìèòðèåâà
64 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
îáåñïå÷èâàþùèé òî÷íîñòü 4-ãî ïîðÿäêà, èëè
G E A E
A
E
A
E
A
E
A
E
A
� � � � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � � � �
2 3 4 5 3�
�
�
�
�
�
�
,
òî÷íîñòü êîòîðîãî îöåíèâàåòñÿ 6-ì ïîðÿäêîì.
Ïðè ðåøåíèè íåîäíîðîäíîé ñèñòåìû íåîáõîäèìî íà êàæäîì øàãå
äîïîëíèòåëüíî âû÷èñëèòü çíà÷åíèÿ âñåõ ôóíêöèé f i t( ) �0, i m�1, , â íå-
ñêîëüêèõ ïðîìåæóòî÷íûõ òî÷êàõ. Ïîñêîëüêó ýòè ôóíêöèè ìîãóò áûòü
ðàçëè÷íûìè, îäíîâðåìåííîå âû÷èñëåíèå èõ íà SIMD êîìïüþòåðå íåâîç-
ìîæíî. Ïîýòîìó ïðåäëàãàþòñÿ äâà ðàçëè÷íûõ ïîäõîäà, ïîçâîëÿþùèõ
èçáåæàòü ïîñëåäîâàòåëüíûõ ó÷àñòêîâ ñ÷åòà.
2. Ïðåäâàðèòåëüíîå âû÷èñëåíèå ïðàâûõ ÷àñòåé ñèñòåìû. Ó÷è-
òûâàÿ ñïåöèôèêó çàäà÷è (1), à èìåííî, íåçàâèñèìîñòü âåêòîðà âîçäåéñòâèé
îò çíà÷åíèé íåèçâåñòíûõ ñèãíàëîâ, ìîæíî âñå ïðîìåæóòî÷íûå çíà÷åíèÿ
ôóíêöèé f i t( ) âû÷èñëèòü çàðàíåå. Ïðè ýòîì, îáîçíà÷èâ ÷èñëî ïðîìåæó-
òî÷íûõ òî÷åê ìåòîäà, ìîæíî îöåíèòü ÷èñëî òàêòîâ ðàñ÷åòà íà òîïîëîãè÷åñ-
êèõ ñòðóêòóðàõ: ëèíåéêå èç m ïðîöåññîðîâ è ðåøåòêå èç m m
ïðîöåññîðîâ
(ðàçìåðíîñòü ïðîöåññîðíîãî ïîëÿ âûáðàíà ñîâïàäàþùåé ñ ðàçìåðíîñòüþ
ñèñòåìû óðàâíåíèé èñêëþ÷èòåëüíî äëÿ óäîáñòâà èçëîæåíèÿ). Îáîçíà÷èì � fi
òðóäîåìêîñòü ðåàëèçàöèè ïðàâûõ ÷àñòåé ñèñòåìû è ïðè ðàñ÷åòå áóäåì îïåðè-
ðîâàòü ñ ìàêñèìàëüíûì çíà÷åíèåì � �f i fi
� max{ }. Åñëè ðàñ÷åò îñóùåñòâ-
ëÿåòñÿ äëÿ îáùåãî ÷èñëà óçëîâ, ðàâíîãî N, òî îáùåå ÷èñëî òàêòîâ ðàáîòû
íà ëèíåéêå ïðîöåññîðîâ ñîñòàâèò äëÿ îäíîãî óðàâíåíèÿ áëèæàéøåå öåëîå
ñâåðõó ê ñîîòíîøåíèþ
r N
m
f�
èëè
r N
m
f��
�
�
�
�
�
�1. Òîãäà âñÿ ñèñòåìà ìîæåò
áûòü ðàññ÷èòàíà çà r N mf� � òàêòîâ. Íà ðåøåòêå ïðîöåññîðîâ îäíî
óðàâíåíèå áóäåò ðåøàòüñÿ çà áëèæàéøåå öåëîå ñâåðõó ê
r N
m
f�
2
�
�
�
�
�
�
÷èñëî
òàêòîâ, à âðåìÿ, êîòîðîå ïîòðåáóåòñÿ äëÿ ðàñ÷åòà âñåé ñèñòåìû ñîñòàâèò
r N
m
f��
�
�
�
�
�
�1. Ïî êàæäîìó óðàâíåíèþ ñèñòåìû ïðèäåòñÿ õðàíèòü äâóìåðíûå
ìàññèâû ðàçìåðíîñòüþ r N
è èñïîëüçîâàòü ïðè ðàñ÷åòå êîýôôèöèåíòû ñ
íóæíûìè èíäåêñàìè.
Ïðè ìîäåëèðîâàíèè õàðàêòåðèñòèê ïàðàëëåëèçìà ðàññìàòðèâàëèñü çà-
âèñèìîñòè óñêîðåíèÿ S è êîýôôèöèåíòà ýôôåêòèâíîñòè Å îò ðàçìåðíîñòè
ñèñòåìû îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé m è òðóäîåìêîñòè
ðåàëèçàöèè ïðàâîé ÷àñòè Q. Íà ðèñ. 1, à, ïðèâåäåíû êðèâûå óñêîðåíèÿ, à íà
ðèñ. 1, á — êðèâûå êîýôôèöèåíòà ýôôåêòèâíîñòè äëÿ òîïîëîãèè 2D-òîð
ïðè ïðåäâàðèòåëüíîì âû÷èñëåíèè ïðàâûõ ÷àñòåé ñèñòåìû. Êàê âèäíî èç
Îá îñîáåííîñòÿõ ìîäåëèðîâàíèÿ ëèíåéíûõ äèíàìè÷åñêèõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 65
ðèñ. 1, ëó÷øèå ïîêàçàòåëè ïàðàëëåëèçìà äîñòèãàþòñÿ äëÿ ñèñòåì, ðåàëè-
çàöèÿ ïðàâûõ ÷àñòåé êîòîðûõ òðåáóåò âûñîêîé òðóäîåìêîñòè.
3. Èíòåðïîëèðîâàíèå ïðàâûõ ÷àñòåé ñèñòåìû. Âòîðîé ïîäõîä,
ïîçâîëÿþùèé èçáåæàòü ïîñëåäîâàòåëüíûõ ó÷àñòêîâ ïðè ïàðàëëåëüíîé
ðåàëèçàöèè ñèñòåìû, îñíîâàí íà ïðåäâàðèòåëüíîì èíòåðïîëèðîâàíèè ïðà-
âûõ ÷àñòåé (1).  âû÷èñëèòåëüíîé ïðàêòèêå íåîáõîäèìîñòü â òàêîì ïîä-
õîäå âîçíèêàåò, åñëè ïðèõîäèòñÿ çàìåíÿòü îäíó ôóíêöèþ f t( ) (èçâåñòíóþ,
íåèçâåñòíóþ èëè ÷àñòè÷íî èçâåñòíóþ) íåêîòîðîé ôóíêöèåé �( )t , áëèçêîé
ê f t( ) è îáëàäàþùåé îïðåäåëåííûìè ñâîéñòâàìè, ïîçâîëÿþùèìè âûïîë-
íÿòü ñ íåþ òå èëè èíûå àíàëèòè÷åñêèå ëèáî âû÷èñëèòåëüíûå îïåðàöèè.
Òàêóþ çàìåíó íàçûâàþò ïðèáëèæåíèåì ôóíêöèè f t( ). Òîãäà ïðè ðåøåíèè
çàäà÷è âìåñòî ôóíêöèè f t( ) îïåðèðóþò ñ ôóíêöèåé �( )t , à çàäà÷à ïîñò-
ðîåíèÿ ôóíêöèè �( )t íàçûâàåòñÿ çàäà÷åé ïðèáëèæåíèÿ. Ïðè ýòîì ôóíê-
öèþ �( )t ìîæíî ïîñòðîèòü òàêèì îáðàçîì, ÷òîáû â çàäàííûõ òî÷êàõ
t t tT0 1
, ,..., îíà ïðèíèìàëà çíà÷åíèÿ, ñîâïàäàþùèå ñ f t f t f tT( ), ( ),..., ( )
0 1
, à
â äðóãèõ òî÷êàõ ïðîìåæóòêà [ , ]0 T ïðèáëèæåííî ïðåäñòàâëÿëà ôóíêöèþ
f t( ) ñ òîé èëè èíîé ñòåïåíüþ òî÷íîñòè.
Ïðèíèìàÿ âî âíèìàíèå áîëüøîå ÷èñëî ðàññ÷èòûâàåìûõ óçëîâ è çàäà-
âàÿñü òðåáóåìîé òî÷íîñòüþ ïðèáëèæåíèÿ ôóíêöèé, ìîæíî óòâåðæäàòü, ÷òî
íàèáîëåå ïåðñïåêòèâíûì ÿâëÿåòñÿ ñëó÷àé, êîãäà èñïîëüçóþòñÿ êóñî÷íî-ïî-
ëèíîìèàëüíàÿ àïïðîêñèìàöèÿ, èëè ñïëàéíû, òàê êàê ïðè ýòîì èíòåðïîëÿ-
öèîííûå ìíîãî÷ëåíû äåéñòâóþò íå íà âñåì èíòåðâàëå ðåøåíèÿ çàäà÷è, à íà
ïîäûíòåðâàëàõ, ÷òî ïîçâîëÿåò èçáåæàòü íàêîïëåíèÿ îøèáîê ïðèáëèæåíèÿ.
Îñíîâíàÿ èäåÿ òàêîãî ïîäõîäà çàêëþ÷àåòñÿ â ñëåäóþùåì: èñõîäíûé
îòðåçîê ðåøåíèÿ äëÿ (1) [ , ]0 T ðàçáèâàåòñÿ íà íåñêîëüêî ïîäûíòåðâàëîâ V ñ
O. À. Äìèòðèåâà
66 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
S
3000
2000
1000
0
20 40 60 80 20 40 60 80 m
E
0,8
0,6
0,4
0,2
0
Q = 1000
500 100
50
5
Q = 1000
500
100
50
5
a á
Ðèñ. 1. Ãðàôèêè çàâèñèìîñòåé óñêîðåíèÿ (à) è êîýôôèöèåíòû ýôôåêòèâíîñòè (á) äëÿ
ðåøåòêè ïðîöåññîðíûõ ýëåìåíòîâ
øàãîì, îïðåäåëÿåìûì èç ñîîòíîøåíèÿ òî÷íîñòè ìåòîäîâ ÷èñëåííîãî
èíòåðïîëèðîâàíèÿ è èíòåãðèðîâàíèÿ (ðèñ. 2), à çàòåì íà êàæäîì òàêîì
èíòåðâàëå ñòðîèòñÿ èíòåðïîëÿöèîííûé ìíîãî÷ëåí. Ïîñêîëüêó â êà÷åñòâå
èíòåðïîëÿöèîííîé ôóíêöèè îáû÷íî âûáèðàþò ìíîãî÷ëåíû íå âûøå 4-é
ñòåïåíè, ÷òî ñîîòâåòñòâóþùèì îáðàçîì âëèÿåò íà òî÷íîñòü èíòåðïîëÿöèè,
íåîáõîäèìî ïðåäâàðèòåëüíî ñîãëàñîâàòü ïîðÿäêè òî÷íîñòè ìåòîäîâ ÷èñ-
ëåííîãî èíòåãðèðîâàíèÿ è ïðåäâàðèòåëüíîãî èíòåðïîëèðîâàíèÿ.
Åñëè ïîðÿäîê ìåòîäà ÷èñëåííîãî èíòåãðèðîâàíèÿ ñèñòåìû (1) îïðåäå-
ëÿåòñÿ êàê O v
( )� , à ïîðÿäîê ñïëàéíà êàê O h( )
4
, òî ìåæäó øàãàìè äâóõ
ðåøàåìûõ çàäà÷ äîëæíî âûïîëíÿòüñÿ ñîîòíîøåíèå �
v h�
4
. Åñëè ïîðÿäîê
òî÷íîñòè ìåòîäà èíòåãðèðîâàíèÿ � ðàâåí ÷åòûðåì èëè áîëåå, ò. å. ìåæäó
÷èñëîì óçëîâ çàäà÷ èíòåðïîëèðîâàíèÿ è èíòåãðèðîâàíèÿ âûïîëíÿåòñÿ
ñîîòíîøåíèå V � N, òî èñïîëüçîâàíèå èíòåðïîëèðîâàíèÿ äëÿ âîññòàíîâ-
ëåíèÿ çíà÷åíèé ïðàâûõ ÷àñòåé ÿâëÿåòñÿ íåðàöèîíàëüíûì.  ýòîì ñëó÷àå
ïðîùå çàðàíåå âû÷èñëèòü çíà÷åíèÿ ïðàâûõ ÷àñòåé íà ïðîìåæóòêå [ , ]0 T .
Åñëè ìåòîä èíòåãðèðîâàíèÿ èìååò ïîðÿäîê ïîãðåøíîñòè ìåíüøå ÷åòûðåõ,
òî òîãäà V < N è ñâÿçü çíà÷åíèé V è N ìîæíî ïðåäñòàâèòü ñ ïîìîùüþ
íåêîòîðîãî êîýôôèöèåíòà �:
N V�� , (2)
ãäå ��1. Ïðè ýòîì æåëàòåëüíî âûáèðàòü ìíîæèòåëü � öåëûì, òàê êàê íà
îäíîì òàêòå ðàñ÷åòà ïðåäïî÷òèòåëüíåå èñïîëüçîâaòü êîýôôèöèåíòû îäíîãî
èíòåðâàëà ñïëàéíà, ÷òî çíà÷èòåëüíî óïðîñòèò àëãîðèòì âû÷èñëåíèÿ è âûáîð
íóæíîãî èíòåðâàëà ïî çàäàííîìó àðãóìåíòó.
Ñîãëàñíî (2) óçëîâ èíòåðïîëèðîâàíèÿ â � ðàç ìåíüøå, ÷åì óçëîâ
èíòåãðèðîâàíèÿ. Êðîìå òîãî, îöåíêó ïîãðåøíîñòè äëÿ ñïëàéíà ïîðÿäêà
Îá îñîáåííîñòÿõ ìîäåëèðîâàíèÿ ëèíåéíûõ äèíàìè÷åñêèõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 67
t t t t t t tn n+ / n+ / n+ / n+ / n+ n+h5 3 2 2 3 �� � � �
h
�
Ðèñ. 2. Ñõåìà ðàñ÷åòà ïðàâûõ ÷àñòåé (1) ñ ïðîìåæóòî÷íûìè òî÷êàìè
O h( )
4
ìîæíî ñ÷èòàòü çàâûøåííîé. Òîãäà èñõîäíàÿ çàäà÷à ìîæåò áûòü
ñâåäåíà ê äâóì ïîäçàäà÷àì, êàæäàÿ èç êîòîðûõ ëåãêî ðàñïàðàëëåëèâàåòñÿ.
Ïåðâàÿ ïîäçàäà÷à çàêëþ÷àåòñÿ â íàõîæäåíèè êîýôôèöèåíòîâ ñïëàéíà.
Çàìåíó èñõîäíûõ ôóíêöèé f ti ( ) â (1) íà ñïëàéí-ôóíêöèè îñóùåñòâëÿåì â
âèäå
a b t c t d t e til il il il il� � � �
2 3 4
, i m�1, , l V�1, .
Òîãäà, ðåàëèçóÿ âòîðóþ ïîäçàäà÷ó, âìåñòî ðàçíîðîäíûõ îïåðàöèé (êîòî-
ðûå íà SIMD ñòðóêòóðàõ âûïîëíÿþòñÿ ïîñëåäîâàòåëüíî) âñå ïðàâûå ÷àñòè
ñèñòåìû (1) áóäåì ñ÷èòàòü ïàðàëëåëüíî ïî îäíèì è òåì æå àðãóìåíòàì t,
íî ñ ðàçíûìè êîýôôèöèåíòàìè ñïëàéí-ôóíêöèé a b c d eil il il il il, , , , , i m�1, ,
l V�1, .
Äëÿ íàõîæäåíèÿ íåèçâåñòíûõ êîýôôèöèåíòîâ ïî êàæäîìó óðàâíåíèþ
ñèñòåìû (1) ïðèäåòñÿ ðåøàòü ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâ-
íåíèé ðàçìåðíîñòüþ 4 4V V
. Ïðè ôîðìèðîâàíèè ñèñòåìû ëèíåéíûõ óðàâ-
íåíèé áóäåì èñõîäèòü èç ïðèíöèïîâ ñîâïàäåíèÿ çíà÷åíèé ôóíêöèè, åå
ïåðâûõ, âòîðûõ è òðåòüèõ ïðîèçâîäíûõ íà ñîñåäíèõ ïîäûíòåðâàëàõ ñëåâà
è ñïðàâà îò óçëà èíòåðïîëÿöèè.
Ïóñòü { }pl — ìíîæåñòâî óçëîâ èíòåðïîëÿöèè, l V�0, . Ïðè÷åì, äëÿ
ëþáîé ïðàâîé ÷àñòè ñèñòåìû (1) ýòî ìíîæåñòâî óçëîâ — âåëè÷èíà ïîñ-
òîÿííàÿ. Ìåæäó óçëàìè pl�1
è pl ôóíêöèþ i-ãî óðàâíåíèÿ ñèñòåìû ïðåä-
ñòàâèì â âèäå
S p a b p p c p p d p p ei il il l il l il l i( ) ( ) ( ) ( )� � � � � � � �
� � �1 1
2
1
3
l lp p( )�
�1
4
,
p p pl l�
� �
1
, i m�1, , l V�1, . (3)
Èñõîäÿ èç ïîñòàíîâêè çàäà÷è èíòåðïîëèðîâàíèÿ, â óçëàõ èíòåðïîëÿöèè
çíà÷åíèÿ èñõîäíîé ôóíêöèè è èíòåðïîëÿöèîííîãî ìíîãî÷ëåíà ñîâïà-
äàþò, ò.å.
S p fi l il( ) � , i m�1, , l V�1, . (4)
Îäíàêî, åñëè àðãóìåíò ñïëàéíà ñîâïàäàåò ñ óçëîì èíòåðïîëÿöèè, òî èç (3)
è (4) ñëåäóåò S p a fi l il il( )
� �
� �
1 1
, i m�1, , l V�1, . Ïîñêîëüêó èíòåðïîëÿ-
öèîííûé ìíîãî÷ëåí ââîäèòñÿ äëÿ ðàâíîîòñòîÿùèõ óçëîâ, ò. å. p p hl l� �
�1
,
èñïîëüçóÿ ïîëó÷åííûå ñîîòíîøåíèÿ, ìîæíî ïåðåïèñàòü ôîðìóëó äëÿ
ñïëàéíà â l-ì óçëå â âèäå f f b hil il il� � �
�1
� � �c h d h e hil il il
2 3 4
.
Äëÿ ïîñòðîåíèÿ îñòàëüíûõ ñîîòíîøåíèé âîñïîëüçóåìñÿ ïðåäïîëîæå-
íèåì î ñîâïàäåíèè 1-é, 2-é è 3-é ïðîèçâîäíûõ ñïðàâà è ñëåâà îò óçëîâ
O. À. Äìèòðèåâà
68 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
èíòåðïîëÿöèè, ò.å. äëÿ ïåðâûõ ïðîèçâîäíûõ:
� � � � � � � �
� � �
S p b c p p d p p e p pi il il l il l il l( ) ( ) ( ) ( )2 3 4
1 1
2
1
3
, p p pl l�
� �
1
,
� � � � � � � �
� � �
S p b c p p d p p e p pi il il l il l il l( ) ( ) ( ) ( )
1 1 1
2
2 3 4
3
,
p p pl l� �
�1
. (5)
Äëÿ êàæäîãî óðàâíåíèÿ ñèñòåìû (1) çàïèøåì (5) â òî÷êå pl .Òîãäà
b b c h d h e hil il il il il�
� � � �
1
2 3
2 3 4 .
Ïðèðàâíèâàÿ çíà÷åíèÿ ïîëó÷åííûõ âûðàæåíèé äëÿ 2-é è 3-é ïðîèç-
âîäíûõ â óçëàõ èíòåðïîëÿöèè è äîáàâëÿÿ ãðàíè÷íûå óñëîâèÿ, àíàëîãè÷íî
ïîëó÷àåì m ñèñòåì ëèíåéíûõ óðàâíåíèé.
Ñôîðìèðîâàííûå ñèñòåìû îòíîñèòåëüíî âåêòîðà íåèçâåñòíûõ êîýô-
ôèöèåíòîâ â îáùåì âèäå ïðåäñòàâèì òàê:
Qi i iy � g , i m�1, , (6)
ãäå y i i i i i i iV iV iV iV iVa b c d e a b c d e� ( , , , , , ..., , , , , )
1 1 1 1 1
, i m�1, .
Îñîáåííîñòüþ ïîëó÷åííûõ ñèñòåì ÿâëÿåòñÿ ëåíòî÷íûé âèä ìàòðèöû
Q, òàê êàê êàæäîå óðàâíåíèå ñèñòåìû (çà èñêëþ÷åíèåì ïåðâîãî è ïîñ-
ëåäíåãî) ñîäåðæèò òîëüêî ÷åòûðå íåèçâåñòíûõ.  ýòîì ñëó÷àå ñèñòåìà
ïðåîáðàçóåòñÿ òàê, ÷òîáû åå ìîæíî áûëî ðåøàòü ìåòîäîì âñòðå÷íîé ïðî-
ãîíêè [9]. Òðóäîåìêîñòü ðåøåíèÿ òàêèõ ñèñòåì íà ïàðàëëåëüíûõ SIMD
ñòðóêòóðàõ ëèíåéíî çàâèñèò îò ðàçìåðíîñòè ðåøàåìîé ñèñòåìû. Äëÿ ñèñòå-
ìû ðàçìåðíîñòüþ k îíà îöåíèâàåòñÿ êàê Q k( ). Ñëåäîâàòåëüíî, äëÿ ðàññìîò-
ðåííîãî ñëó÷àÿ òðóäîåìêîñòü íàõîæäåíèÿ êîýôôèöèåíòîâ ñïëàéí-ôóíêöèè
äëÿ îäíîãî óðàâíåíèÿ ñèñòåìû ñîñòàâèò O V( )4 . Òîãäà äëÿ èñõîäíîé çàäà÷è
(1) ÷èñëî îïåðàöèé ïðèáëèçèòåëüíî áóäåò 4Vm.
Åùå îäèí âîçìîæíûé ïîäõîä ê ðåøåíèþ ñèñòåìû (6), èìåþùåé áîëü-
øóþ ðàçìåðíîñòü è ðàçðåæåííóþ ìàòðèöó êîýôôèöèåíòîâ, çàêëþ÷àåòñÿ â
ïðèâåäåíèè åå ê áëî÷íî-äèàãîíàëüíîé ôîðìå ñ îáðàìëåíèåì [7, 10] è
ôîðìèðîâàíèè âñïîìîãàòåëüíîé ñèñòåìû çíà÷èòåëüíî ìåíüøåé ðàçìåð-
íîñòè, îòíîñèòåëüíî âåêòîðà îïðåäåëÿþùèõ âåëè÷èí, èëè ïåðåìåííûõ
ñâÿçè. Òðóäîåìêîñòü ðåàëèçàöèè òàêîãî ïîäõîäà íà ïàðàëëåëüíûõ âû÷èñ-
ëèòåëüíûõ ñòðóêòóðàõ áóäåò, êàê è â ïðåäûäóùåì ñëó÷àå, ëèíåéíî çàâè-
ñåòü îò ðàçìåðíîñòè ñèñòåìû.
Äëÿ èíòåðïîëèðîâàíèÿ íåîáõîäèìî ïðåäâàðèòåëüíî âû÷èñëèòü çíà-
÷åíèÿ ïðàâûõ ÷àñòåé â V òî÷êàõ, êîòîðûå áóäóò èñïîëüçîâàòüñÿ â êà÷åñòâå
èñõîäíûõ äàííûõ äëÿ ïîñòðîåíèÿ èíòåðïîëÿöèîííîãî ìíîãî÷ëåíà. Òîãäà
äëÿ ñèñòåìû èç m óðàâíåíèé ïîòðåáóåòñÿ m V V f( )4 � � òàêòîâ. Âîçíèêàåò
òàêæå íåîáõîäèìîñòü â âîññòàíîâëåíèè çíà÷åíèé ïðàâûõ ÷àñòåé ïî ïîëó-
÷åííûì êîýôôèöèåíòàì èíòåðïîëÿöèîííûõ ìíîãî÷ëåíîâ â N îñíîâíûõ è
Îá îñîáåííîñòÿõ ìîäåëèðîâàíèÿ ëèíåéíûõ äèíàìè÷åñêèõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 69
r âñïîìîãàòåëüíûõ óçëàõ èíòåãðèðîâàíèÿ. Ïðè ýòîì ïîñëåäîâàòåëüíîñòü
âûïîëíÿåìûõ îïåðàöèé íà SIMD ñòðóêòóðå äëÿ ìíîãî÷ëåíà îáùåãî âèäà
a bt ct dt et� � � �
2 3 4
áóäåò òàêîé:
óìíîæåíèÿ
1-é òàêò — t t,
2-é òàêò — t t2
, t t2 2
— ïàðàëëåëüíî.
3-é òàêò — bt ct dt et, , ,
2 3 4
— ïàðàëëåëüíî,
ñëîæåíèÿ
4-é òàêò — a bt ct dt� �,
2 3
,
5-é òàêò — a bt ct dt et� � � �
2 3 4
.
Òàêèì îáðàçîì, íà îïðåäåëåíèå îäíîãî çíà÷åíèÿ ïðàâîé ÷àñòè òðåáóåòñÿ
ïÿòü âðåìåííûõ òàêòîâ. Åñëè ó÷åñòü, ÷òî ÷èñëî òî÷åê, â êîòîðûõ íåîáõîäèìî
âîññòàíàâëèâàòü çíà÷åíèå ïðàâîé ÷àñòè êàæäîãî óðàâíåíèÿ îïðåäåëÿåòñÿ êàê
rN, òî âñåãî íà âîññòàíîâëåíèå çíà÷åíèé ôóíêöèè ïî èíòåðïîëÿöèîííîìó
ìíîãî÷ëåíó äëÿ ñèñòåìû ïîòðåáóåòñÿ 5mrN âðåìåííûõ òàêòîâ.
O. À. Äìèòðèåâà
70 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
S
6000
4000
2000
20 40 60 80
a
20 40 60 80 m
á
E
0,9
0,8
0,7
0,6
0,5
0,4
0,3
Q = 1000
500
100
50
5
Q = 1000
500
100
50
5
Ðèñ. 3. Ãðàôèêè çàâèñèìîñòåé óñêîðåíèÿ (à) è êîýôôèöèåíòà ýôôåêòèâíîñòè (á) äëÿ
òîïîëîãèè 2D-òîð ïðè ïðåäâàðèòåëüíîì èíòåðïîëèðîâàíèè ïðàâûõ ÷àñòåé ñèñòåìû
×èñëî îïåðàöèé Ïðåäâàðèòåëüíûé ðàñ÷åò Èíòåðïîëèðîâàíèå
Îáùåå r N mf� m V V rNf( )4 5� ��
Íà òîïîëîãèè 1D-òîð [ ]r Nf� � 1 4 5V V rNf� ��
Íà òîïîëîãèè 2D-òîð
r N
m
f��
�
�
�
�
�
� 1 ( ) /4 5V V rN mf� ��
Ñðàâíèòåëüíûå îöåíêè ÷èñëà îïåðàöèé ïðè äâóõ ïîäõîäàõ
íà ïàðàëëåëüíûõ òîïîëîãèÿõ
Ïðè ìîäåëèðîâàíèè õàðàêòåðèñòèê ïàðàëëåëèçìà ñ èñïîëüçîâàíèåì ïîä-
õîäà, îðèåíòèðîâàííîãî íà ïðåäâàðèòåëüíîå èíòåðïîëèðîâàíèå ïðàâûõ ÷àñ-
òåé ñèñòåìû, ðàññìàòðèâàëèñü òå æå çàâèñèìîñòè óñêîðåíèÿ S è êîýôôè-
öèåíòà ýôôåêòèâíîñòè Å, ÷òî è â ðàçäåëå 2. Äëÿ èíòåãðèðîâàíèÿ èñïîëüçîâàí
äâóõñòàäèéíûé ìåòîä. Íà ðèñ. 3 ïðèâåäåíû çàâèñèìîñòè óñêîðåíèÿ è ýôôåê-
òèâíîñòè äëÿ ðåøåòêè ïðîöåññîðíûõ ýëåìåíòîâ, èç êîòîðûõ âèäíî, ÷òî ëó÷-
øèå ïîêàçàòåëè ïàðàëëåëèçìà äîñòèãàþòñÿ äëÿ ñèñòåì, ðåàëèçàöèÿ ïðàâûõ
÷àñòåé êîòîðûõ òðåáóåò âûñîêîé òðóäîåìêîñòè.
Ïîëó÷åííûå ïðèáëèæåííûå ðåçóëüòàòû äâóõ îïèñàííûõ ñïîñîáîâ
ðåàëèçàöèè ïðàâûõ ÷àñòåé ïðèâåäåíû â òàáëèöå.
Ïîñêîëüêó èçíà÷àëüíî ïðåäïîëàãàëîñü, ÷òî òðóäîåìêîñòè âû÷èñëåíèÿ
ïðàâûõ ÷àñòåé � f — âûñîêèå [6], îöåíêó òðóäîåìêîñòè âñåãî àëãîðèòìà
ìîæíî îñóùåñòâëÿòü îòíîñèòåëüíî ýòèõ çíà÷åíèé. Òîãäà, â ñëó÷àå âûïîë-
íåíèÿ ñîîòíîøåíèÿ (2), ïðåäïî÷òèòåëüíåå èíòåðïîëèðîâàòü ïðàâûå ÷àñòè.
Ýòîò ïîäõîä õîòÿ è ñîïðÿæåí ñ àëãîðèòìè÷åñêèìè ñëîæíîñòÿìè, îäíàêî
èìååò áåçóñëîâíûå ïðåèìóùåñòâà.
4. Âûâîäû. Èñïîëüçîâàíèå îïåðàòîðîâ ïåðåõîäà äëÿ ìåòîäîâ ñ êîíò-
ðîëåì ïîãðåøíîñòè íà øàãå ïîçâîëÿåò îñóùåñòâëÿòü ðàñïàðàëëåëèâàíèå
àëãîðèòìîâ ÷èñëåííîãî ðåøåíèÿ ëèíåéíûõ ñèñòåì ÎÄÓ. Îïåðàòîðû ïåðå-
õîäà äëÿ ñèñòåì îïðåäåëÿþòñÿ îäèí ðàç è äàþò âîçìîæíîñòü â íåñêîëüêî
ðàç (â çàâèñèìîñòè îò ïîðÿäêà òî÷íîñòè èñõîäíîãî ìåòîäà) ñîêðàòèòü
÷èñëî ìàòðè÷íûõ îïåðàöèé, âûïîëíÿåìûõ íà êàæäîì øàãå. Ïðè ýòîì äëÿ
óìíîæåíèÿ ìàòðèö èñïîëüçóþòñÿ ìîäèôèöèðîâàííûå ïàðàëëåëüíûå àëãî-
ðèòìû [3], ïîçâîëÿþùèå â äâà ðàçà ñîêðàòèòü ÷èñëî îáìåíîâ ìåæäó ïðîöåñ-
ñîðíûìè ýëåìåíòàìè, âûïîëíÿåìûõ íà êàæäîì øàãå. Ñîêðàùåíèå ÷èñëà
îáìåíîâ äîñòèãàåòñÿ â ðåçóëüòàòå èçìåíåíèÿ ïîðÿäêà íà÷àëüíîé çàãðóçêè
çíà÷åíèé êîýôôèöèåíòîâ ìàòðèö â ðåøàþùåå ïîëå ìèêðîïðîöåññîðîâ ïàðàë-
ëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåì.
Ïðåäëîæåííûå ïîäõîäû ïîçâîëÿþò èçáåãàòü ïîñëåäîâàòåëüíûõ
ó÷àñòêîâ ðàáîòû ìíîãîïðîöåññîðíûõ âû÷èñëèòåëüíûõ SIMD ñèñòåì.
Îäèí èç íèõ îñíîâàí íà ïðåäâàðèòåëüíîì âû÷èñëåíèè ïðàâûõ ÷àñòåé
íåîäíîðîäíîé ëèíåéíîé ñèñòåìû ÎÄÓ. Îí òåì áîëåå ýôôåêòèâåí, åñëè
òî÷íîñòü ìåòîäà èíòåãðèðîâàíèÿ, ñ ïîìîùüþ êîòîðîãî ðåøàåòñÿ çàäà÷à,
âûñîêà. Äðóãîé ïîäõîä, èñêëþ÷àþùèé ïîñëåäîâàòåëüíûå âû÷èñëåíèÿ,
îñíîâàí íà ïðåäâàðèòåëüíîì èíòåðïîëèðîâàíèè ïðàâûõ ÷àñòåé ñèñòåìû
(1) ñ ïîìîùüþ ñïëàéíîâ. Âûÿâëåííûå ñîîòíîøåíèÿ ìåæäó ïîðÿäêàìè
ïîãðåøíîñòåé ìåòîäîâ ÷èñëåííîãî èíòåãðèðîâàíèÿ ñèñòåìû (1) è ìåòî-
äàìè èíòåðïîëèðîâàíèÿ ïîçâîëÿþò îïðåäåëèòü îïòèìàëüíûé âûáîð ìåòî-
äà ïàðàëëåëüíîé ðåàëèçàöèè ïðàâûõ ÷àñòåé.
Îá îñîáåííîñòÿõ ìîäåëèðîâàíèÿ ëèíåéíûõ äèíàìè÷åñêèõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 71
The approaches are proposed which allow to avoid the sequential sections of multiprocessor
computer work. The first approach is based on the preliminary computation of right parts of the
nonuniform linear system of the ordinary differential equations. The second approach is based on
the preliminary interpolation of right parts of the system by splines. The relations between error
orders of the numerical integration and interpolation methods are found which permit the optimal
choice of the approach to the parallel realization of the system solution.
1. Âîåâîäèí Â. Â. Èíôîðìàöèîííàÿ ñòðóêòóðà àëãîðèòìîâ. — Ì.: Èçä. ÌÃÓ, 1997. — 139 ñ.
2. Feldman L., Dmitrieva O., Gerber S. Abbildung der blockartigen Algoritmen auf die
Parallelrechnerarchitekture // 16 Symposium Simulationstechnik ASIM 2002, Rostock,
10.09 bis 13.09.2002. — Erlangen: Gruner Druck, 2002. — P. 359—364.
3. Äìèòðèåâà Î. À. Àíàëèç ïàðàëëåëüíûõ àëãîðèòìîâ ÷èñëåííîãî ðåøåíèÿ ñèñòåì îáûê-
íîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé ìåòîäàìè Àäàìñà—Áàøôîðòà è Àäàìñà—
Ìîóëòîíà // Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå. — 2000. — 12, ¹ 5. — Ñ. 81—86.
4. Äìèòðèåâà Î. À. Ïàðàëëåëüíîå ìîäåëèðîâàíèå äèíàìè÷åñêèõ îáúåêòîâ ñ ñîñðåäî-
òî÷åííûìè ïàðàìåòðàìè // Òåç. äîêë. XII Þáèëåéíîé ìåæäóíàðîäíîé êîíôåðåíöèè ïî
âû÷èñëèòåëüíîé ìåõàíèêå è ñîâðåìåííûì ïðèêëàäíûì ïðîãðàììíûì ñðåäñòâàì. —
Ì. : ÌÃÈÓ, 2003. — Ñ. 242—243.
5. Äìèòðèåâà Î. À. Ïàðàëëåëüíûå áëî÷íûå ìíîãîøàãîâûå àëãîðèòìû ÷èñëåííîãî ðåøå-
íèÿ ñèñòåì îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé áîëüøîé ðàçìåðíîñòè //
Íàó÷. òð. Äîíåöêîãî ãîñ. òåõí. óí-òà. Ñåðèÿ: Ïðîáëåìû ìîäåëèðîâàíèÿ è àâòîìàòè-
çàöèè ïðîåêòèðîâàíèÿ äèíàìè÷åñêèõ ñèñòåì. Âûï. 15: — ÄîíÃÓ. — Äîíåöê: 2000. —
Ñ. 53—58.
6. Äìèòðèåâà Î. À. Îñîáåííîñòè ïàðàëëåëüíîé ðåàëèçàöèè äèíàìè÷åñêèõ ìîäåëåé //
³ñí. Ñõ³äíîóêðà¿íñüêîãî íàö³îíàëüíîãî óí-òó ³ì. Âîëîäèìèðà Äàëÿ. — 2005. — ¹ 5
(87). — Ñ. 61—68.
7. Äìèòðèåâà Î. À. Ðàñïðåäåëåíèå ðåñóðñîâ ìíîãîïðîöåññîðíûõ ñèñòåì ïðè ðàáîòå ñ
ðàçðåæåííûìè ìàòðèöàìè êîýôôèöèåíòîâ//Ìàòåðèàëû ìåæäóíàð. íàó÷.-òåõí. êîíô.
«Èíòåëëåêòóàëüíûå è ìíîãîïðîöåññîðíûå ñèñòåìû 2005», 26 ñåíò. — 1 îêò. 2005 ã. —
Òàãàíðîã : Èçä. ÒÐÒÓ. — Ñ. 162—166.
8. Ôåëüäìàí Ë. Ï., Äìèòðèåâà Î. À. Ýôôåêòèâíûå ìåòîäû ðàñïàðàëëåëèâàíèÿ ÷èñëåí-
íîãî ðåøåíèÿ çàäà÷è Êîøè äëÿ îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé // Ìà-
òåìàòè÷åñêîå ìîäåëèðîâàíèå. — 2001. — 13, ¹ 7, — Ñ. 66—72.
9. Ãàðàíæà Â. À., Êîíüøèí Â. Í. Ïðèêëàäíûå àñïåêòû ïàðàëëåëüíûõ âûñîêîòî÷íûõ
àëãîðèòìîâ ðåøåíèÿ çàäà÷ âû÷èñëèòåëüíîé ãèäðîäèíàìèêè// Òåç. äîêë. Âñåðîñ. íàó÷.
êîíô. «Ôóíäàìåíòàëüíûå è ïðèêëàäíûå àñïåêòû ðàçðàáîòêè áîëüøèõ ðàñïðåäåëåí-
íûõ ïðîãðàììíûõ êîìïëåêñîâ». — Ì. : Èçä-âî ÌÃÓ, 1998. — Ñ. 34—38.
10. Äæîðò À., Ëþ Ä. ×èñëåííîå ðåøåíèå áîëüøèõ ðàçðåæåííûõ ñèñòåì óðàâíåíèé. —
Ì.: Ìèð, 1984. — 333 ñ.
Ïîñòóïèëà 04.09.06;
ïîñëå äîðàáîòêè 26.12.06
ÄÌÈÒÐÈÅÂÀ Îëüãà Àíàòîëüåâíà, êàíä. òåõí. íàóê, äîöåíò êàôåäðû ïðèêëàäíîé ìàòåìàòèêè è
èíôîðìàòèêè Äîíåöêîãî íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà.  1988 ã. îêîí÷èëà Äîíåöêèé
ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìîäåëèðîâàíèå äèíàìè÷åñêèõ ñèñòåì
áîëüøîé ðàçìåðíîñòè ñ ñîñðåäîòî÷åííûìè ïàðàìåòðàìè, ðàçðàáîòêà ÷èñëåííûõ àëãîðèòìîâ,
îðèåíòèðîâàííûõ íà ðåàëèçàöèþ â ìíîãîïðîöåññîðíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ.
O. À. Äìèòðèåâà
72 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
|