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

 

Изобретение относится к вычислительной техйике и может быть использовано>& в различных областях промышленности для моделирования параллельных процессоров, которые алгоритмически описаны с помощью сетей Петри. Цель изобретения - повышение Достоверности моделирования и расширение функциональных возможностей на моделирование оценочных графов Петри (т.е., таких, в которых вершины мест могут содержать любое целое число метокФиг.1Ь.Ого

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

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

РЕСПУБЛИК (si)s G 06 F 15/449

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4816639/24 (22) 20,04.90 (46) 23.02.92. Бюл. N 7 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев, С.В, Зенкин. В.В, Кузьмук, Е.Б. Лисицын,. В,B. Перепелица и В..А. Шумов (53) 681.333(088.8) (56) Авторское свидетельство СССР

М 879594, кл. G 06 F 15/20, 1980.

Авторское свидетельство- СССР

М 1171803, кл. G 06 F 15/20. 1983.

„„Я „„1714621 А1 (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

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

Петри (т.е., таких, в которых вершины мест могут содержать любое целое число меток

1714621

N» О, а кратность (вес) дуг К может быть любым положительным целым числом (К «1). Устройство содержит блок ввода 1, блок хранения вводных векторов 2, блок текущей разметки 3, блок моделей вершин 4, блок хранения выходных векторов 5, блок сравнения 6, генератор тактовых импульсоа 7, блок индикации 8, блок суммиро- . вания 9, блок просмотра входных векторов

10, блок формирования дополнительного кода 11, блок анализа 12, блок фиксации 13. блок просмотра выходных векторов 14. Перед началом работы в устройство вводятся исходные данные: входные разметочные векторы — а блок хранения входных векторов 2, выходные разметочные векторы — в блок хранения выходных векторов 5, время hI срабатывания переходов — в блок моделей вершин 4, вектор начальной разметки - в блок текущей разметки 3, количество переходов в моделируемом графе Петри — в регистры блоков просмотра входных векторов

10 и просмотра выходных векторов 14. Режим моделирования начинается с запуска генератора тактовых импульсов 7 с по-мощью блока просмотра входных векторов

10. На вход блока сравнения 6 из блока хранения входных векторов 2 по очереди

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

Недостатками этого известного устройства являются его узкая специализация и отсутствие возможности моделирования целого класса графов — графов (сетей) Петри.

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

,и и анализируются на принадлежность их вектору текущей разметки m<. Если.это имеет место, то формируется сигнал включения . соответствующей модели вершины t . Одновременно блок формирования дополнительного кода 11 и блок суммирования 9 обеспечивают вычитание вектора е,и иэ вектора mp, а блок анализа 12 обеспечивает запись нового значения вектора текущей разметки а блок текущей разметки 3. Кроме того, в одном цикле работы устройства на вход блока суммирования 9 из блока хранения выходных векторов 10 с помощью блока просмотра выходных векторов 14 подаются значения выходных разметочных векторов е

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

8 служит,для визуального наблюдения за состоянием моделируемого графа Петри.

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

10 процессы в сложных асинхронных, многопроцессорных и многомашинных системах.

Недостатком этого известного устройства является его узкая специализация на моделирования только безопасных графов

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

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

1714621

30

5 и растет время запаздывания между появлением условий для моделирования и фактическим моделированием вершин t y (1 м < m) .

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

На фиг.1 представлена схема предлагаемого устройства; на фиг.2 — схема блока ввода; на фиг.3 — схема блока хранения входных векторов; на фиг.4 — схема блока текущей разметки," на,фиг.5 — схема блока моделей вершин и блока фиксации; на фиг.6—,схема счетчика, входящего в состав блока моделей вершин; на фиг.7 — схема блока

: хранения выходных векторов;.,на фиг.8— схема блока сравнения; на фиг.9 — схемы блока суммирования, блока формирования дополнительного кода и управляющего элемента; на фиг.10 — схемы блока просмотра входных векторов и блока просмотра выходных векторов; на фиг,11 — пример графа

° Петри, иллюстрирующий основные положения теории графов Петри; на фиг.12 — пример графа Петри, иллюстрирующий работу предлагаемого устройства.

Устройство содержит блок 1 ввоДа, блок

2 хранения входных векторов, блок 3 текущей разметки, блок 4 моделей вершин, 35 блок 5 хранения выходных векторов, блок

6.сравнения, генератор 7 тактовых импульсов, блок" 8 индикации, блок 9 суммирования, блок 10 просмотра входных векторов, блок 11 формирования дополнительного ко- 40 да, блок 12 анализа, блок 13 фиксации и блок 14 просмотра выходных векторов.

Блок 1 ввода (фиг,2) содержит набор 15 тумблеров, набор 16 переключателей, набор

RS-триггеров 17.1-17.3, дешифратор 18, набор дешифраторов 19 1-19,3, набор 20 тумблеров, переключателей 21, RS-триггер 22, набор инверторов 23.1-23.3.

Блок 2 хранения входных векторов (фиг,3) содержит m узлов хранения входных 56 векторов 2. v и набор из m элементов HE

26, v. Каждый из узлов хранения входных векторов 2. содержит набор из и 4-разрядных регистров 24. v.e,(я = 1,2,.„,n, где п — число вершин мест в моделируемом гра- о5 фе Петри) и элемент И 25л .

Блок 3 текущей разметки (фиг;4) содержит и 4-разрядных регистров 3. е, эле-. менты ИЛИ 27 и И 28. Каждый из регистров

3. е содержит набор элементов НЕ 29.е, 1 — 29.е. 4, набор триггеров 30. е. 1 — 30.84 и набор элементов ИЛИ 31х 1-31. е .4, Блок 4 моделей вершин (фиг.5) содержит m узлов моделей вершин 4.м, каждый из которых содержит регистр 32.v и счетчик

33. v, Счетчики 33. v предназначены для моделирования срабатывания переходов и могут быть реализованы по известной в ЦВТ схеме. Счетчик 33. v работает в режиме вычитания и содержит набор триггеров

34.v. 1 — 34.v. К, набор элементов 2И-ИЛИ

35л .1 — 35л .К вЂ” 1, RS-триггер 36, элемент

И 37 и набор элементов И-HE 38.v1-38у.К.

Блок 5 хранения выходных векторов 5 (фиг.7) содержит m узлов хранения выходных векторов 5х, m элементов НЕ 39, ми элементов И 40., Блок 6 сравнения (фиг.8) содержит набор из и компараторов 41.е, набор из п элементов ИЛИ 42.я, элементов И. 43, weмент НЕ 44, RS-триггер 45, набор из m элементов И 46. v и набор из m элементов НЕ

47, v.

Блок 9 суммирования (фиг.9) содержит и сумматоров. 9. е .

Блок 10 просмотра входных векторов (фиг,10) содержит генератор 48 прямоугольных импульсов (ГПИ) и узел 49 управления.

Последний содержит регистр 50, счетчик 51 и дешифратор 52.

Блок 11 формирования дополнительного кода (фиг.9) содержит четыре элемента

НЕ 53s. 1-53х.4, и счетчиков 54.е и элемент HE 55.

Блок 12 анализа (фиг.9) содержит два элемента ИЛИ 58 и 59 и элемент 60 задержки.

Блок 13 фиксации (фиг,5) содержит набор из m RS-триггеров 13. к

Блок 14 просмотра выходных векторов (фиг.10) содержит ГПИ.56 и узел 57 управления.

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

Пусть необходимо смоделировать граф

Петри, который содержит два типа вершин: вершины переходов (в дальнейшем переходов) и вершины мест Р (в дальнейшем. мест). Примером может служить граф, приведенный нв фиг.11.

Метки располагаются в вершинах мест

Р и их появление или удаление моделирует соответственно окончание. или начало реальных действий а1, имитируемых переходами . Местонахождение меток в графе

Петри отображается вектором текущей разметки вД" =. (З,О;1,6,1,0,0,0,0,0,1,0,1.0,1,1,1,1}.

Цифра "О"- на втором месте означает, что ме1714621 сто Р2 не содержит метку, "3" на первом поездов одновременно на одну станцию месте-Р1содержит три метки, "1" на треть- (кроме станции отстоя), что привело бы их к ем месте — Рз содержит одну метку. При столкновению. Моделирование построенсоставлении графа Петри устанавливаются ного графа Петри в устройстве для моделиего топология и начальная разметка mo . 5 рования графов Петри позволяет

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

Пефеход может сработать, если в каждом метрополитена. из мест Р, от которых кФ направлено какое- Для загрузки топологии графа Петри и либо количество дуг, находится число меток, 10 начальной разметки составляется таблица большее или равное числу дуг, направлен- топологии графа Петри (таблицы на ных от этого места Р к рассматриваемому фиг,11 и 12). При этом каждой вершине переходу ц. Так, найример, переходы t>, тз перехода ty соответствует входной" и и и с могут сработать. В переход т1 вхОДят выхОднОй,и раэмЕтОчныЕ вектОры, а дуги от переходов Р> и Р1о, в которых нахо- 15 также Ьt — количество единиц модельного дится необходимое число меток. Это являет- времени (количество циклов работы устройся условием начала моделирования ства — однократной последовательности действия а1, которое характеризуется вре- действительныхуровнейсигнала . и 2 ГТИ менем Лц. В момент начала выполнения 7), имитирующих выполнение реального действия а1 из мест Р1 и Р1о убирается по 20 действия а . одной метке (в соответствии с числом дуг, На фиг.12 представлен пример графа направленныхот мест Р1и Р1окti), ичерез Петри, на котором иллюстрируется работа время Ьti в место, к которому направле- устройства. ны дуги от tt(Pz), записывается одна метка. Перед началом работы в режиме ввода

Каждый переход т характеризуется вход--25 исходных данных задачи (топологии графа

iv разметочным вектором 7 и выход- Петри) устанавливаются переводом в соот1. н ым ра зметочн ы м . вектором,и . ветствующее положение переключатели 2 .

Вектора записываются в траьсфор- Данные, представленныевтаблицетополомированной норме. Так, для перехода t : гии графа Петри (фиг.11 и 12) набираются в

= (,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0), 30 двоичном коде на наборе 20 тумблеров в

= (0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), зависимости от положения тумблеров набоЕдиница на первом месте в векторе ра 16 заносятся в следующие блоки устройв ит о том, что от Р1 к ц направлена . ства: входные разметочные векторы — в блок одна дуга, "1" на втором месте в и говорит хранения входных векторов 2, вь ход e о<

2 ны о том, что от t1 к Р2 направлена одна дуга. 35 разметочные векторы — в блок 5 хранения

Если, например, на е-м месте в,й записа- выходных векторов, времена Л t срабаты"3", ает, что от t к P направ- вания переходов — в регистры 32. v блока, лены три дуги. Количество дуг, моделей вершин, вектор начальной разнаправленных от одной вершины к дру- метки — в блок 3 текущей разметки, количегой, называется весом дуги К. 40 ство переходов в моделируемом графе

На фиг.11 представлен пример моде- Петри — в регистры блоков просмотра вход- . лируемого графа Петри для примера мо- ных векторов 10 и просмотра выходных векделирования управления поездами торов 14. Конкретные е узлы и регистры метрополитена. Вершины мест Р2 + Pg мо- блоков хранения входных векторов 2, хранеделируют станции, вершина Р— станцию 45 ния выходных векторов 5, моделей вершин отстоя поездов. Наличие меток в местах Р1- 4, в которые заносится информация, onpePg моделирует наличие поездов на станциях деляются положением тумблеров набора 15

1-9. Наличие меток в местах Р1о — Рп моде- тумблеров, лирует наличие зеленого света на соответ- В связи с особенностями реализации ств ю их перегонах. Каждый из переходов 50 блоков хранения входных векторов 2 и xpat1-tg моделирует время Ь1, включающее нения выходных векторов 5 данные в н их переезд с одной станции на другую и оста- заносятся в инверсном коде. После заненовку на последующей станции. Данный сения исходных данных режим ввода отграф Петри моделирует процесс выхода по- ключается. Режим моделирования ез ов метрополитена на линию и движение 55 устанавливается переводом переключатепоездов по кольцу, Система управления ля ГТИ 7 в положение "Пуск". По приходу обеспечивает максимальную пропускную импульса Ф 1 начинают функционироватьспособность (зеленый свет) наибольшему счетчик 51 и на вход блока 6 сравнения из числу поездов и запрещает попадание двух блока 2 хранения входных векторов по оче10

1714621 во 5 0 0 1 Я100 0 во 2 0 0 1

"р 0100

30 во 4 0 0 1 во 2 1 0 1 во400 1 е иг 000. 40 гпо2001 во 0231

"р 0210

ый реди подаются, начиная с m-го, входные

eо-+ разметочные векторы,и и анализируются набором 41 компараторов на принадлежность их вектору текущей разметки (в дан;

- е - ном случае с начальной) m<,и e m<.Если 5 это имеет место, то с помощью элемента

ИЛИ 42х и элемента И 43, RS-триггера 45, элемента И 46.Р и элемента НЕ 47лг формируется сигнал включения соответствующей модели вершины ty, и RS-триггер 10

36.v у станавливается соответственно в "1", и таким образом счетчик 33.v переводится в режим "Счет". Одновременно в течение для. тельности фазового импульса ГПИ 48 блок

11 формирования дополнительного кода и 15 блок 9 суммиоования обеспечивают вычита й-,- ц) -+ еЮ- ние векторае р из вектора во . во = во -,и, а элемент 12 обеспечивает запись нового значения вектора текущей разметки в блок

3 текущей разметки. Таким образом, на пер- 20 вом цикле работы устройства оказываются запущенными счетчики сначала 33.2,. а затем 33.1, соответствующие переходам t2 и ц. После проверкие р вектор текущей разметки имеет вид

Е1 — >

После проверки вектора,и

et «

После проверки векторов,и и,и изменений вектора текущей разметки не проис45 ходит.

Блок 4 моделей вершин работает следующим обра зом.

При занесении топологии графа в регистре 32. v и счетчике Зф устанавливается

50 время Л1, т,е. устанавливается число Nq, После перевода в режим "Счет" счетчик 33. функционирует в режиме вычитания и его содержимое уменьшается каждый раз на

"1" по приходу импульса Ж ГТИ7, Кроме того, по приходу импульса Ф2 начинает функционировать узел 57 управления, позволяющий последовательно в течение одного импульса Ф2 подавать на вход блока 9 суммирования из блока хранения выходных векторов 10 значения выходных раэметочных векторов,и в случае поступления из у блока 4 моделей через блок 13 фиксации сигналов окончания моделирования переходов tq (по совпадению "Г на входах элементов И 403). Сигнал окончания моделирования переходов ty формируется на первых выходах счетчиков 33л, когда все их разряды устанавливаются в "0", и по этому сигналу в счетчики 33.м снова заносятся значения ЬЛ из регистров 32. v. Таким образом, в рассматриваемом примере после запуска на первом цикле работы устройства переходов t1 и tz в течение 10 циклов не происходит изменение вектора текущей разметки mp (для 1з и t4 условия запуска не возникли, а t> и t2 уже запущены и на элементах И 46.v сигналы запуска переходов не формируются, так как на третьи входы через элементы НЕ 47 с выходов

RS-триггеров 36. v поступают запрещающие сигналы). По приходу десятого импульса Ф2 обнуляется счетчик 33.1, и содержимое узла хранения выходных векторов,5.v в блоке 9 суммирования прибавляется к содержимому блока 3 текущей разметки: (н1 и новое значение mo заносится в блок 3 текущей разметки благодаря поступлению сигнала окончания моделирования перехода

t> через управляющий элемент 12 на пятый вход блока 3 текущей разметки. По приходу

11-го импульса Ф 1 снова запчскается переи - «1е -+ ход .ц и, следовательно, в,>= mo- p — (0,1,0,1) . По приходу 15-го импульса

Ф2 оканчивается моделирование t2: в =

= m4"+,è = (0„1.3,1), по приходу 20-го импульса Ф2 оканчивается моделирование

t>: mo m oo - - p = (0,2,3,1), после чего по приходу 21-го Ф 1 запускается тз: и т.д.

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

1714621 заключается в том, что во время моделирования вершины перехода t< Может начаться моделирование других вершин переходов.

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

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

Петри, содержащее блок хранения входных векторов, блок сравнения, блок моделей вершин, блок хранения выходных векторов. блок суммирования, блок текущей размет- 10 ки, блок индикации, генератор тактовых импульсов и блок ввода, причем информационный выход блока ввода подключен к информационному входу блока хранения входных векторов, к первому информацион- 15 ному входу блока текущей разметки, к информационным входам блока моделей вершин и блока хранения выходных векторов, первый управляющий выход блока ввода подключен к первым управляющим 20 входам блока хранения выходных векторов,блока моделей вершин, блока текущей разметки и блока хранения входных векторов, информационный выхоД которого подключен к первому информационному входу 25 блока сравнения, второй информационный вход которого подключен к первому информационному выходу блока текущей разметки, V-й выход признака "Не меньше" (Ч =

1,2,..., M, где М вЂ” количество вершин-пере- .30 ходов в графе Петри) подключен к V-му входу опроса блока моделей вершин, V-й выход признака моделирования первой группы которого подключен к V-му входу опроса первой группы блока сравнения, тактовый вход 35 блока моделей вершин подключен к первому выходу генератора тактовых импульсов, второй управляющий выход блчока ввода — к второму управляющему входу блока моделей вершин, третий управляющий выход к 40 второму управляющему входу блока текущей разметки, второй информационный выход которого подключен к информационному входу блока индикации, информационный выход блока хранения выходных 45 векторов подключен к входу первого слагаемого блока суммирования, первый инфор-. мационный выход блока текущей разметки подключен к входу второго слагаемого блока суммирования, выход которого подклю- 50 чен к второму информационному входу блока текущей разметки, четвертый и пятый управляющие выходы блока ввода подключены к второму и третьему управляющим входам блока хранения выходных векторов соответственно, а т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем моделиро- . вания оценочных графов Петри, в него введены блок фиксации, блок формирования дополнительного кода, блок анализа и блок просмотра входных векторов, причем первый информационный выход блока ввода подключен к информационному входу блока просмотра входных векторов, первый и шестой управляющие выходы — к первому и второму управляющим входам блока просмотра входных векторов, тактовый вход которого подключен к второму выходу генератора тактовых импульсов, V-й выход группы блока просмотра входных векторов— к V-wy входу опроса блока хранения входных векторов и к V-му входу опроса второй группы блока сравнения, управляющий выход блока просмотра входных векторов подключен к одноименному входу блока сравнения и к первому управляющему входу блока формирования дополнительнога кода, информационный выход которого подключен к информационному выходу блока хранения входных векторов, второй управляющий вход — к первому выходу блока анализа, второй выход которого подключен к третьему управляющему входу блока текущей разметки, V-й выход признака ".Не меньше" блока сравнения подключен к V-му разряду первого информационного входа блока анализа, V-й разряд второго информационного входа которого подключен к V-му управляющему входу первой группы блока хранения выходных векторов и к V-му разряду информационного выхода блока фиксации, V-й разряд информационного входа которого подключен к V-му выходу признака моделирования второй группы, блока моде- лей вершин, тактовый вход блока фиксации подключен к второму выходу генератора тактовых импульсов, первый выход которого подключен к тактовому входу блока просмотра выходных векторов, первый информационный и первый и седьмой управляющие выходы блока ввода подключены к информационному входу и к первому и второму управляющим выходам блока просмотра. выходных векторов соответственно, V-й выход которого подключен к

V-му у про вляющему входу второй груп и ы блока хранения выходных векторов.

1714621

1714б21

1714621

Фиа 4

1714621 иа.

1714б21

171462i

1714621

Фиг, 10 а зивчение

5еюшин

tz

tz .1

zz 7 г

1714621

Составитель С.Зенкин

Техред M.Mîðãåíòàë

Корректор О.Кундрик

Редактор И.Горная

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

Заказ 695 Тираж . Подписное

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

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