Устройство для моделирования графов петри

 

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

СОЮЗ СОВЕТСКИХ.

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (ll) А1 (50 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н A ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И (ЛНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4240557/24-24 (22) 08.05.87 (46) 30.05.89. Бюл. У 20 (71) Институт проблем моделирования в энергетике АН УССР и Специальное конструкторско-технологическое бюро средств моделирования с опытным производством Института проблем моделирования в энергетике АН УССР (72) В.В. Васильев, В.В. Кузьмук, Г.Г. Купченко, Е.Б. Лисицин и В.А. Иумов (53) 681. 333 (088. 8) (56) Питерсон Дж. Теория сетей Петри и .оделирование систем. M. Мир, 1984 » с. 246.

Авторское свидетельство СССР

У 1171803, кл, G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ .

ГРАФОВ ПЕТРИ

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

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

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

Устройство содержит первую-третью группы из регистров 1-3 соответствен но, где М - количество вершин переходов в графе Петри, группу из М счет-, чиков 4, первую и вторую группы из

М блоков 5 и 6 соответственно элементов И, группу из M элементов И 7, группу из М элементов ИЛИ 8, группу из М элементов 9 задержки, группу из М блоков 10 поразрядного сравнения, первый-третий блоки 11-13 соответственно элементов ИЛИ, блок 14

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

Кроме того, на фиг. 1 обозначены входы 28 задания входного вектора

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

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

Пусть требуется смоделировать систему, описанную графом Петри, представленным на фиг. 3. Особенностью графов Петри является наличие двух типов вершин: переходов „ и мест

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

его топология и начальная разметка ш . Каждая вершина перехода t моделирует время выполнения какого-то действия в процессе. Переход t„ сра-. батывает, если во всех местах P дуги от которых направлены к P находятся метки. Так, например, переход t может сработать.В.момент начала выполнения действия a„, (переход t ) метки из всех входных мест перехода й„ удаляются и после окон- 50 чания моделирования действия а (через время ht<) во все выходные места перехода t„ (x которым от Р направлены дуги) записываются.-Кажцый пе,реход .Ю„ характеризуется входным раз- 55 екметочным вектором р и выходным раз

1: меточным вектором ", которые отражают связи перехода с его входными и выходными местами (см. табл. фиг.3).

Одним из наиболее известных и часто применяемых обобщений сетей Петри являются сети Петри с приоритетом. Введение приоритетов позволяет значительно повысить описательную мощность и мощность моделирования сетей Петри, разрешить ряд возникающих при моделировании реальных объектов конфликтных ситуаций. В названном обобщении сетей Петри каждой вершине перехода ставится в соответствие некоторый уровень приоритета, причем наибольшим приоритетом обладает переход для которого Р,,„ = 1, уровень P

= 2, отражает более низкий приоритет и т.д. Переход с более высоким приоритетом обладает преимущественным правом запуска в случае возникнове.ния конфликтных ситуаций. Так, например, на фиг. 3 при установившейся разметке возник конфликт в месте P

5 переходы t< и t претендует на одновременное использование метки из этого места. Введение уровней приоритета Р,, = 1, Р„ = 2, определяет, что вначале будет запущен переход а переход tz может быть запущен только по окончании срабатывания

На фиг. 3 представлен пример моделируемого графа Петри при моделировании управления движением транспортеров в некоторой транспортной сети. Два транспортера непрерывно движутся в этой сети, каждый по своему маршруту и транспортируют детали от общего места загрузки, моделируемого переходом t>, к местам разгрузки. Процессы разгрузки моделируются переходами t> и t<. Переходы

t< моделируют движение соответствующих транспортеров от места загрузки к местам выгрузки и наоборот. Места Р и Р обеспечивают поочередное направление транспортеров к разным местам выгрузки. Система управления должна обеспечить нали-. чие только одного транспортера в месте загрузки. Для этого в модель введено место Р, разрешающее срабатывание только одного из переходов t u

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

Р . Однако в алгорйтме управления возможно возникновение конфликтных ситуаций при одновременном подходе транспортеров к месту разгрузки, че1483460 6

50 е

001 000001 и заносится в регистр 17. му соответствует разметка графа Петри, приведенная на фиг. 3. В сетях Петри традиционного определения нет средств для разрешения подобных конфликтов. .5

Введение уровней приоритетов переходов позволяет решить эту проблему.

При Р„ = 1 и Р„ = 2 определяется преимущественное право проезда транспорта, циркулирующего по маршруту

tr

Моделирование построенного графа

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

Для загрузки графа Петри в устройствовсоставляется таблица топологии графа Петри (см. фиг. 3), позволяющая отразить входные и и выходок -»

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

В процессе загрузки:,исходных дан- 25 ных в устройстве значения " р заносятся в К-е регистры 1 первой группы,, 1 значения"" р в К-е регистры 2 второи группы. Значения d t к заносятся в

К-е регистры 3 третьей группы, значе- З0 ние шр заносится в регистр 17.

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

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

К-го перехода текущему приоритету.

По спаду импульса с выхода 35 блока

25 синхронизации счетчик 26 обнуля40 ется и начинает пересчитывать значения приоритетов переходов начиная с Р„ = 1.

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

® О О О 1 1 ОООО

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

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

После окончания моделирования в восьмой момент модельного времени

«» 8 значение m будет следующим: ша00100001 00001000

1 ш, 0 О 1 Î 1 Î Î O 1

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

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

Петри с приоритетом, описывающие параллельные процессы.

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

Устройство для моделирования графов Петри, содержащее три группы из

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

1483460 пуска которого является входом пуска ! устройства, причем вход задания входного вектора К-й вершины перехода устройства подключен к информационно5 му входу К-го регистра первой группы (К=1,..., М), выход которого подключен к первому информационному входу

К-го блока поразрядного сравнения и к информационному входу К-го бло- 10 ка элементов И первой группы, выход которого подключен к К-му входу первого блока элементов ИЛИ, выход которого подключен к первому информационному входу блока элементов ИСКЛВ- 15

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

И второй группы, выход которого подключен к К-му входу второго блока элементов ИЛИ, выход которого подключен к первому информационному входу блока логического сложения, выход которогб подключен к второму информационному входу коммутатора, вход задания времени исполнения К-й вершины перехода устройства подключен к информационному входу К-го регистра третьей группы, выход которого подключен к информационному входу К-ro счетчика группы, выход признака пере35 хода через ноль которого подключен ,к входу K-ro элемента задержки группы,: к управляющему входу К-го блока элементов И второй группы и к К-му входу первого элемента ИЛИ, выход которого подключен к первому входу первого элемента И, управляющий вход

К-го блока элементов И первой груп пы соединены с входом разрешения счета К-го счетчика группы и с К-м входом второго элемента ИЛИ, выход которого подключен к первому входу второго элемента И, выход первого элемента И подключен к первому управляющему входу коммутатора и к первому50 входу третьего элемента ИЛИ, выход

-которого подключен к входу признака записи регистра, выход второго элемента И подключен к второму входу третьего элемента ИЛИ к. второму управо5 ,ляющему входу коммутатора, выход которого подключен к первому входу третьего блока элементов ИЛИ, выход

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

К-го счетчика группы, вход задания начальной разметки устройства подключен к второму входу третьего блока элементов ИЛИ, вход начальной устанонки устройства подключен к входам признаков записи всех регистров всех групп, к вторым входам всех элементов

ИЛИ группы и к второму входу четвертого элемента ИЛИ, первый выход блока синхронизации подключен к второму входу второго элемента И, второй выход блока синхронизации подключен к второму входу первого элемента И и к вычитающнм входам всех счетчиков группы, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности моделирования графов Петри, за счет исключения конфликтов при выполнении переходов в графе, в него введены группа из К элементов И, счетчик, блок памяти, пятый элемент ИЛИ, к первому входу которого подключен вход начальной установки устройства, к второму входу пятого элемента ИЛИ подключен второй выход блока синхронизации, выход пятого элемента ИЛИ подключен к входу установки в "0" счетчика, третий выход. блока синхронизации подключен к суммирующему sxoду счетчика, выход которого подключен к адресному входу блока памяти, К-й разряд информационного выхода которого подключен к первому входу К-го элемента И группы, к второму входу которого подключен выход признака неравенства нулю результата сравнения К-ro блока поразрядного сравнения группы,, выход К-го элемента И группы подключен к управляющему входу -ro блока элементов И первой группы, установочный вход блока па мяти соединен с входом задания параметров переходов устройст— ва.

14834бО

1483460

Вко

Jlj

Вхо

Составитель А. Мишин

Техред Л. Сердюкова Корректор М. Пожо

Редактор О. Спесивых

Заказ 2834/46 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Я-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101