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

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2пример модулируемого графа Петри; на фиг. 3 - временная диаграмма работы блока синхронизации.

Устройство содержит блок 1 синхронизации, первую группу из М регистров 2, где М - количество вершин- переходов в графе Петри, вторую группу из М регистров 3, третью группу из М регистров 4, группу-из М блоков 5 поразрядного сравнения, первую группу кз М блоков элементов И 6, вторую группу из М блоков элементов И 7, третью группу из М блоков элементов И 8, первую группу из М счетчиков 9, вторую группу из М счетчиков 10,

Јъ 00 00 4 СП

со

.группу из М блоков ИСКЛЮЧАЮЩЕЕ ИЛИ 11 блок элементов НЕ 12, группу из М блоков 13 памяти, блоки элементов ИЛИ с первого по четвертый 14,...,17, блок элементов ИСКЛПЧАЮГ(ЕЕ ИЛИ 18, блок 19 логического сложения,первый- третий элементы ИЛИ 20-22, блок элементов И 23, первый и второй элементы И 24, 25, регистр 26, коммутатор 27, блок 28 переключателей, группу из М элементов 29 задержки и группу из М элементов ИЛИ 30.

Кроме того, на фиг. 1 цифровые обозначения имеют входы 31 задания времени исполнения вершин переходов, вход 32 задания начальной разметки устройства, вход 33 начальной установки устройства, вход 34 пуска устройства, пер вый тактовый выход 35 блока 1 синхронизации, второй тактовый вы-: ход 36 блока 1 синхронизации, входы 37 задания входных векторов К-вершин переходов, входы 38 задания типов дуг, входы 39 задания выходных разметочных векторов.

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

Вторая группа из М регистров 3 предназначена для хранения времен исполнителя верпшн переходов utK.

Третья группа из М регистров 4 предназначена для хранения векторов типов дуг для каждой вершины перехода t K.

Группа из М блоков 5 поразрядного сравнения предназначена для определения вершин переходов tk, у которых выполняются условия запуска.

Первая группа из М блоков элементов И 6 предназначена для отбора входных разметочных векторов переходов, у которых выполнены условия запуска.

Вторая группа из М блоков элемен тов И 7 предназначена для отбора векторов типов дуг, соответствующих переходам tK, для которых выполнено условие запуска.

Третья группа из М блоков элемен-- тов И 8 предназначена для отбора выходных разметочных векторов, соответ0

5

ствующих переходам t«, моделирование выполнения которых окончено.

Первая группа из М счетчиков 9 предназначена для моделирования исполнения вершин переходов.

Вторая группа из М счетчиков 10 предназначена для отсчета числа сра- батывания соответствующих переходов

tKГруппа М блоков ИСКЛЮЧАЮЩЕЕ ИЛИ 11 предназначена для исключения из входных разметочных векторов дуг разру- 5 тающего типа перед определением запускаемых переходов.

Блок элементов НЕ 12 предназначен для обеспечения функционирования регистра хранения текущей разметки без сигнала Установка О.

Группа из М блоков 13 памяти предназначена для хранения переменных значений выходных разметочных векторов переходов и позволяет моделировать циркуляцию раскрашенных меток.

Первый блок 14 элементов ИЛИ предназначен для формирования суммы входных разметочных векторов запускаемых переходов.

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

Третий блок 16 элементов ИЛИ предназначен для подачи нового значения вектора текущей разметки в регистр.

Четвертый блок 17 элементов ИЛИ предназначен для формирования суммы векторов типов дуг запускаемых переходов .

Блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 18 предназначен для вычисления нового .значения вектора текущей разметки после запуска переходов.

Блок 19 логического сложения предназначен для вычисления нового значения вектора текущей разметки после окончания выполнения переходов.

Первый элемент ИЛИ 20 предназначен для формирования признака разрешения 0 изменения значения вектора текущей разметки, если хотя бы для одного перехода Ск выполняется условие запуска .

Второй элемент ИЛИ 21 предназначен 5 для формирования признака разрешения изменения значения вектора текущей- разметки, если окончено моделирование хотя бы одного перехода С.

0

5

0

5

Элемент ИЛИ 22 предназначен для синхронизации занесения информации в регистр 26.

Третий блок элементов И 23 пред- назначен для обеспечения моделирования вершин мест аккумулирующего типа

Первый элемент И 24 предназначен для синхронизации признака разрешения изменения текущей разметки импульсом сигнала Фаза 1 блока 1 синхронизации.

Второй элемент И 25 предназначен для синхронизации признака разрешени изменения текущей разметки импульсом сигнала Фаза 2 блока 1 синхронизации.

Регистр 26 предназначен для имитации вектора текущей разметки в вер- шинах мест моделируемого графа Петри

Коммутатор 27 предназначен для попеременной подачи нового значения вектора текущей разметки на вход регистра 26.

Блок 28 переключателей предназначен для установки типов вершин мест (простые и аккумулирующие) моделируемого графа Петри.

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

Пусть требуется смоделировать систему, описываемую графом Петри (фиг. 2). Данные о топологии графа (входные разметочные вектора, наборы выходных разметочных векторов, вектора типов дуг, начальная разметка графа Петри, времена выполнения переходов) заносятся в соответствующие группы регистров и группу блоков па- мяти. После ввода таблицы топологии графа Петри с помощью блока 28 переключателей устанавливается тип вершин .мест. Если Ј переключатель блока 28 подключен к выходу блока элементов НЕ 12, то Ј -и разряд регистра 26 моделирует наличие меток в месте обычного типа, иначе - в месте аккумулирующего типа. После ввода исходных данных устройство пере- водится в режим моделирования графа Петри посредством воздействия на вход 34 пуска. Значения векторов типов дуг ju и входных разметочных векторове м из регистров 2 и 3 первой и третьей группы подаются на входы блоков группы ИСКЛЮЧАЮЩЕЕ ИЛИ 11 для исключения влияния разрушающих дуг на условия запуска перехода

Так для t{:e |u (1,0,0,0,0,0,0,0); для :е1(и, (0,1,0,0,0,0,0,0).

Далее а в (« подаются на входы блоков 5 поразрядного сравнения, куда также подается значение вектора текущей разметки для проверки выполнения условий запуска переходов. В результате будет разрешено начало моделирования только перехода С

Г

выхода второго блока 5 поразрядного сравнения подается на вход разрешения счета соответствующего счетчика 9 и переводит его в режим Счет, а

ег

JU

и

также, разрешает прохождение

IT через первую 6 и вторую 7 группы блоков И на входы соответственно блоков первого 14 и четвертого 17 элементов ИЛИ, где вычисляются 2Г № и с-04- ,,«-М- «гг «у1$-

X 14. В данном случае ZL | fU,Z Ц

dlp. В блоке элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 18 вычисляется новое значение вектора текущей разметки: т0 (0,0, 0,0,0,0,0,0), которое подается на первый информационный вход коммутатора. Одновременно сигнал с выхода блока 5 поступает на счетный вход соответствующего счетчика 10 и увеличивает его содержимое на 1, что приводит к подключению к выходу соответствующего блока 13, первого из наборов значений переменных выходных разметочных векторов. Этот же сигнал, проходя через элементы ИЛИ 20, И 24, ИЛИ 22 (по приходу импульса Ф 1 с блока 1 синхронизации)подключает первый информационный вход коммутатора 27 к его выходу и формирует сигнал разрешения изменения содержимого .регистра 26. Счетчики 9 работают следующим образом. После перевода в режим счет они начинают работать в режиме вычитания, причем счетными импульсами являются сигналы Ф2 блока 1. При установке во всех разрядах К-го счетчика значений О сигнал на его выходе переполнения через элемент 29 задержки и элемент ИЛИ 30 поступает на собственный вход признака записи и в счетчики снова заносится из регистра 3 второй группы длительность выполнения перехода. Одновременно сигнал с выхода признака переполнения счетчика 9 первой группы поступает на вход соответствующего блока 8 и разрешает прохождение значения0 и на вход блока 15, где формируется2 (СГ, которая подается далее на вход блока 19 логического сложения, где вычисляется новое значение m

подаваемое на второй информационный , вход коммутатора 27. Одновременно сигнал признака окончания моделирования перехода проходит через элементы ИЛИ 21, И 25, ИЛИ 22 и подключает второй информационный вход коммутатора 27 к его выходу, а также разрешаиэ М регистров, где М - количество вершин переходов в графе Петри, регистр, группу из М блоков поразрядного сравнения, группу из М блоков ИСКЛЮЧАЮЩЕЕ ИЛИ, группу из М элементов задержки, первую группу из М блоков элементов И, группу из М элементов ИЛИ, первую группу из М счетчи

Изобретение относится к вычислительной технике и может быть использовано для получения временных диаграмм функционирования систем, описываемых сетями Петри. Целью изобретения является расширение функциональных возможностей устройства за счет моделирования аппаратных графов (сетей) Петри с местами аккумулирующего типа, разрушающими дугами, дугами переменного веса и с метками, раскрашенными в числовые значения. Места аккумулирующего типа позволяют отразить в модели одновременно используемые в нескольких целях переменные, разрушающие дуги позволяют организовать удаление меток из мест аккумулирующего типа. Дуги переменного веса могут принимать при каждом срабатывании перехода, к которому они присоединены, значения "1" или "0", т.е. по окончании срабатывания перехода метка либо передается, либо не передается по этим дугам. Рскрашенным меткам ставятся в соответствие строки бит определенной длины, которые могут моделировать, например, последовательность микрокоманд. 3 ил.

ет перезапись содержимого регистра 26.10 к°в, три блока элементов ИЛИ, блок

Так, по приходу первого же импуль- элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок ло- са Фаза 2 блока 1 моделирование t,,

гического сложения, три элемента ИЛИ, два элемента И, коммутатор, блок синхронизации, блок элементов

будет окончено и установится разметка о (1,0,0,1,0,1,0,0), что позволит

в следующий момент модельного времени 15 НЕ, причем вход задания входного

по приходу Ф1 начать моделирование t и t,. По приходу 20-го с момента запуска t4 Ф2 моделирование t будет завершено. После запуска t4 и tt вычисляется значение т0 (0,0,0,0,0, 0,0,0). По окончании моделирования Ц Шр (0,0,0,1,0,0,0,1). По приходу 50-го после запуска t, Ф2 будет вычислено in„ (0,1,0,1,0,0,0,1). Далее устройство продолжает работать по описанному алгоритму.

Временные диаграммы работы устройства приведены на фиг. 3.

На временной диаграмме работы

вектора К-й вершины перехода устр ства (,..., М) подключен к инф мационному входу К-го регистра пе вой группы, выход которого подклю

20 к первому информационному входу К блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и к информационному входу К-го блок элементов И первой группы, выход которого пбдключен к К-му входу п

25 вого блока элементов ИЛИ, выход к торого подключен к первому информ ционному входу блока элементов ИС КЛЮЧАЮЩЕЕ ИЛИ, выход которого под ключен к первому информационному

устройства приняты следующие обозна- 30 ДУ коммутатора, выход К-го блока элечения: И 25 - уровень сигнала на выходе второго элемента И 25, ИЛИ 21 - уровень сигнала на выходе второго элемента ИЛИ 21, ИЛИ 30. К - уровень сигнала- на выходе К-го элемента группы из М элементов ИЛИ 30, Ст 9. К - значение сигнала на выходе К-го счетчика первой группы из М счетчиков 9, СЧ/ЗАПР 9.К режим работы К-го счетчика группы 9, ИЛИ 22 - уровень сигнала на выходе третьего элемента ИЛИ 22, И 24 - уровень сигнала на выходе первого элемента И 24, ИЛИ 20 - уровень сигнала на выходе первого элемента ИЛИ 20, БЛ.5.К - уровень сигнала на выходе К-го блока поразрядного сравнения группы 5, СТ 10.К, СТ 9,К - значения, содер жащиеся в счетчиках 10.K,9.K,RG26- содержимое регистра 26, Ф2 и Ф1 - уровни сигналов на втором и первом выходах блока 1 синхронизации.

На фиг. 3 .показаны запуск и пас- сивизация перехода tx (&tK - время выполнения перехода tK).

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

Устройство для моделирования графов Петри, содержащее две группы

элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок ло-

гического сложения, три элемента ИЛИ, два элемента И, коммутатор, блок синхронизации, блок элементов

вектора К-й вершины перехода устройства (,..., М) подключен к информационному входу К-го регистра первой группы, выход которого подключен

к первому информационному входу К-го блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и к информационному входу К-го блока элементов И первой группы, выход которого пбдключен к К-му входу первого блока элементов ИЛИ, выход которого подключен к первому информационному входу блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому информационному вхо5

0

5

0

5

ментов ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к первому информационному входу К-го блока поразрядного сравнения, выход признака неравенства нулю результата сравнения которого подключен к управляющему входу К-го блока элементов И первой группы, к входу разрешения счета К-го счетчика первой группы и к К-му входу первого элемента ИЛИ, выход которого подключен к первому входу первого элемента И, вход задания времени выполнения К-й вершины перехода устройства подключен к информационному входу К-го регистра второй группы, выход которого подключен к информационному входу К-го счетчика первой группы, выход признака переполнения которого подключен к входу К-го элемента группы задержки, выход которого подключен к первому входу К-го элемента ИЛИ группы, выход которого подключен к вхоцу признака записи того же счетчика группы, t

выход которого подключен к К-му входу второго элемента ИЛИ, выход которого подключен к первому входу второго элемента И, выход первого элемента И подключен к первому управляющему входу коммутатора и к первому входу третьего элемента ИЛИ, выход второго элемента И подключен к второму управляющему входу коммутатора и к второму входу третьего элемента ИЛИ, выход которого подключен к входу признака записи регистра, выход второго блока элементов ИЛИ подключен к первому информационному входу блока логического сложения, выход которого подключен к второму информационному входу коммутатора, вход задания начальной разметки устройства подключен к первому входу третьего блока элементов ИЛИ, выход которого подключен к входу блока элементов НЕ, выход регистра подключен к вторым информационным входам блоков элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и блоков логического сложения и к вторым информационным входам всех блоков поразрядного сложения группы, выход коммутатора подключен к второму входу третьего блока элементов ИЛИ, вход начальной установки устройства подключен к входам признаков записи всех регистров первой и второй группы, к вторым входам всех элементов ИЛИ группы, и к третьему входу третьего элемента ИЛИ, первый тактовый выход блока синхронизации подключен к второму входу первого элемента И, второй тактовый выход блока синхронизации подключен к второму входу второго элемента И и к первым суммирующим входам всех счетчиков первой группы, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет моделирования аппаратных графов Петри с местами аккумулирующего типа, разрушающими дугами, дугами переменного веса и с метками, раскрашенными в числовые значения, в него введены третья группа из М регистров, вторая и третья группы из М блоков элементов И, вторая группа из М счетчиков, группа из М блоков памяти, четвертый блок элементов ИЛИ, блок переключателей и блок элементов И, причем вход задания вектора типа

дуг, исходящих из К-й вершины перехода устройства, подключен к информационному входу К-го регистра третьей группы, выход которого подключен к второму входу К-го блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ группы и к информационному входу К-го блока элементов И второй группы, выход которого под0 ключей к К-му входу четвертого блока элементов ИЛИ, выход которого подключен к первому информационному входу блока переключателей, второй информационный вход которого соединен

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

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

0 тов И второй группы.

5

0

5

фиг. 1

В

Фив. 2

Фиг. 3