Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання
Вантажиться...
Дата
2024
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Дифучина О.Ю. Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання. – Кваліфікаційна наукова праця на правах рукопису.
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 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 публікація у матеріалах всеукраїнської наукової конференції.
Опис
Ключові слова
багатопотокове програмування, паралельні обчислення, оптимізація, імітаційне моделювання, стохастична мережа Петрі, Петрі-об’єктне моделювання, multithreaded programming, parallel computing, optimization, simulation, stochastic Petri net, Petri-object simulation
Бібліографічний опис
Дифучина, О. Ю. Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання : дис. … д-ра філософії : 126 Інформаційні системи та технології / Дифучина Олександра Юріївна. – Київ, 2024. – 172 с.