Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу
The procedure for interactive evaluation of complex hierarchical network system components is formalized. Appropriate algorithmic constructions are proposed for an effective implementation of this procedure on multi-core computers and clusters. These constructions determine the prospect of paralleli...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/142308 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334341914263552 |
|---|---|
| author | Polishchuk, O. D. Yadzhak, M. S. |
| author_facet | Polishchuk, O. D. Yadzhak, M. S. |
| author_institution_txt_mv | [
{
"author": "O. D. Polishchuk",
"institution": "Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України, Львів"
},
{
"author": "M. S. Yadzhak",
"institution": "Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України, Львів"
}
] |
| author_sort | Polishchuk, O. D. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-08-27T22:12:50Z |
| description | The procedure for interactive evaluation of complex hierarchical network system components is formalized. Appropriate algorithmic constructions are proposed for an effective implementation of this procedure on multi-core computers and clusters. These constructions determine the prospect of parallelization and take into account the limited possibilities of computing resources. Estimates of complexity and speed up of parallel computations, which confirm the high efficiency of proposed constructions, are given. The obtained results can be used by means of modern software for real-time evaluation of many complex systems, the state and behavior of which constantly change over time, in particular transport systems, energy and life support systems, banking and trade networks, ecosystems of separate regions, etc. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2019.2.09 |
| first_indexed | 2025-07-17T10:24:07Z |
| format | Article |
| fulltext |
О.Д. Поліщук, М.С. Яджак, 2019
Системні дослідження та інформаційні технології, 2019, № 2 105
TIДC
МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ,
ПРОБЛЕМИ І ТЕХНОЛОГІЇ ДОСЛІДЖЕННЯ
СКЛАДНИХ СИСТЕМ
УДК 519.6+625.1
DOI: 10.20535/SRIT.2308-8893.2019.2.09
МЕРЕЖЕВІ СТРУКТУРИ ТА СИСТЕМИ:
ІV. ПАРАЛЕЛЬНЕ ОПРАЦЮВАННЯ РЕЗУЛЬТАТІВ
НЕПЕРЕРВНОГО МОНІТОРИНГУ
О.Д. ПОЛІЩУК, М.С. ЯДЖАК
Анотація. Формалізовано процедуру інтерактивного оцінювання об’єктів
складних ієрархічно-мережевих систем. Для ефективної реалізації цієї проце-
дури на багатоядерних комп’ютерах і кластерах запропоновано відповідні ал-
горитмічні конструкції, що виявляють перспективи розпаралелювання та вра-
ховують обмеженість можливостей обчислювальних ресурсів. Наведено
оцінки складності та приcкорення паралельних обчислень, які підтверджують
високу ефективність використання запропонованих конструкцій. Отримані ре-
зультати можуть бути застосовані для оцінювання в режимі реального часу з
використанням сучасних програмних засобів багатьох складних систем, стан
та поведінка яких неперервно змінюються у часі, зокрема транспортних сис-
тем, систем енерго- та життєзабезпечення, банківських і торговельних мереж,
екосистем окремих регіонів тощо.
Ключові слова: мережева система, ієрархія, неперервний моніторинг, інтер-
активне оцінювання, розпаралелювання, обчислювальне середовище, приско-
рення обчислень.
ВСТУП
Методи теорії оцінювання є потужним інструментом для аналізу стану та
ефективності функціонування складних систем різного типу та призначення
[1–3]. У працях [4–7] запропоновано методику комплексного детермінова-
ного оцінювання складних ієрархічно-мережевих систем (СІМС), яка поля-
гає у поєднанні методів локального, прогностичного, агрегованого та інтер-
активного аналізу стану, якості функціонування та взаємодії елементів
таких систем. Величезні обсяги даних, які описують поведінку реальних
СІМС, потребують розроблення ефективних методів їх оброблення. У пра-
цях [8, 9] запропоновано алгоритми розпаралелювання методів локального
та агрегованого оцінювання СІМС, а у [10] подано загальну схему розпара-
лелювання комплексної методики регулярних (планових) оцінювань [11]
системи. Не менш важливою є проблема оперативного оброблення та аналі-
зу даних, які надходять у процесі неперервного моніторингу системи. Ця
проблема достатньо ефективно вирішується методами інтерактивного оці-
нювання, детально описаними у праці [7]. У більшості випадків її доцільно
О.Д. Поліщук, М.С. Яджак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 2 106
вирішувати в режимі реального часу, тому потрібно виявляти та залучати
можливості паралельних обчислень. Зауважимо, що вхідні дані, які надхо-
дять у процесі неперервного моніторингу системи в центр(и) оброблення,
можуть бути дещо спотвореними внаслідок певних пошкоджень на етапі
передавання або похибок вимірювань (реєстрації). Тому для подальшого
використання цих даних у методах інтерактивного оцінювання їх потрібно
попередньо відфільтрувати, щоб усунути проблемні фрагменти. У зв’язку з
цим побудовано й обгрунтовано низку високопаралельних алгоритмів циф-
рової фільтрації, орієнтованих на різні типи архітектур обчислювальних
засобів спеціального (систолічні і квазісистолічні структури [12]) та універ-
сального (засоби зі структурно-процедурною організацією обчислень [13],
багатоядерні комп’ютери, кластери, гібридні архітектури, високопродуктив-
ні обчислювальні середовища [14] тощо) призначення.
Мета роботи — розпаралелювання методів інтерактивного оцінювання
СІМС і побудова відповідних алгоритмічних конструкцій для ефективної їх
реалізації на підставі використання сучасних програмних та апаратних засобів.
НЕПЕРЕРВНИЙ МОНІТОРИНГ ТА ІНТЕРАКТИВНЕ ОЦІНЮВАННЯ
СКЛАДНИХ ІЄРАРХІЧНО-МЕРЕЖЕВИХ СИСТЕМ
Однією з визначальних особливостей реальних мережевих та ієрархічно-
мережевих систем є рух потоків у них. В одних випадках забезпечення руху
потоків є основною метою утворення та функціонування таких систем
(транспортних, систем ресурсопостачання, торговельних та інформаційних
мереж тощо), у інших — основним процесом, який забезпечує їх життєдія-
льність (рух крові, лімфи, нейроімпульсів у людському тілі, сезонну мігра-
цію тварин і т. ін.). Затримка або зупинення руху потоків може призвести до
збоїв або припинення існування таких систем. Часто проводити планові до-
слідження системи немає змоги через значні матеріальні та фінансові витра-
ти [4, 11]. Це означає, що стан або якість функціонування системи, для якої
під час останнього регулярного огляду отримано позитивні висновки, мо-
жуть перетнути «поріг безпеки» до моменту наступного планового дослі-
дження. Окрім того, існують системи, неперервний моніторинг стану та
процесу функціонування яких є обов’язковою умовою забезпечення нормаль-
ної життєдіяльності або самої системи (люди, що хворіють на діабет або гі-
пертонію), або оточуючого середовища (шкідливі та небезпечні виробни-
цтва, атомні електростанції тощо). Запропоновані у працях [7, 11] методи
інтерактивного оцінювання дозволяють оперативно опрацьовувати резуль-
тати неперервного моніторингу та привертати увагу до найбільш проблем-
них елементів системи, які створюють реальну загрозу для її подальшого
функціонування. Застосування цих методів дає об’єктивні підстави для
пришвидшення або відтермінування наступного планового оцінювання еле-
ментів системи та впорядковує цей процес. Це особливо актуально для ве-
ликих СІМС, оскільки одночасне ретельне дослідження багатьох елементів
системи часто є фізично неможливим.
Інтерактивне оцінювання здійснюється на рівні аналізу взаємодії таких
об’єктів СІМС, як потоки MjPj ,1, і лінія ],[ 0 NSS , що є послідовністю
вузлів iS та ребер ),( 1 iii SSD , Ni ,1 , які їх з’єднують. Тут M — кіль-
Мережеві структури та системи: ІV. Паралельне опрацювання результатів …
Системні дослідження та інформаційні технології, 2019, № 2 107
кість потоків, які проходять лінією за певний проміжок часу. Вважаємо, що
проходження потоків є повністю детермінованим, тобто визначено графік їх
руху. Для спрощення подальшого викладу вважаємо, що відправлення пото-
ку з вузла 0S відбувається без затримок.
Затримка потоку на ребрі може бути спричинена [7] такими обставина-
ми, як незадовільний стан ребра, незадовільний стан потоку, неготовність
вузла до приймання потоку тощо. Лише перша обставина стосується безпо-
середньо стану ребра. Затримка потоку у вузлі може бути спричинена таки-
ми обставинами, як незадовільні стан або організація роботи вузла, незадо-
вільний стан потоку, неможливість відправлення потоку у зв’язку з тим, що
наступне у напрямку руху ребро зайняте іншими потоками тощо. Як і у по-
передньому випадку, лише перша обставина стосується безпосередньо орга-
нізації роботи вузла. Із проходженням потоків по лінії вплив наведених
чинників може послідовно нагромаджуватися та компенсуватися. Деякі з
них мають випадковий характер, а деякі можуть бути регулярними. Нерегу-
лярні збої породжують суттєві проблеми у процесі функціонування СІМС
лише у разі їх масовості і потребують розроблення спеціальних методів ана-
лізу їх виникнення. Наприклад, такі збої можливі під час запровадження
нових великих онлайн-сервісів через недостатню потужність обладнання,
слабку захищеність від комп’ютерних вірусів, неякісне програмне забезпе-
чення, яке підтримує процес їх функціонування тощо. Основною метою ін-
терактивного оцінювання є виявлення і локалізація саме регулярних негатив-
них факторів, які зумовлюють відхилення від установленого графіка руху
потоків.
ФОРМАЛІЗАЦІЯ ПРОЦЕДУРИ ІНТЕРАКТИВНОГО ОЦІНЮВАННЯ
Формально процедуру інтерактивного оцінювання об’єктів СІМС можна
подати як послідовність таких кроків [7].
1. Обчислення локальних оцінок ),,( kij TSPe якості оброблення пото-
ку jP у вузлі iS та ),,( kij TDPe якості проходження потоком jP ребра iD
за період kT тривалістю 0T для KkNiMj ,1;,1;,1 .
2. Побудова на підставі локального оцінювання оцінок першого рівня
узагальнення, а саме:
а) оцінок ),,( K
ij TSPE вузла iS та ),,( K
ij TDPE ребра iD за резуль-
татами оброблення потоку jP протягом періоду KT , де 0KTT K , для
NiMj ,1;,1 ;
б) оцінок ),( ki TSEP вузла iS та ),( ki TDEP ребра iD за результатами
проходження сукупності потоків M
jjP 1}{ P протягом періоду kT для
KkNi ,1;,1 ;
в) оцінок ),( kj TPES оброблення потоку jP у послідовності вузлів
N
iiS 1}{ S та ),( kj TPED проходження потоку ребрами N
iiD 1}{ D , що роз-
міщені на лінії, протягом періоду kT для KkMj ,1;,1 .
О.Д. Поліщук, М.С. Яджак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 2 108
3. Обчислення на підставі оцінок першого рівня оцінок другого рівня
узагальнення, зокрема:
а) оцінок ),( K
j TPES оброблення потоку jP у послідовності вузлів S
та ),( K
j TPED проходження потоку ребрами D, які розміщені на лінії, про-
тягом періоду KT для Mj ,1 ;
б) оцінок ),( K
i TSEP вузла iS та ),( K
i TDEP ребра iD за результата-
ми проходження сукупності потоків P протягом періоду KT для Ni ,1 ;
в) оцінок )(, kTE SP оброблення сукупності потоків P у послідовності
вузлів S та )(, kTE DP проходження цих потоків послідовністю ребер D, роз-
міщених на лінії, за період kT для Kk ,1 .
4. Побудова на підставі оцінок другого рівня оцінок третього рівня уза-
гальнення, а саме:
а) оцінок )(,
KTE SP оброблення сукупності потоків P у послідовності
вузлів S та )(,
KTE DP проходження потоками ребер D, розміщених на лінії,
протягом періоду KT ;
б) агрегованих оцінок )( kTEP проходження сукупності потоків P ліні-
єю протягом періоду kT для Kk ,1 .
5. Обчислення на підставі агрегованих оцінок третього рівня узагаль-
нення усередненої оцінки четвертого рівня )( KTEP проходження сукупнос-
ті потоків P лінією протягом періоду KT .
Детальний аналіз наведеної вище процедури інтерактивного оцінюван-
ня об’єктів СІМС дозволяє зробити такі висновки про підходи до її можли-
вого виконання:
усі оцінки в межах кожного з пунктів 1–4 можуть бути обчислені
одночасно, тобто паралельно;
оцінки кожного з пунктів 2–5 є оцінками певного рівня узагальнен-
ня, при цьому оцінки вищого рівня будуються на підставі оцінок нижчого
рівня узагальнення; отже, можемо говорити про паралельно-послідовний
спосіб оброблення даних;
безпосереднє обчислення самих оцінок грунтується на виконанні ве-
кторних операцій;
процедура оцінювання є сукупністю із 5 фрагментів з різним ступе-
нем паралелізму, тому для попереднього оцінювання паралельних обчис-
лень слід використовувати таку характеристику, як середній ступінь парале-
лізму;
реалізація процедури оцінювання може бути доволі ефективною на
сучасних векторно-конвеєрних обчислювальних системах, які мають ієрар-
хічну структуру і натепер є одним з найпотужніших (хоча і дорогих) обчис-
лювальних засобів, а також на кластерах і багатоядерних комп’ютерах.
Очевидно, що залежно від конкретної мети оцінювання та типу дослі-
джуваної складної системи може реалізовуватись не вся описана вище про-
Мережеві структури та системи: ІV. Паралельне опрацювання результатів …
Системні дослідження та інформаційні технології, 2019, № 2 109
цедура, а лише окремі її кроки або деякі фрагменти цих кроків. У цій роботі
розглянемо особливості паралельної реалізації всієї наведеної вище проце-
дури інтерактивного оцінювання об’єктів СІМС.
АЛГОРИТМІЧНІ КОНСТРУКЦІЇ ТА ЇХ АНАЛІЗ
Для виконання описаної вище процедури інтерактивного оцінювання СІМС
розглянемо алгоритмічні конструкції організації паралельних обчислень у
разі, коли немає обмежень на обсяг (кількість ядер, процесорних елементів,
обчислювальних вузлів; ємність оперативної пам’яті вузла) обчислювальних
ресурсів і коли такі обмеження є суттєвими. У першому випадку зможемо
виявити й оцінити потенційний паралелізм операцій у процедурі оцінюван-
ня, а в другому випадку — більш ретельно підійти до реалізації згаданої
процедури на конкретному паралельному комп’ютері з наперед визначеним
обсягом обчислювальних ресурсів. Для задання паралельних гілок будемо
використовувати примітиви fork, join (розгалуження, злиття) [9, 15]. У разі
відсутності обмежень на обсяг обчислювальних ресурсів пропонована алго-
ритмічна конструкція для виконання процедури інтерактивного оцінювання
складається з чотирьох паралельних фрагментів і має такий вигляд:
,),...,,( 00
2
0
1 0
joinhhhfork l
,),...,,( 11
2
1
1 1
joinhhhfork l
,),...,,( 22
2
2
1 2
joinhhhfork l (1)
,),...,,( 33
2
3
1 3
joinhhhfork l
4h ,
де 0
0
' ,1', lihi ; 1
1
' ,1', ljh j ; 2
2
' ,1', lkhk ; 3
3
' ,1', llhl — паралельні гілки, у
яких обчислюються відповідно локальні оцінки та оцінки першого, другого і
третього рівнів узагальнення; 4h — фрагмент, у якому обчислюється оцінка
четвертого рівня узагальнення )( KTEP ; MNKl 20 ; ))((21 NKKNMl ;
)2(22 KNMl ; 23 Kl .
Згідно з працею [7] кожна з локальних оцінок ),,( kij TSPe ,
),,( kij TDPe , ;,1;,1 NiMj Kk ,1 може набувати за уточненою баль-
ною шкалою одне із чотирьох значень, які можна обчислювати одночасно.
Тоді для реалізації обчислень у кожній з гілок 0
0
' ,1', lihi потрібно виконати
щонайбільше 8 арифметичних операцій (7 операцій додавання і 1 операцію
ділення).
Обчислення оцінок першого рівня узагальнення ),,( K
ij TSPE ,
),,( K
ij TDPE ; оцінок другого рівня узагальнення ),( K
j TPES , ),( K
j TPED ,
),( K
i TSEP , ),( K
i TDEP для NiMj ,1;,1 ; оцінок третього рівня уза-
О.Д. Поліщук, М.С. Яджак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 2 110
гальнення )(,
KTE SP , )(,
KTE DP та оцінок четвертого рівня узагальнення
)( KTEP потребує виконання K арифметичних операцій ((K–1) операцію до-
давання та 1 операцію ділення).
Також установлено, що для обчислення оцінок першого рівня узагаль-
нення ),( ki TSEP , ),( ki TDEP , ),( kj TPES , ),( kj TPED та оцінок другого
рівня узагальнення )(, kTE SP , )(, kTE DP для Ni ,1 ; KkMj ,1;,1 необ-
хідно виконати 13 M арифметичну операцію (M операцій множення,
2(M–1) операцій додавання та 1 операцію ділення). Тут слід зауважити, що
для обчислення оцінок KkTETE kk ,1);(),( ,, DPSP пропонується й інший
підхід [7], який потребує виконання 13 N арифметичну операцію (N опе-
рацій множення, 2(N–1) операцій додавання та 1 операцію ділення).
Обчислення оцінок третього рівня узагальнення KkTE k ,1),( P зво-
диться до виконання 5 арифметичних операцій (2 операцій множення,
2 операцій додавання та 1 операції ділення).
На підставі викладеного отримуємо, що загалом для реалізації конструк-
ції (1) потрібно виконати
8}5,max{},13,13max{},13{max KKKNMKM (2)
паралельних операцій.
У разі послідовної реалізації описаної вище процедури інтерактивного
оцінювання потрібно виконати
KMNKKMMNK 4)(6636 2 (3)
арифметичних операцій.
Припустімо, що 321 ,, ttt — відповідно час виконання арифметичних
операцій додавання, множення та ділення і при цьому зазвичай 321 ttt .
Використовуючи наведені оцінки складності обчислень (2) та (3) і поклавши
LKNM (для реальних СІМС L є доволі великим), отримуємо відпо-
відно вирази для часу виконання процедури інтерактивного оцінювання у
послідовному режимі та на підставі застосування паралельно-послідовного
способу згідно з алгоритмічною конструкцією (1):
)(3)972()32(2))(217(2 13312321
2
321
3 tttttLtttLtttL ;
3121 5)3(2 ttttL .
Далі, вважаючи, що L є якзавгодно великим, отримуємо, що приско-
рення обчислень за (1) є близьким до значення
CBLAL 2 ,
де
21
31
3
211
2
tt
tt
A
;
21
213
3
23
1
tt
ttt
B
;
21
123
3
55,05,4
5,0
tt
ttt
C
.
Звідси випливає висновок, що за зроблених вище припущень стосовно
часу виконання арифметичних операцій та KNM ,, прискорення обчислень
може вимірюватися десятками тисяч і більше разів.
Мережеві структури та системи: ІV. Паралельне опрацювання результатів …
Системні дослідження та інформаційні технології, 2019, № 2 111
Отже, алгоритмічна конструкція (1) дозволяє оцінити потенційні мож-
ливості розпаралелювання процедури інтерактивного оцінювання. Хоча за-
галом кожен із паралельних її фрагментів має різну кількість автономних
гілок і в межах цих фрагментів гілки можуть мати різну складність, викори-
стання згаданої конструкції в окремих випадках дасть можливість значно
прискорити обчислювальний процес на обчислювальних засобах як зі спіль-
ною, так і з розподіленою пам’яттю.
У разі обмеження обчислювальних ресурсів для реалізації процедури
інтерактивного оцінювання на сучасних паралельних засобах можна скорис-
татися конструкцією:
,),...,,( 00
2
0
1 joingggfork p
,),...,,( 11
2
1
1 joingggfork p
,),...,,( 22
2
2
1 joingggfork p (4)
,),...,,( 33
2
3
1 joingggfork p
4h ,
де p — кількість паралельних гілок, які реально можна одночасно виконати
на наявній обчислювальній системі; plgl ,1,0 — паралельні гілки, у кож-
ній з яких обчислюється pl /0 локальних оцінок; 1
lg , 2
lg , 3
lg ; pl ,1 — па-
ралельні гілки, у яких обчислюється відповідно pl /1 , pl /2 , pl /3 оцінок
першого, другого і третього рівнів узагальнення. Тут вважається, що
3210 ,,, llll є кратними до p. Обчислення оцінок згідно з конструкцією (4)
можна організувати так, щоб гілки в межах кожного з паралельних фрагме-
нтів мали приблизно однакову складність.
Ураховуючи наведені вище формули для складності обчислення кожної
оцінки, установимо час виконання кожного із чотирьох паралельних фраг-
ментів 3210 ,,, UUUU у конструкції (4), а, отже, і загальний час U реалізації
усієї конструкції. Оскільки обчислення всіх локальних оцінок мають при-
близно однакову складність, то звідси випливає, що час реалізації обчислень
у кожній з гілок plgl ,1,0 набуває значення
pttMNKU /)212(2 310 .
Оцінки першого рівня загальності за складністю можна поділити на два
типи. Обчислення оцінок окремого типу розподілимо між p гілками. Отже,
для реалізації обчислень у кожній з гілок 1
lg , pl ,1 потрібен час:
pttKMKNttMNttKMttMNKU /))2)(()()2()3((2 131321
2
211 .
Оцінки другого рівня узагальнення за складністю можна поділити на
три типи. Аналогічно обчислення оцінок окремого типу розподілимо між p
гілками. Унаслідок цього отримаємо час реалізації обчислень у кожній з гі-
лок 2
lg , pl ,1 :
О.Д. Поліщук, М.С. Яджак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 2 112
pttKttNMttKMKNU /))2(2))(()3)(((2 1313212 .
За складністю оцінки третього рівня узагальнення можна поділити на
два типи. Обчислення K оцінок одного типу розподілимо між p гілками. Од-
нак дві з цих гілок будуть найдовшими, оскільки в них ще обчислювати-
муться по одній оцінці зі складністю K. Отже, для виконання обчислень у
кожній з двох найдовших гілок з набору 3
lg , pl ,1 потрібен час:
1313213 )/))(2(( tttptttKU .
У наведених вище формулах для часу вважається, що M, N, K є кратни-
ми до p.
Таким чином, обчислення згідно з конструкцією (4) будуть виконані за
час:
))(()2()215((2 32121
2
321 tttKNKMttKMtttMNKU
)(2/)))3(5,2())(( 1312313 ttptpttKttNMMN . (5)
Зауважимо, що у наведеній формулі враховано час 4U обчислень у
фрагменті 4h :
314 )1( ttKU .
На підставі формул (3) і (5) за умов LKNM , pL , для якзав-
годно великого L отримуємо, що пришвидшення паралельних обчислень у
даному разі є близьким до свого оптимального значення, тобто до p.
Отже, конструкція (4) дозволяє доволі ефективно реалізовувати мето-
дику інтерактивного оцінювання на наявних обчислювальних засобах зі
спільною та розподіленою пам’яттю з наперед відомим (обмеженим) обся-
гом ресурсів.
Зауважимо, що певні резерви розпаралелювання містять і безпосеред-
ньо фрагменти обчислення оцінок, оскільки в них усюди використовується
операція скалярного добутку векторів, яка ефективно реалізовується у сис-
темах на базі векторно-конвеєрних процесорів. Кластерні системи та систе-
ми зі спільною пам’яттю, побудовані на таких процесорах, натепер одні з
найпродуктивніших у своєму класі, проте є доволі дорогими [16] обчислю-
вальними засобами.
ВИСНОВКИ
Ця робота є продовженням циклу робіт [11, 17, 18], у яких досліджуються
мережеві структури та системи, а також низки робіт [8–10, 12–14, 19, 20],
присвячених проблемам ефективної реалізації методики комплексного оці-
нювання СІМС на сучасних паралельних обчислювальних системах різної
архітектури. Зокрема, формалізовано процедуру інтерактивного оцінювання
об’єктів таких систем у вигляді послідовності кроків. Наведено та дослідже-
но алгоритмічні конструкції для паралельної реалізації цієї процедури.
Отримані оцінки прискорення підтверджують їх високу ефективність.
Мережеві структури та системи: ІV. Паралельне опрацювання результатів …
Системні дослідження та інформаційні технології, 2019, № 2 113
Оскільки запропоновані конструкції є сукупністю фрагментів з автономних
паралельних гілок, то їх реалізація на сучасних обчислювальних системах зі
спільною (багатоядерні комп’ютери) та розподіленою (кластери, гібридні
архітектури, високопродуктивні обчислювальні середовища) пам’яттю не
викликає труднощів. Отримані в роботі результати можуть бути використані
для оцінювання в режимі реального часу СІМС з різних предметних галу-
зей, оскільки сама методика оцінювання є доволі універсальною. Указано
деякі можливі шляхи подальшого прискорення обчислень під час реалізації
процедури інтерактивного оцінювання.
ЛІТЕРАТУРА
1. Owen C.L. Evaluation of complex systems / C.L. Owen // Designe Studies. — 2007.
— 28, N 1. — P. 73–101.
2. Norros L. Usability evaluation of complex systems / L. Norros, P. Saviola // STUK,
Helsinki, 2004. — 44 p.
3. Bar-Yam Y. About Engineering Complex Systems: Multiscale Analysis and Evolu-
tionary Engineering. In: Engineering Self-Organising Systems / Ed. by Y. Bar-
Yam // Heidelberg: Springer-Verlag, 2005. — P. 16–31.
4. Поліщук Д.О. Комплексне детерміноване оцінювання складних ієрархічно-
мережевих систем: І. Опис методики / Д.О. Поліщук, О.Д. Поліщук,
М.С. Яджак // Системні дослідження та інформаційні технології. — 2015.
— № 1. — С. 21–31.
5. Поліщук Д.О. Комплексне детерміноване оцінювання складних ієрархічно-
мережевих систем: ІI. Локальне та прогностичне оцінювання /
Д.О. Поліщук, О.Д. Поліщук, М.С. Яджак // Системні дослідження та інфо-
рмаційні технології. — 2015. — № 2. — С. 26–38.
6. Поліщук Д.О. Комплексне детерміноване оцінювання складних ієрархічно-
мережевих систем: ІII. Агреговане оцінювання / Д.О. Поліщук,
О.Д. Поліщук, М.С. Яджак // Системні дослідження та інформаційні техно-
логії. — 2015. — № 4. — С. 20–31.
7. Поліщук Д.О. Комплексне детерміноване оцінювання складних ієрархічно-
мережевих систем: ІV. Інтерактивне оцінювання / Д.О. Поліщук,
О.Д. Поліщук, М.С. Яджак // Системні дослідження та інформаційні техно-
логії. — 2016. — № 1. — С. 7–16.
8. Поліщук О.Д. Локальне оцінювання якості функціонування складних систем на
підставі паралельних обчислень / О.Д. Поліщук, М.І. Тютюнник, М.С. Яд-
жак // Відбір і обробка інформації. — 2010. — Вип. 32 (108). — C. 119–124.
9. Поліщук О.Д. Оцінювання якості функціонування складних систем на основі
паралельної організації обчислень / О.Д. Поліщук, М.І. Тютюнник,
М.С. Яджак // Відбір і обробка інформації. — 2007. — Вип. 26 (102). —
С. 121–126.
10. Яджак М.С. Оптимізація методики комплексного оцінювання складних систем
на підставі паралельних обчислень / М.С. Яджак, О.Д. Поліщук, М.І. Тю-
тюнник // Інформатика та математичні методи в моделюванні. — 2016. —
№ 4. — С. 347–356.
11. Поліщук О.Д. Мережеві структури та системи: ІІІ. Ієрархії та мережі / О.Д. По-
ліщук, М.С. Яджак // Системні дослідження та інформаційні технології. —
2018. — № 4. — С. 82–95.
12. Анисимов А.В. Построение оптимальных алгоритмов массовых вычислений
в задачах цифровой фильтрации /А.В. Анисимов, М.С. Яджак // Кибернети-
ка и системный анализ. — 2008. — № 4. — С. 3–14.
О.Д. Поліщук, М.С. Яджак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 2 114
13. Яджак М.С. Оптимальный алгоритм решения задачи цифровой фильтрации с
использованием адаптивного сглаживания / М.С. Яджак, М.И. Тютюнник //
Кибернетика и системный анализ. — 2013. — № 3. — С. 142–151.
14. Яджак М.С. Паралельні алгоритми розв’язання просторової задачі цифрової
фільтрації даних / М.С. Яджак // Інформатика та математичні методи в мо-
делюванні. — 2017. — № 3. — С. 234–239.
15. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный
подход / В.А. Вальковский. — М.: Радио и связь, 1989. — 176 с.
16. Рейтинговий список найпотужніших систем світу [Електронний ресурс]. —
Режим доступу: www.top500.org.
17. Поліщук О.Д. Мережеві структури та системи: І. Потокові характеристики
складних мереж / О.Д. Поліщук, М.С. Яджак // Системні дослідження та ін-
формаційні технології. — 2018. — № 2. — С. 42–54.
18. Поліщук О.Д. Мережеві структури та системи: ІІ. Серцевини мереж та мульти-
плексів / О.Д. Поліщук, М.С. Яджак // Системні дослідження та інформа-
ційні технології. — 2018. — № 3. — С. 38–51.
19. Polishchuk O. Issues of Regional Development and Evaluation Problems /
O. Polishchuk, D. Polishchuk, M. Yadzhak, M. Tyutyunnyk // AASCIT Commu-
nications. — 2015. — 2, N 4. — P. 115–120.
20. Polishchuk O. Big Data Processing in Complex Hierarchical Network Systems /
O. Polishchuk, D. Polishchuk, M. Yadzhak, M. Tyutyunnyk // arXiv preprint
arXiv: 1603.00633. — 2016. — 7 p.
Надійшла 18.09.2018
|
| id | journaliasakpiua-article-142308 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:24:07Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/15/b739c3db4a77d00a15683aef3c50b515.pdf |
| spelling | journaliasakpiua-article-1423082019-08-27T22:12:50Z Network structures and systems: IV. Parallel processing of continuous monitoring results Сетевые структуры и системы: IV. Параллельная обработка результатов непрерывного мониторинга Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу Polishchuk, O. D. Yadzhak, M. S. network system hierarchy continuous monitoring interactive evaluation parallelization computer environment speed up of computations сетевая система иерархия непрерывный мониторинг интерактивное оценивание распараллеливание вычислительная среда ускорение вычислений мережева система ієрархія неперервний моніторинг інтерактивне оцінювання розпаралелювання обчислювальне середовище прискорення обчислень The procedure for interactive evaluation of complex hierarchical network system components is formalized. Appropriate algorithmic constructions are proposed for an effective implementation of this procedure on multi-core computers and clusters. These constructions determine the prospect of parallelization and take into account the limited possibilities of computing resources. Estimates of complexity and speed up of parallel computations, which confirm the high efficiency of proposed constructions, are given. The obtained results can be used by means of modern software for real-time evaluation of many complex systems, the state and behavior of which constantly change over time, in particular transport systems, energy and life support systems, banking and trade networks, ecosystems of separate regions, etc. Формализировано процедуру интерактивного оценивания объектов сложных иерархически-сетевых систем. Для эффективной реализации этой процедуры на многоядерных компьютерах и кластерах предложены соответствующие алгоритмические конструкции, определяющие перспективы распараллеливания и учитывающие ограниченность возможностей вычислительных ресурсов. Приведены оценки сложности и ускорения параллельных вычислений, подтверждающие высокую эффективность применения предложенных конструкций. Полученные результаты могут быть использованы для оценивания в режиме реального времени с применением современных программных средств многих сложных систем, состояние и поведение которых непрерывно изменяются во времени, в частности транспортных систем, систем энерго- и жизнеобеспечения, банковских и торговых сетей, экосистем отдельных регионов и т. п. Формалізовано процедуру інтерактивного оцінювання об’єктів складних ієрархічно-мережевих систем. Для ефективної реалізації цієї процедури на багатоядерних комп’ютерах і кластерах запропоновано відповідні алгоритмічні конструкції, що виявляють перспективи розпаралелювання та враховують обмеженість можливостей обчислювальних ресурсів. Наведено оцінки складності та приcкорення паралельних обчислень, які підтверджують високу ефективність використання запропонованих конструкцій. Отримані результати можуть бути застосовані для оцінювання в режимі реального часу з використанням сучасних програмних засобів багатьох складних систем, стан та поведінка яких неперервно змінюються у часі, зокрема транспортних систем, систем енерго- та життєзабезпечення, банківських і торговельних мереж, екосистем окремих регіонів тощо. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/142308 10.20535/SRIT.2308-8893.2019.2.09 System research and information technologies; No. 2 (2019); 105-114 Системные исследования и информационные технологии; № 2 (2019); 105-114 Системні дослідження та інформаційні технології; № 2 (2019); 105-114 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/142308/175467 Copyright (c) 2021 System research and information technologies |
| spellingShingle | мережева система ієрархія неперервний моніторинг інтерактивне оцінювання розпаралелювання обчислювальне середовище прискорення обчислень Polishchuk, O. D. Yadzhak, M. S. Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу |
| title | Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу |
| title_alt | Network structures and systems: IV. Parallel processing of continuous monitoring results Сетевые структуры и системы: IV. Параллельная обработка результатов непрерывного мониторинга |
| title_full | Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу |
| title_fullStr | Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу |
| title_full_unstemmed | Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу |
| title_short | Мережеві структури и системи: IV. Паралельне опрацювання результатів неперервного моніторингу |
| title_sort | мережеві структури и системи: iv. паралельне опрацювання результатів неперервного моніторингу |
| topic | мережева система ієрархія неперервний моніторинг інтерактивне оцінювання розпаралелювання обчислювальне середовище прискорення обчислень |
| topic_facet | network system hierarchy continuous monitoring interactive evaluation parallelization computer environment speed up of computations сетевая система иерархия непрерывный мониторинг интерактивное оценивание распараллеливание вычислительная среда ускорение вычислений мережева система ієрархія неперервний моніторинг інтерактивне оцінювання розпаралелювання обчислювальне середовище прискорення обчислень |
| url | https://journal.iasa.kpi.ua/article/view/142308 |
| work_keys_str_mv | AT polishchukod networkstructuresandsystemsivparallelprocessingofcontinuousmonitoringresults AT yadzhakms networkstructuresandsystemsivparallelprocessingofcontinuousmonitoringresults AT polishchukod setevyestrukturyisistemyivparallelʹnaâobrabotkarezulʹtatovnepreryvnogomonitoringa AT yadzhakms setevyestrukturyisistemyivparallelʹnaâobrabotkarezulʹtatovnepreryvnogomonitoringa AT polishchukod mereževístrukturiisistemiivparalelʹneopracûvannârezulʹtatívneperervnogomonítoringu AT yadzhakms mereževístrukturiisistemiivparalelʹneopracûvannârezulʹtatívneperervnogomonítoringu |