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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 448 А 1 5 0 06 Г 15/347, 15/4 ИСАНИ ОБРЕТЕНИ АВТОРСКОМУ С ТЕ ВУ(56) Авторское свидетельство СССРМ 1322312, кл. 6 06 Р 15/347, 1987.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯСЕТЕЙ ПЕТРИ(57) Изобретениеотносится к вычислительной технике и может быть использовано длярешения матричных линейных уравнений иисследования сетей Петри на достижимость, Цель изобретения состоит в расширении функциональных возможностейустройства за счет алгоритмической разреМ Ю ы Изобретение относится к вычислительной технике, может быть использовано для решения матричных линейных уравнений и исследования сетей Петри на достижимость,Целью изобретения является расширение функциональных возможностей за счет обеспечения проблемы достижимости маркировки в СП.На чертеже представлена функциональная схема устройства,Устройство содержит три блока 1 - 3 памяти, блок 4 регистров, группу 5 блоков 5,1-5,п) схем сравнения. где и) - количество переходов в СП, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, выход блока 4 регистров подключен к входу первого слагаемого блока 9 сумматоГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) шимости проблемы достижимости маркировок в сети Петри. Устройство содержит три блока памяти, блок регистров, группу блоков схем сравнения. регистр результатов сравнения, блок вычитания матриц, блок умножения матриц, блок сумматоров, блок сравнения с нулем, блок синхронизации, а также блок выбора маркировок, блок хранения маркировок, блок записи маркировок текущего уровня, блок хранения маркировок предшествующего уровня, генератор импульсов перезаписи, третий, четвертый, пятый, шестой, седьмой, восьмой регистры, первый, второй, третий счетчики, первый и второй блоки сравнения, элемент задержки, ключ, два элемента ИЛИ и одновибратор, 1 ил. ров, первому информационному входу каждого блока 5.1 - 5.а схем сравнения группы, с первого по и)-1 выходы первого блока 1 а памяти подключены к входу вычитаемого Я блока 7 вычитания матриц и вторым входам с первого по и)-й блоков 5,1 - 5;и) схем сравнения групп 5, выходы признаков неотрицательного результата которых подключены к информационному входу регистра б результатов сравнения, выход которого О подключен к входу первого сомножителя блока 8 умножения матриц и информационному входу блока 10 сравнения с нулем, выход признака равенства нулю которого подключен к входу останова блока 11 синхронизации и является выходом "Останова", выход которого 2 блока. памяти подключен к входу уменьшаемого блока 7 вычитания матриц, выход которого подключен к информационному входу третьего блока памяти 3,выход которого подключен к входу второго регистра, второй информационный выход - сомножителя блока 8 умножения матриц, к информационному входу второго региствыход которого подключен к входу второго ра, к первому входа блока хранения маркислагаемогоблока 9 сумматоров,выходкото- ровок 16, к первому информационному рого подключен к информационному входу 5 входу блока записи маркировок текущего блока 4 регистров, вход начальной установ- уровня 17, второй информационный вход ки блока 11 синхронизации одновременно которого подключен ко второму входу гене- подключен к входам начальной установки ратора импульсов перезаписи, третий иинрегистра 6 результатов сравнения, третьего Формационный выход 38 является выходом блока 3 памяти и является входом началь недостижимости устройства, второй инфорной установки 13, вход пуска блока синхро-. мационный вход подключен к второму иннизации является входом 14 пуска, с формационному выходу блока хранения первого по седьмой выходы блока 11 синх- маркировок предшествующего уровня 18,ронизэции подключены квходам признака вход управления обнулением - к выходу гечтения первого и второго блоков памяти 1, 15 нератора импульсов перезаписи, входу уп и входу признака записи третьего Зблокэ равления записью, блока хранения памяти, к выходу опроса блока 9 суммато- маркировок предшествующего уровня, четров, к входам признака записи 4 регистров, вертый и пятый информационные выходы - к входам опроса каждого блока 5.1 - 5,гп к первому и второму информационным вхосхем сравнения группы и блока 7 вычитания 20 дам блока хранения маркировок предшестматриц, к входу призйака зайиси регистра вующего 18 уровня, третий 6 результатов -сравнения, к входу опроса . информационный вход - ко второму инфор-, блока 8 умноженйяматрицивходупризнака мационному входу блока хранения марки- чтения третьего блока 3 памяти соответст- ровок 16, к выходу первого счетчика 34, вход венно, а также блок вычисления маркировок 25 управления записью - к выходу второго бло, блок хранения маркировок 16, блок за- ка сравнения, ко входу элемента задержки писи маркировок текущего уровня 17, блок, 30, ко входу управления записью блока храхранения маркировок предыдущего уровня ненйя маркировок 16, второй выход которо, генератор импульсов перезаписи 19, го подключен к входу обнуления второго и первый - шестой регистры 20 - 25, первый 30 третьего регистров, к входу первого 20 реги- .34, второй 33, третий 35 счетчики,первый 32 стра, третий информационный вход - к выи второй 31 блоки сравнения, элемент за- ходу третьего счетчика 35, четвертый держки 30, ключ 27, два элемента ИЛИ 28, информационный вход - к выходу пятого 29, одновибратор 26, выход которого под- регистра 24; вход которого подклюЧен к ключен к счетным входам первого и второго 35 третьему информационному выходу блока счетчиков, к Входу управлении считыванием хранения маркировок предшествующего блока вычисления маркировок, а вход - к уровня, четвертый информационный вход - выходу первого элемента ИЛИ, первый вход к управляющему входу ключа, к выходу перкоторого является входом запускаустройст- вого блока сравнения, к входу обнуления ва 36, второй вход подключен к выходу клю второго счетчика 33, выход которого подч а, третий вход - к первому ключен к первому входу первого блока сравинформационному выходу блока хранениянения 32, второй. вхоД которого подключен маркировок предшествующего уровня, чет- к выходу четвертого регистра 23, информавертый вход - к счетному входу обнуления, ционный вход ключа 27 подключен к выходу первого счетчика, к входу управления обну второго элемента ИЛИ 29, первый и второй лением блока хранения маркировок пред- входы которого подключены соответствен- . шествующего уровня, к первому входу но к выходу элемента задержки и к выходу генератора импульсов перезаписи, к перво- блока сравнения с нулем 10, выход второго му информационному выходу записи марки- регистра подключен к первому входу второровок текущего уровня, пятый вход - к 50 го блока сравнения 31, второй вход которого первому информационному выходу блока подключен к выходу третьего регистра 22, хранения маркировок 16, шестой вход - к информационный вход которого подключен первому выходу результатов сравнения к выходу блока сумматоров 9, выход первого блока вычисления маркировок 15, первый реГистрэ подключен к второму информациинформационный выход которого является 55 онному входу блока регистров 4, вход шесвыходомдостижениязаданноймаркировки того 25 регистра соединен с четвертым устройства, второй выход результатов срав- выходом блока хранения маркировок преднения подключен к входу управления обну- шествующего уровня 18.лением блока хранения маркировок 16, Устройство работает следующим обраинформэционный вход - к выходу шестого зом.ных запускающих одновибратором 26 импульсов (т.е, из корневой вершины получены все возможные дочерние маркировки) и этот же сигнал подается на четвертый вход блока хранения маркировок предшествующего уровня, по которому из этого блока в регистры 25 и 24 заносится соответственно следующая (если такая же имеется в блоке хранения маркировок предшествующего уровня) маркировка предыдущего уровня и ее номер 1 на предыдущем уровне.После того как перебраны все вершины предшествующего уровня, для каждой из которых найдены дочерние вершины, которые в свою очередь образуют множество маркировок текущего уровня, необходимо искать дочерниевершины для вновь полученных вершин, т.е. осуществить построение дерева достижимости далее. Импульс со второго вь 1 хода.блока 18 поступает на второй 84 вход блока записи маркировок текущего уровня 17. При этом содержимое счетчика записи, имеющегося в блок 17, соответствующее числу полученных вершин на последнем уровне дерева, поступает в блок сравнения с нулем блока 17, и если число вершин последнего уровня больше нуля, то выдает сигнал импульсной "1", поступающий.на второй выход блока записи маркировок текущего уровня. По этому сигналу, поступающему на второй вход генератора импульсов перезаписи 19, последний выдает импульсы для перезаписи вершин, полученных натекущем уровне дерева, в . блок хранения маркировок предшествующего уровня. Период следования этих импульсов выбирается не меньшим интервала перезаписи информации из ячеек памяти блока 17 в аналогичные ячейки памяти блока 18, Каждый импульс соответствует акту перезаписи одной ячейки, Одновременно сигнал с первого выхода блока записи маркировок текущего уровня подается вход управления обнулением блока хранения маркировок предшествующего уровня для считывания очередной Маркировки на третий и четвертый выходы. блока 18 в шестой 25 и пятый 14 регистры соответственно, а также на вход первого элемента ИЛИ и на вход третьего счетчика 35 (для увеличения на единицу текущего номерауровня дерева достижимости); Если ни одна вершина последнего уровня не имеет дочерней вершины, т.е, соответствующие маркировки недостижимы, блок 17 выдает сигнал на первый выход блока записи маркировок маркеров текущего уровня, свидетельствующий о недостижимости,и из ро .10 15 ройства, выход второго блока памяти подключен к входу уменьшаемого блока 30 вычитания матриц, выход которого подклю 50 стров, к входам опроса блоков схем 20 25 35 40 Устройство прекращает работу, выдавая ответ о недостижимостир из роФормула изобретения Устройство для исследования сетей Петри, содержащие три блока памяти; группу блоков схем сравнения, блок сумматоров, блок регистров, блок умножения матриц, блок сравнения с нулем и блок синхронизации, причем, выход блока регистров подключен к входу первого слагаемого блока сумматоров и первым информационным входам блоков схем сравнения группы, с первого по В-й выходы первого блока памяти, где Й - количество строк в исходных матрицах, подключены к входу вычитаемого блока вычитания матриц и вторым информационным входам с первого по й-й блоков схем сравнения группы, выходы признаков неотрицательного результата которых подключены к информационному входу регистра результатов сравнения, выход которого подключен к входу первого сомножителя блока умножения матриц и информационному входу блока сравнения с нулем, выход признака равенства нулю которого подключен к входу останова блока синхронизации и является информационным выходом устчен к информационному входу третьего блока памяти, выход которого подключен к входу второго сомножителя блока умножения матриц, выход которого подключен к входу второго слагаемого блока сумматоров, выход которого подключен к информационному входу регистров, вход начальной установки блока синхронизации подключен к входам начальной установки регистра результатов сравнения и третьего блока памяти и является входом начальной установки устройства, вход пуска блока синхрониэации является входом пуска устройства с первого по седьмой выходы блока синхронизации подключены к входам признака чтения первого и второго блоков памяти и входу признака записи третьего блока памяти, к входу опроса блока сумматоров, к входу признака записи блока регисравнения группы и блока вычитания матриц, к входу признака записи регистра результатов сравнения, к входу опроса блока умножения матриц и к входу признака чтения третьего блока памяти, соответственно, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения достижимости маркировки в сетях Петри, дополнительно введены блок вычисления маркировок, блокхранения маркировок, блок записи маркировок текущего уровня, блок хранения маркировок предшествующего уровня, генератор импульсов перезаписи, первый -шестой регистры, первый, второй, третийсчетчики, первый, второй блоки сравнения,одновибратор, выход которого подключен к счетным входам первого и второго счетчиков, к входу управления считывания, блока10вычисления маркировок, а вход - к выходупервого элемента ИЛИ, первый вход которого является входом запуска устройства, второй вход подключен к выходу ключа, третий вход - к первому информационному выходу блока хранения маркировок 15предшествующего уровня, четвертый вход -к счетному входу третьего счетчика, к входуобнуления первого счетчика, к входу управления обнулением, блок хранения маркировок предшествующего уровня, к первому 20входу генератора импульсов перезаписи, кпервому информационному выходу блока записи маркировок текущего уровня, пятыйвход - к первому информационному выходублока хранения маркировок, шестой вход - к первому выходу результата сравненияблока вычисления маркировок; первый информационный выход которого является выходом достижения заданной маркировки30устройства, второй выход результатов сравнения подключен к входу управления обнулением блока хранения маркировок, информационный вход - к выходу шестогорегистра, второй информационный выход - к информационному входу второго регист ра, к первому информационному входу блока хранения маркировок, к первому информационному входу блока записи маркировок текущего уровня, второй информа 40ционный выход которого подключен к второму входу генератора импульсов перезаписи, третий информационный выход которого является выходом недостижимостиустройства, второй информационный вход подключен к второму информационному выходу блока хранения маркировок предшествующего уровня, вход управления обнулением - к выходу генератора импульсов перезаписи, к входу управления записью блока хранения маркировок предшествующего уровня, четвертый и пятый информа.ционные выходы - к первому и второму информационным входам блока хранения маркировок предшествующего уровня, третий информационный вход - к второму информационному входу блока хранения маркировок, к выходу второго счетчика, вход управления записью - к выходу второго блока сравнения, к входу элемента задержки, к входу управления записью блока хранения маркировок, второй выход которого подключен к входу обнуления второго регистра, к входу первого регистра, третий информационный вход -к выходу третьего счетчика, четвертый информационный вход - к выходу пятого регистра, вход которого подключен к третьему информационному выходу блока хранения маркировок предшествующего уровня, четвертый информационный выход которого подключен к входу шестого регистра, третий информационный вход - к управляющему входу ключа, к выходу первого блока сравнения, к входу обнуле-. ния второго счетчика выход которого подключен к первому входу первого блока сравнения, второй вход котороо подключен к выходу четвертого регистра, информационный вход ключа подключен к выходу второго элемента ИЛИ, первый и второй входы которого подключены соответственно к выходу элемента задержки и к выходу блока сравнения с нулем, выход второго регистра подключен к первому входу второго блока сравнения, второй вход которого подключен к выходу третьего регистра, информационный вход которого подключен к выходу блока сумматоров, выход первого регистра подключен к второму информационному входу блока регистров.Составитель В. ДорошенкоТехред М,Моргентал Корректор С. Лисина Тираж нного комит 113035, М енно-издатПодписноеета по изобретениям и открытиям при ГКНТ СССРсква, Ж, Раушская наб,4/5льский комбинат "Патент", г, Ужгород, ул.Гагарина, 10