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

 

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

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

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

РЕСПУБЛИК

А1 (19) (11) (51) 4 G 06 F 15/20

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

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTVM

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ (2 I ) 3960366/24-24 (22) 02.!0.85 (46) 07,12.87. Вюл, !(45 (71) Институт проблем моделирования в энергетике АН УССР (72) В ° В.Васильев, В.В.Кузьмук, Е.Б.Лисицин и В.А.!Чумов (53) 681.3(088.8) (56) Авторское свидетельство СССР !

1- 879594, кл. G 06 F 15/20, 1981.

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

Ф 1171803, кл. G 06 F 15/20, 1983. (54) УСТРО(СТВО ДЛЯ МОДЕЛИРОВАНИЯ

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

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

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

1357972

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

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

На фиг.1 представлена схема устройства; на фиг.2 и 3 — пример моделируемой сети Петри.

Устройство состоит иэ двух групп

1 и 2 регистров памяти, коммутатора

3, блока 4 памяти, элемента ИЛИ 5, генератора 6 тактовых импульсов, блока 7 индикации, двух групп блоков 8 и 9 сравнения, блока 10 элементов ИЛИ/О блока 11 элементов ИЛИ-НЕ, элементов

ИЛИ 12 и 13, элементов И 14 и 15, блока 16 задания временных параметров, блока 17 моделей вершин, состоящего иэ регистра 18, счетчика 19 и элемента И 20, Особенностью графов Петри является наличие двух типов вершин: переходов t и мест Р, а также наличие меЭ ток, которые показывают, какие вершины при.обходе графа устройство моделирует в данный момент времени.

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

Местонахождение меток в графе Петри отображается вектором разметки 40 первом месте обозначает, что первое место P не содержит метку, "l" на втором указывает, что во втором месте Р находится метка. При составлении графа Петри устанавливается ее топология и начальная разметка m о

Каждая вершина перехода t моделирует время выполнения какого-то дейст50 вия в процессе. Говорят, что переход ty срабатывает, если во всех местах Р, дуги от которых направлены к находятся метки. Так, например, переходы и и t могут сработать.

В период входят две дуги от мест

Р и Р„, в которых находятся метки.

Зто является условием начала моделирования действия а, которое характериэуется временем И . В момент начала выполнения действия а метки из мест Р и

Рч убираются и через время !!t в места, к которым направлены дуги от (P и Р„ ), записываются. Каждый переход tq характеризуется частичными входным е и выходным разметочными векторами а1 . Векторы записываются

J4 в трансформированной форме. В векторе с „ е2-=(1, 1) "!" на первом месте говорит о том, что в вершине Р находится метка ° При составлении частичных векторов предварительно расстанавливаются по возрастанию индексы мест вершин. Так для е2 . расстановка соответствующих ему мест Р, Р<,, а для— а2 ц Р Рю

На фиг.3 представлен пример моделируемого графа Петри для примера моделирования управления поездами метрополитена. Три поезда непрерывно едут по кольцу, останавливаясь на каждой из восьми станций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что приводит к их столкновению. Вершины мест P, — Pl! моделируют станции, а наличие меток в Р (1 Я 8) моделирует наличие поездов на станциях Е . Наличие меток в местах q (9 c q c 16) моделирует наличие зеленого света для соответствующих поездов. Каждый из переходов

t (1 4 и 8) моделирует время t, включающее переезд поезда с одной станции на другую и остановку на последующей станции.

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

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

ai разметочные векторы. Так, например, переходу t, соответствует е!

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

1357972

Устройство для моделирования графов Петри, содержащее два регистра памяти, коммутатор, блок памяти, первый элемент ИЛИ, генератор тактовых импульсов и блок индикации, о т л ии al- =(0,1,0,0,0,0,0,0,1,0,0,0,0, 0,0,0) . В частичных разметочных векторах "1" стоит в том столбце 1 вершина места Р (1 1 16) которо5

ro содержит метку. Входной разметочный вектор el показывает что ему »

Э соответствует наличие меток в местах

Р, и Р, при моделировании данной сети Петри. В первую группу 1 регистров 1ð памяти записывается множество входных разметочных векторов е = 1 е1-,е2-,т, ...,еш, а во вторую группу F pervczpoo памяти — множество выходных разметочных векторов а = а1 Ц < )» «

15 а2 ...,,am»(. B блок 4 памяти заноситР»

« ся начальная разметка ш сети Петри. о

В блок задания временных параметров записываются времена моделирования

5t; Е Ь для каждой вершины перехода. 2р

При моделировании сетей Петри в момент начала работы системы в первой группе блоков 8 сравнения (фиг.l) одновременно опрашивается возможность срабатывания всех m переходов t, из 25

« которых построен исследуемый граф.

При этом в каждом блоке 8.i опрашивается выполнение условия принадлежности ei C m . Если хотя бы для одно «о го перехода t; имеет место ei E r, Зр

Р

i-й управляющий сигнал поступает на соответствующий вход блока моделей вершин и включает соответствующую

i-ю модель вершины перехода t . Начинается срабатывание перехода 1 и моделирование соответствующей переходу операции а;, характеризуемой длительностью модельного времени 6С;.

Срабатывание перехода t; имитируется счетчиком 19.i, работающим в режиме 4р вычитания. Одновременно с формированием i — ro управляющего сигнала моделирования в элементах ИЛИ 13 и И 15 формируется сигнал установки и через коммутатор 3 в блоке 4 памяти уста- 45 навливается следующее значение вектора текущей разметки. Вектор после-« (<1 дующей разметки m формируется в блоке 11 элементов ИЛИ-НЕ путем вычитания всех входных разметочных век- 50 торов ei, для которых выполнено ус1<» э ловие eiE тп0,из вектора начальной

— «(<)разметки тп =тп — z ei Вычитание

5 O Р суммы входных разметочных векторов ет. обеспечивает исключение пов; (7 торного моделирования вершины t; не предусмотренного параллельным алгоритмом, реализуемым в построенной сети Петри. При окончании срабатывания перехода на всех выходах счетчика

19.i устанавливаются "0" и формируется сигнал окончания моделирования вершин t;(a ). По обратной связи этот сигнал разрешает запись содержимого регистра 18.i в счетчик 19.i и подготавливает таким образом i-ю модель вершины перехода к следующему этапу моделирования. Одновременно с этим во второй группе блоков 9 сравнения в 9,i выбирается соответствующий выходной разметочный вектор а -, который через блок 10 элементов и коммутатор 3 реализует прибавление а1. — к вектору текущей разметки<

- (< - г1 -««1

««<

m (m =пт +, ai ). Новое значео о о . 1т< ! ние вектора текущей разметки записывается в блок 4 памяти. Вычитание векторов ei и прибавление векторов

P ат.-„7 сопровождается на блоке 7 индикации удалением меток иэ вершин мест P,,входящих в t. и появлением

«

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

Таким образом, предлагаемое устройство для моделирования графов

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

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

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

I357972 ч а ю щ е е с я тем, что, с целью повышения точности, в него введены первая и вторая группы блоков сравнения, блок элементов ИЛИ блок элеФ

5 ментов HJIH-HE, два элемента ИЛИ, два элемента И, блок задания временных параметров и блок моделей вершин, причем каждая модель вершины содержит регистр, счетчик и элемент И, первый выход генератора тактовых импульсов соединен с первыми входами первого и второго элементов И, с первыми входами элементов И моделей вершин и входами синхронизации счетчи- Е5 ков моделей вершин, выходы счетчиков моделей вершин соединены со своими входами перезаписи и с первыми входами одноименных блоков сравнения второй группы, выходы которых подклю- щ чены к входам первого элемента ИЛИ, выход которого соединен с вторым входом первого элемента И, выход которого подключен к первому входу второго элемента ИЛИ и первому управля- 25

1 ! ющему входу коммутатора, выходы которого соединены с первой группой инрмационных входов блока памяти, выходы которого подключены к входам блока индикации и первым входам бло- ЗО ков сравнения первой группы, вторые входы к0торых соединены с соответствующими выходами первого регистра памяти, выходы блоков сравнения первой группы подключены к входам третьего элемента ИЛИ, выход которого соединен с вторым входом второго элемента И, выход которого подключен к второму входу второго элемента HJIH. и второму управляющему входу коммутатора, выходы блоков сравнения первой и второй групп соединены с первыми группами входов блока элементов

ИЛИ-НЕ и блока элементов ИЛИ соответственно, выходы которых подключены к первой и второй группам информационных входов коммутатора, вход второго элемента ИЛИ соединен с входом управления записью блока памяти, вторая группа информационных выходов которого подключена к вторым группам входов блока элементов ИПИ-НЕ и блока элементов HJIH, выходы блока задания временных параметров соединены с информационными входами регистров моделей вершин, разрядные выходы которых подключены к информационным входам, кроме входов младших разряов, счетчиков одноименных моделей вершин, выходы блоков сравнения первой группы соединены с вторыми входами элементов И одноименных моделей вершин, выход элемента И в каждой модели вершины подключен к входу младmего разряда счетчика, 1357972! 357972

1 1 111

1 1 1

Составитель И.Загорбинина

Редактор Н.Бобкова Техред JI.Ñåðäþêoâà Корректор Л.Пилипенко

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

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

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

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