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

 

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

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

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

РЕСПУБЛИК (я)з G 06 F 15/347, 15/419

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4903641/24 (22) 21.01.91 (46) 30.12.92. Бюл. М 48 (72) В,ll,Îáðó÷åíêoâ, А.А.Бянкин, В.М.Ла- рин и В.B.Äîðoøåíêo (56) Авторское свидетельство СССР

N. 482749, кл. 6 06 F 15/347, 1972.

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

hL 1322312, кл. 6 06 F 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

СЕТЕЙ ПЕТРИ

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

Петри на достижимость.

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

Петри на достижимость путем их матричного представления и решения линейных матричных уравнений.

Наиболее близким по технической сущности к заявляемому изобретению является устройство для исследования сетей Петри, содержащее последовательно соединенные блок синхронизации, блок регистров, первый блок элементов сравнения, первйй регистр результатов сравнения, блок сравнения с нулем, выход которого является информационным выходом устройства, последовательно соединенные блок памяти матрицы входов, блок вычитания матриц, „,5Q 1784998 А1,2 (57) Изобретение относится к вычислительной технике и может быть использовано для решейия линейных матричных уравнений.

Цель изобретения — расширение функциональных возможностей за счет осуществления анализа на достижимость. В устройство дополнительно введены блок памяти предикатных констант перехода, три элементз задержки, второй блок элементов сравнения, блок датчиков случайных чисел и второй регйстр результатов сравнения. 1 ил.

-Ф блок памяти матрицы изменений, блок умножения матриц, блок сумматоров, а также блок памяти матрицы выходов, выход которого подключай ко второму входу блока вы- Я читания матриц, а вход признака чтения — к входу признака записи блока памяти матрицы изменений, ко второму .вйходу блока а синхронизации и к входу признака чтения блока памяти матрицы входов, выход кото-. ()р рого подключен ко второму ийформацион- р ному входу первого блока элементов сравнения, вход опроса которого подключен к входу опроса блока вычитания матриц и к третьему выходу блока синхронизации, вход пускв которсто явяявтся входам пуска 1кв устройства, четвертый выход подключен к входу признака записи первого регистра результатов сравнения, йятый выход - к входу признака чтения блока йамяти матрицы изменений, шестой и седьмой выходы — к входам опроса соответСктвенно блока умножения матриц и блока сумматоров, вход останова — к выходу блока сравнения с нулем, вход начальной установки — к входам начальной установки блока памяти матрицы изменений, первого регистра результатов

1784998 сравнения и является входом начальной установки устройства, второй информационный вход и выход блока сумматоров подключены соответственно к выходу и к информационному входу блока регистров.

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

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

Петри содержит блок 1 памяти матрицы входов, блок 2 памяти матрицы выходов, блок 3 памяти матрицы изменений, блок 4 регистров, первый блок элементов сравнения, содержащий элементы сравнения 5i-5k (где k — количество строк в исходных матрицах), первый регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок сг фР»

10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства, вход 13 начальной установки, вход 14 пуска устройства, блок 15 памяти предикатных

5 констант перехода, блок 16 датчиков случайных чисел, второй блок элементов сравне. ния, три элемеита 19-21 задержки.

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

10 В исходном состоянии схемы в блоке 1 находится матрица входов Д, например

Д- 0001

15 а в блоке 2-матрица выходов Д, например

100.0

Д - 0210

0001 т.е. данная сеть Петри имеет четыре пози20 ции и три перехода. Первоначальная маркировка находится в блоке 4 и имеет вид: ,и = (1. О, 1, О). . Каждому переходу сети йоставлен в соответствие одноместный предикат,. истин25 ность которого достигается выполнением следующегб условия;

Й >4 (1) . где j — номер перехода, J 1, k; ф — предикатная переменная — случай30 ная величина, равномерно распределенная в интервале (О, 1);

$ — предикатйая константа — постоян- . ная величина, поставленная в соответствие каждому переходу, 2 6(0, 1).

35 Пре»дикатные константы il; для каждого перехода на»ходятся в блоке 15. например:

Х = (0.5, 0.8, 0.3).

Значения ф генерируются в процессе

40 работы устройства блоком 16, СрабатываО ние переходов сети происходит при условии их активности по входным маркировкам и истинности присвоенных предикатов.

Требуегся определить, достижима ли

45 маркировка р из маркировки,и.

Предполагают, что маркировка р до- стижима из маркировки р. Тогда существует последовательность (возможно пустая) запусков переходов о; которая приводит из ,и к,и . Это означает, что f (о) является неот50 рицательным целым решением следующего матричного уравнения для х ф р+ xÄ, (2). где Д - Д+ - Д вЂ” составная матрица измене55 ний, Уравнение (2) называется фундаментальным уравнейием сети Петри, Если,и достижима из р, уравнение (2) имеет решение в неотрицательных целых, если уравне1784998 нение (2) не имеет решения„и не достижима из и.

Под действием синхросигналов с блока

11 информация с выхода блока 1 поступает на вторые входы элементов сравнения 51- 5

5, где происходит ее сравнение со значением начальной маркировки, поступающей на первые входы всех элементов 51-5и, Если результат сравнения больше или равен нулю по всем сравниваемым элементам стро- 10 ки матрицы Д, в соответствующий разряд регистра 6 записывается единица, иначе— нуль.

Таким образом, при сравнении первоначальной маркировки (1, О, 1, О) со строка- 15 ми мат"рицы Д, только третья строка удовлетворяет правилу сравнения. Это означает, что срабатывание третьего перехода по входной маркировке разрешено. В " регистре 6 записано (О, О, 1), 20

Дальне работа устройства направлена на проверкуусловия (1), т.е. истинности предикатов, присвоенных каждому переходу сети. Значение кода с выхода регистра 6 поступает на адресный вход блока 15. Рабо- 25 . та блока 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).

В результате сравнения соответствую- 50 щих значений предикатных переменных с выхода блока 16 и кода с выхода блока 15, на выходах элементов сравнения 17>-17g получается код (0, О, 1), который записывается в регистр 18. Полученный код сви- 55 детельствует о том, что разрешено срабатывание третьего перехода как по входной маркировке, так и истинности присвоенного предиката.

Параллельно информация из блока 2 поступает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация с блока 1. Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле:

Д=Д -Д.

Значение полученной составной матрицы изменений Д записывается в блок 3. Она имеет вид:

О -1 -1 О

Д= 0+2+1-1

О 0-1+1

Дальше работа схемы направлена на реализацию формулы (2). Подставляя полученные значения, она имеет вид:

О -1 -.1 О. ,и = (1, О, 1, 0) + (0, О, 1) О +2 +1 -1

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 будет записан код (О, О, О). Таким образом, в блоке

4 сохранится предыдущая маркировка и на следующем шаге работа устройства начнется опять с нее. Если последовательность запусков переходов по входной маркировке, находящаяся в регистре 6, равна О, блок

10 вырабатывает сигнал. свидетельствующий о том, что предикатно-переходная сеть

Петри при данной начальной маркировке достигла предела выполнимости, т.е, до1784998 стигла такого состояния, когда все переходы запрещены.

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

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

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

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

5 начальной установки блока памяти матрицы изменений, первого регистра результатов сравнения и является входом начальной ус-, тановки устройства, второй информационный вход и выход блока сумматоров

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

20 блоком умножения матриц включены последовательно соединенные блок памяти предикатных констант перехода, второй блок элементов сравнения, второй регистр результатов сравнения, вход начальной уста25 новки которого подключен к:входу начальной установки устройства, вход признака записи — к выходу третьего элемента задержки, вход которого подключен к входу опроса второго блока элементов сравнения, 30 второй информационный вход которого подключен к выходу блока датчиков случай-. ных чисел, вход опроса которого подключен к входу признака чтения блока памяти предикатных констайт перехода и к выходу пер35 вого элемента задержки, вход которого подключен к входу признака записи первого регистра результатов сравнения, выход которого подключен к адресному входу блока памяти предикатных констант перехода, а

40 выход второго регистра результатов сравнения подключен к второму информационному входу блока умножения матриц.

1784998 с

Составитель И. Шелипова

Техред М.Моргентал Корректор П, ) ереши

Редактор Т. Коляда

Производственно-издательский комбинат "Патент", r. Ужгород, ул,Гагарина, 101

Заказ 4366 Тираж Подписное

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

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