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

17146 СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ ЕСПУБЛИК 49(51)5 0 06 ТЕНИЯ СВИДЕТЕЛЬСТВУ АВТО РС делирования в нкин, В.В, Кузьрепелица во СССР, 1980.во СССР ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ИСАНИЕ И(71) Институт проблем мэнергетике АН УССР(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ ПЕТРИ(57) Изобретение относится к вычислительной технике и может быть использовано в различных областях промышленности для моделирования параллельйых процессоров, которые алгоритмически описаны с помощью сетей Петри, Цель изобретения - повышение достоверности моделирований и расширение функциональных возможностей на моделирование оценочных графов Петри (т.е., таких, в которых вершины мест могут содержать любое целое число меток1714621 Составитель С,ЗенкинТехред М.Моргентал Корректор О,Кундрик И.Горн е аказ 695 Тираж . Подписное ВНИИПИ Государственноо комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/5 Производственно.-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, Ю1714621 И О, а кратность (вес) дуг К может быть любым. положительным целым числом (К 1). устройство содержит блок ввода 1, блок хранения вводных векторов 2, блок текущей разметки 3, блок моделей вершин 4, блок хранения выходных векторов 5, блок сравнения 6, генератор тактовых импульсов 7, блок индикации 8, блок суммиро-, вания 9, блок просмотра входных векторов 10, блок формирования дополнительного кода 11, блок анализа 12, блок фиксации 13, блок просмотра выходных векторов 14. Перед началом работы в устройство вводятся исходные данные: входные разметочные векторы - в блок хранения входных векторов 2, выходные разметочные векторы - в блок хранения выходных векторов 5, время й срабатывания переходов - в блок моделей вершин 4, вектор начальной разметки - в блок текущей разметки 3, количество переходов в моделируемом графе Петри - в регистры блоков просмотра входных векторов 10 и просмотра выходных векторов 14. Режим моделирования начинается с запуска генератора тактовых импульсов 7 с помощью блока просмотра входных векторов 10, На вход блока сравнения 6 из блока хранения входных векторов 2 по очередиИзобретение. относится к цифровой вычислительной технике, а именно к устройствам для обработки информации специального назначения, в частности для решения задач на сетях Петри, и может быть применено в различных отраслях промышленности для откладки алгоритмов моделирования параллельных процессов,Известно устройство для моделирования графов, содержащее блок моделей вершин, блок формирования топологии, счетчик, являющийся таймером модели, генератор тактовых импульсов (ГТИ), блок памяти, датчик случайных чисел и дешифратор и характеризующееся тем, что оно позволяет строить специализированные стохастические модели, моделировать различные последовательности действий и последовательностные процессы,Недостатками этого известного устройства являются его узкая специализация и отсутствие возможности моделирования целого класса графов - графов (сетей) Петри.Из известных устройств для моделирования графов Петри наиболее близким по технической сущности к предлагаемому явподаются входные разметочные векторы е,и и анализируются на принадлежность их вектору текущей разметки а. Если это имеет место, то формируется сигнал включения .соответствующей модели вершины 1. Одновременно блок формирования дополнительного кода 11 и блок суммирования 9 обеспечивают вычитание вектора е,и иэ вектора в, а блок анализа 12 обеспечивает запись нового значения вектора текущей разметки в блок текущей разметки 3. Кроме того, в одном цикле работы устройства на вход блока суммирования 9 из блока хранения выходных векторов 10 с помощью блока просмотра выходных векторов 14 подаются значения выходных разметочных векторов е)-р в случае поступления из блока моделей вершин 4 через блок фиксации 13 сигналов окончания моделирования переходов т 1 и прибавляются к содержимому блока текущей разметки 3. Затем с помощью блока анализа 12 изменяется содержимое блока текущей разметки 3, Цикл работы устройства повторяется до окончания моделирования заданного графа Петри. Блок индикации 8 служит,для визуального наблюдения за состоянием моделируемого графа Петри.12 ил,ляется устройство, содержащее блок индикации, блок текущей разметки, блок памяти, генератор тактовых импульсов, блок сравнения, блок ввода, блок моделей вершин, 5 датчик случайных чисел и блок установкипоследующей разметки и характеризующееся тем, что оно позволяет строить специализированные модели на основе теорийсетей Петри и моделировать параллельные 1 О процессы в сложных асинхронных, многопроцессорных и многомашинных системах.Недостатком этого известного устройства является его узкая специализация на моделирования только безопасных графов 15 Г 1 етри, т.е. такой разновидности, в которойвершины мест могут содержать не более одной метки, а кратность дуг, соединяющих вершины графа, может быть равна только единице, Кроме того, устройство неадекват но моделирует параллельные процессы в.связи с последовательным сравнением на каждом участке работы устройства (т.ев каждую единицу модельного времени) только одного входного разметочного вектора с 25 вектором текущей разметки, С увеличениемчисла т моделируемых вершин переходовувеличивается цикл работы счетчика1714621 20 25 30 45 5и растет время запаздывания между появлением условий для моделирования и фактическим моделированием вершин 1(1уПЗ) .Целью изобретения является повыше-. 5 ние достоверности моделирования и расширение функциональных возможностей на. моделирование оценочных графов Петри,т.е. таких, в которых вершины мест могут содержать любое целое неотрицательное число меток йО, а кратность(вес) дуг К может быть любым положительным целымчислом(К1).На фиг.1 представлена схема предлагаемого устройства; на фиг,2 - схема блока ввода; на фиг.З - схема блока хранения входных векторов; на.фиг,4 - схема блока текущей разметки," на,фиг,5 - схема блока моделей вершин и блока фиксации; на фиг.6 -,схема счетчика, входящего в состав блока моделей вершин; на фиг.7 - схема блока хранения выходных векторов;.,на фиг.8 - схема блока сравнения; на фиг.9 - схемы блока суммирования, блока формирования дополнительного кода и управляющего элемента; на фиг,10 - схемы блока просмотра входных векторов и блока просмотра выходных векторов; на фиг,11 - пример графа Петри, иллюстрирующий основные положения теории графов Петри; на фиг.12 - примерграфа Петри, иллюстрирующий работу предлагаемого устройства.Устройство содержит блок 1 ввоДа, блок 2 хранения входных векторов, блок 3 текущей разметки, блок 4 моделей вершин, 35 блок 5 хранения выходных векторов, блок 6.сравнения, генератор 7 тактовых импуль. сов, блок" 8 индикации, блок 9 суммирования, блок 10 просмотра входных векторов,блок 11 формирования дополнительного ко да, блок 12 анализа, блок 13 фиксации иблок 14 просмотра выходных векторов.Блок 1 ввода (фиг,2) содержит набор 15 тумблеров, набор 16 переключателей, набор ВЗ-триггеров 17.1-17.3, дешифратор 18, набор дешифраторов 19 1-19,3, набор 20 тумблеров, переключателей 21, ВЗ-триггер 22,набор инверторов 23,1-23,3,Блок 2 хранения входных векторов(фиг,З) содержит в узлов хранения входных 5 О векторов 2. и и набор из в элементов НЕ 26, ю. Каждый из узлов хранения входных векторов 2. у содержит набор из и 4-разрядных регистров 24.ю,е,(е =1,2,и, где и - число вершинмест в моделируемом гра фе Петри) и элемент И 25 ю .Блок 3 текущей разметки (фиг;4) содержит и 4-разрядных регистров 3. е, эле-. менты ИЛИ 27 и И 28. Каждый из регистров 3. е содержит набор элементов НЕ 29.е,1 - 29.е, 4, набор триггеров 30. е . 1 - 30.е 4и набор элементов ИЛИ 31 е 1-31. е .4,Блок 4 моделей вершин (фиг,5) содержит в узлов моделей вершин 4 у, каждый изкоторых содержит регистр 32 у и счетчик33. Р, Счетчики 33. Р предназначены длямоделирования срабатывания переходови могут быть реализованы по известнойв ЦВТ схеме. Счетчик 33. ю работает в режиме вычитания и содержит набор триггеров34 у. 1 - 34 у. К, набор элементов 2 И-ИЛИ35 л.1 - 35 У .К - 1, КЯ-триггер 36, элементИ 37 и набор элементов И-НЕ 38.м 1-38 у.К.Блок 5 хранения выходных векторов 5(фиг.7) содержит ги узлов хранения выходных векторов 5 х, в элементов НЕ 39, юиэлементов И 40 у,Блок 6 сравнения (фиг,8) содержит набор из и компараторов 41.е, набор изиэлементов ИЛИ 42.е, элементов И. 43, элемент НЕ 44, ЯЯ-триггер 45, набор из щ элементов И 46. ю и набор из щ элементов НЕ47, м.Блок 9 суммирования (фиг.9) содержит исумматоров. 9. е.Блок 10 просмотра входных ееторов(фиг,10) содержит генератор 48 прямоугольных импульсов (ГПИ) и узел 49 управления.Последний содержит регистр 50, счетчик 51и дешифратор 52.Блок 11 формирования дополнительного кода (фиг,9) содержит четыре элементаНЕ 53,е. 1-53 е.4, и счетчиков 54.е и элемент НЕ 55.Блок 12 анализа (фиг.9) содержит дваэлемента ИЛИ 58 и 59 и элемент 60 задержки.Блок 13 фиксации (фиг,5) содержит набор из ВЯЗ-триггеров 13. кБлок 14 просмотра выходных векторов(фиг.10) содержит ГПИ.56 и узел 57 управления.Устройство работает следующим образом.Пусть необходимо смоделировать графПетри, который содержит два типа вершин;вершины переходов (в дальнейшем переходов) и вершины мест Р (а дальнейшеммест). Примером может служить граф, приведенный нв фиг,11.Метки располагаются в вершинах местРе и их появление или удаление моделируетсоответственно окончание. или начало реальных действий а 1, имитируемых переходами 1. Местонахождение меток в графеПетри отображается вектором текущей разметки аР= (З,О;1,6,1,0,0,0,0,0,1,0,1.0,1,1,1,1).Цифра "0" на втором месте означает, что место Р 2 не содержит метку, "3" на первом поездов одновременно на одну станциюместе - Р 1 содержит три метки, "1" на треть- (кроме станции отстоя), что привело бы их кем месте - Рз содержит одну метку. При столкновению. Моделирование построенсоставлении графа Петри устанавливаются ного графа Петри в устройстве для моделиего топология и начальная разметка во . 5 рования графов Петри позволяетКаждая вершина перехода тз моделирует определить оптимальные скорости поезДоввремя выполнения какого-либо действия. и время задержек при различной нагрузкеПеРеход цможет сработать, если в каждом метрополитена.из мест Р, от которых кФнаправлено какое- Для загрузки топологии графа Петри илибо количество дуг, находится число меток, 10 начальной разметки составляется таблицабольшее или равное числу дуг, направлен- топологии графа Петри (таблицы наных от этого места Р к рассматриваемомуфиг,11 и 12). При этом каждой вершинепереходу ц. Так, найример, переходы О, тз перехода 1 соответствует входной" р ии сь могут сработать. В переход т 1 входят выходной,и разметочные векторы, адуги от переходов Р 1 и Р 1 о, в которых нахо также Ь 1 - количество единиц модельногодится необходимое число меток. Это являет- времени (количество циклов работы устройся условием начала моделирования ства - однократной последовательностидействия а 1, которое характеризуется вре- действительных уровней сигнала и 2 ГТИменем Ьт 1. В момент начала выполнения 7), имитирующих выполнение реальногодействия а 1 из мест Р 1 и Р 1 о убирается по 20 действия а.одной метке (в соответствии с числом дуг, На фиг.12 представлен пример графанаправленных от мест Р и Р 1 о к 1), и через Петри, на котором иллюстрируется работавремя Ьт в место, к которому направле- устройства,ны дуги от т 1(Р 2), записывается одна метка. Перед началом работы в режиме вводаКаждый переход тхарактеризется вход-.25 исходных данных задачи (топологии графа1 м разметочным вектором,й и выход- Петри) устанавливаются переводом в соота 1 -+н ым ра зметочн ы м . вектором,и . ветствующее положение переключатели 2 .Вектора записываются в траьсфор- Данные, представленныевтаблицетополомированной норме. Так, для перехода т: гии графа Петри (фиг.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" на втором месте в р говорит хранения входных векторов 2, вь ходео 1-+2ныо том, что от т 1 к Р 2 направлена одна дуга, 35 разметочные векторы - в блок 5 храненияЕсли, например, на е-м месте в р записа- выходных векторов, времена Ь 1 срабаты"3", ает, что от 1 к Р направ- вания переходов - в регистры 32. мблока,лены три дуги. Количество дуг, моделей вершин, вектор начальной разнаправленных от одной вершины к дру- метки - в блок 3 текущей разметки, количегой, называется весом дуги К. 40 ство переходов в моделируемом графеНа фиг.11 представлен пример моде- Петри - в регистры блоков просмотра вхвд- .лируемого графа Петри для примера мо- ных векторов 10 и просмотра выходных векделирования управления поездами торов 14. Конкретные ге узлы и регистрыметрополитена. Вершины мест Р 2 + Р 9 мо- блоков хранения входных векторов 2, хранеделируют станции, вершина Р - станцию 45 ния выходных векторов 5, моделей вершинотстоя поездов. Наличие меток в местах Р 1- 4, в которые заносится информация, опреР 9 моделирует наличие поездов на станциях деляются положением тумблеров набора 151-9. Наличие меток в местах Рю - Рп моде- тумблеров,лирует наличие зеленого света на соответ- В связи с особенностями реализацииств ю их перегонах. Каждый из переходов 50 блоков хранения входных векторов 2 и храт 1-ь моделирует время Ь, включающее нения выходных векторов 5 данные в нихпереезд с одной станции на другую и оста- заносятся в инверсном коде, После заненовку на последующей станции. Данный сения исходных данных режим вводаотграф Петри моделирует процесс выхода по- ключается. Режим моделированияез ов метрополитена на линию и движение 55 устанавливается переводом переключатепоездов по кольцу, Система управления ля ГТИ 7 в положение "Пуск". По приходуобеспечивает максимальную пропускную импульса Ф 1 начинают функционировать .способность (зеленый свет) наибольшему счетчик 51 и на вход блока 6 сравнения изчислу поездов и запрещает попадание двух блока 2 хранения входных векторов по очезаключается в том, что во время моделирования вершины перехода 1 Может начатьсямоделирование других вершин переходов. Ф ор мул а изобретен ия 5 Устройство для моделирования графов Петри, содержащее блок хранения входных векторов, блок сравнения, блок моделей вершин, блок хранения выходных векторов, блок суммирования, блок текущей размет ки, блок индикации, генератор тактовых импульсов и блок ввода, причем информационный выход блока ввода подключен к информационному входу блока хранения входных векторов, к первому информацион ному входу блока текущей разметки, к информационным входам блока моделей вершин и блока хранения выходных векторов, первый управляющий выход блока ввода подключен к первым управляющим 20 входам блока хранения выходных векторов,блока моделей вершин, блока текущей разметки и блока хранения входных векторов, информационный выхоД которого подключен к первому информационному входу 25 блока сравнения, второй информационный вход которого подключен к первому информационному выходу блока текущей разметки, Ч-й выход признака "Не меньше" Ч = 1,2 М, где М - количество вершин-пере- .30 ходов в графе Петри) подключен к Ч-му входу опроса блока моделей вершин, Ч-й выход признака моделирования первой группы которого подключен к Ч-му входу опроса первой группы блока сравнения, тактовый вход 35 блока моделей вершин подключен к первому выходу генератора тактовых импульсов, второй управляющий выход блчока ввода - к второму управляющему входу блока моделей вершин, третий управляющий выход к 40 второму управляющему входу блока текущей разметки, второй информационный выход которого подключен к информационному входу блока индикации, информационный выход блока хранения выходных 45 векторов подключен к входу первого слагаемого блока суммирования, первый инфор-. мационный выход блока текущей разметки подключен к входу второго слагаемого блока суммирования, выход которого подклю чен к второму информационному входу блока текущей разметки, четвертый и пятый управляющие выходы блока ввода подключены к второму и третьему управляющим входам блока хранения выходных векторов соответственно, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем моделиро- . вания оценочных графов Петри, в него введены блок фиксации, блок формирования дополнительного кода, блок анализа и блок просмотра входных векторов, причем первый информационный выход блока ввода подключен к информационному входу блока просмотра входных векторов, первый и шестой управляющие выходы - к первому и второму управляющим входам блока просмотра входных векторов, тактовый вход которого подключен к второму выходу генератора тактовыхимпульсов, Ч-й выход группы блока просмотра входных векторов - к Ч-му входу опроса блока хранения входных векторов и к Ч-му входу опроса второй группы блока сравнения, управляющий выход блока просмотра входных векторов подключен к одноименному входу блока сравнения и к первому управляющему входу блока формирования дополнительнога кода, информационный выход которого подключен к информационному выходу блока хранения входных векторов, второй управляющий вход - к первому выходу блока анализа, второй выход которого подключен к третьему управляющему входу блока текущей разметки, Ч-й выход признака ".Не меньше" блока сравнения подключен к Ч-му разряду первого информационного входа блока анализа, Ч-й разряд второго информационного входа которого подключен к Ч-му управляющему входу первой группы блока хранения выходных векторов и к Ч-му разряду информационного выхода блока фиксации, Ч-й разряд информационного входа которого подключен к Ч-му выходу признака моделирования второй группы, блока моде-лей вершин, тактовый вход блока фиксации подключен к второму выходу генератора тактовых импульсов, первый выход которого подключен к тактовому входу блока просмотра выходных векторов, первый информационный и первый и седьмой управляющие выходы блока ввода подключены к информационному входу и к первому и второму управляющим выходам блока просмотра. выходных векторов соответственно, Ч-й выход которого подключен к Ч-му у про вляющему входу второй груп и ы блока хранения выходных векторов,