Постановка задачи:
Разработать программу, моделирующую работу сетей Петри, с возможностью автоматического моделирования и проверки в ручном режиме.
Сети Петри:
Сети Петри — математический аппарат для моделирования динамических дискретных систем. Представляет собой двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Переход разрешен только в том случае, если каждая из его входных позиций содержит число фишек, не меньшее, чем число дуг, ведущих из этой позиции в переход.
В сетях Петри происходит выполнение одного из возможных дискретных событий. Если в какой-то момент времени разрешено более одного перехода, то любой из них может стать «следующим» запускаемым.
Пример работы сети Петри:
В левой позиции находятся две метки, в правой позиции нет меток:
Для совершения перехода из левой позиции в правую необходимо наличие в левой позиции одной метки. Условия соответствуют требованиям для перехода:
Переход совершен. В левой позиции осталась одна метка, в правой позиции появилась одна метка:
Описание работы программы:
При запуске программы требуется ввести количество переходов, которые должна выполнить программа. Далее пользователю предоставляется выбор между запуском сети Петри в автоматическом режиме или в ручном для самостоятельной работы с сетью. При выборе ручного режима так же предоставляется выбор между использованием уже готовой сети Петри и самостоятельным вводом данных для сети. При выборе автоматического режима генерируется сеть, позволяющая бесконечно использовать любой переход – это требуется для того, чтобы реализовать любое указанное число операций без потери времени на выбор разрешенного перехода.
В автоматическом режиме программа случайным образом выбирает переход, если он доступен, переход выполняется, программа ищет разрешенные переходы. Это повторяется, пока не будет выполнено указанное число переходов. В ручном режиме алгоритм тот же, но выбор переходов предоставлен пользователю.
Для моделирования позиций используется массив 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:
c MPI:
Замеры времени работы програмы для сетей различного размера:
Выводы
Для выполнения было задано 10000 переходов. Программа запускалась на машине с двумя физическими ядрами, но четырьмя логическими процессорами. Программы, выполняющиеся в параллельном режиме с помощью OpenMP и MPI, работают быстрее на 3.284 сек. (41,1%) и 3.157 сек.(39.5%) соответственно, чем программа, работающая в последовательном режиме. Однако, такие результаты можно получить при большом объёме данных – при малом объёме разница во времени будет
менее значительна.
Разработать программу, моделирующую работу сетей Петри, с возможностью автоматического моделирования и проверки в ручном режиме.
Сети Петри:
Сети Петри — математический аппарат для моделирования динамических дискретных систем. Представляет собой двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Переход разрешен только в том случае, если каждая из его входных позиций содержит число фишек, не меньшее, чем число дуг, ведущих из этой позиции в переход.
В сетях Петри происходит выполнение одного из возможных дискретных событий. Если в какой-то момент времени разрешено более одного перехода, то любой из них может стать «следующим» запускаемым.
Пример работы сети Петри:
В левой позиции находятся две метки, в правой позиции нет меток:
Для совершения перехода из левой позиции в правую необходимо наличие в левой позиции одной метки. Условия соответствуют требованиям для перехода:
Переход совершен. В левой позиции осталась одна метка, в правой позиции появилась одна метка:
Описание работы программы:
При запуске программы требуется ввести количество переходов, которые должна выполнить программа. Далее пользователю предоставляется выбор между запуском сети Петри в автоматическом режиме или в ручном для самостоятельной работы с сетью. При выборе ручного режима так же предоставляется выбор между использованием уже готовой сети Петри и самостоятельным вводом данных для сети. При выборе автоматического режима генерируется сеть, позволяющая бесконечно использовать любой переход – это требуется для того, чтобы реализовать любое указанное число операций без потери времени на выбор разрешенного перехода.
В автоматическом режиме программа случайным образом выбирает переход, если он доступен, переход выполняется, программа ищет разрешенные переходы. Это повторяется, пока не будет выполнено указанное число переходов. В ручном режиме алгоритм тот же, но выбор переходов предоставлен пользователю.
Для моделирования позиций используется массив 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). Полные данные нужны для дальнейших расчётов состояния.
Исходный код:
Код:
#include <Windows.h>
#include <iostream>
#include <mpi.h>
#include <math.h>
#include <time.h>
#define ROOT 0
#define SIZE 4
void FindActiveTransistions();
void PrintActiveTransistions();
void Auto();
void Manually();
const int N = 500, M = 500;
long int oper;
//количество операций
int cond, tran;
//количество состояний и переходов
int Sost[N];
//массив состояний
int ch[M];
//массив для проверки активных состояний
int mx1[N][M];
//матрица инцидентности 1
int mx2[M][N];
//матрица инцидентности 2
double times[4];
int sBuf[SIZE][SIZE/2]; //буфер для хранения и передачи адресов
int buf[M];
//буфер для обработки данных поиска активных переходов
int rank, size;
MPI_Status status;
bool fl = true;
int main(int argc, char **argv) {
int choose;
setlocale(LC_ALL, "Russian");
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == ROOT) {
std::cout << "Количество переходов: ";
while (1) {
std::cin >> oper;
if (oper <= 0)
std::cout << "\nВведите число больше нуля." << std::endl;
else
break;
}
std::cout << "\n1.Автоматически\n2.Проверка\n\nВыберите режим работы: ";
std::cin >> choose;
if (choose == 2) {
std::cout << "\n1.Тестовая Сеть Петри\n2.Ввести данные вручную\n\nВыберите режим: ";
std::cin >> choose;
choose++;
}
}
MPI_Bcast(&oper, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
MPI_Bcast(&choose, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
double time = 0;
switch (choose) {
case 1: {
cond = 400;
tran = 500;
for (int i = 0; i < cond; i++)
Sost[i] = 2;
for (int i = 0; i < cond; i++)
for (int j = 0; j < tran; j++)
mx1[i][j] = 2;
for (int i = 0; i < tran; i++)
for (int j = 0; j < cond; j++)
mx2[i][j] = 2;
system("pause");
Barrier(MPI_COMM_WORLD);
time = MPI_Wtime();
times[rank] = MPI_Wtime();
FindActiveTransistions();
Auto();
}
break;
case 2: {
cond = 8;
tran = 8;
int m1[8][8] = {
{1,1,0,0,0,0,0,0},{0,0,2,0,0,0,0,0},{0,0,0,2,0,0,0,0},{0,0,0,0,2,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,10},{0,0,0,0,0,0,2,0},
};
int m2[8][8] = {
{1,1,0,0,0,0,1,1},{0,3,0,0,0,0,0,0},{0,0,1,0,0,0,1,0},{0,0,0,1,0,0,0,0},
{0,0,0,0,1,1,0,0},{0,0,0,0,0,0,1,0},{0,0,0,0,0,0,1,0},{1,1,1,1,1,1,1,1},
};
for (int i = 0; i < cond; i++)
for (int j = 0; j < tran; j++)
mx1[i][j] = m1[i][j];
for (int i = 0; i < tran; i++)
for (int j = 0; j < cond; j++)
mx2[i][j] = m2[i][j];
if (rank == ROOT) {
std::cout << "Введите начальное состояние (8): " << std::endl;
for (int i = 0; i < cond; i++)
std::cin >> Sost[i];
}
MPI_Barrier(MPI_COMM_WORLD);
MPI_Bcast(Sost, cond, MPI_INT, ROOT,MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
FindActiveTransistions();
Manually();
}
break;
case 3: {
if (rank == ROOT) {
std::cout << "Состояния " << std::endl;
std::cin >> cond;
std::cout << "Переходы " << std::endl;
std::cin >> tran;
std::cout << "Матрица (построчно: состояние->требуется для каждого перехода) "
<< std::endl;
for (int i = 0; i < cond; i++)
for (int j = 0; j < tran; j++)
std::cin >> mx1[i][j];
std::cout << "Матрица (построчно: переход->получит каждое состояние) " <<
std::endl;
for (int i = 0; i < tran; i++)
for (int j = 0; j < cond; j++)
std::cin >> mx2[i][j];
std::cout << "Начальное состояние " << std::endl;
for (int i = 0; i < cond; i++)
std::cin >> Sost[i];
}
MPI_Barrier(MPI_COMM_WORLD);
MPI_Bcast(&cond, 1, MPI_INT, ROOT,MPI_COMM_WORLD);
MPI_Bcast(&tran, 1, MPI_INT, ROOT,MPI_COMM_WORLD);
MPI_Bcast(mx1, N*M, MPI_INT, ROOT,MPI_COMM_WORLD);
MPI_Bcast(mx2, M*N, MPI_INT, ROOT,MPI_COMM_WORLD);
MPI_Bcast(Sost, cond, MPI_INT, ROOT,MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
FindActiveTransistions();
Manually();
}
break;
default:
break;
}
times[rank] = MPI_Wtime() - times[rank];
std::cout << "\nВремя [" << rank << "] : " << times[rank] << std::endl;
MPI_Barrier(MPI_COMM_WORLD);
if (rank == 0) {
time = MPI_Wtime() - time;
std::cout << "\nВремя работы программы: " << time << std::endl;
system("pause");
}
MPI_Finalize();
return 0;
}
void FindActiveTransistions() {
if (rank == ROOT) {
for (int i = 0; i < tran; i++)
ch[i] = 0;
int step = tran / size;
for(int i = 0; i < size; i ++) {
sBuf[i][0] = step * i;
sBuf[i][1] = sBuf[i][0] + step;
}
}
int se[SIZE/2];
// Распараллеливание поиска активных переходов
MPI_Scatter(sBuf, 2, MPI_INT, se, 2, MPI_INT, ROOT, MPI_COMM_WORLD);
for (int i = 0; i < tran/SIZE; i++)
buf[i] = 0;
for (int i = se[0]; i < se[1]; i++)
for (int j = 0; j < cond; j++) {
if (mx1[j][i] >= 1)
if (Sost[j] < mx1[j][i])
break;
if (j == cond - 1) {
buf[i-se[0]] = 1;
}
}
MPI_Alltoall(buf, tran/SIZE, MPI_INT, ch, tran/SIZE, MPI_INT, MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
}
void PrintActiveTransistions() {
int cnt = 0;
std::cout << "\n\nАктивные переходы: " << std::endl;
for (int i = 0; i < tran; i++) {
if (ch[i] == 1)
std::cout << i + 1 << " ";
else
cnt++;
}
fl = true;
if (cnt == tran) {
std::cout << "\nАктивных переходов нет!" << std::endl;
fl = false;
}
}
void Manually() {
std::cout << "Текущая маркировка: ";
for (int i = 0; i < cond; i++)
std::cout << Sost[i] << " ";
int per;
FindActiveTransistions();
for (int i = 0; i < oper; i++) {
if (rank == ROOT) {
PrintActiveTransistions();
if (!fl)
break;
std::cout << "\nВыберите активный переход: ";
while (1) {
std::cin >> per;
per--;
if (ch[per] == 0)
std::cout << "\nПереход не активен или его не существует, выберите другой переход: " << std::endl;
else
break;
}
}
MPI_Bcast(&per, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
for (int i = 0; i < cond; i++) {
Sost[i] -= mx1[i][per];
Sost[i] += mx2[per][i];
}
if (rank == ROOT) {
std::cout << "Текущая маркировка: ";
for (int i = 0; i < cond; i++)
std::cout << Sost[i] << " ";
}
FindActiveTransistions();
}
}
void Auto() {
int per;
srand(time(NULL));
for (int i = 0; i < oper; i++) {
if (rank == ROOT) {
if (!fl)
break;
while (1) {
per = rand() % tran;
if (ch[per] == 1)
break;
}
}
MPI_Bcast(&per, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
for (int i = 0; i < cond; i++) {
Sost[i] -= mx1[i][per];
Sost[i] += mx2[per][i];
}
FindActiveTransistions();
}
}Анализ распараллеливания:
диаграммы загрузки процессора для последовательной програмым и с распараллеливанием с openMP:
c MPI:
Замеры времени работы програмы для сетей различного размера:
Выводы
Для выполнения было задано 10000 переходов. Программа запускалась на машине с двумя физическими ядрами, но четырьмя логическими процессорами. Программы, выполняющиеся в параллельном режиме с помощью OpenMP и MPI, работают быстрее на 3.284 сек. (41,1%) и 3.157 сек.(39.5%) соответственно, чем программа, работающая в последовательном режиме. Однако, такие результаты можно получить при большом объёме данных – при малом объёме разница во времени будет
менее значительна.
Последнее редактирование:
