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

ОПИСАНИЕ ИЗОБРЕТЕНИ К АВТОРСКОМУ СВ во СССР 1980. СССР О, 1984. ДЕЛИРОВАНИЯя к вычис к устрой сп стности х Петри 1 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПОДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(71) Институт проблем моделировав энергетике АН УССР(54),УСТРОСТВО ДЛЯ МОГРАФОВ ПЕТРИ(57) Изобретение относитслительной технике, точнеествам для обработки информациициального назначения, в чадля решения задач на графа 801432550 А 1 и может быть применено в различных отраслях промышленности для отладки алгоритмов моделирования параллельных процессов. ель изобретения - расширение функциональных воэможностей за счет моделирования графов Петри, в которых временные задержки ставятся в соответствие вершинам мест, а переходы выполняются мгновенно, В устройство, содержащее регистры задания входных 2 и выходных 3 векторов и текущей разметки 4, блок 5 срав нения входных векторов, блок 6 вычисления последующей разметки и генератор 12 тактовых импульсов, дополнительно введены элемент И 9, элемент ИЛИ 8, блок 11 имитации зарезервированных меток и блок 10 инициации вершин мест. 9 ил.3432550 оставител ехред А.Кр Гречук Юрковецкая Редут орФ рректор Л. Пилипеик ПодписноСР Госуделам 5 скв оизво твенно-полиграфическое предприятие, г, Ужгород, у оектн Заказ 5443/43 ВНИИП по 113035, аж 704рственного комитета зобретений н открыти Ж, Раушская наб., 1432550Изобретение относится к вычислительной технике, к устройствам для обработки информации специального назначения, в частности для решения задач на графах Петри, и может быть5 применено в различных отраслях промьппленности для отладки алгоритмов моделирования параллельных процессов.Целью изобретения является расширение функциональных возможностей устройства за счет моделирования граов Петри, в которых временные заержки ставятся в соответствие вершиам мест, а переходы срабатывают мгно"15 енно.На фиг. 1 представлена функциональая схема устройства; на Фиг.2 - схеа блока ввода; на Фиг. 3 - схема лока регистров задания входных векоров; на фиг. 4 - схема регистра , адания текущей разметки; на Фиг.5 - схемы блока сравнения входных векторов и блока вычисления последующей разметки; на Фиг. 6 - схемы блока 25 индикации вершин мест и блока имитации зарезервированных меток; на Фиг. 7- Схема счетчика, входящего в состав узлов блока имитации зарезервированвых меток на фиг. 8 - иллюстратив- .- 30 ный пример моделируемого графа Петри; на фиг, 9 - таблица подготовки исходных данных для решения задачи на устройстве.Устройство (фиг. 1) содержит блок 1 ввода, блок 2 регистров задания входных векторов, блок 3 регистров задания выходных векторов, регистр 4 задания текущей разметки, 4 лок 5 сравнения входных векторов, блок 6 вычисления последующей размет 40 ки, блок 7 индикации установившихся меток, элемент ИЛИ 8, элемент И 9, блок 10 инициации вершин мест, блок 11 имитации зарезервированных меток, генератор 12 тактовых импульсов и блок 45 13 индикации зарезервированных меток.Блок 1 ввода предназначен для ввода в устройство топологии моделируемого графи Петри, т.е. входных и Выходных разметочных векторов, начальной разметки вершин, длительнос ей резервирования меток в вершинах мест. Блок 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-18.3, группу тумблеров 19, переключатель 20 и триггер 21. Блок 2 регистров задания входных векторов представляет собой группу регистров (Фиг. 3). Каждый регистр блока 2 содержит группу элементов БЕ 22, элемент И 23 и группу триггеров 24.Блок 3 регистров задания выходньсквекторов пр едс тавляет собой группурегистров.Регистр 4 задания текущей разметки 5(фиг. 4) содержит группу элементовИЛИ 25, группу элементов НЕ 26, элемент И 27, элемент ИЛИ 28 и группутриггеров 29.Блок 5 сравнения входных векторов 10(фиг. 5) состоит из группы узлов сравнения, каждый из которых содержитгруппу элементов И 30, элемент ИЛИ-НЕ3 1, группу элементов И 32 и группуэлементов ИЛИ 33. 15Блок 6 вычисления последующей разметки содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ.Блок 10 инициации вершин мест(фиг. 6) содержит группу элементов 2 ОИ 34 и группу элементов ИЛИ 35.Блок 11 имитации зарезервированных меток состоит из группы узловимитации, каждый из которых содержитэлемент И 36, регистр 37 и счетчик 38,5содержащий группу элементов И-НЕ 39,группу триггеров 40, группу элементов И-ИЛИ 41, триггер 42 и элементИ 43.Устройство работает следующим образом.После включения питания переключателем 20 триггер 21 устанавливаетсяв состояние "1", и тем самым обеспечивается режим ввода исходных данныхдпя решения задачи по моделированиюсоставленного графа Петри. Данные(входные разметочные векторы, выходные разметочные векторы, начальнаяразметка графа Петри, длительности 40резервирования меток в вершинах мест)набираемые на группе тумблеров 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" - сигнал разрешения изменения содержимого регистра 4задания текущей разметки, поступающий на вход элемента И 9. Одновременно "1" с выходов признаков сравнения блока 5 поступают на входы бло 1 а 10 инициации вершин мест, далеена входы элементов И 34 групп и разрешают подачу на входы элементовИЛИ 35 значений векторов, соответствующие разряды которых поданы на входы элементов И 34. На элементах ИЛИ 35происходит поразрядное сложение отобранных векторов, что позволяет выработать сигналы инициации вершин мест,в которые попадут зарезервированныеметки после срабатывания переходов,отобранных в блоке 5 сравнения входных векторов,В результате на соответствующихвыходах признаков инициации блока 10появляются "1", поступающие на входыэлементов И 36, С приходом сигнала"Фаза 1" ГТИ 12 на входы элементовИ 36 сигналы признаков инициации пе50 5 14325 реводят соответствующие счетчики 38 в режим "Счет". Одновременно приход сигнала "Фаза 1" на вход элемента И 9 определяет прохождение сигнала разрешения измекения содержимого5 регистра 4 задания текущей разметки на соответствующий вход синхронизации регистра 4, и значение вектора текущей разметки заносится в регистр 4, 1 ОПо приходу сигнала "Фаза 2" уменьшаетсяна единицу содержимое каждого из счетчиков 38. Далее работа устройства повторяется без изменения значения текущей разметки, так как нет 15 переходов, для которых бы выполнялось условие запуска. По приходу третьего ; сигнала "Фаза 2" ГТИ 12 содержимое соответствующего счетчика 38 обнуляется, ка. ецио первом выходе появляети ц,ся 1 , разрешающая перезапись содержимого соответствующего регистра 37 в счетчик 38, а также устанавливающая соответствующий триггер 29 регистра 4 задания текущей разметки в 25 состояние "1", имитируя таким образом процесс перехода метки из зарезервированного в установившееся состояние, в результате чего возникают условия для имитации запуска перехо- ЗО да по приходу очередного сигнала "Фаза 1" ГТИ 12. Далее работа устройства повторяется по описанному алгоритму. Формула изобретения35 Устройство дпя моделирования граФов Петри, содержащее блок регистров задания входных векторов, блок регистров задания выходных векторов, генератор тактовых импульсов, регистр задания текущей разметки, блок сравнения входных векторов, блок вычисления последующей разметки, первые45 информационные входы которого соединены с информационными выходами блока сравнения входных векторов, группауправляющих входов которого . соединена соответственно с группой инверсных информационных выходов регистразадания текущей разметки, информационные входы и прямые информационные выходы которого соединены с информационными выходами и вторыми информационными входами блока, вычисления последующей разметки соответственно, о тл и ч а ю щ е е с я тем, что, сцелью расширения Функциональных возможностей устройства за счет моделирования графов Петри, в которых временные задержки ставятся в соответствие вершинам мест а переходы срабатывают мгновенно, в него введены элемент И, элемент ИЛИ, блок имитациизарезервированных меток, блок инициации вершинмест, информационные входыкоторого соединены с соответствующими информационными выходами регистразадания выходных меток, а управляющиевходы группы соединены с соответствующими входами элемекта ИЛИ и соответствующими управляющими выходами группы блока сравнения входных векторов,информационные входы которого соединены с соответствующими информационными выходами регистра задания входных векторов, первый и второй входыгенератора тактовых импульсов соединены соответственно с первым и вторымвходами синхронизации блока имитациизарезервированных меток, информационные входы которого соединены с соответствующими информационными выходамиблока инициации вершин мест, а управляющие выходы соединены с соответствующими управляющими входами регистразадания текущей разметки, вход записикоторого соединен с выходом элемента И, первый вход которого соединенс вторым выходом генератора тактовыхимпульсов, а второй вход соединен свыходом элемента ИЛИ.