Устройство для моделирования графов Петри Советский патент 1988 года по МПК G06F15/173 

(21) 4122948/24-24

(22)23.09.86

(46) 15.08i88. Бюп. № 30

(71)Институт проблем моделирования в энергетике АН УССР

(72)В.В.Васильев, В.В.Кузьмук, Е.Б.Лисицин и В.А.Шумов

(53) 681.333(088.8)

(56)Авторское свидетельство СССР № 879594, кп. G 06 F 1.5/20, 1979.

Авторское свидетельство СССР № 1171803, кл. G 06 F 15/20, 1984.

(54l устройстве ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ ПЕТРИ

(57)Изобретение относится к области вычислительной техники и может быть

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

(Л

114

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

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

На фиг о 1 представлена схема устройства g на фиг. 2 - схема блока ввода,- на фиг, 3 - схемы блоков текущей размет1-си5 хранения типов дуг и инвертирования на фиг. 4 - схема блока хранения входных векторов; на фиг.5 - схема блока сравнения входных векто

ров 5 на фиг е б - схема блока мод елей вершин5 на фиг,, 7 - схема счетчика,, входящего в состав узлов блока моде- отей вершин; на фиг 8 - схе мы блока исклкя4:ения меток коммутатора и блока : записи меток , на фиг 9 - схема блока сравнения вьпмдных векторов, на фиг, 10 - пример модулируемого графа Петри

Кроме Toroj дана таблица подготовки исходных данньк для решения задачи на предлагаемом устройстве.

Устройст зо (фиг„- 1) со/держит блок 1 ввода, блок 2 текущей разметки блок 3 индикащий блок 4 хранения входных векторовS блок 5 сравнех-шя В кодньк векторов5 блок 6 моделей вершин, блок 7 исключения меток коммутатор 8,j блок 9 записи меток g блок 10 сразкакяя вьшодных векторовs генератор 11 тактовых иг-шульсов, блок 12 хранения разметочных векторов,, блок 13 хранения типов дуг блок 14 инвертироваш- я и элемент ИЛИ i5, .

Блок 1 ввода предназначен для ввода в устройство топологии моделируемого графа Петри5 а именно входных раз- меточкьк векторовэ начальной разметки верпинг длительностей срабатывания переходов э типов дугз вь одных. разметочньк векторов

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

Блок 4 хранения входных векторов предназначен -для хранения входных разметоч1№1х векторов для всех вершин пер.еходовэ у которых вьтолнены условия срабатывания и формирова ия уп равляюпц-JK сигналов вьиитатдая соответ15

10

ствующих входных разметочных векторов из вектора текущей разметки графа Петри.

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

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

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

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

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

Блок 10 сравненияi выходньп: векторов служит для отбора выходных разметочных векторов (соответствугош :-1Х пе- реходам моделирование срабатывания 30 которых окончено) с целью дальнейшего их прибавления к вектору текущей разметки.

Генератор 11 тактовых импульсов формирует непересекающуюся дв хфаз- 5 ную последовательность сигналов Ф1 и 02, управляющих работой устройства.

Блок 12 хранения разметочных векторов предназначен для хранения выходных разметочных векторов для всех 0 вершин переходов.

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

Управляющий элемент ИЛИ 15 формирует сигнал, разрешагошкй изменение Q значения вектора текущей разметки. Блок 1 ввода (фиг, 2) содержит группу 16 тумблеров, группу 17 переключателей, грзтпу триггеров 18.1- 18.3, дешифратор 19, группу дешифра- 5 торов 20.1-20,4J группу 21 тумблеров перехшючатель 22 и триггер 23

Блок 2 текущей разметки (фиг,3) образуют элемент И 24 элемент ИЛИ 25, группа элементов И,ТИ 26.1--26.М (где

М - число вершин мест в моделируемом графе Петри), группа элементов НЕ 27.1-27,т и группа триггеров 28.1- 28,М.g

Блок 4 хранения входных векторов содержит К регистров (К - число переходов в моделируемом графе). Каждый рег.истр содержит группу элементов НЕ 29, элемент И 30 и группу тригге- ю ров- 31 .

Блок 5 сравнения входных векторов (фиг. 5) выполнен в виде К узлов сравнения, каждьш из которых содержит группу элементов И 32, элемент ИЖ-НЕ 15 чальной разметки составляется табли- 33, группу элементов И 34, группуца топологии графа Петри (см. таблиэлементов ИСКЛЮЧАЮЩЕЕ ИЛИ 35, кроме того, в состав блока 5 сравнения входных векторов входят элемент ИЛИ 36, элемент И 37 и группа элементов ИЛИ 20 38.

Блок 6 моделей вершин (фиг. 6) со- держит К узлов моделей вершин, каждый из которых содержит регистр 39 и счетчик 40.25

Счетчики 4О включают группу элементов И-НЕ Д1, группу триггеров 42, группу элементов 2И-ИЛИ 43, триггер 44 и элемент И 45,

Коммутатор 8 состоит из двух групп 30 1 инвертирования. После инвертиро- элементов И 46.1 и 46.2, двух триггеров 47.1 и 47.2 и группы элементов ИЛИ 48.. .

ри, длительности срабатывания переходов), набираемые на тумблерах группы 21, заносятся в соответствующие блоки (4,.12, 13, 2, 6) устройства, определяемые положением переютючателей группы 17 переключателей. , Регистр одного из этих блоков, в который заносится очередной компонент исходных данных задачи, определяется положением тумблеров группы 16 тумблеров После ввода исходных данных режим записи отключается.

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

Режим моделирования графа Петри включается переводом переключателя генератора 11 в положение Пуск.

Значение вектора текущей разметки из блока 2 текущей разметки и значение векторов типов дуг из блока 13 хранения типов дуг подаются на входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 55 блока

вания на элементах НЕ 56.2 инверти- рованные значения вектора подаются на входы элементов И 32 блока срав- нения входных векторов и на выходе элемента ИЛИ-НЕ 33.2 появляется 1, свидетельствующая, что переход может быть запущен на текущем такте модели рования. Эта 1 является управляющим сигналом начала моделирования срабатывания перехода и через четвертый управляющий выход (4) начала имитации срабатывания перехода блока 5 сравнения входных векторов подается-на второй вход (2) блока 6 моделей вершин и переводит счетчик 40.2 в режим Счет.

Блок 10 сравнения входных векторов (фиг. 9) содержит группу триггеров 49, группу элементов И 50, формирователь 51 импульса, элемент РШК 52, элемент И 53 и группу элементов ИЛИ ,54.

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

Блок 13 хранения типов дуг представляет- собЬй группу К регистров.

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

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

После включения питания переключателем 22 триггер 23 устанавливается в состояние 1, обеспечивая режим ввода исходны данных для решения задачи по мод) ированию составленного графа Петри. Данные (входные разметочные векторп, выходные разметочные векторы, BCI торы типов дуг, начальная разметке графа Пет- обобщенного входного вектора, коточальной разметки составляется табли- ца топологии графа Петри (см. таблири, длительности срабатывания переходов), набираемые на тумблерах группы 21, заносятся в соответствующие блоки (4,.12, 13, 2, 6) устройства, определяемые положением переютючателей группы 17 переключателей. , Регистр одного из этих блоков, в который заносится очередной компонент исходных данных задачи, определяется положением тумблеров группы 16 тумблеров, После ввода исходных данных режим записи отключается.

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

Режим моделирования графа Петри включается переводом переключателя генератора 11 в положение Пуск.

Значение вектора текущей разметки из блока 2 текущей разметки и значение векторов типов дуг из блока 13 хранения типов дуг подаются на входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 55 блока

инвертирования. После инвертиро-

ания на элементах НЕ 56.2 инверти- ованные значения вектора подаются на входы элементов И 32 блока срав- нения входных векторов и на выходе элемента ИЛИ-НЕ 33.2 появляется 1, свидетельствующая, что переход может быть запущен на текущем такте моделирования. Эта 1 является управляющим сигналом начала моделирования срабатывания перехода и через четвертый управляющий выход (4) начала имитации срабатывания перехода блока 5 сравнения входных векторов подается-на второй вход (2) блока 6 моделей вершин и переводит счетчик 40.2 в режим Счет.

Для перехода, который не может быть запущен на текущем такте модели- рования, появляется О на выходе соответствующего элемента ИЛИ-НЕ 35 запрещающий запуск соответствующего счетчика 40

Далее значения входных векторов, из которых исключены ссыпки на инверс- ные дуги, через группы элементов И 34.2 и 34.5 подаются на элементы ИЛИ 35.1-35.М, где формируется значение

514169846

рое подается на элементы ИСКЛЮЧАЮЩЕЕ векторов, первые входы которого сое- ИЛИ блока 7 для имитации вычитаниядинены с информационными выходами блоиз вектора текущей разметки,ка моделей вершин, информационные

Новое значение вектора текущейвходы которого соединены с первыми

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

Через количество тактов, записан-первыми информационными входами блоное в счетчик 40„5, по приходу импуль-ю ка исключения.меток, выходы которого

са Ф2 счетчик 40,5 обнуляется (так как счетным импульсом для него является иг-шульс Ф2) и на его выходе по- Я1щйется 1 % которая разрешает занесение числа пересчета счетчиков из регистра в счетчик 40,5, устанавливает триггер 49,5 в состояние 1 и таким образом формирует через элемент ИШ1 52 и элемент И 53 сигнал разрешения изменения вектора текущей разметки 5 а также разрешает подачу значения выходного разметочного вектора из регистра 12„ 5 через группу элементов И 50„5 и группу элементов ШЖ 54 1-54оМ на вторые входы схем ШШ блока 9s где производится имитация сложения с вектором текущей разметки и новое значение вектора текущей разметки заносится через комлутатор 8 в блок 2 текущей разметки,, На следующем цикле м оделирования появляется возможность запуска следующего перехода а

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

соединены с первыми информационными входами коммутатора, вторые информационные ВХОДЫ которого соединены с выходами блока записи меток, а выходы

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

25 хранЕния разметочных векторов,, а выход признака сравнения соединен с . первым управляющим входом коммутатора, второй управляющий вход которого соединен с выходом признака сравне-

30 ния блока сравнения входных векторов первые информационные входы которого соединены с информационными выходами блока хранения входных векторов, о т- личающееся тем, чтор с це лью расширения функциональных возможностей за счет моделирования графов Петри с инверсными дугами, в него введены элемент ИЛИ, блок инвертирования и блок хранения типов.дуг, ин- Устройство для моделирования гра- 40 Формационные выходы которого соединеЗВ

Формула

зобретения

ФОБ ПетриJ содержащее блок текущей разметки5 блок хранения входньк векторов,, блок сравне шя входных векто- роВэ блок моделей вершин, блок хране- Ш5я разметочных векторовj блок сравнения выходных векторов блок исключения меток, блок записи меток, коммутатор, генератор тактовых импуль- coBj первый выход которого соединен с тактовым входом блока сравнения входных векторов,, а второй выход сое- ,цинен с тактовыми входами блока моделей вершин и блока сравнения выходных

ны с первыми информационными входами блока сравнения входных векторов и блока инвертирования, вторые информационные входы которого сое,цинены с

информационными выходами блока текущей коммутации, а выходы соединены с третьими информационными входами блока сравнения входных вектор)он, пер- вьм и второй входы элемента ИЛИ сое-

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

P .. CJpZlZlIZJ

n I

EJ Us:iwI/;isai:i-:i.tfu::air3Ki:;r is:..

Фиг. 2

ФигЛ

Фаг.6

Фиг. 7

Фив. 8