Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання

Скорочена інформація про документ
dc.contributor.advisorПавлов, Олександр Анатолійович
dc.contributor.authorДифучина, Олександра Юріївна
dc.date.accessioned2024-04-26T09:03:33Z
dc.date.available2024-04-26T09:03:33Z
dc.date.issued2024
dc.description.abstractДифучина О.Ю. Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 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 публікація у матеріалах всеукраїнської наукової конференції.
dc.description.abstractotherDyfuchyna O. Optimization method of parallel computing parameters based on Petri-object modeling. Thesis for the degree of Doctor of Philosophy in specialty 126 – Information systems and technologies in the field of knowledge 12 - Information technologies. - National Technical University of Ukraine "Ihor Sikorsky Kyiv Polytechnic Institute", Kyiv, 2024. Ph.D. thesis is devoted to the development of methods and tools for researching the influence of parallel computing parameters on the speed of computing. Modern information technologies require fast operation of algorithms, which can be achieved through the use of parallel computing. However, depending on the parameters that determine the characteristics of the subtasks and the mechanisms of their interaction, the use of parallel computing can lead to both speeding up and slowing down the computing. In practice, the problem of setting the parameters of parallel computing is solved by repeatedly testing the program on different computer platforms with different sets of parameters to guarantee the correctness and efficiency of the calculations. Due to the large number of options for capturing the computing resource and, accordingly, options for executing instructions by individual parallel computing processes, the result of running the same program under the same conditions may differ significantly. Therefore, testing parallel algorithms in real conditions is resource-consuming process. Mathematical methods for evaluating the efficiency of parallel computing are able to indicate the existence of a limit on the maximum achievable speed up under ideal conditions of free access to the computing resource and the absence of synchronization of calculations (that is, in fact, the absence of interaction between parts of the program). Existing program design tools, such as UML, allow (quite generalized) to graphically represent the interaction of individual parts of the program, but do not provide any numerical analysis of calculations. Simulating tools such as high-level Petri nets are recommended by the international standard ISO/IEC 15909-1:2019 as a technique for specifying parallel and distributed systems. To date, there is experience in the development of Petri net-based computing simulators, but none of them have become widely used in the development of parallel computing. Thus, today, there is no unified method for creating a model of parallel computing and, accordingly, there is no tool other than a real program that can be used to optimize the parameters of a parallel program. The lack of simulation tools hinders the development of highly efficient parallel computing. In view of this, the creation of methods and tools aimed at improving the process of setting up multi-threaded programs and increasing the efficiency of using parallel computing in information technology is an urgent scientific task. The purpose of scientific research is to increase the effectiveness of parallel computing usage in information technologies by designing it based on models which can be used for performance time estimation of parallel algorithm and parallel computing parameters optimization. The first section substantiates the need for careful design of parallel computing to achieve their efficiency and provides an overview for methods and tools for parallel computing design and their efficiency analysis. It was found that the mathematical methods of analyzing the efficiency of parallel computing are able to estimate the maximum achievable acceleration under fairly ideal conditions of free access to the computing resource and the absence of synchronization of computing. In contrast, simulation tools are able to reproduce parallel processes in sufficient detail and, unlike experimentation with a real parallel computing program, do not require significant costs for conducting experimental research. Among the parallel computing simulators, there are many that use the Petri net formalism as a tool to describe the computing process. However, as a rule, only the simplest elements of a parallel program are simulated: division into subtasks, waiting for the completion of subtask execution, blocking. More complex tools for interaction between threads, such as wait/notify, are covered only in separate publications. The models do not take into account the limitation of the resource used by the parallel program, which, of course, negatively affects their accuracy. Also considered are tools for testing parallel programs, which are designed to detect interlocking and/or memory consistency errors in already developed programs. Such tools are aimed, first of all, at the analysis of the correctness of the computing, but not at the analysis of the efficiency of parallel studies. As a result, a conclusion was made regarding the need to develop methods and tools for evaluating the effectiveness of parallel computing based on models that take into account the mechanism of capturing the computing resource and the mechanisms of interaction between subtasks performed in parallel. In the second section, the purpose and task of simulating parallel computing are formulated, a formal description of the model is defined, and the method of simulating parallel computing is developed based on this description. For the formal description, the formalism of the Petri-object model was chosen due to a number of advantages: the most accurate (compared to the usual Petri net) reproduction of the structure of the object-oriented program and the behavioral properties of individual objects; more accurate (compared to the usual Petri net) reproduction of the interaction of threads/subtasks due to taking into account time delays for performing computational actions and the stochasticity of computing resource capture; replication of objects with similar behavior with given parameters simplifies the creation of models with a large number of subtasks; replication of groups of connections between objects simplifies the construction of a model with a large number of connections; visualizing the behavioral properties of the model allows us to develop a program with the least number of errors. Simulating templates of multithreaded program computations are defined and developed. They reduce the number of errors in model development, simplify and speed up the model development process. A set of modeling templates contains fragments of Petri nets that reproduce routine program instructions, creating, starting and terminating a thread, stopping a thread for a given time interval, blocking thread actions, waiting by condition, computing subtasks by a thread pool. The process of developing a Petri-object model of a parallel program is described. All the proposed and developed methods, approaches and modeling tools are combined in the parallel algorithm simulation technology. Examples of model development are provided. In the third section, the task of optimizing the parameters of parallel computing is formulated, the existence of optimal values is substantiated and the ways of finding optimal values on the model are determined, the methods and tools of data collection for the model are defined, the methods and tools of developing the Petri-object model of parallel computing are described. The main stages of the method of optimizing the parameters of parallel calculations are formulated and described, in particular, the adaptive step-by-step optimization algorithm and the evolutionary algorithm, which are applied depending on the number of parameters under study. Parallel Program Simulation (PPS) software implements the following functions to support model development: Petri net development in the graphical Petri net editor; saving the Petri net in two formats - a graphical image and in the form of a method; study of time delay parameters; experimental study of the model; search for optimal values of parallel computing parameters by evolutionary method. In the fourth section, the method of optimizing parameters of parallel computing, described in section 3, is tested on the examples of a parallel algorithm for simulating a discrete-event system and a thread pool. This parallel simulation algorithm is complex both in terms of the number of computational operations and in the mechanisms of interaction of subtasks that ensure coordinated actions of all parts of the model. Theoretically and experimentally, it has been proved that the parameters of the parallel algorithm have an influence on the speed of its execution. It was established that the parameter on which the performance time of the algorithm depends to the greatest extent is the complexity of one fragment of the model, which is launched for simultaneous execution. The study of the optimal value of the parameter with increasing complexity of the model was carried out. A Petri-object model of the parallel algorithm was built and the search for optimal parameters was performed on the model experimentally. The evolutionary algorithm is tested on te Petri-object model of thread pool. The optimal values found in both cases quite accurately correspond to those found during experimentation with parallel algorithms in real conditions. The obtained results indicate the correctness of the search for optimal parameters on the model. The results obtained in the research contain scientific novelty. For the first time, а parallel computing simulation technology based on the Petri-object approach has been developed, which provides an opportunity to reduce resource costs in the development of parallel algorithms. Unlike existing ones, it allows to reproduce in detail the structure of a parallel program and the mechanisms of interaction of simultaneously executing parts of the program, taking into account time delays on the execution of computing actions and the stochasticity of capturing the computing resource. Developed technology simplifies the process of building a model due to the replication of program fragments with similar functionality. The models of the basic mechanisms of synchronization of parallel computing have been improved by increasing the accuracy of reproduction, which ensures high accuracy of simulation results. For the first time, typical fragments of Petri nets implementing the mechanisms of Java multithreading technology have been developed, the use of which accelerates the development of a parallel algorithm model by reducing the number of errors and reducing the total number of elements required for model development. For the first time, a technology for optimizing the parameters of parallel computing based on an experimental study of the Petri-object model of computing is proposed. It ensures the efficient use of computing resources and, unlike existing approaches, makes it possible to conduct an experimental study of the efficiency of parallel computing on a model instead of experimenting on a real program. The practical significance of the results of the dissertation research lies in the developed software for modeling and optimizing the parameters of parallel computing based on Petri-object simulation, which is one of the results of the research work "Methods of visual programming of Petri-object models" (state registration number 0117U000918). Technology of parallel computing simulation using Petri net was introduced as part of the distance learning course "Parallel Computing Technologies" (certificate ДК No. 0098, approved by Protocol No. 8 dated June 2, 2023 of the Igor Sikorsky KPI Methodological Council). The results of the dissertation were published in 9 scientific publications, including 3 papers in a periodical scientific publication indexed in the Web of Science Core Collection and Scopus databases, 2 papers in a professional scientific journal, 3 publications in the materials of international scientific conferences indexed in Scopus, 1 publication in the materials of the All-Ukrainian scientific conference.
dc.format.extent172 с.
dc.identifier.citationДифучина, О. Ю. Метод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання : дис. … д-ра філософії : 126 Інформаційні системи та технології / Дифучина Олександра Юріївна. – Київ, 2024. – 172 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/66511
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectбагатопотокове програмування
dc.subjectпаралельні обчислення
dc.subjectоптимізація
dc.subjectімітаційне моделювання
dc.subjectстохастична мережа Петрі
dc.subjectПетрі-об’єктне моделювання
dc.subjectmultithreaded programming
dc.subjectparallel computing
dc.subjectoptimization
dc.subjectsimulation
dc.subjectstochastic Petri net
dc.subjectPetri-object simulation
dc.subject.udc004.41::004.94
dc.titleМетод оптимізації параметрів паралельних обчислень на основі Петрі-об’єктного моделювання
dc.typeThesis Doctoral

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Dyfuchyna_dys.pdf
Розмір:
2.68 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Дисертації (ІСТ)
Дисертації (вільний доступ)