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

t

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

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

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

Изобретение относится к вычислительной технике, точнее к устройствам для обработки информации специального назначения, в частности, для решения задач на графах Петри, и может быть применено в различных отраслях промьшшенности для отладки алгоритмов моделирования параллельных процессов. Цель изобретения -расширение функциональных возможностей за счет моделирования графов Петри, в которых временные задержки ставятся в соответствие вершинам мест, а переходы выполняются мгновенноо В устройство, содержащее регистры задания входных 2 и выходных 3 векторов и текущей разметки 4, блок 5 срав нения входных векторов, блок 6 вычисления последующей разметки и генератор 12 тактовых импульсов, дополнительно введены элемент И 9, элемент ИЛИ 8, блок 11 имитаоди зарезервированных меток и блок 10 инициации вершин мест. 9 ил. сл i4iii 00 to СП ел

1ам мест, а переходы срабатывают мгно-|5 да содержимого регистра 4 задания

зенно.

На фиг. 1 представлена функциональная схема устройства; на фиг.2 - схе- :4а блока ввода; на фиг 3 - схема 5лока регистров задания входнык век горов; на фиг 4 - схема регистра .задания текущей разметки; на фиг.5 - хемы блока сравнения входных векторов и блока вычисления последующей :|)азметки; на фиг. 6 - схемы блока |1ндикации вершин мест и блока ямита- зарезервированных меток; на фиг.7 (|:хема счетчика, входящего в состав блока имитации зарезервировантекущей разметки на индикационную панель, элемент ИЛИ 8 - для формирования сигнала разрешения изменения содержимого регистра 4 задания теку20 щей разметки, элемент И 9 - для синхронизации сигнала, вырабатьшаемого на элементе ИЛИ 8, сигналом Фаза 1 генератора 12 тактовых иьшульсов (ГТИ снимаемым с первого выхода (1) ГТИ.

25 Блок 10 инициации верщин мест вырабатывает сигналы, определяющие начало имитации наличия зарезервированных меток в вершинах мест, входящих в выходные векторы сработавших

к меток; на фиг. 8 - иллгостратив- J- зо верщин переходов.

|1Ый пример моделируемого графа Петри; 11 имитации зарезервированipa фиг. 9 - таблица подготовки исходйых данных для решения задачи на уст зойстве.

Устройство (фиг. 1) содержит блок 1 ввода, блок 2 регистров зада- 1|1ия входных векторов, блок 3 регистров задания выходных векторов, ре- истр 4 задания текущей разметки, $лок 5 сравнения входных векторов, блок 6 вычисления последующей разметки, блок 7 индикации установивщихся меток, элемент ИЛИ 8, элемент И 9, блок 10 инициации вершин мест, блок 11 имитации зарезервированных меток, ге™ нератор 12 тактовых импульсов и блок 13 индикации зарезервированных меток,

Блок 1 ввода предназначен для ввода в устройство топологии моделируемого графи Петри, т.е. входных и выходных разметочных векторов, начальной разметки вершин, дпительнос- {ей резервирования меток в вершинах мест. Блок 2 регистров задания входных векторов предназначен для хране- 1|1ия входных разметочных векторов для Каждой вершины перехода, блок 3 регист- ISOB задания выходных векторов - для хранения выходных разметочных эекто35

40

45

50

ных меток предназначен для имитации наличия в вершинах мест зарезервирова ных меток в течение промежутков времен поставленных в соответствие йершинам мест..

ГТИ 12 формирует управляющие сигналы Фаза 1 и Фаза 2 для тактиро вания устройства, причем последовательность этих сигналов является непересекающейся.

Блок 13 индика1щи зарезервированных меток предназначен для отражения на индикационной панели процессов имитации зарезервированных меток в вершинах мест в блоке 11.

Блок 1 ввода (фиг о 2) содержит группу тумблеров 14, группу переключателей 15, группу триггеров 16.1 и 16,2, дешифратор 17, группу дешифраторов 18.1-18.3, группу тумблеров 19, переключатель 20 и триггер 21.

Блок 2 регистров задания входных векторов пр едставляет собой группу 55 регистров (фиг. 3). Каждый регистр блока 2 содержит группу элементов НЕ 22, элемент И 23 н группу триггеров 24.

текущей разметки на индикационную панель, элемент ИЛИ 8 - для формирования сигнала разрешения изменения содержимого регистра 4 задания текущей разметки, элемент И 9 - для синхронизации сигнала, вырабатьшаемого на элементе ИЛИ 8, сигналом Фаза 1 генератора 12 тактовых иьшульсов (ГТИ), снимаемым с первого выхода (1) ГТИ.

Блок 10 инициации верщин мест вырабатывает сигналы, определяющие начало имитации наличия зарезервированных меток в вершинах мест, входящих в выходные векторы сработавших

верщин переходов.

5

0

5

0

ных меток предназначен для имитации наличия в вершинах мест зарезервирован-/ ных меток в течение промежутков времени, поставленных в соответствие йершинам мест..

ГТИ 12 формирует управляющие сигналы Фаза 1 и Фаза 2 для тактирования устройства, причем последовательность этих сигналов является не . пересекающейся.

Блок 13 индика1щи зарезервированных меток предназначен для отражения на индикационной панели процессов имитации зарезервированных меток в вершинах мест в блоке 11.

Блок 1 ввода (фиг о 2) содержит группу тумблеров 14, группу переключателей 15, группу триггеров 16.1 и 16,2, дешифратор 17, группу дешиф. раторов 18.1-18.3, группу тумблеров 19, переключатель 20 и триггер 21.

Блок 2 регистров задания входных векторов пр едставляет собой группу регистров (фиг. 3). Каждый регистр блока 2 содержит группу элементов НЕ 22, элемент И 23 н группу триггеров 24.

Блок 3 регистров задания выходных векторов представляет собой группу регистров.

Регистр 4 задания текущей разметки (фиг. 4) содержит группу элементов ИЛИ 25, группу элементов НЕ 26, элемент И 27, элемент ИЛИ 28 и группу триггеров 29.

Блок 5 сравнения входных векторов (фиг, 5) состоит из группы узлов сравнения, каждьй из которых содержит группу элементов И 30, элемент ШШ-НЕ 31, группу элементов И 32 и группу элементов ИЛИ 33,

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

Блок 10 инициации вершин мест (фиг, 6) содержит группу элементов И 34 и группу элементов ШШ 35,

Блок 11 имитации зарезервированных меток состоит из группы узлов имитации, каждый из которых содержит

элемент И 36, регистр 37 и счетчик 38,75 го вектора из прямого значения вектосодержащий группу элементов И-НЕ 39, группу триггеров 40, группу элементов И-ИЛИ 41, триггер 42 и элемент И 43,

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

После включения питания переключателем 20 триггер 21 устанавливаетс в состояние 1, и тем самым обеспечивается режим ввода исходных данных для решения задачи по моделированию составленного графа Петри, Данные (входные разметочные векторы, выходные разметочные векторы, начальная разметка графа Петри, длительности резервирования меток в вершинах мест набираемые на группе, тумблеров 19, заносятся в соответствующие блоки (блок 2 регистров задания входных векторов, блок 3 регистров задания выходных векторов, регистр 4 задания текущей разметки, блок 11 имитации зарезервированных меток) устройства, определяемые положением переключателей группы тумблеров 14, Конкретный регистр одного из этих блоков, в который заносится очередной компонент исходных данных задачи, определяется положением переключателей группы переключателей 15, После ввода исходных данных режим записи отключается, все тумблеры переводятся в разомкнутое положение.

Режим моделирования включается переводом переключателя ГТИ 12 в положение Пуск,

Инверсное значение вектора текущей разметки (начальное значение) и значения входных разметочных векторов подаются в блоки 5 сравнения входных разметочных векторов, где на элементах И 30 и ИЛИ-НЕ 31 происходит поразрядное сравнение векторов и на выходе элемента ИЛИ-НЕ 31, являющегося выходом признака сравнения блока 5, появляется 1, которая разрешает подачу значения через группу элементов И 32 на входы группы элементов ИЛИ 33, где вычисляется частичная сумма входных векторов запускаемых переходов, которая подается через выход значения суммы части входных векторов блока 5 на вход блока 6 вычисления последующей разметки, где на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ имитируется вычитание соответствующе0

5

0

5

0

5

ра текущей разметки, подаваемого на другой вход блока 6, Новое значение вектора разметки подается на вход регистра 4 задания текущей разметки. Одновременно 1 с выходов признаков сравнения блока 5 сравнения входных векторов подаются на соответствующие входы элемента ИЛИ 8, на выходе которого фopмIipyeтcя 1 - сигнал разрешения изменения содержимого регистра 4 задания текущей разметки, поступа- кхдий на вход элемента И 9, Одновременно 1 с выходов признаков сравнения блока 5 поступают на входы бло- кa 10 инициации вершин мест, далее на входы элементов И 34 групп и разрешают подачу на входы элементов ИЛИ 35 значений векторов, соответствующие разряды которых поданы на входы элементов И 34, На элементах ИЛИ 35 происходит поразрядное сложение отобранных векторов, что позволяет выработать сигналы инициации вершин мест, в которые попадут зарезервированные метки после срабатывания переходов, отобранных в блоке 5 сравнения входных векторов,

В результате на соответствующих выходах признаков инициации блока 10 появляются 1, поступающие на входы элементов И 36, С приходом сигнала Фаза 1 ГТИ 12 на входы элементов И 36 сигналы признаков инициации пареводят соответствующие счетчики 38 в режим Счет, Одновременно приход сигнала Фаза 1 на вход элемента И 9 определяет прохождение сигнала разрешения изменения содержимого регистра 4 задания текущей разметки на соответствующий вход синхронизации регистра 4, и значение вектора текущей разметки заносится в регистр 4 По приходу сигнала Фаза 2 уменьшается на единицу содержимое каждого из счетчиков 38, Далее работа устройства повторяется без изменения зна чения текущей разметки, так как нет :переходов, для которых бы выполнялос I условие запуска По приходу третьего I сигнала Фаза 2 ГТИ 12 содержимое : соответствующего счетчика 38 обнуля- ; ется, на eiro первом выходе появляет- ;ся 1, разрешающая перезапись содер- ;жимого соответствующего регистра 37 Гв счетчик 38, а также устанавлива- кнцая соответствующий триггер 29 ре- :гистра 4 задания текущей разметки в состояние 1, имитируя таким образом процесс перехода метки из зарезервированного в установившееся состояние, в результате чего возникают условия для имитации запуска перехода по приходу очередного сигнала Фаза 1 ГТИ 12 Далее работа устройства повторяется по описанному алгоритму.

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

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

0

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

5

0

5

0

5

Фи2.2

Фие.З

()

; ..;

7(2j

imт

//

2(2i

(2) (2)

(n} : (n)

(7) (

(2) (n+4) (дУ (

(

ffL H

27

(Г)

(f}

Ш.

8

5

0-(I/

(2) (2)

0-6

(1}

f.

TfeU

n

n

-ЧЕ

(f)

H

28

Фиа.

Фиг. 5

Фиг. 6

Физ.д