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

(51)5 0 06 Р 15/20 ТЕНТНОЕ ГОСУДАРСТВЕННОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) Б САНИ ктрони,Матейдио.В СССР1986,СССР1988,ЕЛИРОВАНИЯ ител вычи риме ия,в Р м не На фиг. 1 и ва; на фиг,2 - одного канала фиг, 3 - приме ме воз ВТОРСКОМУ СВИДЕТЕЛЬС(71) Харьковский институт рки им, акад. М,И.Янгеля(54) УСТРОЙСТВО ДЛЯ МОДГРАФОВ ПЕТРИ(57) Изобретение относитсяной технике специального Изобретение относится к вычислительной технике, а именно к специализированным вычислительным устройствам, в частности, для решения задач на сетях Пети, и может найти применение в тех отрасях народного хозяйства, где возникают задачи моделирования параллельных процессов.Цель изобретения заключается в расшиении класса решаемых задач за счет воэожности моделирования графов с сколькими входными и выходными дугами позиций, с управляющими позициями с естественным и принудительным исключением метки. ставлена схема устройстмер схемной реализацииока моделей вершин; наоделируемой сети Петри,2частности для моделирования безопасных сетей Петри с инверсными дугами. Цель изобретения заключается в расширении класса решаемых задач за счет возможности моделирования графов с несколькими входными и выходными дугами позиций, а также с управляющими позициями с естественным и принудительным исключением меток. Это достигается путем введения двух многовходовых элементов ИЛИ, логического узла удаления меток, логического узла входных разметочных векторов, логического узла выходных разметочных векторов, регистра меток и формирователя импульсов. 3 ил., 1 табл,Эквивалентом графического представления сети Петри на фиг, 3 является табличный способ задания графа Петри с помощьЮ таблицы топологии. Здесь для каждого 3-го .перехода (1) 16) предоставлены входные е 1, е 2, , е 16 и выходные а 1, а 2, а 16 разметочные вектора (в общем.случае 1 = 1, М), а ф также вектор начальной разметки р, 4Устройство состоит из генератора 1 так- ф товых импульсов, блока 2 моделирования вершин, логического узла 3 входных разметочных векторов, М-входовых элементовИЛИ 4 и 5, где М - число переходов в графе Г)етри, формирователя 6 импульсов, логического узла 7 выходных разметочных векто- ф ров, логического узла 8 удаления меток, регистра 10 меток.На фиг. 2 представлена в качестве прира схема реализации первого канала(иэможных М) блока 2 моделирования вер5 10 15 20 25 является инверсной (позиции Р 13, Р 14, Р 15);с принудительным исключением метки, ког 40 ветственно. Таким образом, конфликтные 45ситуации, связанные с позицией рд, в основ 50 шин, Схема содержит счетчик 10, 11 сравнения кодов на равенство, элемент 12 И, триггер 13, элемент задержки 14, элементы 15 и 16 запрета, 17 - регистр кода длительности перехода.На фиг, 3 в качестве примера приведен граф Петри, описывающйй функционирование поездов и станций метрополитена. Здесь используются обозначения р 1, р 2 р 8 и т 1, т 2, , т 8 для кольцевого. участка метрополитена, Позиции р 10, р 11, р 12 выполняют функции депо для поездов метрополитена, Позиция рд играет роль разъезда, через который выводятся поезда из кольцевого участка для постановки в депо и вводятся иэ депо в кольцевую линию. Для ввода/вывода поездов используется также позиция р 1.Нетрудно видеть, что р 1 и рд являются конфликтными позициями, поскольку имеют более одной выходной дуги беэ учета инверсных дуг.ПОЗИЦИИ Р 13, Р 14, Р 15, а также Р 18 И Р 19 являются управляющими, или инициирующими, т.к, не имеют входных дуг. В свою очередь, Различают, два типа управляющих позиций: с естественным исключением метки; когда хотя бы одна выходная дуга не да все выходные дуги являются инверсными (позиции Р 18 и Р 19) Последовательность вывода поездов издепо определяется очередностью записи метки в какую-либо из управляющих позиций Р 1 з Р 14. Р 15, Перемещение метки из поэиции Рд в какую-либо из свободны позиций р 10, р 11, ра производится по следующему правилу; в режиме разгрузки кольцевой линии метка из позиции р через переход 11 о перемещается в позицию рд, откуда - .через переход т 14 в позицию р 12. Следующими по порядку загружаются позиции р 11 и рю через переходы в 15 и 115 соотном разрешаются за счет соответствующей топологии графа Петри. В отличие от этого конфликтные ситуации, связанные с позицией р 1, разрешаются исключительно путем записи соответствующих меток в управляю-ЩИЕ ПОЗИЦИИ Р 18 И Р 19,Формирователь 6 импульсов служит для формирования исполнительного сигнала записи информации по тактируемым входам в регистр 9 меток, Формирователь инициируется сигналами с выходом элементов 4 и 5 ИЛИ и вырабатывает кратковременный импульс,Регистр 9 меток имеет разрядность, соответствующую числу позиций в графе Петри. Запись начального вектора метокпроизводится со стороны группы входов 9,3асинхронной записи информации при поступлении соответствующих сигналов сгруппы входов вектора начальной разметкиграфа устройства и корректировки векторатекущей разметки,Группа входов 9,1 и 9,2 служит для тактируемой установки разрядов регистра влог. "1" и "0" соответственно,С учетом свойств управляющих позицийграфа Петри следует,что число входов 9,2установки"0" регистра меток равно общемучислу позиций графа Петри минус количество управляющих позиций с принудительным исключением метки. Аналогично, числовходов 9,3 установки в "1" равно общемучислу позиций графа Петри минус числовсех управляющих позиций,Логический узел 3 входных разметоч. ных векторов состоит из элементов И, количество которых равно М. Каждый)-й элементИ ( = 1, М) подключен входами к прямым илиинверсным выходам соответствующих разрядов регистра 9 меток в зависимости отзначений ненулевых коэффициентов вовходном разметочном векторе; положительным единицам соответствует подача прямого сигнала, отрицательным единицам -подача инверсного сигнала, Например, элемент И 3.1 на фиг, 2, относящийся к переходу О, формирует на выходе терм р 1 Р 2 Р 19.5 Логический узел 11 выходных разметочных векторов должен формировать сигналыдля установки в лог. "1" (записи метки) в тепозиции графа, которые связаны с возбужденнымими переходами.В зависимости от топологии графа Петри, определяемой выходными разметочными векторами, узел 7 либо обеспечиваетнепосредственное подключение соотаетствующего входа из группы входов 9.1 к соответствующему выходу из второй группывыходов блока 2 моделирования вершин,либо указанная связь осуществляется черезэлемент ИЛИ, если в графе Петри существуют позиции, содержащие две и более входные дуги со стрелками. Например, в графена фиг, 3 позиция р 1 имеет две входные дугисо стрелками, поступающими из переходовс 8 и Фз, поэтому входы элемента ИЛИ из угла7, формирующего сигнал установки в "1"5 первого разряда регистра 9, должны бытьсвязаны с выходами 8- и 9-го каналов второйгруппы выходов блока 2. Аналогично, позиции рд соответствует четырехвходовой элемент ИЛИ, подключенный входами квыходам 10-го. 11-го, 12-го и 13-го каналоввторой группы выходов блока 2, э выходом -к входу установки в лог. "1" 9-го разрядарегистра 9 меток,Остальные сигналы установки в лог. "1"разрядов регистра 9 не требуют элементов 5ИЛИ, поскольку непосредственно снимаются с выходов соответствующих каналов второй группы выходов блока 2 согласнотопологии графа Петри.Узел 8 служит для удаления меток из тех 10позиций, которые связаны со входами возбужденного перехода, т.е, данный узел формирует сигналы установки в лог, "0"соответствующих разрядов регистра 9.Формирование сигнала установки в лог, "О" 151-го разряда происходит при совпадениидвух условий: во-первых, наличия дуги сострелкой с выхода )-го перехода на вход 1-ойпозиции, и во-вторых, необходимо, чтобы вуказанной -ом разряде находилась метка, 20т,е, если р = 1. Таким образом, узел 8 представляет собой совокупность элементовИ/ИЛИ - И, причем составной элементИЛИ-И используется .только для конфликтных позиций. 25Перед началом работы устройства в него должен быть загружен код начальной разметки по входам 9.3 асинхронной записиинформации регистра 9, а также записаныкоды задания длительностей переходов Последние записываются в регистры, входящие в составы каналов блока 2. На фиг. 2такой регистр показан под номером 17 дляпервого канала,Пусть для примера метки записаны в 35позициях р 1, рз, р 4 и р 19 (см. фиг. 3).Непосредственно моменту запуска устройства предшествует сигнал "ОБЩИЙСБРОС", обеспечивающий начальную установку элементов памяти(цепи подачи этого 40сигнала на фиг. 1 не показаны). В представленном на фиг, 3 графе Петри и при заданном векторе начальной разметкисоблюдены услбвия возбуждения переходов 11 и т 4, Элемент И 3.1 вырабатывает 45сигнал лог. "1", и при запуске генератора 1тактовых импульсов сигнал с выхода последнего, проходя через элемент 12 И, устанавливает в "1" триггер 13, выходной сигналкоторого, воздействуя на вход ЕВ разрешения счета счетчика 10, переводит его в режим суммирования.Сразу же после включения в работусчетчика 10 с помощью элементов 14 и 15формируется импульс на выходе 1 блока 2 55моделирования вершин. Этот импульс, проходя через логический узел 8, появляется навходе установки в "0" первого разряда регистра 9 меток. Сама установка в "0" инициируется сигналом с выхода формирователя 6,запускаемого сигналом с выхода М-входового элемента 4 ИЛИ, После исключения метки из позиции р 1 на выходе элемента И 3,1 устанавливается лог, "О".Когда код на выходе счетчика 10 сравняется с кодом в регистре 17, на выходе блока 11 сравнения кодов появляется сигнал лог. "1", который устанавливает в "0" триггер 13. При этом с помощью элементов 14 и 16 на выходе 2 первого канала блока 2 первого канала блока 2 моделирования вершин формируется импульс окончания длительности перехода т 1, который используется также для обнуления счетчика 10, подготавливая тем самым первый канал для нового цикла работы.Импульс с выхода 2 первого канала используется для записи метки в позицию р 2 с помощью М-входового элемента 5 ИЛИ и формирователя 6,Одновременно и параллельно с описанными выше процессами, связанными с возбуждением перехода т 1, происходят процессы, связанные с возбуждением перехода т 4,Путем останова генератора 1 тактовых импульсов можно в любой момент времени прекратить процесс моделирования, ввести новый начальный вектор разметки в регистр меток, Тем самым по значениям меток в управляющих позициях можно изменить, в частности. режим работы метрополитена и промоделировать реальные процессы в нем. При этом следует иметь в виду, что исключение ранее введенных меток из управляющих позиций ри и р 19 возможно только по инициативе оператора путем корректировки вектора текущей разметки.В отличие от устройства-прототипа в заявляемом устройстве достигается расширение класса моделируемых безопасных сетей Петри эа счет включения в граф Петри позиций с несколькиМи входными дугами, позиций с несколькими выходными дугами (конфликтных позиций), э также двух типов управляющих позиций: с естественным и принудительным исключением меток. Все этоделает возможным моделирование весьма сложных с точки зрения структуры и функционирования реальных процессов и обьектов.Другое преимущество заявляемого устройства заключается в том, что оно требует для своей реализации относительно простых аппаратных средств, т,е. происходит упрощение конструкции в сравнении с устройством по прототипу.Формула изобретения Устройство для моделирования графов Петри, содержащее генератор тактовых им1817103 Входные н выходныЕ Равыатонные ВехтераР, Ре. Р Рл Рс Ре Р 1 Р 1 л РЗ Р Р Рле Рла Рлв Рл Р Рлт 198 РЕ 9 е,а е а, Ф 3 .Х 9 е 5 а 5 еЕ Е 3 в в з 9 е,о Влл е евх Ел ее л 5 елеи 1 1 пульсов, блок моделирования вершин, тактовый вход которого соединен с выходом генератора тактовых импульсов, группа входов задания длительностей переходов блока моделирования вершин является группой входов задания длительности переходов устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет возможности моделирования графов с несколькими входными и выходными дугами позиций, с управляющими позицйями с естественным и принудительным исключением метки, в него дополнительно введены первый и второй элементы ИЛИ, логический узел удаления меток, логический узел входных разметочных векторов, логический узел выходных разметочных векторов, регистр меток и формирователь импульсов, первый и второй входы запуска . которого. соединены соответственно с выходами первого и второго элементов ИЛИ, группы входов первого и второго элементов ИЛИ соединены соответственно с первой и второй группами выходов блока моделирования вершин, группа входов текущей разметки которого соединена соответственно с группой выходов логического узла входных раэметочных векторов, группа входов которого соединена соответственно с первой группой выходов регистра меток, вторая 5 группа выходов которого соединена соответственно с первой группой входов логического узла удаления меток, вторая группа входов которого соединена соответственно. с группой выходов начала работы переходов 10 блока моделирования вершин, выходыокончания работы переходов которого соединены соответственно с входами логического узла выходных раэметочных векторов, группа выходов которого соединена соот ветственно с группой входов установки влогическую единицу, разрядов регистра меток, группа входов установки в логический ноль разрядов которого соединена соответственно с группой выходов логического узла 20 удаления меток, выходов формирователяимпульсов соединен с тактовым входом регистра меток, группа входов асинхронной записи информации которого является соответственно группой входов вектора началь ной разметки графа и корректировкивектора текущей разметки устройства.1817103 тавитель В.Гули ред М,Моргента евская дактор Г.Бельска Корректор Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагари Заказ 1724ВНИИП Тираж осударственного ко 113035, МоПодписноеета по изобретениям и открытиям при ГКНТ СССРа, Ж, Раушская наб., 4/5