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

I

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

Цель изобретения - повьппение точности и быстродействия моделировани параллельных процессов.

На фиг.1 представлена схема устройства; на фиг.2 и 3 - пример моде :лируемой сети Петри. ; Устройство состоит из двух групп I и 2 регистров памяти, коммутатора 3, блока 4 памяти, элемента ИЛИ 5, генератора 6 тактовых импульсов, блка 7 индикации, двух групп блоков 8 и 9 сравнения, блока 10 элементов И блока 11 элементов ИЛИ-НЕ, элементо ИЛИ 12 и 13, элементов И 14 и 15, блока 16 задания временных параметров, блока 17 моделей вершин, состоящего из регистра 18, счетчика 19 и элемента И 20.

Особенностью графов Петри является наличие двух типов вершин: перехдов t-j и мест Р , а также наличие мток, которые показывают, какие вершины при.обходе графа устройство моделирует в данный момент времени.

Метки располагаются в вершинах мест Pg (фиг.2) И моделируют fe ди- ;намике окончание реальных действий в соответствии с заданным алгоритмо

представленным графом Петри. I

Местонахождение меток в графе Пери отображается вектором разметки тТ (О, 1,0, 1, J, О, О, О, 1,0,

( V - 9

1, О, О, 1, 1, ,Г . Цифра О - на первом месте обозначает, что первое место Р, не содержит метку, на втором указьшает, что во втором мес те Pj находится метка. При составлении графа Петри устанавливается ее топология и начальная разметка т. Каждая вершина перехода t моделирует время вьшолнения какого-то действия в процессе. Говорят, что переход t;j срабатывает, если во всех метах Р

L, дуги от которых направлены находятся метки. Так, например, переходы t и

-9

t могут сработать.

В период t входят две дуги от мест PJ и Р„, в которых находятся метки. Это является условием начала моделирования действия а, которое характеризу

ется временем ut.B момент начала выполнения действия a,j метки из мест Р и PJ, убираются и через время ut в места, к которым направлены дуги от t.

(Р, и ) , записьшаются. Каждый переход t;} характеризуется частичными входным и выходным разметочны

ми векторами . Векторы записываются в трансформированной форме.В векторе e2rj (1,1) 1 на первом месте говорит о том, что в вершине Р находится метка. При составлении частичных векторов предварительно расстанавливаются по возрастанию индексы мест вер

шин. Так для е2п;. расстановка соответствующих ему мест Р , Р,, , а P-J №

На фиг.З представлен пример моделируемого графа Петри для примера моделирования управления поездами метрополитена. Три поезда непрерьшно едут по кольцу, останавливаясь на каждой из восьми станций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что приводит к их столкновению. Вершины мест Р,- Pj моделируют станции, а наличие меток в Рр (1 ё 8) моделирует наличие

5

0

г

0

5

поездов на станциях . Наличие меток в местах q (9 & q fr 16) моделирует наличие зеленого света для соответствующих поездов. Каждый из переходов t(l - i 8) моделирует время &t, включающее переезд поезда с одной станции на другую и остановку на последующей станции.

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

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

В первую I и вторую 2 группу регистров памяти записьшается топология моделируемого графа Петри. Для этого прежде всего составляется таблица топологии (фиг. 2).. В таблицу заносятся все переходы t; сети Петри, причем каждой вершине перехода t; соответствует входной ei 7 и выходной ai-jj разметочные векторы. Так, например.

переходу t. соответствует el7

i-iv- y 9 . f-vjx iD I .-i.DJ C.l CI

(1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0)

313579724

и alti (0,I,0,0,0,0,0,0,1,0,0,0,0,ритмом, реализуемым в построенной ce- 0,0,0) . В частичных разметочных век-ти Петри. При окончании срабатьшания торах 1 стоит в том столбце ,перехода t на всех выходах счетчика вершина места Р: (1 - - 16) которо- j.19.i устанавливаются. О и формирует- го содержит метку. Входной разметоч-ся сигнал окончания моделирования верный вектор elTj показьшает, что емушин tj(a;). По обратной связи этот соответствует наличие меток в местахсигнал разрешает запись содержимого Р, и Р при моделирований данной се-регистра 18.1 в счетчик 19.1 и под- ти Петри. В первую группу 1 регистров юготавливает таким образом 1-ю модель памяти записьшается множество входныхвершины перехода к следующему этапу разметочных векторов е. ,e2rj ,моделирования. Одновременно с этим s° вторую группу 2 ре-во второй группе блоков 9 сравнения гистров памяти - множество выходныхв 9.1 выбирается соответствующий вы- разметочных векторов ajj в.г , 15ходной разметочный вектор aiij-, кото- a2-j,. .. , В блок 4 памяти заносит-рый через блок 10 элементов ИЛИ и ся начальная разметка m сети Петри.коммутатор 3 реализует прибавление В блок задания временных параметровair к вектору текущей разметки

записываются времена моделирования о) . -(О , т . % .т

..... „ . fm (m m + I air). Новое значеut; e u для каждой вершины перехода. 20 ° ° ;ТГ

При моделировании сетей Петри в ние вектора текущей разметки записы- момент начала работы системы в пер- вается в блок 4 памяти. Вычитание вой группе блоков 8 сравнения (фиг.1) векторов ei и прибавление векторов одновременно опрашивается возможность сопровождается на блоке 7 ин- срабатьшания всех m переходов tj , из 25 дикации удалением меток из вершин которых построен исследуемый граф. мест , входящих в t и появлением При этом в каждом блоке 8.1 опраши- меток в местах Р, дуги к которым вается выполнение условия принадлеж- направлены от t,.

ности . Если хотя бы для одно- Таким образом, предлагаемое уст- го перехода t; имеет место eiTjEr , 30 ройство для моделирования графов 1-й управляющий сигнал поступает на Петри позволяет моделировать различ- соответствующий вход блока моделей ные сети Петри, реализующие парал- вершин и включает соответствующую лельные алгоритмы, и описьшаемые ими 1-ю модель вершины перехода tj . Начи- параллельные процессы. Параллельность нается срабатывание перехода t; и мо- 35 моделирования различных операций aj- делирование соответствующей переходу и их последовательностей реализует- t; операции а|, характеризуемой дли- ся в устройстве для моделирования тельностью модельного времени ut;. графов путем одновременного срабаты- Срабатьшание перехода t; имитируется вания требуемого числа переходов t. счетчиком 19.1, работающим в режиме 40 При этом одновременность срабатыва- вычитания. Одновременно с формирова- ния не противоречит началу срабаты- нием 1-го управляющего сигнала моде- вания нескольких перекодов t,..., лирования в элементах ИЛИ 13 и И 15 .к ° время моделирования опера- формируется сигнал установки и через ций ,. . . ,а (5-4,).,соответствующих за- коммутатор 3 в блоке 4 памяти уста- 45 пущенным переходом t,... ,t Q- . На навливается следующее значение век- примере (фиг.3) показана возможность тора текущей разметки. Вектор после- моделирования времени движения поез- дующей разметки In формируется в дов в метрополитене, двигающихся од- блоке 11 элементов ИЛИ-НЕ путем вы- новременно и в основном независимо, читания всех входных разметочных век- 50 т.е. моделировать параллельные про-, торов eijjj, для которых выполнено ус- цессы управления. ловие ,из вектора начальной

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

разметки га т -г- ei-. Вычитание. - ..суммы входных разметочных векторов 55 Устройство для моделирования граm .. фов Петри, содержащее два регистра

ei. обеспечивает исключение пов- памяти, коммутатор, блок памяти, перторного моделирования вершины t;, не вый элемент РШИ, генератор тактовых предусмотренного параллельным алго- импульсов и блок индикации, о т л ичающееся тем, что, с целью повьшения точности, в него введены первая и вторая группы блоков сравнения, блок элементов ИЛИ, блок элементов ИЛИ-НЕ, два элемента ИЛИ, два элемента И, блок задания временных параметров и блок моделей вершин, причем каждая модель вершины содержит регистр, счетчик и элемент И, первый выход генератора тактовых импульсов соединен с первыми входами первого и второго элементов И, с первыми входами элементов И моделей вершин и входами синхронизации счетчиков моделей вершин, выходы счетчиков моделей вершин соединены со своими входами перезаписи и с первыми входами одноименных блоков сравнения второй группы, выходы которых подключены к входам первого элемента ИЛИ, выход которого соединен с вторым вхо- дом первого элемента И, выход которого подключен к первому входу второго элемента ИЛИ и первому управля- ющему входу коммутатора, выходы кото- iporo соединены с первой группой ин- формационных входов блока памяти, выходы которого подключены к входам блока индикации и первым входам блоков сравнения первой группы, вторые входы которых соединены с соответст- вздащими выходами первого регистра

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

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

Риг. 1

(PU2,2

Изобретение относится к цифровой вычислительной технике, а именно к устройствам для обработки информации специального назначения, в частности для решения задач на сетях Петри, и может быть применено в различ-. ных отраслях промышленности для моделирования параллельных процессов. Целью изобретения является повьшение точности. Для зтого в устройство введены группы блоков сравнения, блок злементов ИЛИ, блок элементов ИЛИ-НЕ, два элемента ИЛИ, два элемента И, блок задания временных параметров и блок моделей вершин, причем каждая модель вершины содержит регистр,счетчик и элемент И. Данное устройство позволяет моделировать различные сети Петри, реализующие параллельные алгоритмы и описьшаемые ими параллельные процессы. Параллельность моделирования различных операций и их последовательностей реализуется в устройстве путем одновременного срабатывания требуемого числа переходов. 3 ил. i (Л

РЗ

.0

Л)

сриг.З

Составитель И.Загорбинина Редактор Н.Бобкова Техред Л.Сердюкова Корректор Л. Пилипенко

Заказ 6000/50 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д,4/5

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