Дисертації (ІСТ)
Постійне посилання зібрання
У зібранні розміщено дисертації, які захищені працівниками кафедри.
Переглянути
Нові надходження
Документ Відкритий доступ Методи підвищення ефективності узгодженості даних в інформаційних системах(КПІ ім. Ігоря Сікорського, 2024) Нікітін, Валерій Андрійович; Крилов, Євген ВолодимировичНікітін В. А. Методи підвищення ефективності узгодженості даних в інформаційних системах. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 126 – Інформаційні системи та технології в галузі знань 12 – Інформаційні технології. – Національний Технічний Університет України «Київський Політехнічний Інститут імені Ігоря Сікорського», Київ, 2024. Дисертаційна робота присвячена розробці методів для розподілених документоорієнтованих баз даних, які дозволяють пришвидшити узгодження даних та покращити колізійну стійкість в процесі пошуку неузгоджених даних в різноманітних мережевих інформаційних системах, таких як, IoT, гетерогенні мультикомп’ютерні системи, аналітичні системи органів адміністративного управління, фінансові системи, дослідження екологічної безпеки та природокористування та інші. Також, було реалізовано спеціальне програмне забезпечення для проведення дослідів. В результаті виконання дисертаційної роботи було отримано такі результати. Розроблено метод забезпечення узгодженості даних у розподілених нереляційних документо-орієнтованих базах даних з використанням транзакційного годинника. Він отримує транзакції від клієнтських додатків та зберігає їх у відповідних чергах. Черги опрацьовуюються в залежності від пріоритету транзакції. При найвищому пріоритеті черга опрацьовується раніше, в порівнянні з тими, які мають нижчий пріоритет. Це дозволяє виділяти критично важливі дані (такі, як фінансові транзакції), які мають бути опрацьовані першочергово. При опрацюванні черги, транзакційний годинник об’єднує транзакції в результуючу транзакцію. Для цього він використовує час створення транзакції, що дозволяє глобально впорядковувати та об’єднувати їх в тому порядку, в якому вони були створені, а не отримані годинником. Після отримання результуючої транзакції, вона передається іншим реплікам, на яких відбувається запис. Слід зазначити, що при використанні транзакційного годинника, операції читання відбуваються напряму з реплік, що дозволяє зменшити навантаження на хостову машину. Удосконалено метод активної антиентропії з використанням спектрального фільтру Блума та алгоритму хешування замість дерева Меркла. Його створення обумовлено тим, що класичний механізм активної антиентропії використовує багато затратних операцій хешування. Також, при хешуванні великої кількості даних збільшується вірогідність колізій, яка може вплинути на вчасну ідентифікацію неузгодженості. Якщо таке буде відбуватися, то система може знаходитись у неузгодженому стані через те, що запуск процедури узгодження розпочнеться пізніше. Тому, для розподілених нереляційних документо-орієнтованих баз даних було вирішено використати протокол пліток, який полягає у децентралізованому способі взаємодії вузлів. Це забезпечує надійність, в порівнянні з централізованим підходом, оскільки виведення з ладу одного вузла не вплине на доступність системи. Проблема використання централізованого підходу полягає в тому, що виведення головного вузла з ладу вимагає певної затримки через використання консенсусного протоколу, який використовується для обрання нового головного вузла з існуючих реплік. Децентралізований підхід дозволяє інформаційній системі бути доступною для операцій запису, хоча це ускладнює підтримку узгодженості. Для пошуку неузгодженостей використовується певний знімок, який складається зі спектрального фільтру Блума та хеш-значення. Спеціально для розробленого методу активної антиентропії було модифіковано алгоритм формування спектрального фільтру Блума, який дозволяє пришвидшити ідентифікування неузгодженісті даних в методі активної антиентропії. Швидкість формування спектрального фільтру Блума було збільшено через використання алгоритму на основі простих чисел замість використання хеш-функцій. Результати дослідів показують, що розроблений алгоритм має вищу колізійну стійкість, ніж при використанні однієї хеш-функції та вищу швидкодію у порівнянні з використанням декількох функцій хешування. Також, спеціально для розробленого методу активної антиентропії було розроблено спосіб хешування, який стійкий до колізій. Його мета полягає у зменшенні кількості колізій при хешуванні даних, які відрізняються за розміром. Це є дуже важлим для активної антиентропії, оскільки дозволяє вчасно знайти неузгодженість. Реалізовано спеціальний сервіс транзакційного годинника із власним програмним інтерфейсом для можливості застосування в інформаційних системах розробленого методу забезпечення узгодженості з використанням транзакційного годинника з розподіленою базою даних MongoDB. Реалізовано спеціальний сервіс активної антиентропії із власним програмним інтерфейсом для використання в інформаційних системах розробленого методу активної антиентропії з розподіленою базою даних MongoDB. Реалізовано прототип фінансової інформаційної системи, в якій розподілена база даних складається з восьми вузлів. З її використанням були отримані результати дослідження розроблених методів забезпечення узгодженості даних. Програмний інтерфейс було реалізовано з використанням мови програмування Python3. Для створення тестового середовища використовувався Docker та docker-compose для оркестрації необхідними компонентами. Дисертаційна робота складається зі вступу, 3 розділів, загальних висновків, списку використаних джерел із 49 найменувань та 6 додатків. Загальний обсяг дисертації становить 165 сторінок, з яких 133 сторінки основного тексту, містить 76 рисунків та 5 таблиць.Документ Відкритий доступ Методи та засоби управління автономними логістичними кіберфізичними системами з використанням технологій штучного інтелекту(КПІ ім. Ігоря Сікорського, 2024) Головатенко, Ілля Анатолійович; Писаренко, Андрій ВолодимировичГоловатенко І. А. Методи та засоби управління автономними логістичними кіберфізичними системами з використанням технологій штучного інтелекту. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 126 – Інформаційні системи та технології з галузі знань 12 – Інформаційні технології. – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2024. Дисертаційна робота присвячена розробленню методів та засобів планування логістики автономних кіберфізичних систем. Сучасний світ швидко розвивається, особливо у сфері інформаційних технологій. Застосування штучного інтелекту в кіберфізичних системах є ключовим фактором в цьому розвитку. Динамічні зміни вимагають нових підходів до управління, і саме це робить тему дослідження вкрай актуальною. Автономні логістичні кіберфізичні системи стають все більш складними та розгалуженими. Ефективне управління ними стає викликом через розмаїття параметрів, що впливають на їх функціонування. Застосування методів штучного інтелекту може значно полегшити цей процес та підвищити його результативність. Ефективне управління логістичними кіберфізичними системами важливе для економії ресурсів, часу та коштів. Застосування технологій штучного інтелекту може сприяти оптимізації процесів, підвищенню продуктивності та зниженню витрат. Автономні системи широко використовуються в різних галузях, включаючи транспорт, виробництво, медицину тощо. Збільшення автономії таких систем породжує нові виклики, такі як безпека, надійність та ефективність. Дослідження, присвячене вирішенню зазначених проблем вкрай важливе, оскільки воно дозволяє вдосконалити функціонування та впровадження автономних логістичних кіберфізичних систем на міжнародному рівні. Застосування штучного інтелекту в управлінні кіберфізичними системами вимагає глибокого розуміння інтеграції різноманітних технологій. Розв’язання цієї проблеми не тільки сприяє розвитку конкретного напряму, але й робить внесок у загальний розвиток наукової думки та суспільства в цілому. Отже, актуальність представленої дисертаційної роботи визначається потребою сучасного світу в ефективних методах управління складними автономними логістичними кіберфізичними системами, що використовують технології штучного інтелекту. Результати дослідження мають значущий вплив на розвиток інформаційних технологій та покращення функціонування важливих галузей господарства та науки. Метою наукового дослідження є підвищення ефективності планування в реальному часі логістики автономних транспортних засобів, як складової кіберфізичної системи з використанням моделей навчання з підкріпленням. Зважаючи на аналіз різноманітних методів побудови кіберфізичних систем у галузі автономної логістики, перший розділ розглядає та систематизує ці підходи. Зокрема, він досліджує та аналізує існуючі методики та інструменти, що використовуються в проектуванні та моделюванні кіберфізичних систем, зокрема в контексті автономних транспортних засобів. Другий розділ присвячений аналізу методів планування логістичних маршрутів та їхнього впливу на ефективність та безпеку автономних транспортних систем. Він досліджує існуючі методи та їхню ефективність, а також вказує на недоліки та можливості вдосконалення. Розділ охоплює розробку та вдосконалення методів контролю та керування кіберфізичними системами з метою підвищення їхньої надійності та ефективності. Цей розділ вивчає принципи функціонування кіберфізичних систем та методи їхнього оптимізованого управління. У третьому розділі розглядається метод побудови безпечних логістичних маршрутів, що базується на модифікації та розвитку алгоритму A*. Даний розділ описує впровадження нових функціональних можливостей та алгоритмів для забезпечення безпеки та ефективності автономних транспортних засобів. Розділ, окрім іншого, присвячений розробці архітектури кіберфізичних систем, яка включає в себе застосування «хмарних» технологій, мікросервісів та ефективних методів зберігання даних для підвищення швидкодії, покращення відмовостійкості та поліпшення надійності усієї системи. Четвертий розділ описує експериментальне підтвердження отриманих результатів шляхом комп’ютерного моделювання кіберфізичних логістичних систем. Він демонструє практичне застосування розроблених методів та алгоритмів у реальних умовах, що дає можливість перевірити їх ефективність та працездатність. Результати, отримані у дисертаційному дослідженні, містять наукову новизну: 1. розроблено новий метод планування шляху для автономних логістичних кіберфізичних систем, що включає в себе модифікації алгоритму A*, які забезпечують управління рухом автономних транспортних засобів у логістичних кіберфізичних системах, з використанням моделей навчання з підкріпленням, для поліпшення прийняття рішень у реальному часі; 2. удосконалено модельно-орієнтований метод до моделювання кіберфізичних систем, який, на відміну від існуючих, передбачає симбіоз метамоделювання та моделей бізнес-процесів, що дозволяє визначати ієрархічні структури, залежності між різними елементами кіберфізичних систем, включаючи аспекти їхньої динаміки, ресурсного управління та взаємодії з оточуючим середовищем; та забезпечує ефективність таких систем і їх відповідність стратегічним цілям; 3. дістав подальшого розвитку метод до побудови адаптивної логістичної системи на основі інтеграції засобів штучного інтелекту задля оптимізації планування шляху та уникнення перешкод, що, на відміну від існуючих, дозволяє логістичній системі гнучко адаптуватися до змін у внутрішніх та зовнішніх умовах та вчасно уникати перешкоди, що визначається високою продуктивністю та задоволенням вимог сучасного логістичного середовища, де швидкість реагування та ефективне управління ресурсами визначають успіх системи. Практичне значення результатів дисертаційного дослідження полягає у розроблені моделі кіберфізичної логістичної системи, що здатна керувати автономним об’єктами. Розроблені моделі навчання з підкріпленням та методи планування шляху дозволяють підвищити ефективність та точність планування маршрутів для автономних транспортних засобів, зменшуючи час доставки та оптимізуючи використання ресурсів. Розроблені методи планування шляху з урахуванням безпекових обмежень дозволяють уникнути небезпек та аварій на дорогах, забезпечуючи безпеку як для автономних транспортних засобів, так і для інших учасників дорожнього руху. Врахування обмежень при плануванні логістичного шляху дозволяє підвищити ефективність та оптимізувати процеси доставки, зменшуючи затрати часу та ресурсів на перевезення вантажів. Результати впроваджені в навчальний процес кафедри інформаційних систем та технологій при підготовці методичних матеріалів до проведення занять за освітнім компонентом «Оптимальні системи». Результати дисертаційної роботи опубліковано у 6 наукових публікаціях, серед яких 1 стаття у періодичному науковому виданні, проіндексованому у Web of Science Core Collection та Scopus базах даних, 2 статті у фахових наукових журналах категорії «Б», 2 публікації у матеріалах міжнародних наукових конференцій, 1 розділ у колективній монографії у співавторстві з науковим керівником, проіндексованій у базі Scopus.Документ Відкритий доступ Інформаційна технологія виявлення рухомих об'єктів у тривимірному просторі з використанням рою гетерогенних БПЛА(КПІ ім. Ігоря Сікорського, 2024) Альбрехт, Йосип Омелянович; Писаренко, Андрій ВолодимировичАльбрехт Й.О. Інформаційна технологія виявлення рухомих об'єктів у тривимірному просторі з використанням рою гетерогенних БПЛА – Кваліфікаційна наукова праця на правах рукопису Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 126 – Інформаційні системи та технології. – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2024. У першому розділі зосереджується увага на інформаційних технологіях, які є важливим аспектом сучасного суспільства, визначаючи розвиток та функціонування різних сфер людської діяльності. Описується базування інформаційних технологій на обробці, передачі та зберіганні даних за допомогою комп'ютерів та інших технічних засобів. Також звертається увага на ключову характеристику інформаційних технологій - швидкість обробки та передачі даних, яка зросла завдяки постійному розвитку апаратних та програмних засобів. Такі технології використовуються в різних галузях, включаючи бізнес, медицину, науку та освіту. Крім того, розглядається роль інформаційних технологій у забезпеченні безпеки даних, зокрема захист від несанкціонованого доступу та кібератак. Описуються концепції "Інтернету речей", де об'єкти оточуючого середовища обладнані сенсорами та здатні обмінюватися даними. Розділ також охоплює кіберфізичні інформаційні технології, що представляють інтеграцію фізичних систем з інформаційними та комунікаційними технологіями. Цей підхід створює єдину екосистему, спрямовану на створення інтелектуальних, автономних систем, які поєднують реальний світ з віртуальним. Зазначається, що кіберфізичні інформаційні технології дозволяють взаємодіяти з фізичними об'єктами в реальному часі, використовуючи розумні алгоритми, давачі та мережі зв'язку. Такі технології включають в себе використання розумних сенсорів, збір даних з фізичних об'єктів та їхню інтеграцію з хмарними системами обробки та аналізу даних. У галузі промисловості кіберфізичні інформаційні технології можуть бути застосовані для створення "розумних заводів", де системи автоматизації та моніторингу взаємодіють з обладнанням та персоналом. У медицині ці технології можуть підтримувати створення інтелектуальних медичних систем та пристроїв для діагностики та лікування. Загалом, кіберфізичні інформаційні технології визначають новий рівень інтеграції між фізичним та цифровим світом, відкриваючи нові перспективи для розвитку інтелектуальних систем та оптимізації різних галузей діяльності. Розділ представляє собою всебічний огляд сучасного стану парадигми штучного інтелекту, що дозволяє агентам вивчати оптимальні стратегії через взаємодію з навколишнім середовищем. Зазначається, що за останні роки навчання з підкріпленням зазнало значного прогресу завдяки методам глибокого навчання, збільшенню обчислювальних потужностей та новим алгоритмічним розробкам. Розділ надає обґрунтування теоретичних засад навчання з підкріпленням, вказуючи на визначні досягнення, виклики та потенційні майбутні напрямки у цій галузі. Особлива увага приділяється ключовим концепціям та передовим дослідженням, що дозволяють зробити висновок про прогрес, досягнутий у навчанні з підкріпленням у різних сферах, таких як робототехніка, ігрові технології та системи прийняття рішень. Цей розділ містить у собі зібрану та систематизовану інформацію щодо поточного стану досліджень у галузі навчання з підкріпленням, надаючи читачу повну картину щодо досягнень, викликів та перспектив цієї важливої області штучного інтелекту. Другий розділ присвячений детальному аналізу середовищ, в яких проводилися експерименти з виконання задач в контексті навчання з підкріпленням. В цьому розділі розглядається залежність швидкості навчання системи в методі навчання з підкріпленням від кількості взаємно незалежних модулів, а також порівняння можливостей систем пошукових модулів та окремих об'єктів у пошуку цілей із невідомим місцезнаходженням відомому середовищі за допомогою алгоритмів навчання з підкріпленням. Також досліджуються можливості гетерогенних роїв БПЛА за допомогою навчання з підкріпленням та системи прийняття рішень з використанням навчання з підкріпленням для керування гетерогенними роями безпілотних літальних апаратів. У цьому розділі подано опис середовищ, в яких проводилися експерименти, їх характеристики та параметри, а також методику та процедури проведення експериментів. Розділ також розглядає результати експериментів та їхню інтерпретацію, що дозволяє зробити висновки щодо ефективності застосованих методів та підходів у вирішенні задач в контексті навчання з підкріпленням у різних середовищах та сценаріях. У другому розділі проведено дослідження, спрямоване на визначення залежності швидкості навчання системи в методі навчання з підкріпленням від кількості взаємно незалежних модулів у середовищі. Відповідно до описаних параметрів та умов експерименту, було обрано три однакових середовища, в кожному з яких знаходиться різна кількість об'єктів дослідження: один, п'ять і десять відповідно. Об'єкти дослідження були однаковими у кожному середовищі. Задача експерименту полягала у визначенні оптимальної кількості об'єктів для використання навчання з підкріпленням, яка забезпечить найкращий результат за однакової кількості ітерацій. Також проводилося порівняння ефективності досліджень, проведених на групі об'єктів, що взаємодіяли, з дослідженнями на взаємно незалежних модулях, які приймали рішення тільки на основі вхідних даних, отриманих незалежно. У експерименті було використано двовимірне поле як середовище, де об'єкти двох типів з'являлися випадковим чином. Один тип об'єктів приносив додаткові бали, а інший віднімав. У агентів було 9 очей з лінійним зором, які розрізняли чотири параметри: відстань до об'єктів різних типів, відстань до іншого об'єкта дослідження та відстань до стіни. Результати дослідження дозволили зробити висновок про ефективність та оптимальну кількість об'єктів для використання навчання з підкріпленням у відповідних умовах, що визначені експериментом. Також було виявлено можливість порівняння різних підходів до пошуку об'єктів у відомому середовищі та їх вплив на ефективність розв'язання задачі. Дослідження, продовжене у другому розділі, зосереджується на порівнянні ефективності двох різних підходів до пошуку об'єктів у відомому середовищі: централізовано керованої системи з використанням окремих модулів та децентралізованого підходу з окремими об'єктами. Дослідження використовує алгоритми навчання з підкріпленням для порівняння швидкості навчання та можливостей цих систем у двох сценаріях: пошуку статичних об'єктів з випадковими місцезнаходженнями та пошуку рухомих об'єктів з постійною швидкістю. Експериментальний дизайн передбачає визначення параметрів для навчання з підкріпленням, таких як нагороди та штрафи, і визначення розмірів вхідних та вихідних даних для нейронної мережі. Мета полягає в оцінці ефективності систем при різних умовах та порівнянні їхньої ефективності. У формулюванні проблеми визначаються експериментальні умови, включаючи постійне співвідношення між площею пошуку та кількістю об'єктів, часові одиниці для експериментів та параметри для навчання з підкріпленням. Дослідження визначає вхідні дані для обох типів систем та наводить критерії для нагород та штрафів. Результати експерименту показали, що система об'єднаних модулів вчиться повільніше, але досягає кращого максимального результату у пошуку статичних об'єктів. У випадку рухомих об'єктів система об'єднаних модулів виявляється більш ефективною як за швидкістю навчання, так і за максимальним результатом. У висновку роботи резюмуються отримані висновки, акцентуючи, що за допомогою навчання з підкріпленням можливо отримати ефективний алгоритм пошуку з використанням системи об'єднаних пошукових модулів, який буде краще застосовуватися, ніж така ж кількість окремих об'єктів з окремим керуванням. Наступний експеримент порівнює гетерогенні та гомогенні рої БПЛА з використанням алгоритмів навчання з підкріпленням. Дослідження оцінює здатність роїв у пошуку об'єктів у невідомій області. Гетерогенний рій, що включав БПЛА з різними можливостями, проявив швидше навчання та досягнув вищих винагород за меншу кількість епізодів порівняно з гомогенним роєм. Дослідження вказує на потенційні переваги використання БПЛА з різними можливостями у роях та важливість оптимізації складу рою для конкретних завдань. Далі досліджено вплив штучного інтелекту та автоматизації на гетерогенні рої безпілотних літальних апаратів. Виявлено, що гетерогенні рої з різними типами агентів та навчанням з підкріпленням мають покращену ефективність у виконанні завдань. Використання нейронних мереж для прийняття рішень та децентралізовані алгоритми дозволяють оптимізувати роботу рою та зменшувати надмірність ресурсів. Це відкриває нові можливості для розвитку автономних систем у різних областях, включаючи логістику та надзвичайні ситуації. Далі проводиться теоретичне обґрунтування змін до методу проксимальної стратегії оптимізації для багатоагентних систем Основною характеристикою алгоритму є його здатність оновлювати стратегію, роблячи кроки максимальної ефективності, при цьому дотримуючись обмежень на розходження між новою і попередньою стратегіями, використовуючи метод відсікання. Використання даного алгоритму дозволяє уникнути проблем, що виникають при застосуванні звичайних градієнтних стратегій, де великі кроки в зміні стратегії можуть привести до значного погіршення результатів через один поганий крок. Ускладнення алгоритму в багатоагентних системах полягає у врахуванні взаємодії та обміну інформацією між агентами. Для цього формула оновлення стратегії містить спеціальні параметри, що враховують дії всіх агентів, а також враховує різноманітні типи агентів та їхніх специфікацій. Третій розділ присвячений вибору середовища моделювання для подальших досліджень та експериментів у галузі робототехніки. З метою об'єктивного вибору оптимального середовища, було проведено оцінку різних інструментів моделювання на основі відгуків та характеристик, наданих джерелами, що знаходяться у вільному доступі. Результати оцінки показали, що AirSim визначається як переважне середовище для моделювання. Його багатоплатформенність, відкритий код та можливість легкого та швидкого додавання змін у середовище через Unreal Engine роблять його привабливим вибором для дослідників. З іншого боку, MissionPlanner та Morse отримали менш позитивні відгуки. Хоча MissionPlanner пропонує доступ до великої кількості реальних безпілотних літальних апаратів, його відсутність тривимірної графіки ставить під сумнів його придатність для деяких досліджень. Morse, зі свого боку, отримав відгуки про відсутність підтримки, що робить його менш привабливим варіантом для досліджень у галузі робототехніки. Нарешті, симулятор Gazebo був визначений як середовище зі широким набором параметрів для кожного агента і можливістю додавання великої кількості агентів одночасно. Проте, його відсутність офіційної підтримки операційної системи Windows і погана якість візуалізації можуть стати перешкодою для деяких досліджень. Далі в розділі розглядається процес симуляції гетерогенного рою безпілотних літальних апаратів для пошуку рухомих об'єктів у невідомому просторі. У даному дослідженні використовувався симулятор Gazebo. Для успішної реалізації симуляції було використано навчання з підкріпленням, зокрема проксимальну стратегію оптимізації. Після встановлення симулятора Gazebo та ROS (Robot Operating System) було створено моделі БПЛА та розроблено програмне забезпечення для керування роєм БПЛА з використанням навчання з підкріпленням. Умови симуляції включали в себе різноманітні топографічні особливості, такі як тунелі, пагорби, нерівності, дерева та рослинність, що підвищували складність завдання та реалізм ситуації. Застосована проксимальна стратегія оптимізації дозволила агентам у рої використовувати навчання з підкріпленням для оптимізації своєї поведінки у реальному часі. У складі рою були три типи БПЛА, кожен з яких мав свої характеристики та функціональні можливості. Під час симуляції агентам доводилося пристосовуватися до різних умов та використовувати свої можливості для успішного виявлення та відстеження об'єктів у невідомому просторі. У четвертому розділі проводиться детальний опис інформаційної технології, з її рівнями та описом збереження, перетворення, створення та обміну данними. Далі в розділі розглядається модель даної інформаційної технології, з описом кожного рівня, починаючи від рівня сенсорів, рівня обробки даних, рівня виявлення, навігації, та рівня комунікації. Описано передачу даних між рівнями та комунікацію агентів між собою і передачу повідомлень до інтерфейсу користувача, з їх подальшим збереженням та відображенням. У дисертації було вирішено усі поставлені задачі та виконано мету роботи. Інформаційну технологію розроблено в рамках науково-дослідницької роботи: «Інтелектуальні високопродуктивні технології управління технічними системами» Державний реєстраційний номер: 0121U110810; Дата реєстрації: 26-04-2021. Наукове дослідження проводилось у Національному технічному університеті України «Київський політехнічний інститут імені Ігоря Сікорського» у відповідності до напряму «Інформаційні та комунікаційні технології» переліку пріоритетних тематичних напрямів наукових досліджень і науково-технічних розробок на період до 2023 року, затвердженого постановою Кабінету Міністрів України №942 від 7.09.2011 (в редакції постанови №463 від 09.05.2023), та у відповідності до тематики наукових розробок кафедри.Документ Відкритий доступ Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання(КПІ ім. Ігоря Сікорського, 2024) Дифучина, Олександра Юріївна; Павлов, Олександр АнатолійовичДифучина О.Ю. Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 126 – Інформаційні системи та технології з галузі знань 12 – Інформаційні технології. – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2024. Дисертаційна робота присвячена розробці методів та засобів дослідження впливу параметрів паралельних обчислень на швидкодію обчислень. Сучасні інформаційні технології потребують швидкої роботи алгоритмів, яку можна досягти за рахунок використання паралельних обчислень. Проте, в залежності від параметрів, що визначають характеристики підзадач та механізми їх взаємодії, використання паралельних обчислень може призвести як до прискорення, так і до сповільнення обчислень. На практиці проблему налаштування параметрів паралельних обчислень вирішують шляхом багатократного тестування програми на різних комп’ютерних платформах при різних наборах параметрів, щоб гарантувати коректність та ефективність обчислень. Через велику кількість варіантів захоплення обчислювального ресурсу та, відповідно, варіантів виконання інструкцій окремими процесами паралельних обчислень результат запуску однієї і тієї ж програми в однакових умовах може суттєво відрізнятись. Тому тестування паралельних алгоритмів в реальних умовах є ресурсовитратним. Математичні методи оцінювання ефективності паралельних обчислень спроможні вказати на існування обмеження на максимально досяжне прискорення за ідеальних умов вільного доступу до обчислювального ресурсу та відсутності синхронізації обчислень (тобто фактично відсутності взаємодії між частинами програми). Існуючі засоби проєктування програм, такі як UML, дають змогу (досить узагальнено) представити графічно взаємодію окремих частин програми, проте не надають можливості будь-якого чисельного аналізу обчислень. Засоби моделювання, такі як високорівневі мережі Петрі, рекомендовані міжнародним стандартом ISO/IEC 15909-1:2019 як техніка для специфікації паралельних і розподілених систем. На сьогоднішній день є досвід розробки симуляторів обчислень на основі мереж Петрі, проте жоден з них не став на сьогоднішній день широко використовуваним у розробці паралельних обчислень. Таким чином, на сьогодні не існує уніфікованого методу створення моделі паралельних обчислень і, відповідно, не існує іншого, окрім реальної програми, засобу, який можна використовувати для оптимізації параметрів паралельної програми. Відсутність засобів моделювання стримує розробку високоефективних паралельних обчислень. З огляду на це, створення методів та засобів, спрямованих на вдосконалення процесу налагодження багатопотокових програм та підвищення ефективності використання паралельних обчислень в інформаційній технології, є актуальним науковим завданням. Метою наукового дослідження є підвищення ефективності використання паралельних обчислень в інформаційних технологіях за рахунок їх проєктування на основі моделей, що можуть бути використані для оцінювання часу виконання паралельного алгоритму, та оптимізації параметрів паралельних обчислень. У першому розділі обґрунтовано необхідність ретельного проєктування паралельних обчислень для досягнення їх ефективності, розглянуті методи та засоби для проєктування паралельних обчислень та аналізу їх ефективності. Виявлено, що математичні методи аналізу ефективності паралельних обчислень здатні оцінити максимально досяжне прискорення за досить ідеальних умов вільного доступу до обчислювального ресурсу та відсутності синхронізації обчислень. На противагу, засоби імітаційного моделювання спроможні достатньо детально відтворювати паралельні процеси і, на відміну від експериментування з реальною програмою паралельних обчислень, не потребують значних витрат на проведення експериментального дослідження. Серед симуляторів паралельних обчислень багато таких, що використовують формалізм мережі Петрі як засіб опису процесу обчислень. Проте, моделюванню, як правило, підлягають найпростіші елементи паралельної програми: розділення на підзадачі, очікування завершення виконання підзадачі, блокування. Більш складні інструменти взаємодії між потоками, як wait/notify, розглядаються лише в окремих публікаціях. У моделях не враховують обмеженість використовуваного паралельною програмою ресурсу, що, звісно, негативно впливає на їх точність. Розглянуті також засоби тестування паралельних програм, які призначені для виявлення взаємоблокування та/або помилки узгодженості пам’яті у вже розроблених програмах. Такі засоби спрямовані, насамперед, на аналіз коректності виконання обчислень, але не на аналіз ефективності паралельних досліджень. У підсумку, зроблено висновок щодо необхідності розвитку методів та засобів для оцінювання ефективності паралельних обчислень на основі моделей, які враховують механізм захоплення обчислювального ресурсу та механізми взаємодії між підзадачами, що виконуються паралельно. У другому розділі сформульовані мета та задача моделювання паралельних обчислень, визначено формальний опис моделі та виконано розробку методу моделювання паралельних обчислень на основі цього опису. Для формального опису обрано формалізм Петрі-об’єктної моделі у зв’язку з низкою переваг: найбільш точне (у порівнянні зі звичайною мережею Петрі) відтворення структури об’єктно-орієнтованої програми та поведінкових властивостей окремих об’єктів; більш точне (у порівнянні зі звичайною мережею Петрі) відтворення взаємодії потоків/підзадач за рахунок враховування часових затримок на виконання обчислювальних дій та стохастичності захоплення обчислювального ресурсу; тиражування об’єктів зі схожою поведінкою із заданими параметрами спрощує створення моделей з великою кількістю підзадач; тиражування груп зв’язків між об’єктами спрощує конструювання моделі з великою кількістю зв’язків; візуалізація поведінкових властивостей моделі дає змогу розробити програму з найменшою кількістю помилок. Визначені та розроблені шаблони моделювання обчислень багатопотокової програми, які зменшують кількість помилок при розробці моделей, спрощують та прискорюють процес розробки моделі. Набір шаблонів моделювання містить фрагменти мереж Петрі, що відтворюють рутинні інструкції програми, створення, початок та завершення роботи потоку, призупинку потоку на заданий інтервал часу, блокування дій потоку, очікування за умовою, обчислення підзадач пулом потоків. Описано процес розробки Петрі-об’єктної моделі паралельної програми. Усі запропоновані та розроблені методи, підходи та засоби моделювання поєднані у технологію моделювання паралельного алгоритму. Наведено приклади розробки моделей. У третьому розділі сформульована задача оптимізації параметрів паралельних обчислень, обґрунтовано існування оптимальних значень та визначені шляхи пошуку оптимальних значень на моделі, визначені методи та засоби збору даних для моделі, описані методи та засоби розробки Петріоб’єктної моделі паралельних обчислень. Програмне забезпечення Parallel Program Simulation (PPS) реалізує такі функції для підтримки розробки моделі: розробка мережі Петрі у графічному редакторі мереж Петрі; збереження мережі Петрі у двох форматах - графічне зображення та у вигляді методу; дослідження параметрів часової затримки; експериментальне дослідження моделі; пошук оптимальних значень параметрів паралельних обчислень еволюційним методом. У четвертому розділі метод оптимізації параметрів паралельних обчислень, описаний у розділі 3, апробовано на прикладах паралельного алгоритму імітації дискретно-подійної системи та пулу потоків. Паралельний алгоритм імітації є складним як за кількістю обчислювальних дій, так і за механізмами взаємодії підзадач, які забезпечують злагоджені дії усіх частин моделі. Теоретично та експериментально доведено наявність впливу параметрів паралельного алгоритму на швидкодію його виконання. Встановлено, що параметром, від якого у найбільшій мірі залежить час виконання алгоритму – це складність одного фрагменту моделі, який запускається на одночасне виконання. Виконано дослідження оптимального значення параметру при зростанні складності моделі. Побудована Петрі-об’єктна модель паралельного алгоритму та виконано пошук оптимальних параметрів на моделі експериментально. Еволюційний алгоритм апробовано на Петрі-об’єктній моделі пулу потоків. Знайдені оптимальні значення в обох випадках достатньо точно відповідають таким, що були виявлені при експериментуванні з паралельними алгоритмами в реальних умовах. Отримані результати свідчать про коректність пошуку оптимальних параметрів на моделі. Результати, отримані у дисертаційному дослідженні, містять наукову новизну: - вперше розроблено технологію моделювання паралельних обчислень на основі Петрі-об’єктного підходу, що надає можливість скоротити ресурсні витрати при розробці паралельних алгоритмів, і, на відміну від існуючих, дає змогу відтворити деталізовано структуру паралельної програми та механізми взаємодії одночасно виконуваних частин програми з урахуванням часових затримок на виконання обчислювальних дій та стохастичності захоплення обчислювального ресурсу і спрощує процес побудови моделі за рахунок тиражування фрагментів програми зі схожою функціональністю; - удосконалено моделі базових механізмів синхронізації паралельних обчислень за рахунок підвищення точності відтворення, що забезпечує високу точність результатів моделювання; - вперше розроблено типові фрагменти мереж Петрі, що реалізують механізми багатопотокової технології Java, використання яких прискорює розробку моделі паралельного алгоритму за рахунок зменшення кількості помилок та зменшення загальної кількості елементів, необхідних для розробки моделі; - вперше запропоновано метод оптимізації параметрів паралельних обчислень на основі експериментального дослідження Петрі-об’єктної моделі обчислень, що забезпечує ефективне використання обчислювальних ресурсів і, на відміну від існуючих підходів, дає змогу проводити експериментальне дослідження ефективності паралельних обчислень на моделі замість експериментування на реальній програмі. Практичне значення результатів дисертаційного дослідження полягає у розробленому програмному забезпеченні для моделювання паралельних обчислень та оптимізації їх параметрів на основі Петрі-об’єктного моделювання, що є одним з результатів виконання науково-дослідної роботи «Методи візуального програмування Петрі-об'єктних моделей» (державний реєстраційний номер 0117U000918). Технологія моделювання паралельних обчислень мережею Петрі впроваджена у рамках навчального дистанційного курсу «Технології паралельних обчислень» (сертифікат ДК № 0098, затверджений протоколом №8 від 02.06.2023 Методичної ради КПІ ім. Ігоря Сікорського). Результати дисертаційної роботи опубліковано у 9 наукових публікаціях, серед яких 3 статті у періодичних наукових виданнях, проіндексованих у Web of Science Core Collection та Scopus базах даних (дві з них у видннях, віднесених до третього квартиля (Q3)), 1 стаття у фаховому науковому журналі категорії «Б» (зі спеціальності 126), 1 стаття у фаховому науковому журналі з переліку до 12.03.2020 р. (технічні науки), 3 публікації у матеріалах міжнародних наукових конференцій, 1 публікація у матеріалах всеукраїнської наукової конференції.