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

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

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

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

Устройство содержит три блока 1-3 памяти, блок 4 регистров, группу 5 блоков 5.1 -5.т схем сравнения, где т- количество переходов в СП, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, выход блока 4 регистров подключен к входу первого слагаемого блока 9 сумматоров, первому информационному входу каждого блока 5.1 -5.ГП схем сравнения группы, с первого по т-1 выходы первого блока 1 памяти подключены к входу вычитаемого блока 7 вычитания матриц и вторым входам с первого по m-й блоков 5,1 - 5.т схем сравнения групп 5, выходы признаков неотрицательного результата которых подключены к информационному входу регистра 6 результатов сравнения, выход которого подключен к входу первого сомножителя блока 8 умножения матриц и информационному входу блока 10 сравнения с нулем, выход признака равенства нулю которого подключен к входу останова блока 11 синхронизации и является выходом Останова, выход которого 2 блока памяти подключен к входу уменьшаемого блока 7 вычитания матриц, выход которого подключен к информационному входу третьего блока памяти 3,

00

о Ј

Ј

00

выход которого подключен к входу второго сомножителя блока 8 умножения матриц, выход которого подключен к входу второго слагаемого блока 9 сумматоров, выход которого подключен к информационному входу блока 4 регистров, вход начальной установки блока 11 синхронизации Одновременно подключен к входам начальной установки регистра 6 результатов сравнения, третьего блока 3 памяти и является входом начальной установки 13, вход пуска блока синхронизации является входом 14 пуска, с первого по седьмой выходы блока 11 синх- о14изации подключены k:входам признака чтения первого и второго блоков памяти 1, 2 и входу признака записи третьего 3 блока памяти, к выходу опроса блока 9 сумматоров, к входам признака записи 4 регистров, к входам сипроса каждого блока 5.1 - Б.гп схем сравнения группы и блока 7 вычитания матриц, к входу признака записи регистра б результатов сравнения, к входу опроса блока 8 умножения матриц и входу признака чтения третьего блока 3 памяти соответственно, а также блок вычисления маркировок 15, блок хранения маркировок 16, блок записи маркировок текущего уровня 17, блок. хранения маркировок предыдущего уровня 18, генератор импульсов перезаписи 19, первый - шестой регистры 20 - 25, первый 34, второй 33, третий 35 счетчики, первый 32 и второй 31 блоки сравнения, элемент задержки 30, ключ 27, два элемента ИЛИ 28, 29, одновибратор 26, выход которого подключен к счетным входам первого и второго счетчиков, к входу управления считыванием блока вычисления маркировок, а вход - к выходу первого элемента ИЛИ, первый вход которого является входом запуска устройства 36, второй вход подключен к выходу ключа, третий вход - к первому информационному выходу блока хранения маркировок предшествующего уровня, четвертый вход -1 к счетному входу обнуления первого счетчика, к входу управления обнулением блока хранения маркировок предшествующего уровня, к первому входу генератора импульсов перезаписи, к первому информационному выходу запиёи маркировок текущего уровня, пятый вход - к первому информационному выходу блока хранения маркировок 16, шестой вход - к первому выходу результатов сравнения блока вычисления маркировок 15, первый информационный выход которого является выходом достижения заданной маркировки устройства, второй выход результатов сравнения подключен к входу управления обнулением блока хранения маркировок 16, информационный вход - к выходу шестого

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

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

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

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

0 третьего регистров, к входу первого 20 регистра, третий информационный вход - к выходу третьего счетчика 35, четвертый информационный вход - к выходу пятого регистра 24, вход которого подключен к

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

0 второго счетчика 33, выход которого подключен к первому входу первого блока сравнения 32, второй вход которого подключен к выходу четвертого регистра 23, информа- . ционный вход ключа 27 подключен к выходу

5 второго элемента ИЛИ 29, первый и второй входы которого подключены соответственно к выходу элемента задержки и к выходу блока сравнения с нулем 10, выход второго регистра подключен к первому входу второ0 го блока сравнения 31, второй вход которого подключен к выходу третьего регистра 22, информационный вход которого подключен к выходу блока сумматоров 9, выход первого регистра подключен к второму информаци5 он ному входу блока регистров 4, вход шестого 25 регистра соединен с четвертым выходом блока хранения маркировок предшествующего уровня 18.

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

Импульс запуска подается на вход 36 устройства, который проходя через элемент ИЛИ 28 поступает на вход одновибратора 26, с выхода которого соответствующий импульс поступает на вход управления считыванием блока вычисления маркировок и счетные входы счетчиков 34 и 33, в которых первоначально записаны были О. Модуль счета счетчика 33 равен т, а в счетчике 34 хранится текущий номер проверяемой вершины дерева маркировок.

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

.

-хС, где х {1,0,....О).

Далее в соответствии с вышеописанным алгоритмом полученное значение маркировки сравнивается поэлементно на условие 0 (если это условие не выполняется, то полученное значение не является дочерней вершиной 3, стр. 19) и со значением . . j ., то выдается положительный ответ о достижимости

Р

из fi° на выход 37 устройства.

Если же//l+1 , , и

fi , j о . то на втором выходе результатов сравнения блока вычисления маркировок возникает импульс, поступающий на вход управления обнулением блока хранения маркировок, на его первый вход поступает значение для дальнейших проверок (со второго информационного вы- хода блока вычисления маркировок).

В блоке хранения маркировок 16 происходит сравнение/г|+1, со всеми уже имеющимися в дереве маркировок вершинам (первоначально дерево представлено только корнем). Со второго информационного выхода блока вычисления маркировок на первый вход блока хранения маркировок поступает значение :/ ,j. требующее сравнения с уже имеющимися вершинами, на вход управления обнулением - запускаю- щий импульс. При равенстве ,j ft маркировка/ 1 1, j исключается из дальнейшего рассмотрения, вырабатывается импульс 1, который выдается на первый . информационный выход блока хранения маркировок и на второй вход ИЛИ 28, инициируя тем самым вычисление следующей . В случае ,j/ Ц ° 1, считывается очередная полученная ранее маркировка - вершина дерева достижимости. При переборе вершин для сравнения с исследуемой

,1+1 :

/it J выдается импульс на второй выход блока для инициирования проверки необходимого условия достижимости из /г0// 1,.

По этому сигналу значение первой на- 5 чальной маркировки заносится из первого 20 регистра блок 4, обнуляется третий регистр 22 (от значения, хранимого в нем от предыдущих циклов работы устройства) и запускается прототип по входу 14 для опре0 деления необходимого условия достижимости , из fi°. При этом, по логике работы прототипа в регистре 9 размещается на каждом шаге маркировка последовательно достижимая из fi° (это же самое заносится и в

5 регистр 22). Если же на определенном шаге работы прототипа в регистре 22 окажется значение/ l+1,j, то тем самым существует необходимое условие достижимости//1 из , блок сравнения 31 вы дает об этом соот0 ветствующий импульсный сигнал. Если необходимое условие не выполняется, в регистр 22 никогда не занесется значение /il+1 ,j, а исследуемая сеть при начальной (.1° достигает своего предела достижимости,

5 и на выходе 12 прототипа Останов вырабатывается соответствующий сигнал, являющийся отрицательным ответом на вопрос достижимости / J . При этом/i ,} исключается из дальнейшего рассмотрения:

0 сигнал с выхода 12 прототипа поступает на второй вход элемента ИЛИ 29 и далее через ключ 27 на третий вход элемента ИЛИ 28 для вычисления проверки очередной дочерней маркировки (вершины дерева).

5 в случае положительного ответа на существование необходимого условия достижения маркировки значение заносится в блок хранения маркировок 16 и блок записи маркировок текущего значения

0 уровня 17 и используется в дальнейших проверках в качестве новой вершины дерева достижимости.

После записи ,j задержанный им- пульс на величину задержки элемента 30

5 поступает на вход элемента ИЛИ 29, ключ 27, элемента ИЛИ 28 для вычисления очередной вершины дерева. Задержка элемента 30 выбрана таким образом, чтобы исключить возможность состязания при за0 писи в блоки 16, 17 и вычислением новой маркировки.

При достижении в счетчике 33 числа m (это свидетельствует о том. что перебраны все строки матрицы инцидентности сети и

5 соответственно все возможные дочерние вершины перебраны), блок сравнения 32 выдает сигнал, по которому обнуляется счетчик 33. закрывается ключ 27 для исключения возможности генерирования очередных запускающих одновибратором 26 импульсов (т.е. из корневой вершины получены все возможные дочерние маркировки) и этот же сигнал подается на четвертый вход блока хранения маркировок предшествую- щего уровня, по которому из этого блока в регистры 25 и 24 заносится соответственно следующая (если такая же имеется в блоке хранения маркировок предшествующего уровня) маркировка предыдущего уровня и ее номер I на предыдущем уровне.

После того как перебраны все вершины предшествующего уровня, для каждой из которых найдены дочерние вершины, которые в свою очередь образуют множество маркировок текущего уровня, необходимо искать дочерние вершины для вновь полученных вершин, т.е. осуществить построение дерева достижимости далее. Импульс со второго выхода.блока 18 поступает на второй 84 вход блока записи маркировок текущего уровня 17. При этом содержимое счетчика записи, имеющегося в блок 17, соответствующее числу полученных вершин на последнем уровне дерева, поступает в блок сравнения с нулем блока 17, и если число вершин последнего уровня больше нуля, то выдает сигнал импульсной 1, поступающий на второй выход блока записи маркировок текущего уровня. По этому сиг- налу, поступающему на второй вход генератора импульсов перезаписи 19, последний выдает импульсы для перезаписи вершин, полученных на текущем уровне дерева, в блок хранения маркировок предшествую- щего уровня. Период следования этих импульсов выбирается не меньшим интервала перезаписи информации из ячеек памяти блока 17 в аналогичные ячейки памяти блока 18, Каждый импульс соответствует акту перезаписи одной ячейки. Одновременно сигнал с первого выхода блока записи маркировок текущего уровня подается вход управления обнулением блока хранения маркировок предшествующего уровня для считывания очередной маркировки на третий и четвертый выходы блока 18 в шестой 25 и пятый 14 регистры соответственно, а также на вход первого элемента ИЛИ и на вход третьего счетчика 35 (для увеличения на единицу текущего номера уровня дерева

ДОСТИЖИМОСТИ);

ЕСЛИ ни одна вершина последнего уровня не имеет дочерней вершины, т.е. со- бтветствующие маркировки недостижимы, блок 17 выдает сигнал на первый выход блока записи маркировок маркеров текущего уровня, свидетельствующий о недостижимости ; ИЗ fio .

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

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

Я

. /5

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

#.

35

2У

ft

iD

ter

ЯС

/f -:

Лс

- s

v 1o

30

#