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

.4 Вк.,с. 4 .с ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ Е ИЗОБРЕТЕН К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ 24-2 Бюл.20т проблем моделУССРсильев, В. В. Кузьи В. А. Шумов88.8)Дж. Теориясистем: Пер. вания в му сетеис англ ри и Мир,свидетельство СССРл. б 06 Г 15/20, 1983 54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВНИЯ ГРАФОВ ПЕТРИ(57) Изобретение относится к вычислительной технике, а именно к устройствам для моделирования параллельных процессов, которые алгоритмически описаны с помощью сетей Петри. Устройство позволяет выявлять наличие критических свойств в графах Петри за счет введения блоков контроля конфликтных ситуаций, безопасного свойства и живого свойства. Выявление хотя бы одного критического свойства в блоках контроля приводит к прекращению моделирования соответствующего графа. Кроме того, за счет параллельного выполнения операций в блоках сравнения входных и выходных векторов достигается сокращение времени моделирования. 2 з.п.ф-лы. 8 ил.1314350 2 Редактор А. ДолиничЗаказ 200750ВНИИПИ Государст11303Гроизводственноч Составитель А. УшакТехред И. ВересТираж 673венного комитета СССР по деламИзобретение относится к цифровой вычислительной технике, а именно к устройствамдля обработки информации специального назначения, в частности для разрешения задачна сетях Петри, и может быть примененодля отладки алгоритмов моделированияпараллельных процессов,Целью изобретения является расширение функциональных возможностей за счетконтроля наличия критических свойств вграфах.На фиг, 1 представлена схема устройства; на фиг. 2 - схемы блока регистровзадания входных векторов и блока коммутации; на фиг. 3 - схема блока сравнения входных векторов; на фиг. 4 - схемыблока элементов ИСКЛЮЧАЮ 1 ЦЕЕ ИЛИ,блока элементов ИЛИ, блока контроля конфликтных ситуаций, блока контроля безопасного свойства; на фиг. 5 - схемаблока сравнения выходных векторов; нафиг. 6 - схемы блока контроля живогосвойства и генератора тактовых импульсов;на фиг, 7 - иллюстрированный примермоделируемого графа Петри; на фиг. 8фрагменты графов Петри, иллюстрирующиекритические свойства, анализируемые предлагаемым устройством.Устройство (фиг. 1) содержит блок 1ввода, блок 2 регистров задания входныхвекторов, регистр 3 задания текущей разметки, блок 4 индикации, блок 5 сравнениявходных векторов, коммутатор 6, блок 7 элементов ИСКЛ ЮЧАЮ 1 ЦЕЕ ИЛИ, блок 8 элементов ИЛИ, блок 9 сравнения выходныхвекторов, блок 10 регистров задания выходных векторов, блок 11 коммутации, блок 12контроля живого свойства, регистр 13 начальной разметки, элемент ИЛИ 14, генератор 5 тактовых импульсов, блок 16 контроля конфликтных ситуаций, опорный генератор 17, блок 18 контроля безопасногосвойства.Блок 1 ввода предназначен для вводав устройство топологии моделируемого графаПетри, а именно входных разметочных векторов, начальной разметки вершин, выходных разметочных векторов, а также необходимого числа циклов работы устройства.Блок 2 регистров задания входных векторов предназначен для хранения входныхразметочных векторов для каждой вершиныперехода , (1 (( т).Регистр 3 задания текущей разметкипредназначен для хранения текущей разметки вершин мест в моделируемом графеПетри,Блок 4 индикации предназначен длявывода содержимого регистра 3 на индикационную панель.Блок 5 сравнения входных векторовпредназначен для определения вершин переходов 1, у которых выполнены условиясрабатывания и формирования управляющихсигналов вычитания соответствующих вход 5 10 15 20 25 30 35 40 45 50 55 ных разметочных векторов от вектора текущей разметки графа Петри.Коммутатор 6 предназначен для управления занесением информации в регистр 3задания текущей разметки, а именно либоиз блока 7 элементов ИСКЛЮЧАЮ 1 ЦЕЕИЛИ, либо из блока 8 элементов ИЛИ, либоиз регистра 13 начальной разметки.Блок 7 элементов ИСКЛ ЮЧАЮ 1 ЦЕЕИЛИ предназначен для реализации вычитания -х входных разметочных векторов извектора текущей разметки при выполненииусловия разрешения срабатывания переходов 1,Блок 8 элементов ИЛИ предназначен дляприбавления -х выходных разметочных векторов к вектору текущей разметки.Блок 9 сравнения выходных векторовпредназначен для определения вершин переходовмоделирование которых окончено,и формирования управляющих сигналов,позволяющих прибавлять соответствующие-е выходные разметочные вектора к векторутекущей разметки.Блок 10 регистров задания выходныхвекторов предназначен для хранения выходных разметочных векторов для каждой вершины перехода.Блок 11 коммутации предназначен дляформирования текущего значения векторавходных управляющих воздействий Х, а также для формирования последовательностейконтролирующих сигналов, позволяющих определять критические свойства в сетях Петри.Блок 12 контроля живого свойства предназначен для выявления и индикации неживого критического свойства в моделируемомграфе Петри.Регистр 13 начальной разметки предназначен для хранения начальной разметки моделируемого графа Петри.Элемент ИЛИ. 14 предназначен для формирования сигнала, разрешающего изменение вектора текущей разметки, хранящегосяв регистре 3.Генератор 15 тактовых импульсов предназначен для формирования управляюгцихсигналов г 1) 1 и ч) 2 для тактирования устройства.Блок 16 контроля конфликтных ситуаций предназначен для обнаружения и индикации конфликтного критического свойствав моделируемом графе Петри.Опорный генератор 17 предназначен дляформирования непересекающейся двухфазовой последовательности сигналов Фи Ф 2.Блок 18 контроля безопасного свойствапредназначен для обнаружения и индикациинебезопасного критического свойства в моделируемом графе Петри.Блок 2, представленный на фиг. 2, представляет собой набор из т (по числу тмоделируемых вершин переходов 1,) и-разрядных (по числу п моделируемых вершин мест р,) регистров 2 м (1 ( ъ ( т)(здесь и везде в дальнейшем цифрами после точки, стоящей после цифры, обозначены порядковые номера одинаковых по техническому исполнению блоков, узлов и элементов, а также входов и выходов блока, узла или элемента, которые объединены в общую шину).Регистр 3 представляет собой п-разрядный регистр (по числу моделируемых вершин мест р), каждый разряд которого предназначен для моделирования наличия (1) или отсутствия (0) метки в соответствующей вершине места р (т (р) = 1) графа Петри. Особенностью блока текущей разметки является то, что в него может заноситься информация, поступающая либо на первый вход (1), либо на второй вход (2), а также функционирование без применения сигнала Установка 0,Блок 4 индикации может быть выполнен в виде индикаторной панели, в которой каждой вершине места в графе Петри соответствует элемент индикации.Блок сравнения входных векторов, схема которого приведена на фиг. 3, содержит первую группу из т подгрупп элементов И 19 л. 1 Г 9 л.п (ъ = 1)и), т элементов ИЛИ-НЕ 20 л, вторую группу из т подгрупп элементов И 21 л. 1 21 л.п, группу из п элементов ИЛИ 22.122, п, элемент ИЛИ 23 и элемент И 24.Элементы И 19 л.119 л.п предназначены для реализации функции конъюнкции над инверсными значениями векторов текущей разметки и значениями входных разметочных векторов. Элементы ИЛИ-НЕ 20. предназначеныдля отыскания хотя-бы одной 1, получившейся в результате конъюнкции инверсногозначения вектора текущей разметки то" съ-м входным разметочным вектором р,еч-указывающей на то, что г р т".Элементы И 21 л, 121 л.п предназначены для формирования сигналов вычитания извектора текущей разметки тех входных разметочных векторов "гг, для которых выполнено условие е) р, Е тоо),Элементы ИЛИ 22.122.п предназначены для формирования обобщенного входногоразметочного вектора, подлежащего вычитанию из вектора текущей разметки то наданном цикле процесса моделирования.Элемент ИЛИ 23 предназначен для формирования управляющего сигнала изменениятекущей разметки при наличии хотя бы одного входного разметочного вектораег- - (к)гайтоЭлемент И 24 предназначен для синхронизации формирования управляющего сигнала с фазой Ф 1.Коммутатор 6 представляет мультиплексор с запоминанием подключаемого входа,до прихода следующего управляющего сигнала.40 4550 55 5 10 15 20 25 30 35 Блок 8 элементов ИЛИ, схема которого приведена на фиг. 4, предназначен для прибавления ъ-х выходных разметочцых вскто.- (к) ров а" д к вектору текущей разметки пгч после окончания моделирования срабатывания перехода 1 что позволяет реализовать появление меток в выходных местах перехода 1,.Блок 9 сравнения выходных векторов, схема которого приведена на фиг. 5, содержит группу из и подгрупп элементов И 25 л.125 л.п, группу элементов ИЛИ 26.126.п, элемент ИЛИ 27, элемент И 28.Подгруппы элементов И 25 л предназначены для выборки соответствующих выходаУ -ных разметочных векторов 1 г, подлежащих сложению с вектором текущей разметки ао, по окончанию моделирования вершин 1,Группа элементов ИЛИ 26, е ( = 1п) предназначена для стохастического, несинхронного вычитания выходных разметочных векторов а р из вектора текущей разметки - (к)то в непрерывном режиме работы устройства.Элемент И 27 предназначен для формирования сигнала управления, разрешагощсго изменение вектора текугцей разметки г)7".Элемент И 28 предназначен для синхронизации сигнала управления изменением век- (к)тора текущеи разметки ггго по частоте Ф 2.Блок 1 О регистров задания выходных векторов представляет собой набор из т и-разрядных регистров 1 Ол.Блок 11, приведенный на фиг. 2, содержит пг-разрядцый счетчик 29, пг групп элементов И 30 л (1( т ( и), элемент И 31 и элемент ИЛИ-НЕ 32.Счетчик 29, работающий в режиме вычитания, предназначен для хранецця значения вектора Х и постепенного его уменьшения от значения 1,11 до значения 0,00. Группы элементов И 30.1 - 30.пг предназначены для разрешения или запрещения в зависимости от состояния соответствующего ъ-го разряда счетчика 29, подачи входных разметочных векторов, хранящихся в блоке 2, в блок 5 сравнения входных векторов.Элемент И 31 предназначен для определения такого состояния счетчика 29, когда во всех его разрядах содержатся 1, элемент ИЛИ-НЕ 32 предназначен для определения такого состояния счетчика 29, когда во всех его разрядах содержатся 0.Блок 12 контроля живого свойства, схема которого приведена на фиг. 6, содержит элементы НЕ 33, группу триггеров 34.134, т, элемент И-НЕ 35, элементы И 3639, элементы ИЛИ 40, 41, индикаторный элемент 42, элемент ИЛИ 43, элемент НЕ 44, регистр 45, счетчик 46.Элемент НЕ 33 предназначен для инвертирования сигнала признака наличия хо 13143505 10 15 20 25 1 000 0100 0010 30 35 40 45 50 55 тя бы одного активного перехода для которого выполняется условие " ртс".Группа триггеров 34 л предназначена для фиксации признака срабатывания переходаи хранения его до прихода сигнала сброса.Элемент И-НЕ 35 предназначен для фиксации признака лог. 1 и не все переходы 1, сработали.Элемент И 36 предназначен для установки флажка начала следующего шага моделирования при новом значении вектора Л по совпадению признаков нет активных переходов и не все разряды вектора Х находятся в состоянии лог. 1,Элемент ИЛИ 37 предназначен для установки признака обнаружения неживого свойства по совпадению признаков нет активных переходов и все разряды вектора Х находятся в состоянии лог. 1.Элемент И 38 предназнацен для установки признака обнаружения неживого свойства по совпадению признака не все переходы 1,. сработали и признаки окончания моделирования графа, введенного в устройство.Элемент И 39 предназначен для установки признака окончания моделирования по совпадению признака все разряды вектора У находятся в состоянии логического О и сигнала установки в О счетчика 46.Элемент ИЛИ 40 предназначен для формирования управляющего сигнала установки начальных условий нового цикла моделирования.Элемент ИЛИ 41 предназначен для формирования управляющего сигнала останова устройства по признаку обнаружения неживого свойства.Индикаторный элемент 42 предназначен для индикации условия обнаружения неживого свойства.Элемент ИЛИ 43 предназначен для формирования управляющего сигнала останова устройства.Элемент НЕ 44 предназначен для формирования управляющего сигнала не все разряды вектора Х находятся в состоянии лог. 1.Регистр 45 предназначен для хранения числа циклов работы устройства, составляк- щих один шаг моделирующего эксперимента при фиксированном значении вектора Х.Сцетчик 46, работающий в режиме вычитания, предназначен для счета циклов работы устройства в диапазоне от числа, хранимого в регистре 45, до О. При установке всех разрядов счетчика в О выдается сигнал окончания текущего шага моделирования, разрешающий изменение значения вектора Х.Элемент ИЛИ 47 предназначен для формирования управляющего сигнала занесения в счетчик 46 числа, хранящегося в регистре 45. Регистр 13 начальной разметки (фиг, 1) представляет собой п-разрядный (по числу моделируемых вершин мест р,.), каждый разряд которого предназначен для моделирования наличи (1) или отсутствия (О) метки в соответствующей вершине места р, (т(р,)=1) графа Петри.Генератор 15, приведенный на фиг. 6, содержит элементы И 48, 49.1, 49.2 и триггер 50 для управления пуском-остановом генератора 15.Блок 16 контроля конфликтных ситуаций, схема которого представлена на фиг. 4, выполнен содержащим набор из ц (по числу вершин мест р,) узлов 53, в постоянной памяти (1 ( в ( л) (ПЗУ) группу 51 элементов индикации и элемент ИЛИ-НЕ 52.Каждый блок 53.е предназначен для хранения признаков конфликтных разметок вершин мест р, При моделировании графа Петри, содержащего т вершин переходов 1,. и п вершин мест р в каждом блоке 53.е используются первые т адресных входов 1), (2)(т) ). При этом в ПЗУ 53.в по каждому адресу 1,0,00; 0,1,00;0,0,01, содержащему лишь одну 1 (описывается ортогональным вектором), записаны О. о о отПо всем остальным адресам записаны лог. сс 1, показывающие наличие конфликтной разметки в графе Петри.Группа 51 элементов индикации выполнена содержащей а (по числу вершин мест р,.) индикаторных элементов, причем каждой вершине места р, соответствует е-й индикаторный элемент, подключенный к блоку 53,в, и предназнацена для индикации возникновения конфликтной разметки мест р,Элемент ИЛИ-НЕ 52 предназначен для формирования сигнала останова устройства в слуцае возникновения конфликтной разметки мест р графа Петри.Блок 18 контроля безопасного свойства, представленный на фиг. 6, выполнен содержащим набор из а (по числу вершин мест) блоков 54.в постоянной памяти, (ПЗУ) элемент ИЛИ-НЕ 55 и группу 56 элементов индикации.Блоки 54.в предназначены для хранения признаков возникновения небезопасных разметок мест р,. При моделировании графа Петри, содержащего т вершин переходови л вершин мест р в каждом е-м ПЗУ 54.в используются первые т+1 адресных входов (1), (2), , (т) (т+1). При этом в каждом кристалле ПЗУ по адресу5 10 15 20 25 10000 01000 00100 00010 ООО, ОО т+1 1,0,00,0; 0,1,00,0; .; 0,0,00,1, содержащему лишь одну 1, записаны все 0. По остальным адресам, кроме адреса 0,0,00,0, записаны лог. 1, показывающие наличие небезопасной разметки в сети Петри. По адресу 0,0,00,0, записан 0. Группа 56 элементов индикации выполнена содержащей п (по числу вершин мест р,.) индикаторных элементов, причем каждой вершине места р, соответствует в-й индикаторный элемент, подключенный к блоку 54.в, и предназначена для индикации обнаружения небезопасного свойства в вершинах мест р,Элемент ИЛИ-НЕ 55 предназначен для формирования сигнала останова устройства в случае обнаружения небезопасного свойства в любом из мест р,. графа Петри.Рассмотрим основные положения теории графов Петри на конкретном примере графа Петри, приведенном на фиг. 7.Особенностью графов Петри является наличие двух типов вершин: переходов 1,., и мест р а также наличие меток, которые показывают, какие вершины при обходе графа устройство моделирует в данный момент времени. Метки располагаются в вершинах мест р,. (фиг. 7) и моделируют в динамике окончание реальных действий, в соответствии с заданным алгоритмом, представленным графом Петри. Местонахождение меток в графе Петри отображается вектором разметки то = (0,1,0,1,1,0,0,0,1,0,1,0,0, 1,1,1)г. Цифра О на первом месте обозначает, что первое место р не содержит метку, и 1 на втором указывает, что во втором месте р находится метка. При составлении графа Петри устанавливается ее топология и начальная разметка то Каждая вершина перехода 1,. моделирует время выполнения какого-то действия в процессе. Говорят, что переход 1 срабатывает, если во всех местах рдуги от которых направлены к 1,., находятся метки. Так, например, переходы 1, и 1, могут сработать. В переход 1 входят две дуги от места р и р ь в которых находятся метки. Это является условием начала моделирования действия аг, которое характеризуется временем Ж. В момент начала выполнения действия а метки из мест р и рц убираются и через время Л 1, в места, к которым направлены дуги от 6 (рз и ро) записываются. Каждый переход 1 характеризуется частич 30 35 40 45 50 55 ным входным вектором р и выходным разметочным вектором ф и. Вектора записываются в трансформированной форме. В векторе еи = (1,1) 1 на первом месте говорит о том, что в вершине р находится метка. При составлении частичных векторов предварительно расстанавливаются по возрастанию индексов мест вершин, Так для ТГ расстановки соответствующих ему мест рр,й 2а для р - рз, роНа фиг. 7 представлен пример моделируемого графа Петри для примера моделирования управления поездами метрополитена. Три поезда непрерывно едут по кольцу, останавливаясь на каждой из восьми станций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что привело бы к их столкновению. Вершины мест рь,р моделируют станции, а наличие меток в р,. (1 (( 8) моделируют наличие поездов на станциях х. Наличие меток в местах р(9 ( д ( 16) моделирует наличие зеленого света для соответствующих поездов. Каждый из переходов 1,. (1 (( 8) моделирует время Л 1 включающее переезд с одной станции на другую и остановку на последующей станции. Моделирование построенного графа Петри в устройстве для моделирования графов Петри позволяет определить оптимальные скорости поездов и время их остановки при различной нагрузке метрополитена.Построенный граф Петри, представляющий собой параллельный алгоритм, может обладать критическими свойствами, наличие которых при его реализации делает неработоспособными проектируемое устройство или параллельную программу. Предлагаемое устройство моделирования графов Петри позволяет моделировать обход графа, т. е. отработку параллельного алгоритма, с целью выявления и устранения критических свойств.Различают три критических свойства в графах Петри: конфликтная разметка верацин мест р,; небезопасная разметка вершин мест р,; неживое свойство графов Петри.Правильно построенный (реализуемый) граф Петри должен обладать безконфликтным, безопасным и живым свойствами.Остановимся подробнее на определениях критических свойств в графах Петри.Конфликтное свойство.Безконфликтным называется такой граф Петри, который при его обходе не содержит конфликтных разметок вершин мест р т. е. если при всех разметках графа т, М не наступает ситуации, при которой срабатывание одного из возбужденных переходов 1, ведет к запиранию других возбужденных переходов , 1314350 10На фиг. 8 а показана конфликтная разметка подграфа в графе Петри. Разметка мест т(р = т(рг) = 1 и т(рз).= - т(рз) = 1 ведет к тому, что переходы 1) и Ьз могут сработать. Но срабатывание одного из них, характеризующееся устранением меток из входящих в переход мест (например р) и рз для , ведет к запиранию другого (для 6 з т(рз) = 0 и т(рз) = 1.Безопасное свойство. Безопасным называется такой граф Петри, который при его обходе не содержит небезопасных разме(к)ток мест р,. Разметка то графа Петри называется безопасной, если разметка каждого места при перемещении меток является безопасной (т (р,.) ( 1), Если разметка хотя бы одного места р, , (р,.) ) 1, то такой граф имеет небезопасное свойство.Пример небезопасного графа Петри приведен на фиг. 8 б. При последовательности срабатываний переходов т = 1 Ь, Ь в место ро попадают две метки и тз(рз) =2.Живое свойство. Живым называется такой граф Петри, который содержит лишь живые вершины переходов 1. В свою очередь переход 1 называется живым при заданном множестве возможных разметок -(к)т афпг, если существует такая последовательность срабатываний переходов г):= ),в которой переход 1 срабатывает хотя бы один раз и может сработать еще раз.Возможны два случая несрабатывания переходов 1, В первом случае (фиг. 8 в) не существует последовательность срабатываний переходов б, при которой переход г 4 может сработать. Это обуславливается тем, что одновременно по одной метке в местах рз и рз быть не может. Во втором случае (фиг. 8 г) срабатывание перехода приводит к тому, что переходы 1) и 1; не могут сработать. Для анализа графа Петри на некритические свойства вводится вектор добавочного условия х = ( х, хх"х), позволяющий моделировать самые различные последовательности срабатываний переходов.Таким образом, для срабатывания переходов 1 при проверке их на живость необходимо совпадение двух условий: " 1 х 6 т -д О)х = 1.Последовательное изменение значения вектора проверочных сигналов от (1,1,1, ,1) до ,0,0,0, , О) позволяет реализовать полный перебор всех последовательностей срабатываний переходов графа Петри 0 для данной начальной разметки то. Для определения любого критического свойства достаточно двухкратного срабатывания каждого из переходов 1,Устройство работает следующим образом.Записывается топология моделируемого графа Петри в блоки 2, начальная разметка -- в регистры 3 и 13, необходимое число циклов работы устройства на одном шаге моделирования -- в регистр 45 бло 5 О 15 20 25 30 35 40 45 50 55 ка 12 контроля живого свойства. Все разряды счетчика 29 находятся в состоянии 1. Ввод данных осуществляется при помощи блока 1 ввода следующим образом.Для моделирования графа Петри, содержащего гг вершин мест р, и т вершин переходов 1 требуется наличие т узлов в блоках 2, 5, 9, 10 т групп элементов И 30 л, т триггеров в группе 34, а все группы элементов - содержать по а элементарных схем.Для загрузки топологии графа и начальной разметки составляется таблица топологии графа Петри (см. табл.). Причем каждой вершине перехода 1 соответствует входной " р, и выходнойц разметочные вектора, Все переходы 1 графа Петри заносятся в колонку Обозначение переходов. Например, переходу 1) соответствует 1 г = = ( 1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0) и= (0.1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)" . В )-х входных (выходных) разметочных векторах 1 стоят в тех е-х столбцах, которым соответствуют места рявляющиеся входными (выходными) для перехода 1,Режим моделирования графа Петри включается после подачи сигнала Пуск на вход установки триггера 50 и подключением к устройству опорного генератора 17.На первом шаге моделирования все разряды счетчика 29, имитирующего вектор дополнительных условий Х, находятся в состоянии 1 и, следовательно, значение всех входных разметочных векторов, хранящихся в блоке 2, подаются через группы элементов И 30.130,т на схему блока 5 сравнения входных векторов, где они одновременно анализируются в узлах 5.15.т на принадлежность к вектору текущей разметки то к" цтос). Выполнение условия о рто говорит о том, что переход 1,. подлежит запуску на данном цикле моделирования, и " р. необходимо вычесть из то". Векторы текущей разметки " 1 г, подлежащие- (к)вычитанию из то на данном шаге моделирования, через подгруппы элементов 21.1 21.т подаются на элементы ИЛИ 22.122 п группы для формирования суммарного входного вектора, вычитаемого из вектора то в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ,ед -+ - гк) Одновременно значение всех 1 г Е то через соответствующие выходы подаются на блок 16 для анализа конфликтных ситуаций. Конфликтная ситуация возникает в случае наличия 1 в каком-либо в-м разряде более чем одного вектора 1 гто). Тогда соответствующий блок 50.в выдает признак конфликтной ситуации, индицируемый соответствующим е-м элементом индикации группы 51, а на элементе ИЛИ-НЕ 52 формируется инверсный управляющий сигнал, прекращающий подачу тактирующих сигналов Ф 1 и Ф 2 от генератора 15. Устройство прекращает работу и на блоке 4 индикации индицируется текущая разметка, при которой возниклаконфликтная ситуация. Если конфликтная ситуация не обнаружена на элементе И 24 по совпадению признака наличия запускаемых переходов, формируемым элементом ИЛИ 23, и тактового импульса Ф 1, вырабатывается управляющий сигнал, разрешающий через коммутатор 6 запись нового- (К+1)значения вектора текущей разметки то определенного в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, в регистр 3 задания текущей разметки.Приход сигнала Ф 1 инициирует вычитание 1 из значения, хранящегося в счетчике 46, В случае отсутствия на первом шаге моделирования при логическом сигнале все разряды вектора ( в состоянии 1 переходов 1 для которых бы выполнялось условие " р б т(о)к), в блоке контроля живого свойства 12 по совпадению сигнала уровня 1 на выходе элемента И 31 и О на выходе элемента И 24 на элементах И 37 и ИЛИ 41, 43 формируется управляющий сигнал обнаружения неживого свойства, прекращающий подачу тактовых импульсов г 1) 1 и Ф 2, и индицируемый элементом 42. Если неживое свойство не обнаружено, то логические единицы с выходов элементов ИЛИ-НЕ 20 л для которых ( 6 то ) подаются соответственно на входы блока 9 сравнения выходных векторов и одновременно запоминаются в -х триггерах группы триггеров 34.1 - 34.т. Так как для проверки на критические свойства предполагается мгновенное срабатывание переходов в нашем случае время срабатывания переходов равно промежутку между появлением сигнала Ф 1 и Ф 2), то необходимо на этом же цикле работы устройства промоделировать окончание работы только что запущенных переходов, Значения выходных разметочных векторов р, переходов 1 запущенных на длинном цикле моделирования, через -е группы элементов И 25.1 - 25.т подаются на схему формирования суммарного выходного вектора группа элементов ИЛИ 26.1 - 26.п), подлежащего сложению с вектором текуи -з (КФ 1)щеи разметки то в блоке 8 элементов ИЛИ. Кроме того значения всехр-+(К+1)прибавляемых к то на данном цикле-(к+омоделирования, и значение то подаются на схему блока 18 для контроля безопасного свойства. Небезопасное свойство имеет место при наличии 1 в каких либо е-х разрядах объединенного вектора, объедиф (ки)няющего вектор то и набор векторов аи -ъ (кн)р, прибавляемых к то на данном цикле работы устройства . Тогда соответствующий блок 54,е выдает признак конфликтной ситуации, индицируемой соответствующим в-м элементом индикации группы 56 и на элементе ИЛИ-НЕ 55 формируется инверсный управляющий сигнал, прекращающий подачу тактовых импульсов Ф 1 и Ф 2 на схему устройства. Если небезопасное свойство не обнаружено, то по приходу тактового импуль са Ф 2 на выходе элемента И 28 форма.,1 ся управляющий сигнал, разрепаюньнй сение нового значения вектора текунц и 1;.метки то(к"), определенного в блоке 8,:( ментов ИЛИ, через коммутатор 6 в реги(р задания текущей разметки. Новое значение(к+1.)вектора текущей разметки то заносится в регистр 3 и работа устройства повторяется до установления О во всех разрядах счетчика 46, что свидетельствует об окончании шага моделирования. Счетчиком 46 вырабатывается управляющий сигнал начала нового шага моделирования, по которому число, хранящееся в регистре 45, заносится в счетчик 46, в регистр 3 через ком мутатор 6 заносится значение вектора начальной разметки Ио из регистра 3, все триггеры набора 34 устанавливаются в состояние О, из счетчика 29, имитирующего вектор дополнительных условий хо вычитается 1. Условием начала нового шага моде 2025 3035 формула изобретения 40 45 50 55 лирования может быть отсутствие запускаемых переходов ,. на очередном цикле моделирования, если все разряды счетчика 29 находятся в состоянии 1 управляюгций сигнал формируется на элементах НЕ 44, НЕ 33, И 36, ИЛИ 40). Шаги моделирования повторяются до появления О во всех разрядах счетчиков 29 и 46, на основании которого элементами И 39, ИЛИ 43 формируется сигнал окончания работы устройства без обнаружения критических свойств.Если в ходе моделирования будет обнаружено хотя бы одно критическое свойство, необходимо устранить его из графа Петри и провести повторное моделирование до полного устранения критических свойств.Таким образом, предлагаемое устройство позволяет моделировать графы Петри, описывающие параллельные процессы, на наличие критических свойств. 1. Устройство для моделирования графов Петри, содержащее блок регистров задания входных векторов, блок регистров задания выходных векторов, регистр задания текущей разметки, блок сравнения входных векторов, блок сравнения выходных векторов, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок элементов ИЛИ и генератор тактовых импульсов, инверсный выход регистра задания текущей разметки является выходом текущей разметки устройства и соединен с первым информационным входом блока сравнения входных векторов, выход сопровождения информации которого соединен с первым управляющим входом коммутатора, выход которого соединен с информационным входом регистра задания текущей разметки, прямой выход которого соединен с первыми входами блока элементов ИЛИ и блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы ко 13 1314350торых соединены с первым и вторым информационными входами коммутатора соответственно, выход признаков сравнения блока сравнения входных векторов иодклюцен к второму входу блока элементов ИСКЛ 10- ЧАЮ 1 ЦЕЕ ИЛИ, первый выход блока регистров задания выходных векторов подключен к первому информационному входу блока сравнения выходных векторов, выход признаков сравнения которого подключен к второму входу блока элементов ИЛИ, выход сопровождения инфорации блока сравнения выходных векторов подключен к второму управляющему входу коммутатора, отличающееся тем, цто, с целью расширения функциональных возможностей за счет контроля наличия критических свойств в графах, в него введены регистр начальной разметки, блок коммутации, блок контроля конфликтных ситуаций, блок контроля безопасного свойства, блок контроля живого свойства, элемент ИЛИ, выход регистра начальной разметки подключен к третьему информационному входу коммутатора, с второго по т-й выходы блока регистров задания выходных векторов (где т - число моделируемых вершин переходов) подклк)цены к второму по т-й информационным входам блока сравнения выходных векторов соответстенно, с первого ио л-й информационные выходы которого (где и - число моделируемых вершин мест) подключены к первому по п-й информационным входам блока контроля безопасного свойства соответственно, (и+1) -й информационный вход блока контроля безопасного свойства подключен к прямому выходу регистра задания текущей развертки, с первого по т-й выходы блока регистров задания входных векторов подключены к первому по т-й информационным входам блока коммутации соответственно, с первого по т-й выходы которого подключены к второму ио (т+)-й информационным входам блока сравнения входных векторов соответственно, с первого по т-й информационные выходы которого подключены к первому по т-й информационным входам блока контроля конфликтных ситуаций, выход признака конфликтной ситуации которого подключен к первому входу останова генератора тактовых импульсов, первый выход которого подклюцен к входам синхронизации блока контроля живого свойства и блока сравнения входных векторов, с первого ио т-й выходы признака перехода которого иодклюцены к первому ио т-и одноименным входам блока сравнения выходных векторов и блока контроля живого свойства, выход признака неживого свойства которого иодклюцен к второму входу останова генератора тактовых импульсов, третий вход останова - которого подключен к выходу признака небезопасной разметки блока контроля безопасного свойства, выход признака нового цикла блока контроля живого свойства иодклюцен к перво 5 10 15 20 25 30 35 40 4 с 50 55 му входу элемента ИЛИ, к третьему управ ляющему входу коммутатора и к управляю. щему входу блока коммутации, выходы признаков начала и конца моделирования которого подключены к одноименным входам блока контроля живого свойства, вход признака наличия перехода которого подключен к второму входу элемента ИЛИ и к выходу сопровождения информации блока сравнения входных векторов, выход сопровождения информации блока сравнения выходных векторов подключен к третьему входу элемента ИЛИ, выход которого подключен к входу синхронизации регистра задания текущей разметки, а блок контроля живого свойства содержит группу триггеров, элемент И-НЕ, два элемента НЕ, четыре элемента И, четыре элемента ИЛИ, регистр задания числа циклов, счетчик, причем в блоке контроля живого свойства информационный вход сцетцика соединен с выходом регистра задания числа циклов, входы установки с первого по т-й триггеров группы являются с первого ио т-й входами признака перехода блока контроля живого свойства, вход признака налиция перехода которого соединен через первый элемент НЕ с первыми входами первого и второго элементов И, выходы которых подключены к первым входам первого и второго элементов ИЛИ, выход первого элемента ИЛИ иодклюцен к первому входу четвертого элемента ИЛИ и является выходом признака нового цикла блока контроля живого свойства, вход синхронизации которого подключен к выцитающему входу сцетцика, выход признака нулевого состояния которого подключен к первому входу четвертого элемента И и к вторым входам первого и четвертого элементов ИЛИ, выход которого подклюцен к входу записи счетчика, выход второго элемента ИЛИ подклюцен к входам сброса триггеров группы и к первому входу третьего элемента ИЛИ, выход которого является выходом признака неживого свойства блока контроля живого свойства, входы признаков начала и конца моделирования которого соединены с вторыми входами второго и четвертого элементов И соответственно, второй вход второго элемента И соединен с входом второго элемента НЕ, выход которого соединен с вторым входом первого элемента И, выходы триггеров группы подключены к входам элемента И-НЕ, выход которого подклюцен к первому входу третьего элемента И, выход которого подключен к второму входу второго элемента ИЛИ, выход четвертого элемента И подключен к вторым входам третьих элементов И и ИЛИ, второй выход генератора тактовых импульсов подключен к входу синхронизации блока сравнения выходных векторов.2. Устройство по п. 1, отличающееся тем, цто, с цельк повышения быстродействия, блок сравнения входных векторов содер 15 1314350жит две группы из т подгрупп по и элементов И, где т и и - число моделируемых вершин мест и переходов соответственно, т элементов ИЛИ-НЕ, группу элементов ИЛИ, элемент ИЛИ и элемент И, первые входы элементов И всех подгрупп первой группы поразрядно объединены и образуют первый информационный вход блока, выходы элементов И р-й подгруппы (р=1 т) первой группы подключены к входам р-го элемента ИЛИ-НЕ, выход которого подключен к первым входам элементов И р-й подгруппы второй группы, к р-му входу элемента ИЛИ и является р-м выходом признака перехода блока, вторые входы элементов И р-й подгруппы первой и второй групп поразрядно объединены и образуют (р+ 1)-й информационный вход бока, выход (й - 20)-го элемента И (/г= 1п) р-й подгруппы второй группы подключен к р-му входу й-го элемента ИЛИ группы и к выходу р-го разряда Й-го информационного выхода блока, выход элемента ИЛИ подключен к первому входу элемента И, второй вход и выход которого являются входом синхронизации и выходом сопровождения информации блока соответственно, выходы элементов ИЛИ группы образуют выход признаков сравнения блока. 3. Устройство по п. 1, отличающеесятем, что, с целью повышения быстродействия, блок сравнения выходных векторов содержит группу из и подгрупп элементов И, группу элементов ИЛИ, элемент ИЛИ и элемент И, первые входы элементов И р-й подгруппы элементов (р=1и) образуют р-й информационный вход блока, вторые входы элементов И р-й подгруппы группы соединены с р-м входом элемента ИЛИ и с р-м входом признака перехода блока, выход й-го элемента И (Ф= 1л) р-й подгруппы группы является р-м разрядом 1-го информационного выхода блока и соединен с р-м входом 1-го элемента ИЛИ группы, выходы элементов ИЛИ группы образуют выход признаков сравнения блока, 20 выход эле ента ИЛИ подключен к перво увходу элемента И, второй вход и выход которого являются входом синхронизации и выходом сопровождения информации блока соответственно.