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

(я)5 6 06 Р 15/347, 15/ ТЕНТНОЕ ОСУДАРСТВЕННОЕ ЕДОМСТВО СССР ОСПАТЕНТ СССР) НИЕ ИЗОБРЕТЕНИ О ЕЛЬСТВ К АВТО У СВ 57 ной тех решейи Цель и нальнц ния ана дополн катнцх держки блок да гйстр р(56) Авторское свидетельство СССРМ 482749, кл. О 06 Р 15/347, 1972.Авторское свидетельство СССР1 Ф 1322312, кл, 6 06 Г 15347, 1986.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯСЕТЕЙ ПЕТРИ Изобретение относится к вычислительной технике, может быть использовано для решения линейных матричных уравнений и позволяет исследовать матричное представление. предикатно-переходных сетей Петри на. достижимость.Известно устройство для операций над матрицами; недостатком которого являетсъ узкий класс решаемых задач и ограниченность функциональных возможностей, заключающиеся в невозможности реализаций устройством алгоритма исследования сетей Петри на достижимость путем их матричного представления и решения линейных матричных уравнений.Наиболее близким по технической сущности к заявляемому изобретению является устройство для исследования сетей Петри, содержащее последовательно соединенные блок синхронизации, блок регистров, первый блок элементов сравнения, первйй регистр результатов сравнения, блок сравнения с нулем, выход которого является информационным выходом устройства, последовательно соединенные блок памяти матрицы входов, блок вычитания матриц,обретение относитсяк вычислитель- нике и может быть использовано для я линейных матричных уравнений, зобретения - расширение функциох возможностей за счет осуществлелиза на достижимость. В устройство ительно введены блок памяти предиконстант перехода, три элементз за, второй блок элементов сравнения, тчиков случайных чисел и второй реезультатов сравнения. 1 ил. блок памяти матрицы изменений, блок умноженйя матриц, блок сумматоров, а также блок памяти матрицывыходов, выход которого подключай ко второму входу блока вы- Я читания матриц, а вход признака чтения - к входу признака записи блока памяти матрицы изменений, ко второму вйходу блока а синхронизации и к входу признака чтения блока памяти матрицы входов, выход кбто-. (О рого подключен ко второму ийформацион- р ному входу первого блока элементов сравнения, вход опроса которого подключен к входу опроса блока вцчитания матриц и к третьему аыхощ блока синхронизации, вход пускв которсто явяявтся входам пуска 1 кв устройства, четвертый выход подключен к входу признака записи первого регистра результатов сравнения, йятый выход - к входу признака чтения блока памяти матрицы изменений, шестой и седьмой выходы - к входам опроса соответСктвенно блока умножения матриц и блока сумматоров, вход останова - к выходу блока сравнения с нулем, вход начальной установки - к входам начальной установки блока памяти матрицы изменений, первого регистра результатовсравнения и является входом начальной установки устройства, второй информационный вход и выход блока сумматоров подключены соответственно к выходу и к информационному входу блока регистров.Недостатком данного устройства является ограниченность функциональных воэможностей, заключающаяся в невозможности реализации устройством правил срабатывания переходов предикатно-переходных сетей Петри, что не позволяет исследоватьданный класс сетей Петри на достижи масть,Целью изобретения является расширение функциональных возможностей устройства за счет осуществления анализа предикатно-переходных сетей Петри на достижимость,Указанная цель достигается тем, что в устройство дополнительно введены последовательно соединенные первый, второй и третий элементы задержки, а также блок датчиков случайных чисел, а между первым регистром результатов сравнейия и блоком умножения матриц включенй последовательно соединенные блок памяти предикатных констант перехода, второй блок элементов сравненйя, второй регистр результатов сравнения, вход начальной установки которого подключен к входу начальной установки устройства, вход признака записи - к выходу третьего элемента задержки, вход которогоподключен к входу опроса второго блока элементов сравнения, второй информационный вход которого подключен к выходу блока датчиков случайных чиселвход опроса которого подключен ко входу признака чтения блока памяти предикатных констант перехода и к выходу первого элемента задержки, вход которого подключен к входу признака записи первого регистра результатов сравнения, выход которого подключен к адресному входу блока памяти предикатных констант перехода, а выход второго регистра результатов сравнения подключен ко второму информационному входу блока умножения матриц,Ка чертеже представлена функциональная схема устройства,Устройство для исследования сетей Петри содержит блок 1 памятй матрицы входов, блок 2 памяти матрицы выходов, блок 3 памяти матрицы изменений, блок 4 регистров, первый блок элементов сравнения, содержащий элементы сравнения 51-5 (где К - количество строк в исходных матрицах), первый регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства,вход 13 начальной установки, вход 14 пускаустройства, блок 15 памяти предикатных5 констант перехода, блок 16 датчиков случайных чисел, второй блок элементов сравне. ния, три элемеита 19-21 задержки.Устройство работает следующим образом10 В исходном состоянии схемы в блоке 1находится матрица входов Д, например1110Д001015 а в блоке 2 - матрица выходов Д, например1000Д - 02100001т,е. данная сеть Петри имеет четыре пози 20 ции и три перехода. Первоначальная маркировка находится в блоке 4 и имеет вид;. Каждому переходу сети йоставлен в соответствие одноместный предикат, истин 25 ность которого достигается выполнениемследующегбусловияф ,1). где) - номер перехода.) 1, к;- предикатная переменная - случайЗО ная величина, равномерно распределеннаяв интервале О, Ц;Л - предикатйая константа - постоян- .ная величина, поставленная в соответствиекаждому переходу, Я 60, 1).З 5 Предикатные константы Х для каждогоперехода находятся в блоке 15, наприМерХ = (0.5, 0.8, О.З),Значения ф генерируются в процессеработы устройства блоком 16, Срабатыва 40 ние переходов сети происходит при условииих активности по входным маркировкам иистинности присвоенных предикатов,Требуетсяопределить, достижима ли45маркировкаи из маркировки,и,Предполагают, что маркировка р до-стижима из маркировки р. Тогда существует последовательность возможно пустая)запусков переходов о; которая приводит из,и к и. Это означает, что 1 о) является неот 50 рицательным целым решением следующегоматричного уравнения для х,и,и+ х.Д, Р).где Д - Д - Д - составная матрица измене ний,Уравнениеназывается фундаментальным уравнейием сети Петри, Если,и достижима из и, уравнение (2) имеет решение в неотрицательных целых, если уравненение (2) не имеет решенияи не достижима из и.Под действием синхросигналов с блока11 информация с выхода блока 1 поступает на вторые входы элементов сравнения 51- 5 5 ь, где происходит ее сравнение со значением начальной маркировки, поступающей на первые входы всех элементов 51-5 ь Если результат сравнения больше или равен нулю по всем сравниваемым элементам стро ки матрицы Д, в соответствующий разряд регистра 6 записывается единица, иначе - нуль,Таким образом, при сравнении первоначальной маркировки (1, О, 1, 0) со строка ми мат"рицы Д, только третья строка удовлетворяет правилу сравнения. Это означает, что срабатывание третьего перехода по входной маркировке разрешено, В " регистре 6 записано (О, О, 1), 20Дальне работа устройства направлена на проверку условия (1), т.е, истинности предикатов, присвоенных каждому переходу сети. Значение кода с выхода регистра 6 поступает на адресный вход блока 15. Рабо . та блока 15 организована так, что при г оступлении на любую из шин адресного входа сигнала "1" (признака активности пе.рехода по входной маркировке), на соответствующем выходе блока появляется 30 значение предикатной константы,. иначе - значение "1". Таким образом, при поступлении на вход блока 15 кода (О, О, 1) на его выходах появляется код (1, 1, 0,3). Далее информация свыхода блока 15 поступает на 35 соответствующие вторые входы элементов.сравнения 171 - 17 ь где происходит ее сравнение со значениями предикатных переменных, поступающими на первые входы элементов 171 - 17 ь Значения предикатных 40 переменных для каждого перехода сети генерируются случайным образом датчиками случайных чисел блока 16 и поступают на его выходы путем одновременного опроса всех датчиков. Пусть в результате опроса на 45 выходе блока 16 получен следующий код предикатных переменных; ф = (0.7, 0.9, 0,5).В результате сравнения соответствую щих значений предикатных переменных с выхода блока 16 и кода с выхода блока 15, на выходах элементов сравнения 171-17 получается код (О, О, 1), который записывается в регистр 18. Полученный код сви детельствует о том, что разрешено срабатывание третьего перехода как по входной маркировке, так и истинности присвоенного предиката,Параллельно информация из блока 2 поступает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация с блока 1. Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле:Д=Д -Д.Значение полученной составной матрицы изменений Д записывается в блок 3. Она имеет вид:0 -1 -1 0Д= 0+2 +1 -10 0-1+1Дальше работа схемы направлена на реализацию формулы (2). Подставляя полученные значения, она имеет вид: О -1 -1 0 .,и=(1,0,1,0)+(0,0,1) 0 +2 +1 -10 0-1+1Под действием управляющих сигналов с блока 11 информация из блока 3 и регистра 18 поступает в блок 8, где происходит перемножение матриц, Результат умножения (О, О, -1, +1) поступает в блок 9, где происходит сложение результата произведения со значением маркировки из блока 4, в результате чего получается новая маркировка сети Петри(1, О, О, 1), которая вновь заносится в блок 4 регистров, Процесс работы устройства повторяется,Элементы задержки 19 - 21 обеспечивают последовательность срабатывания блоков 15-18 в интервал времени от момента записи информации в регистр 6 до момента перемножения матриц в блоке 8,На каждом шаге работы устройства происходит проверка кода, находящегося в регистре 6, т,е. последовательности запусков переходов, на нуль в блоке 10. Если информация больше нуля. процесс работы продолжается, При этом возможна ситуация, когда при активности перехода по входной маркировке он может быть неактивен из-за ложности присвоенного предиката. Например, при получении с выхода блока 16 значений предикатных переменных = (0,7, 0,9, 0.2), третий переход перестает быть активным, и в регистре,8 будет записан код(0, О, 0). Таким образом, в блоке 4 сохранится предыдущая маркировка и на следующем шаге работа устройства начнется опять с нее. Если последовательность запусков переходов по входной маркировке, находящаяся в регистре 6, равна О, блок 10 вырабатывает сигнал, свидетельствующий о том, что предикатно-переходная сеть Петри при данной начальной маркировке достигла предела выполнимости, т,е, достигла такого состояния, когда все переходы запрещены,Таким образом, предлагаемое устройство для исследования сетей Петри позволяет исследовать матричное представление сетей; может быть использовано для решения линейных матричных уравнений и позволяет существенно расширить функциональные возможности устройства за счет анализа предикатно-переходных сетей Петри на достижимость. Формула изобретения Устройство для исследования сетей Петри, содержащее последовательно соединенные блок синхронизации, блок регистров, первый блок элементов сравнения, первый регистр результатов сравнения, блок сравнения с нулем, выход которого является информационным выходом устройства, последовательно соединенные блок памяти. матрицы входов, блок вычитания матриц, блок памяти матрицы изменений, блок умножения матриц, блок Сумматоров, а также блок памяти матрицы выходов, выход которого подключен к второму входу блока вычитания матриц, а вход признака чтения - к входу признака записиблока памяти матрицы изменений, к второму выходу блока синхронизации и к входу призна ка чтения блока памяти матрицы входов, выход которого подключен к второму информационному входу первого блока элементов сравнения, вход опроса. которого подключен к входу опроса блока вычитания матриц и к третьему выходу блока синхронизации, вход пуска которого является входом, пуска устройства, четвертый выход подключен к входу признака записи первого регистра результатов сравнения, пятый выход - к входу признака чтения блока памяти матрицы изменений, шестой и седьмой выходы - к входам опроса соответственно блока умножения матриц и блока сумматоров, вход останова - к выходу блока сравнения с нулем, вход начальной установки - к входам5 начальной установки блока памяти матрицы изменений, первого регистра результатовсравнения и является входом начальной ус-, тановки устройства, второй информационный вход и выход блока сумматоров10подключены соответственно к выходу иинформационному входу блока регистров, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей путем осуществления анализа на до стижимость, дополнительно введеныпоследовательно соединенные первый, второй и третий элементы задержки, а также блок датчиков случайных чисел, а между, первым регистром результатов сравнения и .20 блоком умножения матриц включены последовательно соединенные блок памяти предикатных констант перехода, второй блок элементов сравнения, второй регистр результатов сравнения, вход начальной уста новки которого подключен к:входуначальной установки устройства, вход признака записи - к выходу третьего элемента задержки, вход которого подключен к входу опроса второго блока элементов сравнения, 30 второй информационный вход которогоподключен к выходу блока датчиков случай-.ных чисел, вход опроса которого подключен к входу признака чтения блока памяти предикатных констайт перехода и к выходу пер вого элемента задержки, вход которогоподключен к входу признака записи первого регистра результатов сравнения, выход которого подключен к адресному входу блока памяти предикатных констант перехода, а 40 выход второго регистра результатов сравнения подключен к второму информационному входу блока умножения матриц.1784998 дактор Т, Кол Корректор П, 3 ереши а роизводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина,Составитель И. ШелипоТехред М.Моргентал аказ 4366 Тираж ВНИИПИ Государственного комитета по изобрет 113035, Москва, Ж, РаушсПодписноеям и открытиям при ГКНТ СССнаб., 4/5