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

.В. Кузьмук,умов етей Петри Мир, 1984 ьство СССР 15/20, 1983. ОДЕЛИ РОВ сится к вычи может быть и ния временныхания систем,три. Целью изобирение функциоГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗО АВТОРСКОМУ СВИДБТЕЛЬСТ(71) Институт проблем моделв энергетике АН УССР(56) Питерсон Дж. Теория си моделирование систем. М.с. 264.Авторское свидетел11 1171803, кл . С 06 Р(54) УСТРОЙСТВО ДЛЯГРАФОВ ПЕТРИ(57) Изобретение отнслительной технике и пользовано для получ диаграмм функциониро описываемых сетями П ретения является рас Изобретение относится к области цифровой вычислительной техники и может быть использовано для получения временных диаграмм функционирования систем, описываемых сетями Петри,Целью изобретения является расширение функциональных возможностей устройства за счет моделирования аппаратных графов Петри с местами акку мулирующего типа, разрушающими дугами, дугами переменного веса и с метками, распространенными в числовые значения.На фиг, 1 пнальная схема редставлена функциоустройства; на фиг.2 нальных воэможностей устройства засчет моделирования аппаратных графов(сетей) Петри с местами аккумулирующего типа, разрешающими дугами, дугами переменного веса и с метками, раскрашенными в числовые значения. Местааккумулирующего типа позволяют отразить в модели одновременно используемые в нескольких целях переменные,разрушающие дуги позволяют организовать удаление меток из мест аккумулирующего типа. Дуги переменноговеса могут принимать при каждом срабатывании перехода, к которому ониприсоединены, значения "1" или "0",т.е, по окончании срабатывания перехода метка либо передается, либо непередается по этим дугам. Раскрашенним меткам ставятся в соответствиестроки бит определенной длины, кбторые могут моделировать, например,последовательность микрокоманд. 3 илпример модулируемого графа Петри;на фиг. 3 - временная диаграмма работы блока синхронизации,Устройство содержит блок 1 синхронизации, первую группу из М регистров 2, где М - количество вершинпереходов в графе Петри, вторую группу из М регистров 3, третью группу изМ регистров 4, группу из М блоков 5поразрядного сравнения, первую группуиз М блоков элементов И 6, вторуюгруппу из М блоков элементов И 7,третью группу из М блоков элементовИ 8, первую группу из М счетчиков 9,вторую группу из М счетчиков 10, 14834591 О группу из М блоков ИСКЛЮЧАЮЩЕЕ ИЛИ 11блок элементов НЕ 12, группу из Мблоков 13 памяти, блоки элементовИЛИ с первого по четвертый 14 17,блок элементов ИСКЛГ)ЧАЮ 111 ЕЕ ИЛИ 18,блок 19 логического сложения, первыйтретий элементы ИЛИ 20-22, блок элементов И 23, первый и второй элементы И 24, 25, регистр 26, коммутатор27, блок 28 переключателей, группуиз М элементов 29, задержки и группуиз М элементов ИЛИ 30,Кроме того, на фиг. 1 цифровыеобозначения имеют входы 31 задания 15времени исполнения вершин переходов,вход 32 задания начальной разметкиустройства, вход 33 начальной установки устройства, вход 34 пуска устройства,первый тактовый выход 35 блока 201 синхронизации, второй тактовый выход 36 блока 1 синхронизации, входы37 задания входных векторов К-вершинпереходов, входы 38 задания типовдуг, входы 39 задания выходных разме. 25точных векторов.Блок 1 синхронизации предназначендля .Формирования непересекающейсядвухфазной,последовательности сигналов "Фаза 1" и "Фаза 2", управляющих работой устройства,Первая группа из М регистров 2предназначена для хранения входныхраэметочных векторов для всех вершин.переходов (К=1,2 И),Вторая группа из М регистров 3предназначена для хранения времен исполнителя вершин переходов ЬС.Третья группа из М регистров 4предназначена для хранения векторовтипов дуг для каждой вершины переходаГруппа из И блоков 5 поразрядногосравнения предназначена для определения вершин переходов , у которыхвыполняются условия запуска.Первая группа из М блоков элементов И 6 предназначена для отборавходных разметочных векторов переходов, у которых выполнены условиязапуска.50Вторая группа из М блоков элементов И 7 предназначена для отбора векторов типов дуг, соответствующих переходам , для которых выполненоусловие запуска. 55Третья группа иэ М блоков элемен-.тов И 8 предназначена для отбора выходных разметочных векторов, соответствующих переходам г, моделированиевьколнения которых окончено.Первая группа из М счетчиков 9предназначена для моделирования испол.кения вершин переходов. Вторая группа из М счетчиков 10предназначена для отсчета числа срабатывания соответствующих переходов"кГруппа И блоков ИСКЛЮЧАЮЩЕЕ ИЛИ 11предназначена для исключения из входных разметочных векторов дуг разрушающего типа перед определением запускаемых переходов.Блок элементов НЕ 12 предназначендля обеспечения функционирования регистра хранения текущей разметки безсигнала "Установка 0".Группа из М блоков 13 памяти предназначена для хранения переменныхзначений выходных разметочных векторов перехоДов и позволяет моделировать циркуляцию раскрашенных меток.Первый блок 14 элементов ИЛИ предназначен для формирования суммы входных раэметочных векторов запускаемыхпереходов.Второй блок 15 элементов ИЛИ предназначен для Формирования суммы выходных разметочных векторов перехо"дов, моделирование которых окончено.Третий блок 16 элементов ИЛИ предназначен для подачи нового значениявектора текущей разметки в регистр.Четвертый блок 17 элементов ИЛИпредназначен для формирования суммывекторов типов дуг запускаемых переходов,Блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 18предназначен для вычисления новогозначения вектора текущей разметкипосле запуска переходов,Блок 19 логического сложенияпредназначен для вычисления новогозначения вектора текущей разметкипосле окончания выполнения переходов.Первый элемент ИЛИ 20 предназначендля формирования признака разрешенияизменения значения вектора текущейразметки, если хотя бы для одногоперехода С выполняется условие запуска.Второй элемент ИЛИ 21 предназначендля Формирования признака разрешенияизменения значения вектора текущей.разметки, если окончено моделированиехотя бы одного переходаЭлемент ИЛИ 22 предназначен для синхронизации занесения информации в регистр 26.Третий блок элементов И 23 предназначен для обеспечения моделирования вершин мест аккумулирующего типа,Первый элемент И 24 предназначен для синхронизации признака разрешения изменения текущей разметки импульсом сигнала "Фаза 1" блока 1 синхронизации. Второй элемент И 25 предназначен для синхронизации признака разрешения изменения текущей разметки импульсом сигнала "фаза 2" блока 1 синхронизации.Регистр 26 предназначен для имитации вектора текущей разметки в вершинах мест моделируемого графа Петри.Коммутатор 27 предназначен для попеременной подачи нового значения вектора текущей разметки на вход регистра 26.Блок 28 переключателей предназначен для установки типов вершин мест (простые и аккумулирующие) моделируемого графа Петри.Усгройство работает следующим образом.Пусть требуется смоделировать систему, описываемую графом Петри (фиг. 2). Данные о топологии графа (входные разметочные вектора, наборы выходных разметочных векторов, вектора типов дуг, начальная разметка графа Петри, времена выполнения переходов) заносятся в соответствующие группы регистров и группу блоков памяти. После ввода таблицы топологии графа Петри с помощью блока 28 переключателей устанавливается тип вершин,мест, Если Я переключательблока 28 подключен к выходу блока элементов НЕ 12, то Я -й разряд регистра 26 моделирует наличие меток в месте обычного типа, иначе - в месте аккумулирующего типа. После ввода исходных данных устройство переводится в режим моделирования графа Петри посредством воздействия на вход 34 пуска. Значения векторов тиЬ чпов дуг р и входных разметочных векторовф р из регистров 2 и 3 первой и третьей группы подаются на входы блоков группы ИСКЛЮЧАЮЩЕЕ ИЛИ 11 для исключения влияния разрушающих дуг на условия запуска перехода. Так для с .е р = (1,О,О,О,О,О,О,О)1е- Далее р подаются на входы блоков 5 поразрядного сравнения, кудатакже подается значение вектора текущей разметки для проверки выполненияусловий запуска переходов. В результате будет разрешено начало модели рования только перехода Т. "1" свыхода второго блока 5 поразрядногосравнения подается на вход разрешениясчета соответствующего счетчика 9и переводит его в режим "Счет", ае -также, разрешает прохождение р ир через первую 6 и вторую 7 группыблоков И на входы соответственно блоков пеового 14 и четвертого 17 элее 1 -ментов ИЛИ, где вычисляются . р 20, В данном случае, (ц = , Р"= р . В блоке элементов ИСКЛЮЧАЮЩЕЕИЛИ 18 вычисляется новое значениевектора текущей разметки: ш 0 = (О,О,О, О, О, О, О, О), которое подается напервый информационный вход коммутатора. Одновременно сигнал с выходаблока 5 поступает на счетный входсоответствующего счетчика 10 и увеличивает его содержимое на 1, что чри водит к подключению к выходу соответствующего блока 13, первого из наборов значений переменных выходных разметочных векторов. Этот же сигнал,проходя через элементы ИЛИ 20, И 24, З 5 ИЛИ 22 (по приходу импульса Ф 1 сблока 1 синхронизации)подключает первый информационный вход коммутатора27 к его выходу и формирует сигналразрешения изменения содержимого,ре гистра 26Счетчики 9 работают следующим образом. После перевода врежим счет они начинают работать в.режиме вычитания, причем счетнымиимпульсами являются сигналы Ф 2 бло ка 1. При установке во всех разрядахК-го счетчика значений "О" сигнал наего выходе переполнения через элемент29 задержки и элемент ИЛИ 30 поступает на собственный вход признака записи и в счетчики снова заносится изрегистра 3 второй группы длительностьвыполнения перехода, Одновременносигнал с выхода признака переполнения , счетчика 9 первой группы поступаетна вход соответствующего блока 8 ио 4 -фразрешает прохождение значения р на .вход блока 15, где формируется, р,которая подается далее на вход блока19 логического сложения, где вычи 1483459сляется новое значение ш, поф кФ 11даваемое на второй информационныйвход коммутатора 27. Одновременносигнал признака окончания моделиро 5вания перехода проходит через элементы ИЛИ 21, И 25, ИЛИ 22 и подключаетвторой информационный вход коммутатора 27 к его выходу, а также разрешает перезапись содержимого регистра 26.10Так, по приходу первого же импульса "Фаза 2" блока 1 моделирование С2будет окончено и установится разметкатп,= (1,0,0,1,0,1,0,0), что позволитв следующий момент модельного времени 15по приходу Ф 1 начать моделированиеи С;. По приходу 20-го с моментазапуска С ф 2 моделирование С будетзавершено, После запуска С и С вычисляется значение в = (Ою 0,0,0,0, 200,0,0). По окончании моделированияС+ ш = (0,0,0,1,0,0,0,1)По приходу50-го после запуска С, Ф 2 будет вычислено в, = (0,1,0,1,0,0,0,1), Далееустройство продолжает работать по 25описанному алгоритму.Временные диаграммы работы устройства приведены на фиг. 3.На временной диаграмме работыустройства приняты следующие обозначения: И 25 - уровень сигнала на выходе второго элемента И 25, ИЛИ 21 уровень сигнала на выходе второгоэлемента ИЛИ 21, ИЩ 1 30. К - уровеньсигнала на выходе К-го элемента груп 35пы иэ М элементов ИЛИ 30, Ст 9. К -значение сигнала на выходе К-го счетчика первой группы из М счетчиков 9,СЧ/ЗАПР 9,К - режим работы К-госчетчика группы 9, ИЛИ 22 - уровеньсигнала на выходе третьего элемента ИЛИ 22, И 24 - уровень сигналана выходе первого элемента И 24,ИЛИ 20 - уровень сигнала на выходепервого элемента ИЛИ 20, БЛ,5.Куровень сигнала на выходе К-го блокапоразрядного сравнения группы 5,СТ 10.К, СТ 9.К - значения, содержащиеся в счетчиках 10.К, 9,К,ЕО 26содержимое регистра 26, Ф 2 и Ф 1уровни сигналов на втором и первомвыходах блока 1 синхронизации.На фиг. З,показаны запуск и пассивизация перехода Ск (ЬС, - времявыполненИя перехода Ск).55Формула изобретенияУстройство для моделирования графов Петри, содержащее две группы иэ М регистров, где М - количествовершин переходов в графе Петри,регистр, группу из М блоков поразрядного сравнения, группу из М блоковИСКЛЮЧАЮЦЕЕ ИЛИ, группу иэ М элементов задержки, первую группу из М блоков элементов И, группу из М элементов ИЛИ, первую группу из М счетчиков, три блока элементов ИЛИ, блокэлементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок логического сложения, три элементаИЛИ, два элемента И, коммутатор,блок синхронизации, блок элементовНЕ, причем вход задания входноговектора К-й вершины перехода устройства (К=1 М) подключен к информационному входу К-го регистра первой группы, выход которого подключенк первому информационному входу К-гоблока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ ик информационному входу К-го блокаэлементов И первой группы, выходкоторого пбдключен к К-му входу первого блока элементов ИЛИ, выход ко 1торого подключен к первому информационному входу блока элементов ИСКЛОЧАЮЦЕЕ ИЛИ, выход которого подключен к первому информационному входу коммутатора, выход К-го блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключен кпервому информационному входу К-гоблока поразрядного сравнения, выходпризнака неравенства нулю результатасравнения которого подключен к управляющему входу К-го блока элементовИ первой группы, к входу разрешениясчета К-го счетчика первой группыи к К-мувходу первого элемента ИЛИ,выход которого подключен к первомувходу первого элемента И, вход задания времени выполнения К-й вершиныперехода устройства подключен к информационному входу К-го регистравторой группы, выход которого подключен к информационному входу К-госчетчика первой группы, выход признака переполнения которого подключенк входу К-го элемента группы задержки, выход которого подключен к первому входу К-го элемента ИЛИ группы,выход которого подключен к вхоцу приз"нака записи того же счетчика группы,свыход которого подключен к К-му входу второго элемента ИЛИ, выход которого подключен к первому входу второго элемента И, выход первого элемента И подключен к первому управляющему входу коммутатора и к пер 1483459 1 Овому входу третьего элемента ИЛИ, выход второго элемента И подключен квторому управляющему входу коммутатора и к второму входу третьего элемента ИЛИ, выход которого подключен к5входу признака записи регистра, выход второго блока элементов ИЛИ подключен к первому информационному входу блока логического сложения, выходкоторого иодключен к второму информационному входу коммутатора, вход. задания начальной разметки устройстваподключен к первому входу третьегоблока элементов ИЛИ, выход которогоподключен к входу блока элементовНЕ, выход регистра подключен к вторыминформац%онным входам блоков элементов ИСКЛЮЧАВГЕЕ ИЛИ и блоков логического сложения и к вторым информа Оционным входам всех блоков поразрядного сложения группы, выход коммутатора подключен к второму входу третьего блока элементов ИЛИ, вход начальной установки устройства подключен к входам признаков записи всехрегистров первой и второй группы,к вторым входам всех элементов ИЛИгруппы, и к третьему входу третьего,элемента ИЛИ, первый тактовый выход 30рлока синхронизации подключен к вто 1рому входу первого элемента И, второйтактовый выход блока синхронизациипоДключен к второму входу второгоэлемента И и к первым суммирующимвходам всех счетчиков первой группы,о т л и ч а ю щ е е с я тем; что,с целью расширения функциональныхвозможностей устройства за счет моделирования аппаратных графов Петрис местами аккумулирующего типа,разрушающими дугами, дугами переменного веса и с метками, раскрашеннымив числовые значения, в него введенытретья группа из М регистров, вторая и третья группы из М блоков эле 45ментов И, вторая группа из М счетчиков, группа из М блоков памяти,четвертый блок элементов ИЛИ, блокпереключателей и блок элементов И,причем вход задания вектора типа 50 дуг, исходящих из К-й вершины перехода устройства, подключен к информационному входу К-го регистра третьей группы, выход которого подключен к второму входу К-го блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ группы и к информационному входу К-го блока элементов И второй группы, выход которого подключен к К-му входу четвертого блока элементов ИДИ, выход которого подключен к первому информационному входу блока переключателей, второй информационный вход которого соединен с выходом блока элементов НЕ, выход блока переключателей подключен к пер- вому информационному входу регистра и инверсному инфорлационному входу блока элементов И, прямой информационный вход которого подключен к выходу третьего блока элементов ИЛИ, выход блока элементов И подключен к второму информационному входу регистра, выход признака неравенства нулю результата сравнения К-го блока поразрядно го сравнения группы подключен к первому управляющему входу К-го блока элементов И второй группы и к суммирующему входу К-го счетчика второй группы, выход которого подключен к адресному входу К-го блока памяти группы,выход которого подключен к информационному входу К-го блока элементов И третьей группы, выход которого подключен к К-му входу второго блока элементов ИЛИ, выход признака переполнения К-го счетчика первой группы подключен к управляющему входу К-го блока элементов И тре-. тьей группы, вход начальной установки устройства подключен к входам признаков записи всех регистров третьей группы и к входам установкив "О" всех счетчиков второй группыУ вход задания выходных разметочных векторов устройства подключен к инФормационным входам всех блоков памяти группы, первый тактовый выход блока синхронизации подключен к вторым управляющим входам всех блоков элементов И второй группы., ипигВыХ,ИИНих.СтяФфалр.УИвггИ 2 И 8 Я СТ 10,К СТ Э./ гюгоФ 2 Ф иг оставитель А. Мишин Сактор О, Спесивых Техред Л. Сердюкова Корректор М. Максимишинец Заказ 2834/46 Тираж 668 Подписно ВНИИПИ Государственного комитета по изобретениям и открыткой113035, Москва, Ж, Раушская наб., д. 4/ НТ С ул. Гагарина, 1 оизводственно-издательский комбинат "Патент", г. Ужго