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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 050 4006715/ ОПИСАНИЕ ИЗОБРЕТЕ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ВТОРСИОМУ СВИДЕТЕЛЬС(46) 23.06.88. Бюл. У 23 (7) Институт проблем моделирования в энергетике АН УССР(53) 681,333(088.8)ф (56) Авторское свидетельство СССР 9 879594, кл. С 06 Г 15/20, 1980.Авторское свидетельство СССР В 1171803, кл. О 06 Р 15/20, 1983, (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ ПЕТРИ(57) Изобретение относится к вычислительной технике, может быть испол зовано для моделирования сетей Петри и позволяет повысить достоверностьрезультатов за счет обеспечения возможности изменения количества перехо"дов в сети, которые могут быть выполнены параллельными. С этой цельюв блок моделирования введены два преобразователя кодов и реверсивный счетчик, которые позволяют огранйчитьчисло запускаемых моделей вершинпереходов независимо от количествазаявок на моделирование. Таким образом устройство позволяет имитироватьвыполнение параллельных алгоритмовна вычислительных устройствах различной конфигурации. 6 ил.СоставительТехред М,дгщ Редакт Корректор И;Муск улл каз 3104/54 Тираж 704 ВИИИПИ Государств по делам изобр 113035, Москва, Жческое предприятие, г. Ужгород, у ектная,Производственно-полиг Подписноеного комитета СССРений и открытийРаущская наб., д, 4/5Изобретение относится к вычислиельной технике, может быть использоано для решения задач на графахетри и позволяет проводить отладку 5алгоритмов моделирования параллельщх процессов.Целью изобретения является расшиение функциональных возможностейстройства путем обеспечения возможости изменения количества вершинереходов, которые могут быть выолнены параллельно,На Фиг. 1 представлена функциоальная схема устройства; на фиг.2 - 5ункциональная схема блока сравненияходных векторов; на фиг. 3 - функцинальнаясхема блока сравнения выодных векторов; на фиг, 4 - функциоальная схема первого преобразователя 20ода; на Фиг. 5 - функциональнаяхема второго преобразователя кода;а Фиг. 6 - моделируемая сеть Петри,Устройство (фиг. 1) содержит блокпамяти текущей разметки, блок 2равнения входных векторов, блок 3авнения выходных векторов, блок 4ожения по модулю два, блок 5 логиеского сложения, блок 6 моделей верн, реверсивный счетчик 7, мульти- ЗОлексор 8, первый преобразователь 9ода, второй преобразователь 10 кода. Блок 2 сравнения входных векторов.1(Я=1ш, где ш - количество вер 1 пин переходов в,графе), каждый из которых содержит набор элементов И11,4,1-11.1.и ( где и - число вершинмест графа Петри), набор элементовК 12.1,1-1.2.1 .и, элемент ИЛИ 13, кроме того, в состав блока 2 входят набор из и ш-входовых элементов ИЛИ14.3. (3.=1и),. и-входовый элементИЛИ 15, двухвходовый элемент И 1 б.Блок 3 сравнения выходных векторов(Фиг, 3) содержит ш наборов из двух входовых элементов И 17,.1-17,4.и,набор из и ш-входовых элементов ИЛИ18.Х, ш-входовый элемент ИЛИ 19, эле 50мент И 20.. Блок 4 сложения по модулю два состоит из и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4.1.Блок 5 логического сложения содер 55жит и двухвходовых элементов ИЛИ5.1.Блок 6 моделей вершин содержит шмоделей 6,вершин, каждая из которых представляет собой счетчик, работающий в режиме вычитания, и регистр,хранящий число пересчета счетчика,Преобразователь 9 кода (фиг, 4)содержит элемент НЕ 21, элемент И-НЕ22, г-разрядный (2" =тп) счетчик 23,дешифратор 24, набор элементов ИЛИНЕ 25.1-25.т, ш-входовый элементИЛИ 26, набор из ш ВБ-триггеров27. д,Преобразователь 10 кода (фиг. 5)содержит набор из ш ВБ-триггеров28.1, набор из ш элементов ИЛИ-НЕ29.4, набор из ш НБ-триггеров 30,1,ш-входовый элемент ИЛИ 31, дешифратор32, счетчик 33, элемент НЕ 34,Устройство работает следующим образом.Пусть необходимо смоделироватьпараллельный алгоритм, описанный графом Петри (фиг. 6). Здесь, в частности, могут одновременно выполняться ветви алгоритма, описанные переходами С,Для загрузки топологии графа иначальной разметки составляется таблица топологии графа Петри (фиг, 6).Причем каждой вершине перехода Ссоответствуют входнойи выходнойразметочные векторы,М .еЗначения входных разметочных векторов переходов С 1 подаются на входынаборов элементов И 11,1 для сравнения со значением вектора текущей разметки, подаваемой в инверсном коде.Например, для перехода С 1ш 111 0000001 ш, О О О 1 1 1. 1 1 1е 1100000000Р000000000 В результате на выходе элемента ИЛИ 13,1 появляется "0", разрешающий запуск перехода С 1 на текущем цикле работы устройства. Аналогично разрешается запуск переходов Си С,"О" с выхода элемента ИЛИ 13. 1 подается на первый вход элемента ИЛИ-НЕ 25,4. По приходу сигнала Ф 1 и в случае наличия положительного числа свободных процессоров в реверсивном счетчике 7 (в данном случае в первомцикле работы устройства содержится какое-, либо начальное значение, большее нуля) на выходе элемента И-НЕ 22 появ-ляется логический "0", разрешающий работу дешифратора 24, который начиЗ 4050704 нает поочередно выдавать "0" на вто- типлексор 8 в блок рые входы элементов ИЛИ-НЕ 25,1, при- разметки. По спаду чем значение 4 зависит от двоичного ББ-триггеры 27. и кода подаваемого с выходов постоянно- ние логического чОФ5го работающего счетчика 23, По сов- окончанию первой ф падению логических "0" на входах работы устройства элементов ИЛИ-НЕ 25.4 на их выходах чике 7 содержится появляются логические "1", разрешаю-. ных процессоров, а щие начало имитации срабатывания пе значение вектора т реходов 1 на текущем цикле работы ш,:(0,0,0,0,0,0,0 устройства, устанавливающие в состо- Указанное верно яние "1" ВБ-триггеры 27, 1 и иниципервоначально зане ирующие через элемент ИЛИ 26 вычита- ных процессоров тр ние единицы из числа свободных про то после генерации цессоров, хранящихся в счетчике 7 ния запуска, напри (считается, что один из процессоров и 1реверсивный с загружается выполнением фрагментавается в "0", а на алгоритма, описанного переходом 1). И-НЕ 22 появляетсяЛогические "1" на выходах ББ-триг прещает работу деш геров 27. 4 запускают 1-е модели вер- зультате на элемен шин, кроме того, логические "1" пода- решающий сигнал за ются на вторые входы элементов И не формируется, и 12,4 и, таким образом, разрешают ток из входного ме прохождение входных разметочных век не проводится, а в торов ена входы элементов ИЛИ 14 сигнала ф 1 хранитс/для формирования суммарного входно- тора текущей разме го вектора, вычитаемого из вектора 0,0,0,0) и сигналРтекущей разметки на данном цикле ра- вершины 6,3 не фор боты устройства. В данном случае 30 Предположим, чт е 1 100000000 е 2 010000000 еЗр 001000000 фр 111 ОООООО шО О О О О 0 О 0 О веф 111000000С выходов элементов 14 значение р подается на первый вход блока 4 сложения по модулю два, на второй вход которого подаются значения разрядов вектора текущей разметки, и Происходит имитация удаления меток входных мест запускаемых переходови зш 111000000 Одновременно логические "1" с выходов ВБ-триггеров 27.4 подаются на входы элемента ИЛИ 15, на выходе которого формируется логическая "1", разрешающая изменение содержимого бло ка памяти текущей разметки, Эта "1" через элемент И 16 разрешает занесение нового значения вектора текущей разметки с выхода блока 4 через муль 1 памяти текущейимпульса Ф всериводятся в состояВ результате поазы первого циклав реверсивном счет 0" - нет свободв блоке 1 - новоеекущей разметки0 0)Рдля случая, когдасенное число свободи. Если. число два,сигналов разрешемер, переходов 1четчик 7 устанавливыходе элемента"1", которая заифратора 24, В рете ИЛИ-НЕ 25.3 разпуска перехода 1 змитация изъятия места перехода 1 Зблоке 1 по спадуя содержимое вектки ш=(0,0,1,0,запуска моделимируется.о в условиях задачи введены следующие продолжительности срабатывания переходов Д 1 - 10, д 1 - 25, д 1- 20 моментов модельного времени, Тогда в течение девяти циклов работы устройства какихлибо изменений не происходит за исключением того, что с приходом каждого импульса Ф 2 содержимое счетчиков в запущенных моделях вершинуменьшается на "1". Если на текущемцикле работы устройства число свобод-.ных процессоров равно нулю, то не работающий в результате этого дешифратор 24 не позволяет генерировать управ 45 ляющие сигналы разрешения запуска переходов, а если ни для одного из переходов 1 не выполняется условиер ею 1,", то не на одном из элементов ИЛИ 13, не формируется признакзапуска перехода на текущем цикле.По приходу десятого импульса Ф 2счетчик 6,1 обнуляется и на его выхо"де появляется логический 0 , ВБ 1триггер 27.1 приводится в состояние"1" а на его инверсном выходе появ"ляется "0".По приходу фронта импульса Ф 2 на вход элемента НЕ 34, на его выходепоявляется "0", подаваемый на строби706 5 0050 рующий вход дешифратора 32. Дешифра. тор 32 начинает выдавать поочередно в зависимости от двоичного кода в непрерывно работающем счетчике 33, логические "0" на свои -е выходы, с которых они подаются на вторые входыы элементов ИЛИ-НЕ 29.1. По совпа, дению нулей на входах элемента ИЛИ-НЕ 29.1 на его выходе появляется сиг нал уровня логической "1", устанавливающий триггер 30.1 в состояние и через элемент ИЛИ 31 инициирующий прибавление единицы к числу свободных процессоров в счетчике 7 (процес сор, занятый выполнением фрагмента алгоритма, представленного переходомосвободился). Логическая "1" с выхода триггера 30,1 поступает на первые входы элементов И 17. и по зволяет подачу вектора р на входы элементов ИЛИ 18, где формируется суммарный выходной вектор эфиз выходных разметочных векторов переходов Ср моделирование срабатывания 25 .которых оканчивается на данном цикле работы устройства, Так как в данном случае оканчивается только 1 , то Р = =(1)рОрОр 1 рОрОрОрОрО) , Далее Э"р подается в блок 5 логического З 0 сложения для сложения со значением вектора текущей разметки, Если срабатывают все три перехода 1 р Ср устройства аналогично оканчиваетсямоделирование перехода тз, после чего значение вектора текущей разметкив блоке 1 т,(ОрОрОр 1 рОр 1 рОрОрО)в счетчике 7 содержится число свободных процессоров два. В результате возникает воэможность запуска на 21 цикле работы устройства перехода 1.Если начальное число свободныхпроцессоров два, и вначале запущеныпереходы 1 и 1, то после окончаниямоделирования перехода С значениетекущей разметки ш "=(0,0, 1,1,0,0,0,0,0) , а число свободных процессоровЕодин, следовательно, на одиннадцатомцикле работы устройства запускаетсяпереход 1 . Далее устройство Функционирует аналогично,В случае начального числа свободных процессоров один производитсяимитация выполнения алгоритма на однопроцессорной системе.Таким образом, предлагаемое устройство позволяет имитировать выполнение параллельных алгоритмов, представляемых графами Петри, на вычислительных устройствах различной конфигурации. Формула изобретения Устройство для моделирования графов Петри, содержащее блок сравнения40 ш о 0 0 О О 0 О 0 О О ". ,у О О О0 О О 0 О ш 000100000 Кроме того, логическая "1" с выхода БЯ-триггера 30,1 подается на первый вход элемента ИЛИ 19, где формируется управляющий сигнал уровня логической "1", раэрешаюшей изменение вектора текущей разметки, который через элемент И 20 подается на второй , вход признака записи блока 1. В результате новое значение вектора текущей разметки И" с выхода блока 5 заносится в блок 1. По спаду импульса Ф 2 наборы ВЯ-триггеров 28 и 30 устанавливаются. в "О", В результате после спада десятого импульса Ф 2 в блоке памяти текущей разметки содержится значение вектора текущей разметки ш=(0 рОрОр 1 рОрОрОрОрО) , а в счетчйке 7 - число свободных процессоров один, Еще через десять циклов работы входных векторов, блок сравнения выходных векторов, блок сложения помодулю два, блок логического сложения,мультиплексор, блок памяти текущейразметки и блок моделей, причем -й информационный вход блока сравнения входных векторов (=1ш, где ш - количество вершин переходов в графе) является входом задания 11-го входного вектора графа Петри устройства,информационный выход блока сравнениявходных векторов подключен к первомувходу блока сложения по модулю два,выход которого подключен к первомуинформационному входу мультиплексора,-й информационный вход блока сравнения выходных векторов является входом задания 1-го выходного вектораграфа Петри устройства, информацион-ный выход блока сравнения выходных векторов подключен к первому входу1 блока логического сложения, выходкоторого подключен к второму информационному входу мультиплексора, выход которого подключен к информаци 1405070онному входу блока памяти текущейразметки, выход которого лодключенк (ш+1)-му информационному входублока сравнения входных векторов ик вторым входам блока сложения помодулю два и блока логического сложения, выход признака окончания операций сравнения блока сравнения входных векторов подключен к первому уп. 10равляющему входу мультиплексора и кпервому входу признака записи блокапамяти текущей разметки, выход признака окончания операции сравненияблока сравнения выходных векторов 15подключен к второму управляющему входу мультиплексора и к второму входупризнака записи блока памяти текущейразметки, установочный вход которогоявляется входом задания начальной 20разметки устройства, установочныйвход блока моделей является входомзадания параметров моделей устройства, тактовый вход блока сравнениявходных векторов является первым так бтовым входом устройства, тактовыйвход блока сравнения выходных векторов соединен с тактовым входом блокамоделей и является вторым тактовымвходом устройства, о т л и ч а ю - 30щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения возможности измерения количества вершин пере- .ходов, которые могут быть выполненыпараллельно, в него введены два преобразователя кода и реверсивный счетчик, установочный вход которого является входом задания количества параллельно выполняемых вершин переходов, причем 4-й выход признака равенства блока сравнения входных векторов подключен к 1-му разряду информационного входа первого преобразователя кода, тактовый выход которого подключен к вычитающему входуреверсивного счетчика, выход которого подключен к входу разрешения работыпервого преобразователя кода, 4-йразряд информационного. выхода которого подключен к 4-му входу синхронизации блока сравнения входных векторов и к 1-му входу пуска блока моделей,-й выход признака окончания моделирования которого подкаочен к 4 -муразряду информационного входа второгопреобразователя кода, тактовый выходкоторого подключен к суммирующемувходу реверсивного счетчика, первыйтактовый вход устройства подключенк первому тактовому входу первогопреобразователя кода, второй тактовый вход устройства подключен к первому тактовому входу второго преобразователя кода, третий тактовый входустройства подключен к вторым такто"вым входам первого и второго преобразователей кода, 4 -й разряд информационного выхода второго преобразова-,теля кода подключен к -му входу син-,хронизации блока сравнения выходныхвекторов.