Устройство для моделирования графов Петри Советский патент 1989 года по МПК G06F15/173 

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

Целью изобретения является повышение достоверности моделирования графов Петри за счет исключения конфликтов при выполнении переходов в графе.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - временная диаграмма работы блока синхронизации; на фиг. 3 - пример моде(лируемого графа Петри и таблица исходных данных для его моделирования. Устройство содержит первую-третью группы из регистров 1-3 соответственно, где М - количество вершин переходов в графе Петри, группу из М счет- чиков 4, первую и вторую группы из М блоков 5 и 6 соответственно эле- ментов И, группу из М элементов И 7, группу из М элементов ИЛИ 8, группу из М элементов 9 задержки, группу из М блоков 10 поразрядного сравнения, первый-третий блоки 11-13 соответственно элементов ИЛИ, блок 14

4ь

00

со

4Ь

О

элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок 15 логического сложения, коммутатор 16, , регистр 17, с первого по пятый элементы 18,..., 22 соответственно ИЛИ, первый и второй элементы 23 и 24 соответственно, блок 25 синхронизации, счетчик 26 и блок 27 памяти.

Кроме того, на фиг. 1 обозначены входы 28 задания входного вектора К-й вершины перехода устройства входы 29, входы 30 задания времени исполнения К-й верщины перехода устройства, вход 31 начальной установки устройства, вход 32 пуска устрой- ства, вход 33 задания начальной разметки устройства, первый-третий выходы 34-36 соответственно блока 25 синхронизации, вход 37 задания приоритетов переходов.

Устройство работает следующим образом.

Пусть требуется смоделировать систему, описанную графом Петри, представленным на фиг. 3. Особенностью графов Петри является наличие двух типов вершин: переходов tK и мест Рр, а также наличие меток, которые, показывают, какие вершины при обходе графа устройство моделирует в данный момент. Метки располагаются в вершинах мест Рр и моделируют в динамике окончание реальных действий, местонахождение метод отображается вектором разметки Шд (0,0,1,1,1,0, 0,0,1). Цифра О на первом месте обозначает, что место Р( , не содержит метку, а 1 на третьем месте обозначает, что РЗ содержит метку. При составлении графа Петри устанавливается

его топология и начальная разметка

т0. Каждая вершина перехода t моделирует время выполнения какого-то действия в процессе. Переход tk срабатывает, если во всех местах Pg , дуги от которых направлены к РЈ, находятся метки. Так, например, переход t может сработать.В момент начала выполнения действия ак, (переход tK) метки из всех входных мест перехода tK удаляются и после окон- чания моделирования действия а к (че рез время At) во все выходные места перехода tK (к которым от Ре направлены дуги) записываются. Каждыц переход Јк характеризуется входным раз-

меточным векторомек лГ и выходным раз

1

мы

меточным вектором Цд , которые отражают связи перехода с его входным

g $ 0

5

0

0 5

0

5

и выходными местами (см. табл. фиг.З). Одним из наиболее известных и часто применяемых обобщений сетей Петри являются сети Петри с приоритетом. Введение приоритетов позволяет значительно повысить описательную мощность и мощность моделирования сетей Петри, разрешить ряд возникающих при моделировании реальных объектов конфликтных ситуаций. В названном обобщении сетей Петри каждой вершине перехода ставится в соответствие некоторый уровень приоритета, причем наибольшим приоритетом обладает переход t, для которого Ргк 1, уровень Ргк 2, отражает более низкий приоритет и т.д. Переход с более высоким приоритетом обладает преимущественным правом запуска в случае возникновения конфликтных ситуаций. Так, например, на фиг. 3 при установившейся разметке возник конфликт в месте Ps - переходы t и tg претендует на одновременное использование метки из этого места. Введение уровней приоритета РГ5 1, РГ6 2, определяет, что вначале будет запущен переход t5, а переход t6 может быть запущен только по окончании срабатывания t7.

На фиг. 3 представлен призер моделируемого графа Петри при моделировании управления движением транспортеров в некоторой транспортной сети. Два транспортера непрерывно движутся в этой сети, каждый по своему маршруту и транспортируют детали от общего места загрузки, моделируемого переходом t, к местам разгрузки. Процессы разгрузки моделируются переходами t и t. Переходы t(, ta, ts, t6 моделируют движение соответствующих транспортеров от места загрузки к местам выгрузки и наоборот. Места Ре и Р9 обеспечивают поочередное направление транспортеров к разным местам выгрузки. Система управления должна обеспечить наличие только одного транспортера в месте загрузки. Для этого в модель введено место Ру, разрешающее срабатывание только одного из переходов t5 и tg и только в случае незанятости места загрузки,что обеспечивается определением Р5 как выходного места для Р7. Однако в алгоритме управления возможно возникновение конфликтных ситуаций при одновременном подходе транспортеров к месту разгрузки, че514834606

му соответствует разметка графа Петри, После перевода счетчика 4

жим Счет он начинает работ жиме вычитания, причем счетн него являются импульсы, пост с выхода 35 блока 25 синхрон После обнуления пятого счетч на его выходе появится сигнал нака окончания имитации 5, оп

приведенная на фиг. 3. В сетях Петри традиционного определения нет средств, для разрешения подобных конфликтов. Введение уровней приоритетов переходов позволяет решить эту проблему. При РР5 1 и РП6 2 определяется преимущественное право проезда транспорта, циркулирующего по маршруту

t fcj W

Моделирование построенного графа Петри позволяет определить пропускную способность транспортной сети, частоту возникновения конфликтов, длительности простоя и т.д.

Для загрузки графа Петри в устройство «составляется таблица топологии графа Петри (см. фиг, 3), позвои выход.5

в режим Счет он начинает работать в режиме вычитания, причем счетными для него являются импульсы, поступающие с выхода 35 блока 25 синхронизации, После обнуления пятого счетчика 4 на его выходе появится сигнал признака окончания имитации 5, определя10 ющий перезапись из пятого регистра 3 времени исполнения 5-й вершины перехода устройства в пятый счетчик 4, а также разрешающий подачу из второго регистра 2 значения выходного вектора

15 на вход блока 15 логического сложения для сложения со значеняем вектора текущей разметки. Одновременно сигнал признака окончания моделирования tf разрешает запись нового значения вектора текущей разметки в регистр 17. Таким образом, моделирование перехода tj. будет окончено по приходу восьмого импульса с выхода 35 блока 25 синхронизации (восьмой момент модельного

20

ляющая отразить входные8 1 лГ

QK -Ч

ные и разметочные вектора переходов tK приоритеты переходов Р, начальную разметку и длительности срабатывания переходов tK.

В процессе загрузки .исходных дан- 25 времени). В девятый момент модельног ных в устройстве значения к7Г заносят- времени в течение Т3 (см. фиг. 2) ся в К-е регистры 1 первой группы,, будет запущен tr, после окончания

моделирования которого в 14-й момент модельного времени будут запущены

значения щ в К-е регистры 2 второй

труппы. Значения u t k заносятся в

К-е регистры 3 третьей группы, значе- gg tfe, Ц и т.д.

ние тд заносится в регистр 17.

Режим моделирования графа Петри начинается по заднему фронту импульса на входе 32 пуска устройства.

Разрешение на запуск К-го переходапоступит при выполнении условия Рк- - (Кет, и при соответствии приоритета

К-го перехода текущему приоритету. По спаду импульса с выхода 35 блока 25 синхронизации счетчик 26 обнуляется и начинает пересчитывать значения приоритетов переходов начиная с Р„ 1.

При изменении кода на адресном входе блока 27 памяти на информационных выходах, соответствующих переходам, появляются разрешающие (при выполнении ек ju e mQ) или запрещающие запуск перехода сигналы. При выполнении указанных условий первым запустится переход (см. фиг. 3), при этом в состояние Счет переходит , счетчик 4, вычисляется новое значение вектора текущей разметки:

5 001 1 10001

esfi® 0001 1 0000

Iм

001000001

,лЛ

и заносится в регистр 17.

35

40

После окончания моделирования tf в восьмой момент модельного времени значение тп0 будет следующим:

Тао о 0100001 О О О 1 000

Sjfo о 1 о 1 о о a 1

Далее устройство продолжает работать по описанному алгоритму.

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

45 Формула изобретения

Устройство для моделирования графов Петри, содержащее три группы из М регистров, где М - количество вер50 шин переходов в графе Петри, группу из М элементов ИЛИ, группу из М блоков поразрядного сравнения, две группы из М блоков элементов И, группу . из М счетчиков, группу из М элементов

55 задержки, три блока элементов ИЛИ, четыре элемента ИЛИ, два элемента И, блок логического сложения, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, коммутатор, регистр и блок синхронизации, вход

После перевода счетчика 4

5

в режим Счет он начинает работать в режиме вычитания, причем счетными для него являются импульсы, поступающие с выхода 35 блока 25 синхронизации, После обнуления пятого счетчика 4 на его выходе появится сигнал признака окончания имитации 5, определя0 ющий перезапись из пятого регистра 3 времени исполнения 5-й вершины перехода устройства в пятый счетчик 4, а также разрешающий подачу из второго регистра 2 значения выходного вектора

5 на вход блока 15 логического сложения для сложения со значеняем вектора текущей разметки. Одновременно сигнал признака окончания моделирования tf разрешает запись нового значения вектора текущей разметки в регистр 17. Таким образом, моделирование перехода tj. будет окончено по приходу восьмого импульса с выхода 35 блока 25 синхронизации (восьмой момент модельного

0

tfe, Ц и т.д.

После окончания моделирования tf в восьмой момент модельного времени значение тп0 будет следующим:

Тао о 0100001 О О О 1 000

Sjfo о 1 о 1 о о a 1

Далее устройство продолжает работать по описанному алгоритму.

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

Формула изобретения

Устройство для моделирования графов Петри, содержащее три группы из М регистров, где М - количество вершин переходов в графе Петри, группу из М элементов ИЛИ, группу из М блоков поразрядного сравнения, две группы из М блоков элементов И, группу из М счетчиков, группу из М элементов

задержки, три блока элементов ИЛИ, четыре элемента ИЛИ, два элемента И, блок логического сложения, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, коммутатор, регистр и блок синхронизации, вход

|пуска которого является входом пуска устройства, причем вход задания входного вектора, К-й вершины перехода устройства подключен к информационному входу К-го регистра первой группы (,..., М), выход которого подключен к первому информационному входу К-го блока поразрядного сравнения и к информационному входу К-го блока элементов И первой группы, выход которого подключен к К-му входу первого блока элементов ИЛИ, выход ко- торого подключен к первому информационному входу блока элементов ИСКЛЮ- ЧАЮЩЕЕ ИЛИ, выход которого подключен к первому информационному входу коммутатора, вход задания выходного вектора К-й вершины перехода устройства подключен к информационному входу К-го регистра второй группы, выход которого подключен к информационному входу К-го блока элементов И второй группы, выход которого подключен к К-му входу второго блока элементов ИЛИ, выход которого подключен к первому информационному входу блока логического сложения, выход которого подключен к второму информационному входу коммутатора, вход задания времени исполнения К-й вершины перехода устройства подключен к информационному входу К-го регистра третьей группы, выход которого подключен к информационному входу К-го счетчика группы, выход .при знак а перехода через ноль которого подключен ,к входу Кто элемента задержки груп- ды, к управляющему входу К-го блока элементов И второй группы и к К-му входу первого элемента ИЛИ, выход которого подключен к первому входу первого элемента И, управляющий вход К-го блока элементов И первой группы соединены с входом разрешения счета К-го счетчика группы и с К-м входом второго элемента ИЛИ, выход ,которого подключен к первому входу второго элемента И, выход первого элемента И подключен к первому управляющему входу коммутатора и к первому входу третьего элемента ИЛИ, выход которого подключен к входу признака записи регистра, выход второго элемента И подключен к второму входу третьего элемента ИЛИ к: второму управ яющему входу коммутатора, выход которого подключен к первому входу

0

0

5

5 0 5

0

5

0

5

третьего блока элементов ИЛИ, выход которого подключен к информационному входу регистра, выход которого подключен к второму информационному входу блока логического сложения, к второму информационному входу блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и к вторым информационным входам всех блоков поразрядного сравнения группы, выход К-го элемента задержки группы подключен к первому входу К-го элемента ИЛИ группы, выход которого подключен к входу признака записи К-го счетчика группы, вход задания начальной разметки устройства подключен к второму входу третьего блока элементов ИЛИ, вход начальной установки устройства подключен к входам признаков записи всех регистров всех групп, к вторым входам всех элементов ИЛИ группы и к второму входу четвертого элемента ИЛИ, первый выход блока синхронизации подключен к второму входу второго элемента И, второй выход блока синхронизации подключен к второму входу первого элемента И и к вычитающим входам всех счетчиков группы, отличающееся тем, что, с целью повышения достоверности моделирования графов Петри, за счет исключения конфликтов при выполнении переходов в графе, в него введены группа из К элементов И, счетчик, блок памяти, пятый элемент ИЛИ, к первому входу которого подключен вход начальной установки устройства, к второму входу пятого элемента ИЛИ подключен второй выход блока синхронизации, выход пятого элемента ИЛИ подключен к входу установки в О счетчика, третий выход блока синхронизации подключен к суммирующему входу счетчика, выход которого подключен к адресному входу блока памяти, К-й разряд информационного выхода которого подключен к первому входу К-го элемента И группы, к второму входу которого подключен выход признака неравенства нулю результата сравнения К-го блока поразрядного сравнения группы, выход К-го элемента И группы подключен к управляющему входу К-го блока элементов И первой группы, установочный вход блока памяти соединен с входом задания параметров переходов устройст - ва.

«i

Фиг.1

J/H53

тг

28т

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