Устройство для исследования сетей Петри Советский патент 1992 года по МПК G06F15/347 G06F15/419 

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

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

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

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

Ј

00

4

Ю Ю 00

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

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

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

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

На чертеже представлена функциональная схема устройства,

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

0

5

0

5

0

5

0

5

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

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

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

1110 Д 0001 0010 5 а в блоке 2 - матрица выходов Д+, например

1000

Д+ 0210

0001

т.е. данная сеть Петри имеет четыре позиции и три перехода. Первоначальная маркировка находится в блоке 4 и имеет вид:

/«-(1,0,1,0).

Каждому переходу сети поставлен в соответствие одноместный предикат,- истинность которого достигается выполнением следующего условия:

k 4 О)

где j - номер перехода, j 1, k;

§ - предикатная переменная - случайная величина, равномерно распределенная в интервале 0,

Я - предикатная константа - постоянная величина, поставленная в соответствие каждому переходу, /У 6 0,1}.

Предикатные константы Я дли каждого перехода находятся в блоке 15. например: Я (0.5,0.8, 0.3).

Значения Ј генерируются в процессе работы устройства блоком 16. Срабатывание переходов сети происходит при условии их активности по входным маркировкам и истинности присвоенных предикатов.

Требуется определить, достижима ли маркировка из маркировки ft.

Предполагают, что маркировка ft достижима из маркировки ft. Тогда существует последовательность (возможно пустая) запусков переходов а, которая приводит из ft к р Это означает, что f (с) является неотрицательным целым решением следующего матричного уравнения для х

Х / + х.Д,(2).

Д - Д - Д - составная матрица изменений.

Уравнение (2) называется фундаментальным уравнением сети Петри. Если ft достижима из ft, уравнение (2) имеет решение в неотрицательных целых, если уравненение (2) не имеет решения, /г не достижима из ц.

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

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

Дальне работа устройства направлена на проверку условия (1), т.е. истинности предикатов, присвоенных каждому переходу сети. Значение кода с выхода регистра б поступает на адресный вход блока 15. Рабо- та блока 15 организована так, что при поступлении на любую из шин адресного входа сигнала 1 (признака активности перехода по входной маркировке), на соответствующем выходе блока появляется значение предикатной константы, иначе - значение 1. Таким образом, при поступлении на вход блока 15 кода (О, О, 1) на его выходах появляется код (1, 1, 0.3). Далее информация с выхода блока 15 поступает на соответствующие вторые входы элементов сравнения 17i-17k, где происходит ее сравнение со значениями предикатных пере- менн,ых, поступающими на первые входы элементов 17i-17k. Значения предикатных переменных для каждого перехода сети генерируются случайным образом датчиками случайных чисел блока 16 и поступают на его выходы путем одновременного опроса всех датчиков. Пусть в результате опроса на выходе блока 16 получен следующий код предикатных переменных:

| (0.7, 0.9, 0.5).

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

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

Д Д+-Д.

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

0-1-10

Д 0+2+1-1 О 0-1+1

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

,« (1,0, 1,0) + (0.0, 1)

О -1 --1 О О +2 +1 -1 00-1+1

Под действием управляющих сигналов с блока 11 информация из блока 3 и регистра 18 поступает в блок 8, где происходит перемножение матриц. Результат умножения (О, О, -1, +1) поступает в блок 9, где происходит сложение результата произведения со значением маркировки из блока 4, в результате чего получается новая маркировка сети Петри (1, 0,0,1), которая вновь заносится в блок 4 регистров. Процесс работы устройства повторяется.

Элементы задержки 19-21 обеспечивают последовательность срабатывания блоков 15-18 в интервал времени от момента записи информации в регистр 6 до момента перемножения матриц в блоке 8.

На каждом шаге работы устройства происходит проверка кода, находящегося в регистре б, т.е. последовательности запусков переходов, на нуль в блоке 10. Если информация больше нуля, процесс работы продолжается. При этом возможна ситуация, когда при активности перехода по входной маркировке он может быть неактивен из-за ложности присвоенного предиката. Например, при получении с выхода блока 16 значений предикатных переменных Ј (0.7, 0.9, 0.2), третий переход перестает быть активным, и в регистре .8 будет записан код (О, О, 0). Таким образом, в блоке 4 сохранится предыдущая маркировка и на следующем шаге работа устройства начнется опять с нее. Если последовательность запусков переходов по входной маркировке, находящаяся в регистре 6, равна 0. блок 10 вырабатывает сигнал, свидетельствующий о том, что предикатно-переходная сеть Петри при данной начальной маркировке достигла предела выполнимости т е достигла такого состояния, когда все переходы запрещены,

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

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

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

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

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

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

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

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