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

Тема в разделе "Общие вопросы по С и С++", создана пользователем rrrFer, 26 сен 2016.

  1. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Постановка задачи:
    Разработать программу, моделирующую работу сетей Петри, с возможностью автоматического моделирования и проверки в ручном режиме.

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

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

    Пример работы сети Петри:
    В левой позиции находятся две метки, в правой позиции нет меток:
    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). Полные данные нужны для дальнейших расчётов состояния.

    Исходный код:

    Код (C):
    #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%) соответственно, чем программа, работающая в последовательном режиме. Однако, такие результаты можно получить при большом объёме данных – при малом объёме разница во времени будет
    менее значительна.
     
    #1 rrrFer, 26 сен 2016
    Последнее редактирование: 26 сен 2016
    vital нравится это.
Загрузка...
Похожие Темы - Моделирование сети Петри
  1. Alex92
    Ответов:
    1
    Просмотров:
    1.324
  2. smthelse
    Ответов:
    1
    Просмотров:
    1.264
  3. smthelse
    Ответов:
    0
    Просмотров:
    1.236
  4. Webkiller
    Ответов:
    0
    Просмотров:
    1.460
  5. Lesha1111
    Ответов:
    0
    Просмотров:
    2.083

Поделиться этой страницей