Моделирование сети Петри на С++. Параллельная реализация с MPI
Постановка задачи: Разработать программу, моделирующую работу сетей Петри, с возможностью автоматического моделирования и проверки в ручном режиме.
Сети Петри: Сети Петри — математический аппарат для моделирования динамических дискретных систем. Представляет собой двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Переход разрешен только в том случае, если каждая из его входных позиций содержит число фишек, не меньшее, чем число дуг, ведущих из этой позиции в переход.
В сетях Петри происходит выполнение одного из возможных дискретных событий. Если в какой-то момент времени разрешено более одного перехода, то любой из них может стать «следующим» запускаемым.
Пример работы сети Петри: В левой позиции находятся две метки, в правой позиции нет меток:
Описание работы программы: При запуске программы требуется ввести количество переходов, которые должна выполнить программа. Далее пользователю предоставляется выбор между запуском сети Петри в автоматическом режиме или в ручном для самостоятельной работы с сетью. При выборе ручного режима так же предоставляется выбор между использованием уже готовой сети Петри и самостоятельным вводом данных для сети. При выборе автоматического режима генерируется сеть, позволяющая бесконечно использовать любой переход – это требуется для того, чтобы реализовать любое указанное число операций без потери времени на выбор разрешенного перехода.
В автоматическом режиме программа случайным образом выбирает переход, если он доступен, переход выполняется, программа ищет разрешенные переходы. Это повторяется, пока не будет выполнено указанное число переходов. В ручном режиме алгоритм тот же, но выбор переходов предоставлен пользователю.
Для моделирования позиций используется массив Sost, он содержит в себе данные о текущем положении меток в позициях. Условия переходов реализованы при помощи двумерных массивов mx1 и mx2. Массив mx1 содержит в себе условия, необходимые для выполнения перехода, mx2 содержит последствия выполнения перехода. Для вычисления разрешенных переходов используется функция FindActiveTransistions, в которой реализован параллельный поиск. Состояния переходов хранятся в массиве ch.
Последствия перехода рассчитываются по массиву mx2 – используется строка, соответствующая выбранному переходу, по которой выполняется пересчёт состояний положений.
При выполнении программы в автоматическом режиме происходит подсчёт времени работы каждого процесса, для сравнения их скорости работы. Так же ведётся подсчёт времени выполнения всей программы – оно выводится в главном процессе(ROOT).
Причины распараллеливания: Для распараллеливания была выбрана функция поиска разрешенных переходов FindActiveTransistions. В данной функции программа проходит по всему массиву mx1, сравнивая по столбцам число меток, имеющихся в каждой позиции, участвующей в переходе, и необходимое число меток для перехода. Если число меток удовлетворяет условиям перехода, номер перехода записывается в массив ch, как разрешенный.
При большом количестве переходов их последовательный поиск будет занимать много времени. Для ускорения работы программы массив разбивается на части по количеству переходов (по столбцам). В итоге, при параллельном выполнении каждый процесс будет перебирать сегмент массива, равный (P*S)/N, а при последовательном P*S, где P – число переходов, S – число состояний, N – число процессов.
Описание работы параллельных частей: Распараллеливание заключается в разделении массива mx1 на равные сегменты для каждого процесса. Главный процесс (ROOT) рассчитывает размер сегмента и с помощью функции MPI_Scatter рассылает каждому процессу, в том числе и себе, границы выделенного ему сегмента в массиве.
Получив границы, каждый процесс выполняет поиск разрешенных переходов в рамках своего сегмента, результаты поиска записываются в буфер buf. Завершив поиск в своём сегменте, каждый процесс отправляет свои результаты всем другим процессам. Для этого используется функция MPI_Alltoall, она заменяет две функции, требующиеся для сбора фрагментов с результатами поиска каждого процесса в одном процессе (MPI_Gather) и рассылке полных данных каждому процессу (MPI_Scatter). Полные данные нужны для дальнейших расчётов состояния.
Исходный код:
Анализ распараллеливания:
диаграммы загрузки процессора для последовательной програмым и с распараллеливанием с openMP:
Замеры времени работы програмы для сетей различного размера:
Выводы Для выполнения было задано 10000 переходов. Программа запускалась на машине с двумя физическими ядрами, но четырьмя логическими процессорами. Программы, выполняющиеся в параллельном режиме с помощью OpenMP и MPI, работают быстрее на 3.284 сек. (41,1%) и 3.157 сек.(39.5%) соответственно, чем программа, работающая в последовательном режиме. Однако, такие результаты можно получить при большом объёме данных – при малом объёме разница во времени будет менее значительна.