Использование свободного ПО для разработки средств моделирования сетевых моделей сложных систем (Николай Муравьев, OSSDEVCONF-2022)

Ссылки сюда (1) →

Короткая ссылка: 20220521E

Докладчик

Николай Муравьев

В докладе рассматриваются вопросы использования свободного программного обеспечения для создания пакета программ, предназначенного для исследования сетевых моделей сложных параллельных систем.

В качестве инструмента для построения сетевых моделей используется аппарат сетей Петри. Создаваемый пакет программ также относится к свободному программному обеспечению.

Видео

on youtube

Презентация

Thesis

• https://github.com/tuplecats/GPTN

Понятие сложной дискретной динамической системы является одним из наиболее общих понятий в информатике и вычислительной технике. В настоящее время дискретными сложными системами являются компьютеры, вычислительные сети, специализированные процессоры различной структуры, системы обработки данных, сенсорные сети и др.

Одним из инструментов для решения задач, связанных с исследованием сложных систем, является аппарат сетей Петри. Существуют подходы для поиска альтернативных структур сложных систем с использованием сетей Петри, они заключаются в декомпозиции и синтезе. Благодаря таким подходам построения вариантов на основе обобщённой модели позволяет проектировщику сложной системы получить множество возможных альтернативных структур, из которых выбрать оптимальные структуры, применив методы метрической оценки. Однако такой подход является NP-сложной задачей, для решения которой необходимы вычислительные ресурсы.

Сеть Петри (СП) — математический аппарат для формализации, анализа и моделирования дискретно-событийных систем. СП может использоваться для эффективного моделирования параллельных распределённых систем, а также технологических процессов.

Программный

Мотивация разработки программного комплекса для анализа и моделирования параллельных процессов на основе сетевых моделей опирается на наличие малого количества и неразвитость существующего программного обеспечения в данном направлении. Текущие решения предлагают следующие возможности :

• задание СП-моделей;
• анализ СП-моделей с помощью имитации поведения сетей Петри;
• построение и анализ пространства состояний модели (построение дерева достижимых разметок);
• оценка сетей на живость, ограниченность, наличие конфликтов.

Разрабатываемый комплекс программ включает функционал существующих программных средств, а также содержит новые компоненты.

Программный комплекс написан на двух языках программирования: С++ и Rust и состоит из следующих модулей и составляющих:

• графический интерфейс;
• модуль визуализации сетей Петри;
• модуль декомпозиции;
• модуль синтеза новых структур;
• модуль построения дерева достижимых разметок;
• модуль анализа СП на основе решения систем линейных уравнений.

Графический интерфейс служит для возможности интерактивной работы с СП-моделями, т. е. является frontend для остальных модулей. Для написания графического интерфейса используется фреймворк Qt. Qt является кроссплатформенным и позволяет писать программное обеспечение под разные семейства ОС, а также позволяет писать свободное ПО используя лицензии GNU GPLv3 (GNU General Public License, version 3) или GNU LGPLv2.1 (GNU Lesser General Public License, version 2.1).

В качестве модуля визуализации используется ПО Graphviz, которое позволяет визуализировать графы, а в данном случае сети Петри, в удобном виде посредством алгоритмов визуализации. Graphviz распространяется по свободной лицензии EPL (Eclipse Public License v1.0). На данный момент программный комплекс использует 3 алгоритма: dot, FDP (Force Directed Placement), SFDP (Scalable FDP). Другие алгоритмы, такие как patchwork, circo, osage, neato поддерживаются, но не используются. Пример использования ПО Graphviz в разрабатываемом программном комплексе:

Визуализация сети Петри алгоритмом Dot

Модуль декомпозиции производит разделение сети на линейно-циклические и линейные базовые фрагменты для дальнейшего их использования в модуле синтеза новых структур. Алгоритм декомпозиции основан на преобразовании матрицы инцидентности сети Петри.

Для реализации алгоритмов использовалась библиотека openBLAS, которая позволяет эффективно работать с матрицами и линейной алгеброй. OpenBLAS представляет собой реализацию BLAS (базовые подпрограммы линейной алгебры) и LAPACK API интерфейсов со множеством оптимизаций для разных типов процессоров. OpenBLAS распространяется по лицензии «BSD 3-Clause».

Модуль синтеза новых структур является прямым продолжением модуля декомпозиции. Данный компонент также использует библиотеку openBLAS. Основной задачей синтеза является поиск всех возможных структур, которые можно получить, опираясь на исходную сеть Петри.

Функционал программного комплекса активно развивается и расширяется, что позволит в будущем поддерживать разный набор методов анализа сетей Петри. В краткосрочном плане стоит решение задачи синтеза новых структур сетей Петри при сохранении первоначально заданных функций, но обладающих более эффективными показателями. Эффективное решение этой задачи возможно с использованием вычислений на GPU.

Используемые сторонние библиотеки и фреймворки в работе имеют разные лицензии. Для лицензирования разрабатываемого программного комплекса используется лицензия LGPLv2.1.