Моделирование сети Петри на С++. Параллельная реализация с MPI

  • Автор темы rrrFer
  • Дата начала
R

rrrFer

Гость
#1
Постановка задачи:
Разработать программу, моделирующую работу сетей Петри, с возможностью автоматического моделирования и проверки в ручном режиме.

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

В сетях Петри происходит выполнение одного из возможных дискретных событий. Если в какой-то момент времени разрешено более одного перехода, то любой из них может стать «следующим» запускаемым.

Пример работы сети Петри:
В левой позиции находятся две метки, в правой позиции нет меток:
1.png
Для совершения перехода из левой позиции в правую необходимо наличие в левой позиции одной метки. Условия соответствуют требованиям для перехода:
2.png
Переход совершен. В левой позиции осталась одна метка, в правой позиции появилась одна метка:
3.png

Описание работы программы:
При запуске программы требуется ввести количество переходов, которые должна выполнить программа. Далее пользователю предоставляется выбор между запуском сети Петри в автоматическом режиме или в ручном для самостоятельной работы с сетью. При выборе ручного режима так же предоставляется выбор между использованием уже готовой сети Петри и самостоятельным вводом данных для сети. При выборе автоматического режима генерируется сеть, позволяющая бесконечно использовать любой переход – это требуется для того, чтобы реализовать любое указанное число операций без потери времени на выбор разрешенного перехода.

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

Для моделирования позиций используется массив 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:
omp.png
c MPI:
mpi.png

Замеры времени работы програмы для сетей различного размера:
Снимок экрана из 2016-09-26 23-59-34.png

Выводы
Для выполнения было задано 10000 переходов. Программа запускалась на машине с двумя физическими ядрами, но четырьмя логическими процессорами. Программы, выполняющиеся в параллельном режиме с помощью OpenMP и MPI, работают быстрее на 3.284 сек. (41,1%) и 3.157 сек.(39.5%) соответственно, чем программа, работающая в последовательном режиме. Однако, такие результаты можно получить при большом объёме данных – при малом объёме разница во времени будет
менее значительна.
 
Последнее редактирование модератором:
Симпатии: Понравилось vital