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

 

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

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

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

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

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

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4893557/12 (22) 25.12.90 (46) 15.04,93. Бюл, bJ. 14 (72) А.А,Бянкин, В.В,Дорошенко, В,М.Ларин. В. П, Обручен ков, А. В. Паде рин, Г.Д.Пантелеев и А.Г.Янковский (56) Авторское свидетельство СССР

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

СЕТЕЙ ПЕТРИ (57) Изобретение относится к вычислительной технике и может быть использовано для решения матричных линейных уравнений и исследования сетей Петри на достижимость. Цель изобретения состоит в расширении функциональных возможностей устройства за счет алгоритмической разреИзобретение относится к вычислительной технике, может быть использовано для решения матричных линейных уравнений и исследования сетей Петри на достижимость.

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

На чертеже представлена функциональная схема устройства, Устройство содержит три блока 1 — 3 памяти, блок 4 регистров, группу 5 блоков

5,1 -5.m схем сравнения. где m — количество переходов в СП, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок

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

Bbtxo4 которого подключен к входу второго регистра, второй информационный выход— сомножителя блока 8 умножения матриц, к информационному входу второго региствыход которого подключен к входу второго ра, к первому входа блока хранения маркислагаемого блока 9 сумматоров, выход кото- ровок 16, к первому информационному рого подключен к информационному входу 5 входу блока записи маркировок текущего блока 4 регистров, вход начальной установ- уровня 17, второй информационный вход ки блока 11 синхронизации одновременно которого подключен ко второму входу генеподключен к входам начальной установки ратора импульсов перезаписи, третий иинрегистра 6 результатов сравнения, третьего формационный выход 38 является выходом блока 3 памяти и является входом началь- 10 недостижимости устройства, второй инфорной установки 13, вход пуска блока синхро-. мационный вход подключен к второму иннизации является входом 14 пуска, с формационному выходу блока хранения первого по седьмой выходы блока 11 синх- маркировок предшествующего уровня 18, ронизации подключейы к входам признака вход управления обнулением — к выходу гечтения первого и второго блоков памяти 1, 15 нератора импульсов перезаписи, входу уп2 и входу признака записи третьего Зблока равления записью . блока хранения памяти, к выходу опроса блока 9 суммато- маркировок предшествующего уровня, четров, к входам признака записи 4 регистров, вертый и пятый информационные выходы— к входам бпроса каждого блока 5.1 — 5.rn к первому и второму информационным вхосхем сравнения группы и блока 7 вычитания 20 дам блока хранения маркировок предшестматриц, к входу призйака зайиси регистра вующего 18 уровня, третий

6 результатов-сравнения, к входу опроса . информационный вход — ко второму инфор-, блока8умноженйяматрицивходупризнака мационному входу блока хранения маркичтения третьего блока 3 памяти соответст- ровок 16, к выходу первого счетчика 34, вход венно, а также блок вычисления маркировок 25 управления записью — к выходу второго бло15, блок хранения маркировок 16, блок за- ка сравнения, ко входу элемента задержки писи маркировок текущего уровня 17, блок. 30, ко входу управления записью блока храхранения маркировок предыдущего уровня нвнйя маркировок 16, второй выход которо18, генератор импульсов перезаписи 19, ro подключен к входу обнуления второго и первый — шестой регистры 20 — 25, первый 30 третьего регистров, к входу первого 20 реги- .

34, второй 33, третий 35 счетчики, первый 32 стра, третий информационный вход — к выи второй 31 блоки сравнения, элемент за- ходу третьего счетчика 35, четвертый держки 30, ключ 27, два элемента ИЛИ 28, информационный вход — к выходу пятого

29, одновибратор 26, выход которого под- регистра 24; вход которого подклюЧен к ключен к счетным входам первого и второго 35 третьему информационному выходу блока счетчиков, к входу управления считыванием хранения маркировок предшествующего блока вычисления маркировок, а вход — к уровня, четвертый информационный вход— выходу nepeoro элемента ИЛИ, первый вход к управляющему входу ключа, к выходу перкоторого является входом запускаустройст- вого блока сравнения, к входу обнуления ва 36, второй вход подключен к выходу клю- 40 второго счетчика 33, выход которого подч а, третий вход — к первому ключен к первому входу первого блока сравинформационному выходу блока хранения нения 32, второй вхоД которого подключен маркировок предшествующего уровня, чет-" к выходу четвертого регистра 23, информавертый вход — к счетному входу обнуления, ционный вход ключа 27 подключен к выходу первого счетчика, к входу управления обну- 45 второго элемента ИЛИ 29, первый и второй лением блока хранения маркировок пред- входы которого подключены соответствен- . шествующего уровня, к первому входу но к выходу элемента задержки и к выходу генератора импульсов перезаписи, к перво- блока сравнения с. нулем 10, выход второго му информационному выходу записи марки- регистра подключен к nepeovy входу второровок текущего уровня, пятый вход — к 50 го блока сравнения 31, второй вход которого первому информационному выходу блока подключен к выходу третьего регистра 22, хранения маркировок 16, шестой вход — к информационный вход которого подключен первому выходу результатов сравнения к выходу блока сумматоров 9, выход первого блока вычисления маркировок 15, первый реГистра подключен к второму информациинформационный выход которого является 55 онному входу блока регистров 4, вход шесвыходом достижения заданной маркировки того 25 регистра соединен с четвертым устройства, второй выход результатов срав- выходом блока хранения маркировок преднения подключен к входу управления обну- шествующего уровня 18. лением блока хранения маркировок 16, Устройство работает следующим обраинформационный вход — к выходу шестого зом.

1809448

Импульс запуска подается на вход 36 устройства, который проходя через элемент

ИЛИ 28 поступает на вход одновибратора

26, с выхода которого соответствующий импульс поступает на вход управления считы- 5 ванием блока вычисления маркировок и счетные входы счетчиков 34 и 33, в которых первоначально записаны были "0", Модуль счета счетчика 33 равен m, а в счетчике 34 хранится текущий номер проверяемой вер- 10 шины дерева маркировок.

Под действием импульса. поступающего на вход управления считыванием блока вычисления маркировок реализуется вычисление дочерней вершины eдереве маркиро- 15 вок по формуле: ,и", j =,и - х С, где х = (1,0,...,0).

Далее в соответствии с вышеописан-. 20 ным алгоритмом полученное значение маркировки сравнивается поэлементно на условие 0 (если это условие не выполняется, то полученнбе значение не является. дочерней вершиной 3, стр. 19) и со значени- 25 ем,и . Если и j =p то выдается !

+1 положительный ответ о достижимости .,и из,и на выход 37 устройства.

Если же и +",J =,и, и 30 ,и, j < о >, то на втором выходе результатов сравнения блока вычисления маркировок возникает импульс, поступающий на- вход управления обнулением блока хранения маркировок, на его первый вход по- 35 ступает значение и j для дальнейших проверок (со второго информационного вы хода блока вычисления маркировок).

В блоке хранения маркировок 16 проис1+1 ходит сравнение и,j со всеми.уже имеющимися в дереве маркировок вершинам (первоначально дерево представлено только корнем), Со второго информационного выхода блока вычисления маркировок на 45 первый вход блока хранения маркировок поступает значение и,j, требующее сравР1 нения с уже имеющимися вершинами, на вход управления обнулением — запускаю. ы ий импульс. При равенстве,и,J = 50, маркировка,и .; J исключается из дальнейшего рассмотрения, вырабатывается импульс "1", который выдается на первый информационный выход блока хранения маркировок и на второй вход ИЛИ 28, инициируя тем самым вычисление следующей ,и . В случае и jj,и, считывается

+1 t+> . О.1 очередная полученная ранее маркировка —. вершина дерева достижимости. При переборе вершин для сравнения с исследуемой,и,j выдается импульс на второй выход бло-!

+» ° ка для инициирования проверки необходимого условия достижимости из,ио,и,j.

По этому сигналу значение первой начальной маркировки заносится из первого

20 регистра блок 4, обнуляется третий регистр 22 (от значения, хранимого в нем от предыдущих циклов работы устройства) и запускается прототип по входу 14 для определения необходимого условия достижимости,и +.,j из ио . При этом, по логике работы прототипа в регистре 9 размещается на каждом шаге маркировка последовательно достижимая из,ио (это же самое заносится и в регистр 22); Если же на определенном шаге работы прототипа в регистре 22 окажется значениеи,j, то тем самым существует необходимое условие достижимости,и,j из ,ио, блок сравнения 31 выдает об этом соответствующий импульсный сигнал. Если необходимое условие не выполняется, в регистр 22 никогда не занесется значение ,и,j, а исследуемая сеть при начальной

»+1

,и достигает своего предела достижимости, и на выходе 12 прототипа "Останов" вырабатывается соответствующий сигнал, являющийся отрицательным ответом íà вопрос достижимости и .J из,и . При этом и исключается из дальнейшего рассмотрения: сигнал с выхода 12 прототипа поступает на второй вход элемента ИЛИ 29 и далее через ключ 27 на третий вход элемента ИЛИ 28 для вычисления проверки очередной дочерней . маркировки (вершины дерева).

В случае положительного ответа на существование необходимого условия достижения маркировки значение -,и j заносится в блок хранения маркировок 16 и блок записи маркировок текущего значения уровня 17 и используется в дальнейших проверках в качестве новой вершины дерева достижимости.

После записи,и,j задержанный им° пульс на величину задержки элемента 30 поступает на вход элемента ИЛИ 29, ключ

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

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

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

25 и пятый 14 регистры соответственно, а также на вход первого элемента ИЛИ и на вход третьего счетчика 35 (для увеличения на единйцу текущего номера уровня дерева достижимости);

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

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

30 вычитания матриц, выход которого подклю50 стров, к входам опроса блоков схем

Устройство прекращает работу, выдавая ответ о недостижимостии из йо.

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

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

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

1809448

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

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

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

1809448

Составитель В. Дорошенко

Техред М.Моргентал Корректор С. Лисина

Редактор

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

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

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

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