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

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

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

На фиг. 1 представлена схема устройства; на фиг. 2 - пример схемной реализации одного канала блока моделей вершин; на фиг, 3 - пример моделируемой сети Петри.

Эквивалентом графического представления сети Петри на фиг. 3 является табличный способ задания графа Петри с помощью таблицы топологии. Здесь для каждого j-ro перехода (1 j 16) представлены входные ем, в2,..., §Те и выходные ai, 32,..., aie разметочные вектора (в общем случае j 1 М), а также вектор начальной разметки /Ло,

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

На фиг. 2 представлена в качестве примера схема реализации первого канала (из возможных М) блока 2 моделирования версо

с

00

о

СА)

шин. Схема содержит счетчик 10, 11 сравнения кодов на равенство, элемент 12 И, триггер 13, элемент задержки 14, элементы 15 и 16 запрета, 17 - регистр кода длительности перехода.

На фиг. 3 в качестве примера приведен граф Петри, описывающий функционирование поездов и станций метрополитена. Здесь используются обозначения pi, p2, .... Р8 и ti, t2, ..., ts для кольцевого участка мет- рополитена. Позиции рю, Р11, Р12 выполняют функции депо для поездов метрополитена. Позиция рэ играет роль разьезда, через который выводятся поезда из кольцевого участка для постановки в де- по и вводятся из депо в кольцевую линию. Для ввода/вы вода поездов используется также позиция pi.

Нетрудно видеть, что pi и рэ являются конфликтными позициями, поскольку име- ют более одной выходной дуги без учета инверсных дуг.

Позиции pis, P14, Р15, а также pie и pig являются управляющими, или инициирующими, т.к. не имеют входных дуг. В свою очередь, различают-два типа управляющих позиций: с естественным исключением метки, когда хотя бы одна выходная дуга не является инверсной (позиции pi3, p 14, pis); с принудительным исключением метки, кЬг- да все выходные дуги являются инверсными (позиции рта и pig).

Последовательность вывода поездов из депо определяется очередностью записи метки в какую-либо из управляющих пози- ций pis, Р14, pis. Перемещение метки из позиции рэ в какую-либо из свободных позиций рю, Р11, Р12 производится последующему правилу: в режиме разгрузки кольцевой линии метка из позиции pf через переход tio перемещается в позицию рэ, откуда -.через переход ti4 в позицию р12. Следующими по порядку загружаются позиции рп и рю через переходы tis и tie соответственно. Таким образом, конфликтные ситуации, связанные с позицией рэ, в основном разрешаются за счет соответствующей топологии графа Петри. В отличие от этого конфликтные ситуации, связанные с позицией pi, разрешаются исключительно путем записи соответствующих меток в управляющие позиции pis и pig..

Формирователь 6 импульсов служит для формирования исполнительного сигнала записи информации по тактируемым входам в регистр 9 меток. Формирователь инициируется сигналами с выходом элементов 4 и 5 ИЛИ и вырабатывает кратковременный импульс.

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

Группа входов 9.1 и 9.2 служит для тактируемой установки разрядов регистра в лог. 1 и О соответственно,

С учетом свойств управляющих позиций графа Петри следует, что число входов 9,2 установки 0 регистра меток равно общему числу позиций графа Петри минус ко ичест- во управляющих позиций с принудительным исключением метки. Аналогично, число входов 9.3 установки в 1 равно общему числу позиций графа Петри минус число всех управляющих позиций.

Логический узел 3 входных разметоч- . ных векторов состоит из элементов И, количество которых равно М. Каждый j-й элемент И (j 1, М) подключен входами к прямым или инверсным выходам соответствующих разрядов регистра 9 меток в зависимости от значений ненулевых коэффициентов во входном разметочном векторе: положительным единицам соответствует подача прямого сигнала, отрицательным единицам - подача инверсного сигнала. Например, элемент И 3.1 на фиг, 2, относящийся к переходу ti, формирует на выходе терм .

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

В зависимости от топологии графа Петри, определяемой выходными разметочными векторами, узел 7 либо обеспечивает непосредственное подключение соответствующего входа из группы входов 9.1 к соответствующему выходу из второй группы выходов блока 2 моделирования вершин, либо указанная связь осуществляется через элемент ИЛИ, если в графе Петри существуют позиции, содержащие две и более входные дуги со стрелками. Например, в графе на фиг, 3 позиция pi имеет две входные дуги со стрелками, поступающими из переходов ta и tg, поэтому входы элемента ИЛИ из угла 7, формирующего сигнал установки в 1 первого разряда регистра 9, должны быть связаны с выходами 8- и 9-го каналов второй группы выходов блока 2. Аналогично, позиции рэ соответствует четырехвходовой элемент ИЛИ, подключенный входами к выходам 10-го, 11-го, 12-го и 13-го каналов

второй группы выходов блока 2, а выходом - к входу установки в лог. 1 9-го разряда регистра 9 меток.

Остальные сигналы установки в лог. 1 разрядов регистра 9 не требуют элементов ИЛИ, поскольку непосредственно снимаются с выходов соответствующих каналов второй группы выходов блока 2 согласно топологии графа Петри.

Узел 8 служит для удаления меток из тех позиций, которые связаны со входами возбужденного перехода, т.е. данный узел формирует сигналы установки в лог. О соответствующих разрядов регистра 9. Формирование сигнала установки в лог. О i-ro разряда происходит при совпадении двух условий: во-первых, наличия дуги со стрелкой с выхода j-ro перехода на вход i-ой позиции, и во-вторых, необходимо, чтобы в указанной i-ом разряде находилась метка, т.е. если pi 1. Таким образом, узел 8 представляет собой совокупность элементов И/ИЛИ-И, причем составной элемент ИЛИ-И используется только для конфликтных позиций.

Перед началом работы устройства в него должен быть загружен код начальной разметки по входам 9.3 асинхронной записи информации регистра 9, а также записаны коды задания длительностей переходов.По- следние записываются в регистры, входящие в составы каналов блока 2. На фиг. 2 такой регистр показан под номером 17 для первого канала. ,

Пусть для примера метки записаны в

ПОЗИЦИЯХ Р1, рЗ, р4 И р19 (СМ. фИГ. 3).

Непосредственно моменту запуска устройства предшествует сигнал ОБЩИЙ СБРОС, обеспечивающий начальную установку элементов памяти (цепи подачи этого сигнала на фиг. 1 не показаны). В представленном на фиг. 3 графе Петри и при заданном векторе начальной разметки соблюдены условия возбуждения переходов ti и t4. Элемент И 3.1 вырабатывает сигнал лог. 1, и при запуске генератора 1 тактовых импульсов сигнал с выхода последнего, проходя через элемент 12 И, устанавливает в 1 триггер 13, выходной сигнал которого, воздействуя на вход ER разрешения счета счетчика 10, переводит его в режим суммирования.

Сразу же после включения в работу счетчика 10 с помощью элементов 14 и 15 формируется импульс на выходе 1 блока 2 моделирования вершин. Этот импульс, проходя через логический узел 8, появляется на входе установки в О первого разряда регистра 9 меток. Сама установка в О инициируется сигналом с выхода формирователя 6,

запускаемого сигналом с выхода М-входо- вого элемента 4 ИЛИ. После исключения метки из позиции pi на выходе элемента И 3.1 устанавливается лог. О. Когда код на выходе счетчика 10 сравняется с кодом в регистре 17, на выходе блока 11 сравнения кодов появляется сигнал лог. Г1, который устанавливает в О триггер 13. При этом с помощью элементов 14 и 16 на

0 выходе 2 первого канала блока 2 первого канала блока 2 моделирования вершин формируется импульс окончания длительности перехода ti, который используется также для обнуления счетчика 10, подготавливая

5 тем самым первый канал для нового цикла работы.

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

0 формирователя 6.

Одновременно и параллельно с описанными выше процессами, связанными с возбуждением перехода ti, происходят процессы, связанные с возбуждением пере5 хода 14.

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

0 меток. Тем самым по значениям меток в управляющих позициях можно изменить, в частности, режим работы метрополитена и промоделировать реальные процессы в нем. При этом следует иметь в виду, что

5 исключение ранее введенных меток из управляющих ПОЗИЦИЙ Р18 И р19 ВОЗМОЖНО

только по инициативе оператора путем корректировки вектора текущей разметки.

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

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

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

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

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

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

1L

V

ч Л

ч

ч ч ь t

ч t

1р 1 р 1 РЬ fр iF р 1р р ь ЁГ РЛ 1 P(J IP tf ip i p

,

,

f;

-s.

ec Ъ

tf 1. e,o

т,..

Ъ. т«

T.5 K

«, &.,

Фи.г.2.