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

 

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

СОК)3 СОВЕТСКИХ

СОЦИАЛИСТИ-IFСКИХ

РЕСПУБЛИК (51)5 G 06 F 15/20

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

06

О

Cd (21) 4815063/24 (22) 16.04.90 (46) 23,05.93. Бюл. М 19 (71) Харьковский институт радиоэлектроники им, акад. М,И.Янгеля (72) В.А.Гулиус, Г.А.Калинин и В.В.Матейченко (56) Авторское свидетельство СССР

М 1357972, кл. 6 06 F 15/20, 1986.

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

М 1416984; кл, С 06 F 15/20, 1988, (54} УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ ПЕТРИ (57) Изобретение относится к вычислительной технике специального применения, в

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

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

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

„„59ÄÄ 1817103А1

2 частности для моделирования безопасных сетей Петри с инверсными дугами. Цель изобретения заключается в расширении класса решаемых задач за счет возможности моделирования графов с несколькими входными и выходными дугами позиций, а также с управляющими позициями с естественным и принудительным исключением меток. Это достигается путем введения двух многовходовых элементов ИЛИ, логического узла удаления меток, логического узла входных разметочных векторов, логического узла выходных разметочных векторов, регистра меток и формирователя импульсов. 3 ил., 1 табл, Эквивалентом графического представления сети Петри на фиг. 3 является табличный способ задания графа Петри с помощьЮ таблицы топологии. Здесь для каждого j-го перехода (1 | Ы 6) представлены входные е1, е2, ..., е16 и выходные а1, а2, ..., а16фаэмЕточные вектора (в общем. случае j = 1, М), а также вектор начальной разметки,и .

Устройство состоит из генератора 1 тактовых импульсов, блока 2 моделирования вершин, логического узла 3 входных разметочных векторов, M-входовых элементов

ИЛИ 4 и 5, где М вЂ” число переходов в графе

Г1етри, формирователя 6 импульсов, логического узла 7 выходных разметочных векторов, логического узла 8 удаления меток, регистра 10 меток.

На фиг. 2 представлена в качестве примера схема реализации первого канала (иэ возможных М) блока 2 моделирования вер1817103 шин. Схема содержит счетчик 10, 11 сравнения кодов на равенство, элемент 12 И, триггер 13, элемент задержки 14, элементы 15 и

16 запрета, 17 — регистр кода длительности перехода.

На фиг, 3 в качестве примера приведен граф Петри, описывающйй функционирование поездов и станций метрополитена.

Здесь используются обозначения р1, p2, ..., ро и t1, t2, ..., t8 для кольцевого.участка метрополитена, Позиции pto, p11, р12 выполняют функции депо для поездов метрополитена, Позиция pg играет роль разъезда, через который выводятся поезда из кольцевого участка для постановки в депо и вводятся иэ депо в кольцевую линию.

Для ввода/вывода поездов используется также позиция р1.

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

Позиции р1з, р14, р1ь, а также р1в и р19 являются управляющими, или инициирующими, т.к, не имеют входных дуг. В свою очередь, различают, два типа управляющих позиций: с естественным исключением метки; когда хотя бы одна выходная дуга не является инверсной (позиции р1з, р 14, р15); с принудительным исключением метки, когда все выходные дуги являются инверсными (позиции р18 и p19).

Последовательность вывода поездов из депо определяется очередностью записи метки в какую-либо из управляющих позиций р1з, р14. pts, Перемещение метки из позиции рд в какую-либо из свободных позиций plO, p», р12 производится по следующему правилу; в режиме разгрузки кольцевой линии метка из позиции р1 через переход 11о перемещается в позицию рд, откуда —.через переход t14 в позицию р12.

Следующими по порядку загружаются позиции р» и р1о через переходы 15 и 116 соответственно. Таким образом, конфликтные ситуации, связанные с позицией pg, в основном разрешаются за счет соответствующей топологии графа Петри. В отличие от этого конфликтные ситуации, связанные с позицией р1, разрешаются исключительно путем записи соответствующих меток в управляю ЩИЕ ПОЗИЦИИ Р18 И P1g.

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

ИЛИ и вырабатывает кратковременный импульс.

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

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

Логический узел 3 входных разметочных векторов состоит из элементов И, количество которых равно M. Каждый J-й элемент

И 0 = 1, М) подключен входами к прямым или инверсным выходам соответствующих разрядов регистра 9 меток в зависимости от значений ненулевых коэффициентов во входном разметочном векторе: положительным единицам соответствует подача прямого сигнала, отрицательным единицам— подача инверсного сигнала, Например, элемент И 3.1 на фиг, 2, относящийся к переходу 1, формирует на выходе терм р1р2р19

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

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

te и tg, поэтому входы элемента ИЛИ из угла

7, формирующего сигнал установки в "1"

5 первого разряда регистра 9, должны быть связаны с выходами 8- и 9-го каналов второй группы выходов блока 2. Аналогично, позиции pg соответствует четырехвходовой элемент ИЛИ, подключенный входами к выходам 10-ro. 11-го, 12-ro и 13-ro каналов

1817103 второй группы выходов блока 2, а выходом— к входу установки в лог. "1" 9-го разряда регистра 9 меток, Остальные сигналы установки в лог. "1" разрядов регистра 9 не требуют элементов 5

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

Узел 8 служит для удаления меток из тех 10 позиций, которые связаны со входами возбужденного перехода, т.е, данный узел формирует сигналы установки в лог. "0" соответствующих разрядов регистра 9.

Формирование сигнала установки в лог. "0" 15

i-го разряда происходит при совпадении двух условий: во-первых, наличия дуги со стрелкой с выхода j-ro перехода нэ вход i-ой позиции, и во-вторых, необходимо, чтобы в указанной i-ом разряде находилась метка, 20 т,е, если р = 1. Таким образом, узел 8 представляет собой совокупность элементов

И/ИЛИ вЂ” И, причем составной элемент

ИЛИ-И используется .только для конфликтных позиций. 25

Перед началом работы устройства в неro должен быть загружен код начальной разметки по входам 9.3 асинхронной записи информации регистра 9, а также записаны коды задания длительностей переходов По- 30 следние записываются в регистры, входящие в составы каналов блока 2. На фиг. 2 такой регистр показан под номером 17 для первого канала, Пусть для примера метки записаны в 35 позициях р1, рз, p4 M p19 (см. фиг. 3).

Непосредственно моменту запуска устройства предшествует сигнал "ОБЩИЙ

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

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

3,1 устанавливается лог. "0".

Когда код на выходе счетчика 10 сравняется с кодом в регистре 17, на выходе блока

11 сравнения кодов появляется сигнал лог.

"1", который устанавливает в "0" триггер 13.

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

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

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

В отличие от устройства-прототипа в заявляемом устройстве достигается расширение класса моделируемых безопасных сетей

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

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

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

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

Петри, содержащее генератор тактовых w1817103

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

Р, Р» Р, Р» Р5 Ре Р1 Р!» РФ Р Р Рле Р»3 Рлв Рл Р РГТ 115 РЕ9 е, а е а, Ф, 3

-Х9 ев а5 еЕ

» -1

В в в а

P., лл е„ е»х

t»t

Елв ее

»5

»6 о »9 еле ви

С»6

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

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

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

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

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

1817103

1817103

Составитель В.Гулиус

Техред М,Моргентал Корректор Н.Ревская

Редактор Г. Бельская

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

Заказ 1724 Тираж Подписное

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

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