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

(51 СУДАРСТВЕННЫЙ НОМИТ ОДЕЛАМ ИЗОБРЕТЕНИЙ И ССРРЫТИЙ ОБРЕТЕНИЯ ОПИСАНИ А ВТОРСНОМУ ДЕТЕЛ 22948/24.09.86.08;88, Бюп, Иф 30ститут проблем модетике АН УССРВ,Васильев, В.ицин и В.А,Шум1,333(088,8)торское свидетельс4, кл. С 06 Р 1.5/2рское свидетельств03, кл. С 06 Г 15/ ир ования В.Кузов во СССР 1979,СССР О, 1984(54) УСТРОЙС ГРАФОВ ПЕТРИ (57) Изобрет вычислитепьн О ДЛЯ МОДЕЛИРОВАНИЯ тся к област и может быть отн ехнииспользовано для решения задачна безопасных графах Петри. Цель изобретения - расширение класса решаемых задач за счет моделирования графов Петри с инверсными дугами - достигается тем, что в устройство, содержащее генератор тактовых импульсов, блок текущей разметки, блок хранения входных векторов, блок сравнения входных векторов, блок моделей вершин, блок исключения меток, коммутатор, блок записи меток, блок сравнения выходных векторов, блок хранения выходных векторов, дополнительно введены блок хранения типов дуг, блок инвертирования и элемент ИЛИ. 10 ил ., 1 табл.1416984 Составитель О.Гречухинаактор А,Огар Техред Л.Олийньпс Корректор Г,Решетни Заказ 542 4 Подписноеударственного комитета. СССм изобретений и открытийа, Ж, Раушская наб., д,Производственно-полиграфическое предприятие, г, Ужгоро ектная,Тираж 7 ВНИИПИ Го по дел 13035, Моск1 4 16984 2Изобретение относится к вычислительной технике и может быть использова.но для решения задач на безопасных граФах Петри.Цель изобретения - расширениеФункциональных возможностей устройства за счет моделирования граФов Петри с инверсными дугами.На Фиг. 1 представлена схема устройства; ча Фиг. 2 - схема блока ввода; на Фиг, 3 - схемы блоков текущейразметки, хранения типов дуг и инвертирОБЯния на Фиг, 4 - схема блокЯхранения входных векторов На Фиг.5 - 15схема блока сравнения входных векторов; на Фиг. 6 - схема блока моделейБерпин ня Фиг 7 - схема счетчикярвходящего Б состав узлов блока моделей вершин; на Фиг. 8 - схем блока 20исключения меток коммутатора и блоказаписи меток, на Фиг, 9 . схема бло ка сравнения выходных векторов, наФиг. 10 - пример модулируемого гра;а Итри АЭКроме того., дана таблица подготовки исходных дяннььх цля Оешениязадачи ня предлягяемом ус.рОЙствеоУСТООйСТВО (йиг. 11 СЭДЕржнт бЛОКввода, блок 2 текущей разметки, 30блок 3 индикации, блок 4 хранениявходных векторов блок 5 сравненияБходньх векторов, блок 6 моделейвершин, блок 7 исключения меток,каячутатор Ьблок 9 записи меток,35блок0 соавнения выходных векторовгенератор 11 тактовых импульсов,блок 12 хранения разметочных векторов блок 13 хранения:.илов дуг, блок14 инвертирования и элемент ИЛИ 15,Блок 1 ввода предназначен для Бво-да в "стройство топологии моделируемо-.го граФЯ петри, а именно входных разМЕтОИНЬВ" ВЕКТОРОБ НЯЧЯЛЬНОй РЯЗМЕТки Бершин р длит ельностей сряоятывяния переходов, типов дуг, Бй:Одныхразметочных векторов.Блок 2 текущей рЯзметки служитдля хранения текущей разметки вершинмест Б МОДелиоуемОМ графе Петри50Блок 3 индикации предусмотрендля вывоца содержимого блока текущейряэмеки на индикяционную панельБлок 4 хранения входных векторовЙреднязнячен для хрянения входныхразметочных векторов для всех Берпинпереходов, у которых выполнены условия срЯбатывания и Формирования управляюцрх сигналов вычитания соответ1416984 М - число вершин мест в моделируемом графе Петри), группа элементов НЕ 27.1-27,ш и группа триггеров 28,1- 28,М.Блок 4 хранения входных векторов содержит К регистров (К - число переходов в моделируемом графе). Каждый регистр содержит группу элементов НЕ 29, элемент И 30 и группу тригге ров 31.Блок 5 сравнения входных векторов (фиг. 5) выполнен в виде К узлов сравнения, каждый из которых содержит группу элементов И 32, элемент ИЛИ-НЕ 15 33, группу элементов И 34, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 35, кроме того, в состав блока 5 сравнения входных векторов входят элемент ИЛИ 36, элемент И 37 и группа элементов ИЛИ 20 38.Блок 6 моделей вершин (фиг. 6) со - держит К узлов моделей вершин, каждый из которых содержит регистр 39 и счетчик 40. 25Счетчики 40 включают группу элементов И-НЕ 41, группу триггеров 42, группу элементов 2 И-ИЛИ 43, триггер 44 и элемент И 45.Коммутатор 8 состоит из двух групп 30 элементов И 46,1 и 46.2, двух трчггеров 47.1 и 47.2 и группы элементов ИЛИ 48. Для перехода, который не может быть запущен на текущем такте моделирования, появляется "0" на выходе соответствующего элемента ИЛИ-НЕ 35 запрещающий запуск соответствующего счетчика 40;Далее значения входных векторов, из которых исключены ссылки на инверсные дуги, через группы элементов И 34.2 и 34,5 подаются на элементы ИЛИ 35.1-35,М, где формируется значение обобщенного входного вектора, котоБлок 10 сравнения входных векторов (фиг, 9) содержит группу триггеров 49, группу элементов И 50, формирователь 51 импульса, элемент ИЛИ 52, элемент И 53 и группу элементов ИЛИ ,54.40Блок 12 хранения разметочных векторов представляет собой группу К регистров.Блок 13 хранения типов дуг представляет соббй группу К регистров.Блок 14 инвертирования содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 55 и ,группу элементов НЕ 56.Устройство работает следующим образом,50После включения питания переключателем 22 триггер 23 устанавливается в состояние "1", обеспечивая режим ввода исходньк данных для решения задачи по мод ированию составленного графа Петри, бранные (входные разметочные векто 1,1, выходные разметочные векторы, в торы типов дуг, начальная разметкя графа Пет- . ри, длительности срабатывания переходов), набираемые на тумблерах группы21, заносятся в соответствующие блоки (4,. 12, 13, 2, 6) устройства, определяемые положением переключателейгруппы 17 переключателей, , Регистродного из этих блоков, в которыйзаносится очередной компонент исходных данных задачи, определяется положением тумблеров группы 16 тумблеров.После ввода исходных данных режимзаписи отключается,Для загрузки топологии графа и начальной разметки составляется таблица топологии графа Петри (см. таблицу), причем каждой вершине переходасоответствуют входной и выходной разметочные векторы, а также вектор типов дуг,Режим моделирования графа Петривключается переводом переключателягенератора 11 в положение "Пуск".Значение вектора текущей разметки из блока 2 текущей разметки и значение векторов типов дуг из блока 13хранения типов дуг подаются на входыэлементов ИСКЛЮЧАЮЩЕЕ ИЛИ 55 блока14 инвертирования. После инвертирования на элементах НЕ 56,2 инвертированные значения вектора подаютсяна входы элементов И 32 блока сравнения входных векторов и на выходеэлемента ИЛИ-НЕ 33,2 появляется "1",свидетельствующая, что переход можетбыть запущен на текущем такте моделирования. Эта " 1" является управляющимсигналом начала моделирования срабатывания перехода и через четвертыйуправляющий выход (4) начала имитациисрабатывания перехода блока 5 сравнения входных векторов подается навторой вход (2) блока 6 моделей вершин и переводит счетчик 40,2 в режим5 141 б 9рое подается на элементы ИСКЛЮЧа 10 ЩЕЕИЛИ блока 7 для имитации вычитанияиз вектора текущей разметки,Новое значение вектора текущей5разметки по приходу импульса Ф 1 заносится через коммутатор 8 в блок 2текущей разметки.Через количество тактов, записанное в счетчик 40.5, по приходу импуль са Ф 2 счетчик 40,5 обнуляется (так1.как счетным импульсом для него является импульс Ф 2)и на его выходе появляется "1" которая разрешает занесение числа пересчета счетчиков 15из регистра 39.5 в счетчик 40,5, устанавливает триггер 49.5 в состояние"1" и таким образом формирует черезэлемент ИЛИ 52 и элемент И 53 сигчалразрешения изменения вектора текущей 20ра.зметки, а также разрешает подачузначения выходного разметочного вектора из регистра 12.5 через группуэлементов И 50.5 и группу элементовИЛИ 54,154,И на вторые входы схем 28ИН 4 блока 9, гце производится имитациясложения с вектором текущей разметки,и новое значение вектора текущей разметки заносится через коммутатор 8 вблок 2 текущей разметки Иа следую" 30щем цикле моделирования появляетсявозможность запуска следующего перехода. Далее устройство продолжает работать аналогично. формула и з о б р е т е н и я Устройство для моделирования граФов Петри содержащее блок текущей разметки, блок хранения входных векторов, блок сравнения входных векторов, блок моделей верплн, блок хранения разметочньи векторов., блок сравнения выходных векторов блок исключения меток, блок записи меток, коммутатор, генератор тактовых импульсов, первый вьиод которого соединен с тактовым входом блока сравнения входных векторов, а второй выхоц сое,цинен с тактовыми входами блока моделей вершин и блока сравнения вьиодных векторов, первые входы которого соединены с информационньпя выходами блока моделей вершин, информационные входы которого соединены с первыми Фкнформационными выходами блока сравнения входных векторов, вторые информационные входы которого соединены с первыми информационными входами блока исключения меток, выходы которого соединены с первьпя информационными входами коммутатора, вторые информационные входы которого соединены с выходами блока записи меток, а выходы соединены с информационными входами блока текущей разметки, вьиод которого соединен с вторыми информационными входами блока исключения меток и блока записи меток, первый информационный вход которого соединен с инФормационньпи выходами блока сравнения выходных векторов,. вторые ин- Формационные входы которого соединены с информационными выходами блока хранения разметочных векторов,. а выход признака сравнения соединен с первым управляющим входом коммутатора, второй управляющий вход которого соединен с выходом признака сравнения блока сравнения входньи векторов, первые информационные входы которого соединены с информационными выходами блока хранения входных векторов, о тл и ч а ю щ е е с я тем, что, с целью расширения Функциональных возможностей за счет моделирования графов Петри с инверсными дугами, в него введены элемент ИЛИ, блок инвертиро" вания и блок хранения типов дуг, информационные выходы которого соедчнены с первыми информационными входами блока сравнения входных векторов и блока инвертирования, вторые информационные входы которого соединены с информационными выходами блока текущей коммутации, а выходы соединены с третьими информационными входами блока сравнения входных векторов, первый и второй входы элемента ИЛИ соединены соответственно с первым и вторым управляющими входами коммутатора, а выход элемента ИЛИ соединен с входом записи блока текущей разметки,1416984 Привлеки дуг Разметочяме векторы фа Рф Р Рз Р Рт Рв Р, Ре Р Рф Рф Ре Рт Ре 0 6 О 0 О О О О О 0а О 0 О 0 О ОО О О О01 О 0 0 0