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

 

Изобретение относится к вычислительной технике и может быть использовано для получения временных диаграмм функционирования систем, описываемых сетями Петри. Целью изобретения является расширение функциональных возможностей устройства за счет моделирования аппаратных графов (сетей) Петри с местами аккумулирующего типа, разрушающими дугами, дугами переменного веса и с метками, раскрашенными в числовые значения. Места аккумулирующего типа позволяют отразить в модели одновременно используемые в нескольких целях переменные, разрушающие дуги позволяют организовать удаление меток из мест аккумулирующего типа. Дуги переменного веса могут принимать при каждом срабатывании перехода, к которому они присоединены, значения "1" или "0", т.е. по окончании срабатывания перехода метка либо передается, либо не передается по этим дугам. Рскрашенным меткам ставятся в соответствие строки бит определенной длины, которые могут моделировать, например, последовательность микрокоманд. 3 ил.

СОЮЗ СОВЕТСКИХ.

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УБЛИН (191 SU (11) А1 (5й 4 С 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4227?93/24-24 (22) 10.04.87 (46) 30.05.89. Бюл. Р 20 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев, В.В. Кузьмук, Е.Б. Лисицин и В.А. Шумов (53) 681.333(088.8) (56) Питерсон Дж. Теория сетей Петри и моделирование систем. M.: Мир, 1984,,с. 264..

Авторское свидетельство СССР Н9 1171803, кл . G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.22 нальных воэможностей устройства за счет моделирования аппаратных графов (сетей) Петри с местами аккумулирующего типа, разрешающими дугами, дугами переменного веса и с метками, раскрашенными в числовые значения. Места аккумулирующего типа позволяют отразить в модели одновременно используемые в нескольких целях переменные, разрушающие дуги позволяют организовать удаление меток из мест аккумулирующего типа. Дуги переменного веса могут принимать при каждом срабатывании перехода, к которому они присоединены, значения "1" или "0", т.е. по окончании срабатывания перехода метка либо передается, либо не передается по этим дугам. Раскрашенним меткам ставятся в соответствие строки бит определенной длины, кбторые могут моделировать, например, последовательность микрокоманд. 3 ил.

1 пример модулируемого графа Петри; на фиг. 3 — временная диаграмма работы блока синхронизации.

Устройство содержит блок 1 синхронизации, первую группу из М регистров 2, где М вЂ” количество вершинпереходов в графе Петри, вторую групI пу из М регистров 3, третью группу из

М регистров 4, группу.из M блоков 5 поразрядного сравнения, первую группу из M блоков элементов И 6, вторую группу из M блоков элементов И 7, (третью группу из М блоков элементов

И 8, первую группу из M счетчиков 9, вторую группу из M счетчиков 10, 1

1483459

1О группу из М блоков ИСКЛЮЧАЮЩЕЕ ИЛИ 11 блок элементов НЕ 12, группу из M блоков 13 памяти, блоки элементов

ИЛИ с первого по четвертый 14,..., 17, блок элементов ИСКЛ11ЧАЮЩЕЕ ИЛИ 18, блок 19 логического сложения, первыйтретий элементы ИЛИ 20-22, блок элементов И 23, первый и второй элементы И 24, 25, регистр 26, коммутатор

27, блок 28 переключателей, группу из М элементов 29, задержки и группу из M элементов ИЛИ 30.

Кроме того, на фиг. 1 цифровые обозначения имеют входы 31 задания времени исполнения вершин переходов, вход 32 задания начальной разметки устройства, вход 33 начальной установки устройства, вход 34 пуска устройства,первый тактовый выход 35 блока 2()

1 синхронизации, второй тактовый вы-, ход 36 блока 1 синхронизации, входы

37 задания входных векторов К-вершин переходов, входы 38 задания типов дуг, входы 39 задания выходных разме- g$ точных векторов.

Блок 1 синхронизации предназначен для .формирования непересекающейся: двухфазной .последовательности сигналов "Фаза 1" и "Фаза 2", управляющих работой устройства.

Первая группа из М регистров 2 предназначена для хранения входных раэметочных векторов для всех вершин. переходов (К=1,2,..., M), Вторая группа из M регистров 3 предназначена для хранения времен исполнителя вершин переходов 5С„.

Третья группа из M регистров 4 предназначена для хранения векторов типов дуг для каждой вершины перехода

Группа из M блоков 5 поразрядного сравнения предназначена для определения вершин переходов t у которых выполняются условия запуска.

Первая группа из М блоков элементов И 6 предназначена для отбора входных разметочных векторов переходов, у которых выполнены условия запуска.

Вторая группа из M блоков элемен« тов И 7 предназначена для отбора векторов типов дуг, соответствующих переходам t, для которых выполнено условие запуска. 55

Третья группа. иэ М блоков элемен-тов И 8 предназначена для отбора выходных разметочных векторов, соответствующих переходам tg моделирование выполнения которых окончено.

Первая группа из М счетчиков 9 предназначена для моделирования исполнения вершин переходов.

Вторая группа из М счетчиков 10 предназначена для отсчета числа срабатывания соответствующих переходов

"к

Группа М блоков ИСКЛЮЧАЮЩЕЕ ИЛИ 11 предназначена для исключения из входных разметочных векторов дуг разрушающего типа перед определением запускаемых переходов.

Блок элементов НЕ 12 предназначен для обеспечения функционирования регистра хранения текущей разметки без сигнала "Установка 0".

Группа из М блоков 13 памяти предназначена для хранения переменных значений выходных разметочных векторов переходов и позволяет моделировать циркуляцию раскрашенных меток.

Первый блок 14 элементов ИЛИ предназначен для формирования суммы входных раэметочных векторов запускаемых переходов.

Второй блок 15 элементов ИЛИ предназначен для формирования суммы выходных разметочных векторов переходов, моделирование которых окончено.

Третий блок 16 элементов ИЛИ предназначен для подачи нового значения вектора текущей разметки в регистр.

Четвертый блок 17 элементов ИЛИ предназначен для формирования суммы векторов типов дуг запускаемых переходов.

Блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 18 предназначен для вычисления нового значения вектора текущей разметки после запуска переходов.

Блок 19 логического сложения предназначен для вычисления нового значения вектора текущей разметки после окончания выполнения переходов.

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

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

1483459 6

Элемент ИЛИ 22 предназначен для синхронизации занесения информации в регистр 26.

Третий блок элементов И 23 предназначен для обеспечения моделирования вершин мест аккумулирующего типа.

Первый элемент И 24 предназначен для синхронизации признака разрешения изменения текущей разметки импульсом сигнала "Фаза 1" блока 1 синхронизации.

Второй элемент И 25 предназначен для синхронизации признака разрешения изменения текущей разметки импульсом сигнала "Фаза 2" блока 1 синхронизации.

Регистр 26 предназначен для имитации вектора текущей разметки в вершинах мест моделируемого графа Петри.

Коммутатор 27 предназначен для попеременной подачи нового значения вектора текущей разметки на вход регистра 26.

Блок 28 переключателей предназначен для установки типов вершин мест (простые и аккумулирующие) моделируемого графа Петри.

Усгройство работает следующим образом.

Пусть требуется смоделировать систему, описываемую графом Петри (фиг. 2). Данные о топологии графа (входные разметочные вектора, наборы выходных разметочных векторов, вектора типов дуг, начальная разметка графа Петри, времена выполнения переходов) заносятся в соответствующие группы регистров и группу блоков памяти. После ввода таблицы топологии графа Петри с помощью блока 28 переключателей устанавливается тип вершин.мест. Если Я переключатель блока 28 подключен к выходу блока элементов НЕ 12, то Я -й разряд регистра 26 моделирует наличие меток в месте обычного типа, иначе — в месте аккумулирующего типа. После ввода исходных данных устройство переводится в режим моделирования графа

Петри посредством воздействия на вход 34 пуска. Значения векторов тиу пов дуг р и входных разметочных векторовЕ р из регистров 2 и 3 первой и третьей группы подаются на входы блоков группы ИСКЛЮЧАЮЩЕЕ ИЛИ

11 длтт исключения влияния разрушающих дуг на условия запуска перехода.

Т для t< . ш = (1,0,0,0,0,0,0,0); е Далее подаются на входы блоков 5 поразрядного сравнения, куда также подается значение вектора текущей разметки для проверки выполнения условий запуска переходов. В результате будет разрешено начало модели10 рования только перехода t . "1" с выхода второго блока 5 поразрядного сравнения подается на вход разрешения счета соответствующего счетчика 9 и переводит его в режим "Счет", а еътакже, разрешает прохождение р и

Ь4 -+ р через первую 6 и вторую 7 группы блоков И на входы соответственно блоков первого 14 и четвертого 17 элее ментов ИЛИ, где вычисляются . р

20 ;> д. В данном случае; (и = 1т, р

= р . В блоке элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ 18 вычисляется новое значение

- ( вектора текущей разметки: m = (О,О, О, О, 0,0, О, О), которое подается на первый информационный вход коммутатора. Одновременно сигнал с выхода блока 5 поступает на счетный вход соответствующего счетчика 10 и увеличивает его содержимое на 1, что три30 водит к подключению к выходу соответствующего блока 13, первого из наборов значений переменных выходных разметочных векторов. Этот же сигнал, проходя через элементы ИЛИ 20, И 24, ИЛИ 22 (по приходу импульса Ф 1 с блока 1 синхронизации)подключает первый информационный вход коммутатора

27 к его выходу и формирует сигнал разрешения изменения содержимого ре40 гистра 26 ° Счетчики 9 работают следующим образом. После перевода в режим счет они начинают работать в .режиме вычитания, причем счетными импульсами являются сигналы Ф2 бло45 ка 1. При установке во всех разрядах

К-го счетчика значений "О" сигнал на его выходе переполнения через элемент

29 задержки и элемент ИЛИ 30 поступает на собственный вход признака записи и в счетчики снова заносится из регистра 3 второй группы длительность вьптолнения перехода, Одновременно сигнал с выхода признака переттолнения, счетчика 9 первой группы поступает на вход соответствующего блока 8 и о4 - разрешает прохождение значения р на . вход блока 15, где формируется, р, которая подается далее на вход блока

19 логического сложения, где вычи1483459 сляется новое значение m t, по- к+(1 даваемое на второй информационный вход коммутатора 27. Одновременно сигнал признака окончания моделиро5 вания перехода проходит через элемен» ты ИЛИ 21, И 25, ИЛИ 22 и подключает второй информационный вход коммутатора 27 к его выходу, а также разреша ет перезапись содержимого регистра 26.10

Так, по приходу первого же импуль са "Фаза 2" блока 1 моделирование t

2 будет окончено и установится разметка тп, — (1,0,0,1,0,1,0,0), что позволит в следующий момент модельного времени 15 по приходу Ф1 начать моделирование и t;. По приходу 20-ro с момента запуска t< Ф2 моделирование t будет завершено. После запуска ty и t вычисляется значение во = (Ою0 0 0 0 20

0,0,0). По окончании моделирования

t+ ш = (0,0,0,1,0,0,0,1) ° По приходу

50-ro после запуска t, Ф2 будет вычислено m = {0,1,0,1,0,0,0,1). Далее устройство продолжает работать по 25 описанному алгоритму.

Временные диаграммы работы устройства приведены на фиг. 3.

На временной диаграмме работы устройства приняты следующие обозна- 30 чения: И 25 — уровень сигнала на выходе второго элемента И 25, ИЛИ 21уровень сигнала на выходе второго элемента ИЛИ 21, ИЩ1 30. К вЂ” уровень сигнала на выходе K-ro элемента груп35 пы иэ M элементов ИЛИ 30, Ст 9. Кзначение сигнала на выходе К-ro счетчика первой группы из М счетчиков 9, СЧ/ЗАПР 9.К вЂ” режим работы К-го счетчика группы 9, ИЛИ 22 — уровень сигнала на выходе третьего элемента ИЛИ 22, И 24 - уровень сигнала на выходе первого элемента И 24, ИЛИ 20 - уровень сигнала на выходе первого элемента ИЛИ 20, БЛ.5.Куровень сигнала на выходе -ro блока поразрядного сравнения группы 5, СТ 10.К, СТ 9.К - значения, содержащиеся в счетчиках 10.К, 9.K RG 26 содержимое регистра 26, Ф2 и Ф1 уровни сигналов на втором и первом выходах блока 1 синхронизации.

На фиг. 3 .показаны запуск и пассивизация перехода t» (ht„, — время выполнения перехода й»).

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

Устройство для моделирования графов Петри, содержащее две группы иэ М регистров, где M — количество вершин переходов в графе Петри, регистр, группу из М блоков поразрядного сравнения, группу из М блоков

ИСКЛЮЧАЮЦЕЕ ИЛИ, группу иэ М элементов задержки, первую группу из М блоков элементов И, группу из М элементов ИЛИ, первую группу из М счетчиков, три блока элементов ИЛИ, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок логического сложения, три элемента

ИЛИ, два элемента И, коммутатор, блок синхронизации, блок элементов

НЕ, причем вход задания входного вектора К-й вершины перехода устройства (К=1,..., М) подключен к информационному входу К-го регистра первой группы, выход которого подключен к первому информационному входу -ro блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и к информационному входу К-го блока элементов И первой группы, выход которого пбдключен к К-му входу первого блока элементов ИЛИ, выход ко1 торого подключен к первому информационному входу блока элементов ИСКЛОЧАЮЦЕЕ ИЛИ, выход которого подключен к первому информационному входу коммутатора, выход -ro блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к первому информационному входу К-го блока поразрядного сравнения, выход признака неравенства нулю результата сравнения которого подключен к управляющему входу -ro блока элементов

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

10 вому входу третьего элемента ИЛИ, выход второго элемента И подключен к второму управляющему входу коммутатора и к второму входу третьего элемента ИЛИ, выход которого подключен к

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

НЕ, выход регистра подключен к вторым информац%онным входам блоков элементов ИСКЛЮЧАВШЕЕ ИЛИ и блоков логического сложения и к вторым информа- щ0 ционным входам всех блоков поразрядного сложения группы, выход коммутатора подключен к второму входу третьего блока элементов ИЛИ, вход начальной установки устройства подклю- 25 чен к входам признаков записи всех регистров первой и второй группы, к вторым входам всех элементов ИЛИ группы, и к третьему входу третьего, элемента ИЛИ, первый тактовый выход

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

ИСКЛЮЧАЮЩЕЕ ИЛИ группы и к информационному входу К-го блока элементов

И второй группы, выход которого подключен к К-му входу четвертого блока элементов ИДИ, выход которого подключен к первому информационному входу блока переключателей, второй информационный вход которого соединен с выходом блока элементов НЕ, выход блока переключателей подключен к пер- вому информационному входу регистра и инверсному инфорлационному входу блока элементов И, прямой информацион.ный вход которого подключен к выходу третьего блока элементов ИЛИ, выход блока элементов И подключен к второму информационному входу регистра, выход признака неравенства нулю результата сравнения К-го блока поразрядно.го сравнения группы подключен к первому управляющему входу К-го блока элементов И второй группы и к суммирующему входу К-ro счетчика второй группы, выход которого подключен к адресному входу К-ro блока памяти группы, выход которого подключен к информационному входу К-ro блока элементов И третьей группы, выход которого подключен к К-му входу второго блока элементов ИЛИ, выход признака переполнения К-го- счетчика первой группы подключен к управляющему входу -ro блока элементов И тре-. тьей группы, вход начальной установки устройства подключен к входам признаков записи всех регистров третьей группы и к входам установки

I в "О" всех счетчиков второй группы

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

l483459

1483459

1483459

025, ИЛИ21

BblA,ИИ

Них.С79

8jmnp.у, ИЯИ22

И24

ИОКИ

0л. 5

СТ N.Ê

СТЭ.Б гюго

Ф2

Ф!

e O @

° ° °

° ° °

Фиг. 3

Составитель А. Мишин

Техред Л. Сердюкова

Корректор М. Максимишинец

Редактор О. Спесивых Заказ 2834/46 Тираж Ь68 Подписное

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

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

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