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

N О, а кратность (вес) дуг К может быть любым положителыным целым числом (К 1). Устройство содержит блок ввода 1, блок хранения вводных векторов 2, блок текущей разметки 3, блок моделей вершин 4, блок хранения выходных векторов 5, блок сравнения 6, генератор тактовых импульсов 7, блок индикации 8, блок суммирования 9, блок просмотра входных векторов 10, блок формирования дополнительного кода 11, блок анализа 12, блок фиксации 13. блок просмотра выходных векторов 14. Перед началом работы в устройство вводятся исходные данные: входные раз еточные векторы - 8 блок хранения входных векторов 2, выходные разметочные векторы - в блок хранения выходных векторов 5, время At срабатывания переходов - в блок моделей вершин 4, вектор начальной разметки - в блок текущей разметки 3. количество переходов в моделируемом графе Петри - в регистры блоков просмотра входных векторов 10 и просмотра выходных векторов 14. Режим моделирования начинается с запуска генератора тактовых импульсов 7 с по- мощью блока просмотра входных векторов 10. На вход блока сравнения 6 из блока хранения входных векторов 2 по очереди

подаются входные разметочные векторы и анализируются на принадлежность их вектору текущей разметки то. имеет место, то формируется сигнал включения соответствующей модели вершины t. Одно- временно блок формирования дополнительного кода 11 и блок суммирования 9 обеспечивают вычитание вектора /Г из вектора гпо, а блок анализа 12 обеспечивает запись нового значения вектора текущей . разметки в блок текущей разметки 3. Кроме того, в одном цикле работы устройства на вход блока Суммирования 9 из блока хранения выходных векторов 10с помощью блока просмотра выходных векторов 14-подаются значения выходных разметочных векторов (Л в случае поступления из блока моделей вершин 4 через блок фиксации 13сигналов окончания моделирования переходов t и прибавляются к содержимому блока текущей разметки 3, Затем с помощью блока анализа 12 изменяется содержимое блока текущей разметки 3. Цикл работы устройства повторяется до окончания моделирования заданного графа Петри. Блок индикации 8 служит для визуального наблюдения за состоянием моделируемого графа Петри. 12 ил.

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

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

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

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

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

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

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

На фиг.1 представлена схема предлагаемого устройства; на фиг.2 - схема блока ввода; на фиг.З - схема блока хранения входных векторов: на .фиг.4 - схема блока текущей разметки: на.фиг.5 - схема блока моделей вершин и блока фиксации; на фиг.6 схема счетчика, входящего в состав блока моделей вершин; на фиг.7 - схема блока хранения выходных векторов; ,на фиг.8 схема блока сравнения; на фиг.9 - схемы блока суммирования, блока формирования дополнительного кода и управляющего элемента; на фиг. 10 - схемы блока просмотра входных векторов и блока просмотра выходных векторов: на фиг.11 - пример графа Петри, иллюстрирующий основные положения теории графов Петри; на фиг.12 - примерграфа Петри, иллюстрирующий работу предлагаемого устройства.,

Устройство содержит блок 1 ввода, блок 2 хранения входных векторов, блок 3 текущей разметки, блок 4 моделей вершин, блок 5 хранения выходных векторов, блок 6 сравнения, генератор 7 тактовых импульсов, блок 8 индикации, блок 9 суммирования, блок 10 просмотра входных векторов, блок 11 формирования дополнительного кода, блок 12 анализа, блок 13 фиксации и блок М просмотра выходных векторов. ;

Блок 1 ввода (фиг.2) содержит набор 15 тумблеров, набор 16 переключателей, набор RS-триггеров 17.1-17.3, дешифраторов, набор дешифраторов 19.1-19.3, набор 20 тумблеров, переключателей 21, RS-триггер , набор инверторов 23.1-23.3.V

Блок 2 хранения входных векторов (фиг,3) содержит m узлов хранения входных векторов 2. V и набор из m элементов НЕ 26. V . Каждый из узлов хранения входных векторов 2. гсодержит набор из п 4-разрядных регистров 24.v.Е.( 1,2,.,мПггде п - число вершинмест в моделируемом графе Петри) и элемент И 25.v .v

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

Блок 4 моделей вершин (фйг.Б) содержит m узлов моделей вершин 4.г, каждый из которых содержит регистр 32.V и счетчик 33. V , Счетчики 33. V предназначены для моделирования срабатывания переходов t и могут быть реализованы по известной в ЦВТ схеме. Счетчик 33. v работает в режиме вычитания и содержит набор триггеров 34.V . 1-34.v. К, набор элементов 2И-ИЛИ 35.V .1 - 35.V .К -1, RS-триггер 36, элемент И 37 и набор элементо.в И-НЕ 38.V 1-38.V.K.

Блок 5 хранения выхгдных вбкторов 5 (фиг.7) содержит m узлов хранения выходных векторов 5.V, m элементов НЕ 39- V элементов И 40.V.

Блок 6 сравнения (фиг.8) содержит набор из п компараторов 41.е , набор из п элементов ИЛИ 42. , элементов И 43, элемент НЕ 44, RS-триггер 45. набор из m элементов И 46. V и набор из m элементов НЕ 47. V. , .

Блок 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) содержит набор из m.RS-тpиггepo8 13. V.

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

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

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

Метки располагаются в вершинах мест Pg и их появление или удаление моделирует соответственно окончание или начало реальных действий а , имитируемых переходами-k). Местонахождение меток в графе Петри отображается вектором текущей разметки (3,0,1,0,1,0,0,0,0,0,1,0,1.0,1,1,1.1). Цифра О на втором месте означает, что место Pa не содержит метку, 3 на первом месте - Р1 содержит три метки, 1 на третьем месте - РЗ содержит одну метку. При составлении графа Петри устанавливаются его топология и начальная разметка то . Каждая вершина перехода t моделирует время выполнения какого-либо действия. Переход цможет сработать, если в каждом из мест Р , от которых к4; аправлено какоелибо количество дуг, находится число меток, большее или равное числу дуг, направленных от этого места Pg к рассматриваемому переходу t. Так, например, переходы ti, t3 и ts могут сработать. В переход ti входят дуги от переходов Pi и Рю, в которых находится необходимое число меток. Это является условием начала моделирования действия 31, которое характеризуется временем Ati. В момент начала выполнения дeйcтвvlя ai из мест Pi и Рю убирается по ОДНОЙ метке (в соответствии с числом дуг, направленных от мест Pi и Рю к ti), и через время Ati в место, к которому направлены дуги OTti(P2), записывается одна метка. Каждый переход Г:)характеризуется вход-ным разметочным вектором / и выходным разметочным вектором Jt. Вектора записываются в трансформированной норме. Так, для перехода ti: /Г (1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0) / (0,1,0,0,Q,0,0,0,0,0,0,0,0,0,0,0,Of. Единица на первом месте в векторе

( /7 говорит о том, что от PI к 11 направлена одна дуга, 1 на втором месте говорит о том, что от ti к Р2 направлена одна дуга. Если, например, на -м месте записана 3, это означает, что от Р направлены три дуги. Количество дуг, направленных от одной вершины к другой, называется весом дуги К.

На фиг.11 представлен пример моделируемого графа Петри для примера моделирования управления поездами метрополитена. Вершины мест Рг + Рэ моделируют станции, вершина Pi - станцию отстоя поездов. Наличие меток в местах PIРЭ моделирует наличие поездов на станциях 1-9. Наличие меток в местах Pio-Pi7 моделирует наличие зеленого света на соответствующих перегонах. Каждый из переходов ti-tg моделирует время At, включающее переезд с одной станции на другую и остановку на последующей станции. Данный граф Петри моделирует процесс выхода поездов метрополитена на линию и движение поездов по кольцу. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух

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

Для загрузки топологии графа Петри и

начальной разметки составляется таблица

топологии графа Петри (таблицы на

фиг.11 и 12). При этом каждой

перехода t: соответствует входной; и

выходной разметочные векторы, а

также А t -количество единиц модельного времени (количество циклов работы устройства - однократной последовательности действительных уровней сигнала -и 2 ГТИ 7), имитирующих выполнение реального

действия а.

На фиг.12 представлен пример графа Петри, на котором иллюстрируется работа устройства.

Перед началом работы в режиме ввода

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

двоичном коде на наборе 20 тумблеров в зависимости от положения тумблеров набора 16 заносятся в следующие блоки устройства: входные разметочные векторы - в блок хранения входных векторов 2, выходнЬ|е

разметочные векторы - в блок 5 хранения выходных векторов, времена At срабатывания переходов - в регистры 32. v блока .4 моделей вершин, вектор начальной разметки - в блок 3 текущей разметки, количество переходов в моделируемом графе Петри - в регистры блоков просмотра входных векторов 10 и просмотра выходных векторов 14. Конкретные узлы и регистры блоков хранения входных векторов 2, хранения выходных векторов 5, моделей вершин 4, в которые заносится информация, определяются положением тумблеров набора 15 тумблеров.

В связи с особенностями реализации

блоков хранения входных векторов 2 и хранения выходных векторов 5 данные в них заносятся в инверсном коде. После занесения исходных данных режим ввода отключается. Режим моделирования

устанавливается переводом переключателя ГТИ 7 в положение Пуск. По приходу импульса Ф 1 начинают функционировать счетчик 51 и на вход блока 6 сравнения из блока 2 хранения входных векторов по очереди подаются, начиная с m-ro, входные разметочные векторы / и анализируются набором 41 компараторов на принадлежность их вектору текущей разметки (в данном случае с начальной) ть-/ е Шо .Если это имеет место, то с помощью элемента ИЛИ A2.V и элемента И 43, RS-триггера 45, элемента И 46.V и элемента НЕ 47.V формируется сигнал включения соответствующей модели вершины t;, и RS-триггер 36,vустанавливается соответственно в 1, и таким образом счетчик 33.v переводится в режим Счет. Одновременно в течение дли тельности фазового импульса ГПИ 48 блок 11 формирования дополнительного кода и блок 9 суммирования обеспечивают вычитаoj- - - е5 ние вектора /1 из вектора шо : то mo-fi . а элемент 12 обеспечивает запись нового значения вектора текущей разметки в блок 3 текущей разметки. Таким образЪм, на первом цикле работы устройства оказываются запущенными счетчики сначала 33.2. а затем. 33.1, соответствующие переходам t2 и ti. После проверки® // вектор текущей разметки имеет вид 5 О О 1 е 1 000 О 01 .После проверки вектора ft Тпо 4 О О 1 / 2 000 О 01 ез После проверки векторов /и и// изменений вектора текущей разметки не происходит.V Блок 4 моделей вершин работает следующим образом. При занесении топологии графа в регистре 32. V и счетчике устанавливается время At, т.е. устанавливается число NQ. После перевода в режим Счет счетчик 33. V функционируете режиме вычитания и его содержимое уменьшается каждый раз на Г по приходу импульса Ф2 ГГИ7 , Кроме того, по приходу импульса Ф2 начинает функционировать узел 57 управления, по зволяющий последовательно в течение одного импульса Ф 2 подавать на вход блока 9 суммирования из блока хранения выходных векторов 10 значения выходных разметочных векторов°/Г в случае поступления из блока 4 моделей через блок 13 фиксации сигналов окончания моделирования переходов t. (ло совпадению Л на входах элементов И 40.). Сигнал окончания моделирования переходов tj Формируется на первых выходах счетчиков 33.V, когда все их разряды устанавливаются в О, и по этому сигналу в счетчики 33.V снова заносятся значения Д1;)из регистров 32. V. Таким образом, в рассматриваемом примере после запуска на первом цикле работы устройства переходов ti и t2 в течение 10 циклов не происходит изменение вектора текущей разметки пь (для ts и t4 условия запуска не возникли, а ti и t2 уже запущены и на элементах 14 46.V сигналы запуска переходов не формируются, так как на третьи входы через элементы НЕ 47 с выходов RS-триггеров 36. v поступают запрещаю щие сигналы). По приходу десятого импульса Ф2 обнуляется счетчик 33.1, и содержимое узла хранения вь1ходных векторов 5.V в блоке 9 суммирования прибавляетсяк содержимому блока; 3 текущей разметки: О 01 / О 1 О О 1 01 и новое значение Шо заносится в блок 3 текущей разметки благодаря поступлению сигнала окончания моделирований перехода ti через управляющий элемент 12 на пятый ВХОД блока 3 текущей разметки. По приходу 11-го импульса Ф 1 снова запускается переход ti и, следовательно, то tno-fi « (0,1,0,1). По приходу 15-го импуя ьса Ф2 оканчивается моделирование 12:Тт1о moVV (,), по приходу 20-го импульса Ф2 оканчивается моделирование ti: (0,2,3,1) , после чего по приходу 21-го Ф 1 запускается ta: tif 023 1 fi 02 1 О - ttZ-l.v л о гпо 0021 и т.д. Таким образом, устройство для моделирования графов Петри позволяет моделировать оценочные сети Петри, описывающие параллельные процессы. Параллельность

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

Формул а и 3 о бретени я Устройство для моделирования графов Петри, содержащее блок хранения входных векторов, блок сравнения, блок моделей вершин, блок хранения выходных векторов, блок суммирования, блок текущий разметки, блок индикации, генератор тактовых импульсов и блок ввода, причем информационный выход блока ввода подключен к информационному входу блока хранения входных векторов, к первому информационному входу блока текущей разметки, к информационным входам блока моделей вершин и блока хранения выходных векторов, первый управляющий выход блока ввода подключен к первым управляющим входам блока хранения выходных векторов,блока моделей вершин, блока текущей разметки и блока хранения входных векторов, информационный выход которого подключен к первому информационному входу блока сравнения, второй информационный вход которого подключен к первому информационному выходу блока текущей разметки, V-й выход признака Не меньше (V 1,2,..., М, где М - количество вершин-переходов в графе Петри) подключен к V-му входу опроса блока моделей вершин, V-й выход признака моделирования первой группы которого Подключен к V-му входу опроса первой группы блока сравнения, тактовый вход блока моделей вершин подключена первому выходу генератора тактовых импульсов, второй управляющий выход блр, ввода - к второму управляющему входу ёлока моделей вершин, третий управляющий выход к второму управляющему входу блока текущей разметки, второй информационный выход которого подключен к информационному входу блока индикации, информационный выход блока хранения выходных векторов подключен к входу первого слагаемого блока суммирования, первый инфор-. мацмонный выход блока текущей разметки подключен к входу Btoporo слагаемого блока суммирования, выход которого подключен к второму информационному входу блока текущей разметки, четвертый, и пятый управляющие выходы блока ввода подключены к второму и третьему управляющим

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

5 вания оценочных графов Петри, в него введены блок фиксации, блок формирования дополнительного кода, блок анализа и блок просмотра входных векторов, причем первый информационный выход блока ввода

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

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

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

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

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

Фиг

Ю

fm) {nutl ) Й)Т1Пт г; f)

Фи5.9

А