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

 

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

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

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

РЕСПУБЛИК (51)4 С 06 F

ICE.lHt? iv g

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

ИЗМА-, д„:, „

I — н ме

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4219160/24-24 (22) 03.04.87 (46) 23.10.88. Бюл. Ф 39 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев, В.В. Кузьмук, Е.Б. Лисицын и В.А. Шумов (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Р 879594, кл. С 06 F 15/20ъ 1980 °

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

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

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

В устройство, содержащее регистры задания входных 2 и выходных 3 векторов и текущей разметки 4, блок 5 сравнения входных векторов, блок 6 вычисления последующей разметки и генератор 12 тактовых импульсов, дополни с тельно введены элемент И 9, элемент р

ИЛИ 8, блок 11 имитации зарезервированных меток и блок 10 инициации вер1432550

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

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

На фиг. 1 представлена функциональая схема устройства; на фиг.2 — схеа блока ввода; на фиг, 3 .- схема лока регистров задания входных векоров, на фиг. 4 — схема регистра, адания текущей разметки; на фиг.5— схемы блока сравнения входных векторов и блока вычисления последующей разметки, на фиг. 6 — схемы блока 25 индикации вершин мест и блока имита ции зарезервированных меток, на фиг.7Схема счетчика, входящего в состав

Узлов блока имитации зарезервирован1 вых меток„ на фиг. 8 — иллюстратив- - 30 алый пример моделируемого графа Петри; на фиг. 9 — таблица подготовки исходных данных для решения задачи на устройстве.

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

13 индикации зарезервированных меток.

Блок 1 ввода предназначен для ввода в устройство топологии моделируемого графи Петри, т.е. входных и

Выходных разметочных векторов, начальной разметки вершин, длительносf åé резервирования меток в вершинах мест. Блок 2 регистров задания входных векторов предназначен для хранения входных разметочных векторов для враждой вершины перехода, блок 3 регистров задания выходных векторов — для хранения выходных разметочных векторов для каждой вершины перехода, регистр 4 задания текущей разметки— для хранения текущей разметки вершин мест в моделируемом графе Петри, блок

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

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

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

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

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

Блок 1 ввода (фиг. 2) содержит группу тумблеров 14, группу переключателей 15, группу триггеров 16.1 и 16,2, дешифратор 17, группу дешифраторов 18. 1- t8.3, группу тумблеров

19, переключатель 20 и триггер 21.

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

HE 22, элемент И 23 и группу триггеров 24.

1432550

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

Регистр 4 задания текущей разметки 5 (фиг. 4) содержит группу элементов

ИЛИ 25, группу элементов НЕ 26, элемент И 27, элемент ИЛИ 28 и группу триггеров 29.

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

3 1, группу элементов И 32 и группу элементов ИЛИ 33. 15

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

Блок 10 инициации вершин мест (фиг. 6) содержит группу элементов 2р

И 34 и группу элементов ИЛИ 35.

Блок 11 имитации зарезервирован-! ных меток состоит из группы узлов имитации, каждый из которых содержит элемент И 36, регистр 37 и счетчик 38,?5 содержащий группу элементов И-НЕ 39, группу триггеров 40, группу элементов И-ИЛИ 41, триггер 42 и элемент

И 43.

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

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

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

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

Одновременно "1" с выходов признаков сравнения блока 5 сравнения входных векторов подаются на соответствующие входы элемента ИЛИ 8, на выходе которого формируется "1" — сигнал paspemeния изменения содержимого регистра 4 задания текущей разметки, поступающий на вход элемента И 9. Одновременно "1" с выходов признаков сравнения блока 5 поступают на входы блока 10 инициации вершин мест, далее на входы элементов И 34 групп и разрешают подачу на входы элементов

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

В результате на соответствующих выходах признаков инициации блока 10 появляются "1", поступающие на входы элементов И 36. С приходом сигнала

"Фаза 1" ГТИ 12 на входы элементов

И 36 сигналы признаков инициации пе50

5 14325 реводят соответствующие счетчики 38 в режим "Счет". Одновременно приход сигнала "Фаза 1" на вход элемента

И 9 определяет прохождение сигнала разрешения измекения содержимого

5 регистра 4 задания текущей разметки на соответствующий вход синхронизации регистра 4, и значение вектора текущей разметки заносится в регистр 4. 10 По приходу сигнала "Фаза 2" уменьшается на единицу содержимое каждого из счетчиков 38. Далее работа устройства повторяется без изменения значения текущей разметки, так как нет .переходов, для которых бы выполнялось условие запуска. По приходу третьего

; сигнала "Фаза 2" ГТИ 12 содержимое соответствующего счетчика 38 обнуляется, ка. его первом выходе появляетtt М ,ся 1, разрешающая перезапись содержимого соответствующего регистра 37

:в счетчик 38, а также устанавливающая соответствующий триггер 29 регистра 4 задания текущей разметки в 26 состояние "1", имитируя таким образом процесс перехода метки из зарезервированного в установившееся состояние, в результате чего возникают условия для имитации запуска перехо- gg да по приходу очередного сигнала

"Фаза 1" ГТИ 12. Далее работа устройства повторяется по описанному алгоритму.

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

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

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

1432550 1432550

3432550

1432550

1 43 2550

1432550

f 4325SO

ФР2. Ю

1432550. Фи, ф

Составитель О. Гречухина

Техред А.Кравчук Корректор Л. Пилипенко

РедМтор О. Юрковецкан

Заказ 5443/43

Тираж 704 Подписное

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

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

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