Устройство для исследования сетей Петри Советский патент 1987 года по МПК G06F17/16 

13

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

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

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

На фиг . 1 представлена (Ьунюдио- нальная схема устройства; на фиг.2 - пример реализации блока синхроюгза- ции устройства.

Устройство для исследо зания сетей Петри содержит три блока 1-3 ппььчти, б л , 4 рег истрог, груш .у j б кисоз 5-1,...,5-k схем сравнения, где k - количс:С во строк в исходпь1Х матрицах регистр Г) результа1 ов сравнения, блок 7 15ычитания матриц, бло1; 8 ум- южения магриц, блок 9 сумматоров, блок 10 сравнения с nyjiCM и блок 11 синхронизации, причем выход блока 4 регистров по,ги Л1очен к вхо/т,у первого слагаемого блока 9 сумматорот и пер- BONty информационному входу кажд(:1го блока 5-1,...,5-k схем сравнения гру пн, с пе рвого но k-й выходы первого блока 1 памяти подключены к пходу В1л читаемого блока 7 вычитания .1атриц и вторьи входам с первого по k-й блоков 5-1,...,5-k схем сравнения группы 5, В111ХОДЫ признаков неотрицательного результата которых нодк.гпочены к информационному входу регистра 6 результатов сравнения, В1 1ход, которог иодк:ночен к входу первого сомпожи

12

ИЫ выходов, в блоке 9 полученное произведение суммируется со значением начальной маркировки и полученное новое значение маркировки записывается п блок Д. Процесс продолжается до тех нор, пока результат сравнения не станет равен нулю по всем строкам матрицы входов. В этом случае блок 10 (Нормирует сигнал, свидетельствующий о том, что сеть Петри при данной начальной маркировке достигла предела в1лпол Н1 ости, т.е. такого состоя- ни, когда нее переходы запрещены. 2 ил.

5

5

0

5

0

теля блока 8 умножения матриц и ин- 1)ормационному входу блока 10 сравнения с нулем, выход признака равенства нулю которого подключен к входу останова блока 11 синхронизации и является информационным выходом 12 устройства, выход второго блока 2 памяти подключен к входу уменьшаемого блока 7 вычита 1Н1Я матриц, выход которого подключен к информационному входу третьего блока 3 памяти, выход которого подключен к входу второго сомножителя блока 8 умножения матриц, выход которого подключен к входу второго слагаемого блока 9 сумматоров, выход которого подключен к информационному входу блока 4 регистров, вход начальной установки блока 11 синхронизации подключен к входам начальной установки регистра 6 результатов сравнения и третьего блока памяти и является входом 13 начальной установки устройства, вход пуска блока синхро- низап,-н1 является входом 14 пуска устройства, с первого по седьмой выходы 15,...,21 блока 11 синхронизации подключены к входам признака чтения первого и второго блоков 1 и 2 памяти и входу признака записи третьего блока 3 памяти, к входу опроса блока 9 сумматоров, к входу признака записи блока 4 регистров, к входам опроса каждого блока 5-1,...,5-k схем сравнения группы и блока 7 вы- Ч1ггания матриц, к входу признака записи регистра 6 результатов ср авнения, к входу опроса блока 4 умножения матриц и входу признака чтения третьего блока 3 памяти соответственно.

Блок 11 синхронизации (фиг,2) со- держит триггер 22, элементы И 23-25, генератор 26 тактовых импульсов, счетчики 27 и 28, регистры 29 и 30, элементы НЕ 31 и 32, элементы 33-37 задержки и элемент ИЛИ 38.

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

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

Д

1110 0001 0010

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

Д

1000 0210 0001

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

/К (1, О, 1, 0)

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

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

р + Х-Д.

Если fu достижима из ju , уравнение (1) имеет решение в неотрицательных целых, если уравнение (1) не имеет решения, ffl не достижима из JU .

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

5

0

5

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

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

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

Д Д - Д-.

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

Д

0-1-10 0-1-2+1-1 О 0-1+1

35

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

(1, О, 1, 0)+(0, О, 1)

0-1-10

0+2+1-1

00-1+1

45

,

50

5

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

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

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

Блок 11 синхронизации (фиг.2) работает следующим образом.

Первоначально триггер 22 находится в нулевом состоянии. По сигнал начальной установки, который, пройдя через элемент ИЛП 23, постутгает на входы записи счетчиков 27 и 28, иро- и:и5оди 1 ся запись информации г. соответствующего регистра 29, где хранит СИ число строк исходной матрииы, и регистра 30, где хранится чис.чо ст(збцов исходной матрицы. С приходом сигнала ио входу 14 Пуст; тригтер 2 переходит в единичное состспние и высокий потенциал с его прямого выхода разрешает ирохо г;иение тактовых импульсов с генератора 26 элемент II 23. Импульсы поступают на вы- читаюиц1Й вход счетчика 27 и ирохо; ят через ojiCMeirr И 24, o ri;pi, высоким

iiOTCHiuiajioM с выхода иерс.гю. тнения счетчика 27.

С выхода элемента И 24 импульсы поступают на первый выход 15 блока 1 и про1(дя через элементы 36 и 37 задержки, поступают соответстве1И1о на четвертый: и пятый выходь; 18 и 1 9 блока 11.

После того как содержимое счетчи-

ка 27 станет равным нулю, на его выходе переполнения появится низкий потенциал, который закроет элемент И 24 и, пройдя через элемент ПЕ 31, откроет элемент И 25. Тактовые импульсы начнут поступать на вычитаюц лй вход счетчика 28, на седьмой выход 21 блока и, пройдя через элe ieнты 34 и 35 задержки, на шестой и второй выходы

20 и 16 блока 11 соответственно.

50

После обнуления счетчика 28 низкий потенциал с его выхода пройдет через элемент НЕ 32, элемент 33 зад,ержки и поступит на третий выход 17 блока 11, пройдет через элемент ИЛИ 38 и посту- сг пит на входы записи счетчиков 27 и 28 и перепишет на них содержимое соот- ветств-,пощих регистров 29 и 30. Процесс работы блока повторяется. PtiCo

та продолжается до тех пор, пока на вход 12 останова блока не поступит сигнал, который установит триггер 22 в нулевое состояние, низкий потенциал с его прямого выхода запретит прохождение тактовых импульсов с генератора 26 через элемент И 23.

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

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

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

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

Редактор Н.Рогулич

Составитель А.Мишин Техред Л.Олийнык

Заказ 2867/47Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная.4

128

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

(Ри.2

Корректор Г.Решетник

Изобретение относится к вычислительной технике, может быть использовано для решения линейных матричных уравнений и позволяет исследовать матричное представление сетей Петри на достижимость. С этой целью в состав устройства входят три блока 1,2 и 3 памяти, блок 4 регистров, группа 5 блоков 5-1,...,5-k схем сравнения, где k - количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства, вход 13 начальной установки и вход 14 пуска устройства. В исходном состоянии в блоках 1 и 2 памяти записаны матри(Л Фиг /