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

 

СОЮЗ СОВЕТСНИХ

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

РЕСГ)УБЛИН (gi) 4 G 06 F 15/20

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

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4122948/24-24 (22) 23.09.86 (46) 15.08;88, Бюл. №- 30 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев, В.В.Кузьмук, Е.Б.Лисицин и В.А.Шумов (53) 68 1.333(088,8) (56) Авторское свидетельство СССР № .879594, кл. G 06 Р 15/20, 1979, Авторское свидетельство СССР

¹ 1171803, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДПЯ МОДЕЛИРОВАНИЯ

ГРАФОВ ПЕТРИ (57) Изобретение относится к области вычислительной техники и может быть

„„SU „„1416984 А 1 использовано для решения задач на безопасных графах Петри. Цель изобретения — расширение класса решаемых задач за счет моделирования графов

Петри с инверсными дугами — достигается тем, что в устройство, содержащее генератор тактовых импульсов, блок текущей разметки, блок хранения входных векторов, блок сравнения входных векторов, блок моделей вершин, блок исключения меток, коммутатор, блок записи меток, блок сравнения выходных векторов, блок хранения выходных векторов, дополнительно введены блок хранения типов дуг, блок инвертирования и элемент ИЛИ. 10 ил ., 3

1 табл, 1 1416984 2

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

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

Ня фиг. 1 представлена схема устройства; ча фиг. 2 — схема блока вводя; на фиг, 3 — схемы блоков текущей разметки, хранения типов дуг и инвертировЯния на фиг, 4 — схема блОкЯ хранения входных векторов! На фиг.5 - 15 схема блока сравнения входных векторов; на фиг. 6 — схема блока моделей ьершин; на фиг,. 7 — схема счетчика, входящего в состав узлов блока моде-: лек вершин, на сдвиг. 8 — схемы блока -0 исключения меток коммутатора и блока записи меток, на фиг, 9 - схема бло-ка сравнения выходных векторов, на фиг„. 10 — пример модулируемого гра1 яя Пе "Рпи „ АЭ

Кроме того-, даня таблица подготовки исходных данных цля Оешения задачи ня предлягяемОм ;":, рсйстве о

Устройство (Фиг. 1) с одержит блок ввода,, блок 2 текущей р Iзметки, 30 бЛОк 1 инДикации блок 4 хрЯнения входных векторов,, блок 5 .равнения входньх векторов, блок 6 моделей вершин, блок 7 исключения меток, ко ячутатор Ь.,блок 9 записи меток,„.

35 блок Q на-- пения выходньгх вектопон генератор 11 тактовых импульсов, блок 12 хранения разметочных векторов.-., блок, хранения ..илов дуг, блок

14 инвертирования и элемент ИЛИ 15, Блок 1 ввода предназначен для ввода в " тройство топологии маделируемо"=

I"DBôB i!.B!. pI- ;. я именно входных pB.BМЕ i ОЧНЫХ BBKTOP OH НЯЧЯЛЬНОй РЯ ЗМЕТ ки вершин,„ длительностей срабатыва- 4,-„ ния переходов, типов дуг, вьЬ:одных разметочных векторов.

БЛОК 2 текущей рЯзметки служит для хранения текущей разметки вершин месT в мОДелиоуемОм графе Петри„

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

Блок 5 сравнения входных векторов служит для обора верпин.

Блок 6 моделей вершин предназначен для моделирования во времени реальных действий, соответствующих переходам.

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

Коммутатор 8 управляет занесением нового значения вектора текущей разметки в блок 2 текущей разметки, а именно либо из блока 7, либо из блока 9.

Блок 9 предназначен для прибавления выходных разметочных векторов, соответствующих переходам, моделирование срабатывания которых окончено, к вектору текущей разметки.

Блок 10 сравнения выходных векторов служит для отбора выходных разметочных векторов (соответствующих переходам, моделирование срабатывания которых окончено} с цепью дальнейшего их прибавления к вектору текущей разметки, Генератор 11 тактовых импульсов формирует непересекающуюся двухфазную последовательность сигналов Ф1 и

Ф2, управляющих работой устройства.

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

Управляющий элемент ИЛИ 15 формирует сигнал, разрешающий изменение значения вектора текущей разметки.

Блок 1 ввода (фиг, 2) содержит группу 16 тумблеров, группу 17 переключателей, группу триггеров 18. 118.3, дешифратор 19, группу дешнфраторов 20.1-20.4, группу 21 тумблеров переключатель 22 и триггер 23, Блок 2 текущей разметки (фиг.3) образуют элемент И 24, элемент ИЛИ 25, группа элементов ИЛИ 26,1-26,i> (где

1416984

М вЂ” число вершин мест в моделируемом графе Петри), группа элементов НЕ

27.1-27.m и группа триггеров 28,128,М.

Блок 4 хранения входных векторов содержит К регистров (К вЂ” число переходов в моделируемом графе) . Каждый регистр содержит группу элементов

НЕ 29, элемент И 30 и группу тригге- 10 ров 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 импульса, элемент Hei 52, элемент И 53 и группу элементов KIN .54.

Блок 12 хранения разметочных векторов представляет собой группу К регистров, Блок 13 хранения типов дуг представляет соббй группу К регистров.

Блок 14 инвертирования содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 55 и ,группу элементов НЕ 56.

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

После включения питания переключателем 22 триггер 23 устанавливается в состояние "1", обеспечивая режим ввода исходньы данных для решения задачи по моделированию составленного графа Петри, анные (входные разметочные вектор, i, выходные разметочные векторы, в<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, по приходу импуль-10 са Ф2 счетчик 40,5 обнуляется (так

>. как счетным импульсом для него является импульс Ф2) ° и на его выходе появляется "1"„ которая разрешает занесение числа пересчета счетчиков 15 из регистра 39.5 в счетчик 40.5, устанавливает триггер 49.5 в состояние

"1" и таким образом формирует через элемент ИЛИ 52 и элемент И 53 сигчал разрешения изменения вектора текущей 20 разметки, а также разрешает подачу значения выходного разметочного вектора из регистра 12.5 через группу эл:ементов И 50.5 и группу элементов

ИЛИ 54,1--54.И на вторые входы схем

ИН4 блока 9, где производится имитация сложения с вектором текущей разметки, и новое значение вектора текущей разметки заносится через коммутатор 8 в блок 2 текущей разметки,, На следую-" ЗО щем иу кле моделирования появляется возможность запуска следующего перехода.

Далее устройство продолжает работать аналогично „

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

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

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

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

Прабабки аут

Разметочяме векторы

0 t О 0

С!»

Р

О 6 0 О

0 0 О

2 tà

0 0 О 0

0 О

0 0 0 О t 0 О. 0

Р 0 а

О О

0 0 0 0

000000.0

О О О О 0 0 0

0 0 О 0 0 1

В йв

1 0

6% ! в

»к 4в ! ею

Р! Р, Рф Р» Рз Рю Рт Рв Р! РФ Р» РФ Рт Рб Рч Рб

О 0 0 0 0

0 t 0 0 0 0 0

0 1 t 0 0 0 0

0 0 1 0 0 0 0

О 0 ! a O 0 0

0 f 0 0 О 0

S 0 0 f 1 0 0 0

0 0 0 e t 0 О О

О 0 О О 1 0 0

0 0 0 О О t 0 0

0 0 0 t О 0

0 0 0 1. 1 0

000000!0

0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 О 0 0 О 0 4 1698k

Й

«( )

lt

pi 1 !

g

141 Ь984

1416984

141 6984

141 6984

141 6984 (42 (д О (2) (У (К) Ц/ к 2) (к)

К+ (В (И (Л

C2) (S) (к+6

fK) б.ш

9) й) и (3 (3)

40N

®(к+д к+2) 141 б984

141 6984

1416984

1416984

Ю

Фиг./О

Составитель О.Гречухина

Редактор A.Îãàð Техред Л. Олийньпс Корректор Г.Решетник

Заказ 5427

Тираж 704 Подписное

ВНИИПИ Государственного комитета. СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4