Устройство для исследования сетей петри
Изобретение относится к вычислительной технике, может быть использовано для решения линейных матричных уравнений и позволяет исследовать матричное представление сетей Петри на достижимость. С этой целью в состав устройства входят три блока 1,2 и 3 памяти, блок 4 регистров, группа 5 блоков 5-1,...,5-k схем сравнения , где k - количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц , блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем , блок 11 синхронизации, информационный выход 12 устройства, вход 13 начальной установки и вход 14 пуска устройства. В исходном состоянии в блоках 1 и 2 памяти записаны матри (Л Фиг /
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН
„.Я0„„1322312
А1 (511 4 G 06 F 15 347
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4016682/24-24 (22) 04.02.86 (46) 07.07.87. Бюл. У 25 (72) Б.М.Герасимов, С.Ю.Переваров и С.Ч.Колесник (53) 681.325 (088.8) (56) Авторское свидетельство СССР
В 647687, кл . G 06 F 15/347, 1976.
Авторское свидетельство СССР
Ф 482749, кл. С 06 F 15/347, 1972. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ
СЕТЕЙ ПЕТРИ (57) Изобретение относится к вычислительной технике, может быть использовано для решения линейных матричных уравнений и позволяет исследовать матричное представление сетей Петри на достижимость. С этой целью в состав устройства входят три блока 1,2 и 3 памяти, блок 4 регистров, группа 5 блоков 5-1,...,5-1 схем сравнения, где k — количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства, вход 13 начальной установки и вход 14 пуска устройства. В исходном состоянии в блоках 1 и 2 памяти записань1 матри 322312 цы входо13 I I Выходон сетll !1ет!3«соот
neTcTneIIfto, а в блоке 4 — э11,.<«ение начальной маркировки. После пуска производится сраззнение элементо13 каждой строки матрицы входов с с< от13етствуюшим элементом маркировк11, «р11 этом результат cpa»!le!If»t — <.It! It!»fry длл тех строк, все элеме«т11 которых боль<не пли ра1зны coo TIIoòcò» <лоц«м элементам маркировки, и «о;и. — 1з «ротивном случае — используется 13 качестве первого сом«аж«талл блока 8, на вход второго сомножителя катар >гo поступает результат вьв»1та1«1л матр«Изобретение относится к вычис:1«тельной технике If может 6ыт1, исп >ль onafIo для исследования сетей !1етр11 на достижимость.
Цель изобретения — расшире «Io кпао-5 сВ решаемых задач за счет осуществле«ил анализа сетей Петр« ff;x;IocT»,1<имасть.
На фиг. 1 представле»а <11у»1;Jilfo
«аль»ал схема устройст»а; на ф11г. 2 пример р< алиэации 6«ока синзсрош! з»l1lttt устройства. у с T p i7 It c T I3 о дл л и с с л е д о 13 а н 31 л с е т B l f
lIe грп со;1ержит l p» 6«ока 1-3 «;<мяти, 6л<зк -< рс гистро», груп.; 5 <> <оков
5-1,..., 57-1с с, м сравне»ия, где к <7«11-1 ес-. no с грок» ffcxo<1«1,1х . <атридах, рогlfc гр 6 реэультато13 < !за1111ен«л, 631О1с 7 tfhf 1«та«11л мат!зи1<, 6 Iof ноже1п|л tfaтриц, блок 9 сум:.f«торов, блок 10 сравнения с нуле f и 6:1ок 11 синхро1гизации, «pl«teil в11ход блока 4 рег1<строн подкл1очен к входу первого слагаемого блока 9 сумматоров и первому информационному входу 1;аж;1<зго блока 5-1,...,5-1с схем сра13»е«ил грун«ю, с первого по k и выхлопы «ер»ог о блока 1 «B IIITII подклночены к дхоцу вычитaef oão 6.1ока 7 в tat » блок 4. Процесс продолжается до. тех «ор, пока результат сравнения «е станет ранен нулю по всем строкам матрицы входов. В этом случае блок 10 1<ормпрует сигнал, свидетельствующий о том, чгo сеть Петри при данной начальной маркировке достигла предела выполгн1 ости, т.е. такого состояни, когда все переходы запрещены. 2 ил. те.tÿ 6лoка 8 умножения матриц и информационному входу блока 10 сравне»ил с »упем, выход признака равенства нул1о которого подкл<очен к входу останова бл<гка 11 синхронизации и являетсл информационным выходом 12 устройства, выход второго блока 2 памяти «Одключе« к входу уменьшаемого блока 7 вычита«ия матриц, выход которого подключен к информационному входу третьего блока 3 памяти, выход которого подкп очен к входу второго сомножителя блока 8 умножения матриц, выход которого подключен к входу второгo сз1.<гаемогo блока 9 сумматоров, вы:од которого подключен к информацио!I!lofty входу блока 4 регистров, вход ! fft «одклн1чены к входам признака чтения «ер»ого и второго блоков 1 и 2 памят:1 и входу признака записи третьего блока 3 памяти, к входу опроса блока 9 сумматоров, к входу признака записи блока 4 регистров, к входам опроса казкдого блока 5- 1,...,5-k схем сравнения группы и блока 7 вычитания матриц, к входу признака записи регистра. 6 результатов сравне1322312! f5 1110 0001 0010 1000 0210 0001 Π— 1 — 10 0+2+1 †ΠΠ— 1+1 Π— 1 — 1 О 0+ 2+ 1 — 1 00 †1 р = ш+ х-д. ния, к входу опроса блока 4 умножения матриц и входу признака чтения третьего блока 3 памяти соответственно. Блок 11 синхронизации (фиг.2) содержит триггер 22, элементы И 23-25, генератор 26 тактовых импульсов, счетчики 27 и 28, регистры 29 и 30, элементы НЕ 31 и 32, элементы 33-37 задержки и элемент ИЛИ 38. Устройство работает следующим образом. В исходном состоянии схемы в блоке 1 находится матрица входов Д например + а в блоке 2 — матрица выходов Д например т.е. данная сеть Петри имеет четыре 30 позиции и три перехода. Первоначальная маркировка находится в блоке 4 и имеет вид: Требуется определить достижима ли t маркировка р из маркировки !! Предполагают, что маркировка (и достижима из маркировки р . Тогла су. 40 ществует последовательность (возможно пустая) запусков переходов б, которая приводит из ш к ш . Это означает, что й(б) является неотрицательным целым решением следующего матричного 45 уравнения для Х Если р достижима из pè, уравнение (1) 50 имеет решение в неотрицательных целых, если уравнение (1) не имеет решения, не достижима из Под действием синхросигналов с блока 11 информация с выхода блока 1 поступает на вторые входы блоков 5-1,...,5-k схем сравнения группы, где происходит ее сравнение со значением начальной маркировки, поступаюшей ня IIEpвые входы всех блоков 5-1,...,5-k. Если результат срав— пения больше или равен нулю по всем сравниваемым элементам строки матрицы Д, в соответствующий разряд регистра 6 записывается единица, иначе нуль. Таким образом, при сравнении первоначальной маркировки (1, О, 1, 0) со строками матрицы Д, только третья строка удовлетворяет правилу сравнения. Это означает, что срабатывание третьего перехода разрешено. В регистре 6 записано (О, О, 1). Параллельно информация иэ блока 2 поступает на вход уменьшаемого блоKà 7, на вход вычитаемого которого поступает информация с блока 1. Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле: Д = Д+ — Д Значение полученной составной матрицы изменений Д записывается в блок 3. Она имеет вид: Дальше работа схемы направлена на реализацию формулы (1). Подставляя полученные значения, она имеет вид: =(1, О, 1, 0)+(0, О, 1) Под действием управляющих сигналов с блока 11 информация из блока 3 поступает в блок 8, где происходит перемножение матриц, Результат умножения (О, О, — 1, +1) поступает в блок 9, где происходит сложение результата произведения со значением маркировки, в результате чего получается новая маркировка сети Петри (1, О, О, 1), которая заносится в блок 4. Процесс работы устройства повторяется. На каждом шаге работы устройства происходит проверка кода, находящегося в блоке 4, т.е. последовательности запуска переходов на нуль в блоке 10. Если информация больше нуля, процесс работы продолжается. Если последова1322312 тельность запуска переходов равна нулю, блок 10 вырабатывает сигнал, свидетельствующий о том, что сеть Петри при данной начальной маркировке достигла предел выполнимости, т.е. 5 достигла такого состояния, когда все переходы запрещены. Таким образом, устройство для исследования сетей Петри позволяет производить анализ сетей Петри 11» достижимость. Блок 11 синхронизации (фиг.2) работает следующим образом. Первоначально триггер 22 нахо! 5 дится в нулевом состоянии. По сигналу начальной установки, который, пройдя через э:1емент !!НИ 23, поступ»ет и» входы записи счетчиков 27 и 28, npott»13oд1п ся запись информ»цип с сооТ 33 Отс твующего регистра 29, Где хранит- 20 СЯ 111С.:10 CTPOI< IICXOДНОй tt»Tl>ltII!1, регttcтр» 30, где xp;»!»TcII !1!с 3!о стобцов исходной матрицы. С нрпходoM спгн»л» по входу l- t Пус1;" триггер 22 переходит в единичное состсt! t!1!e и высокий потенциал с его пря:.!ОГО 13b! хоца разрешает прохоя,-1е11ие т»ктоиых импульсов с генератор» 26 через элеь;ент И 23. Импульсы:!оступ»ют на вы«птающий вход счетчи!!» 27 1! проход1!1 ! Орсз э31смент И 2ч, От1;рытый высоким 110 т О 11!П!»3!им С выХО13» 1! (;".!1О 131е IIIISI счетчика 27. С т311хоца элемента И 2ч импульсы пос гул»к!т н» перв11!! т!ыход 15 блока 11 35 и 1 ро!!дл через элемсгсгы 36 и 37 эадс13жк!1, поступают соответственно на четверт1гй и пятый выходь! 18 и 19 блока 11. !!Ос Iе ТОГО к»к соде!3ж11мое с 1етчи 40 к» 27 станет р»нным нулю, на егo выходе переполнения появится низкий потенциал, который закроет элемент И 2А и, пройдя через элемент !!Е 31, откроет элемент И 25. Тактовые импульсы 45 начнут поступ»ть на вычитаюший вход счетчик» 28, на седьмой выход 21 блок» и, пройдя через элементы 34 и 35 з»цсржки, на шестой и второй вь1ходы 20 и 16 блока 11 соответствснно. После обнуления счетчика 28 низкий потенц3!ал с его выхода пройдет через элемент HF. 32, элемент 33 э»дсржки и поступит на третий выхоц 17 блока 11, пройдет через элемент ИЛИ 38 и !!оступит на входы записи счетчиков 28 и перепишет на них содержимое соответству3ощ3!х регистров 29 и 30. процесс работы блока повторяется. Работа продолжается до тех пор, пока на вход 12 останова блока не поступит сигнал, который установит триггер 22 в нулевое состояние, низкий потенциал с его прямого вьгхода запретит прохождение тактовых импульсов с генератора 26 через элемент И 23. Таким образом, устройство для исследования сетей Петри позволяет выяснить возможность функционирования модели, представленной в виде сети Петри, т,е. произвести анализ на достижимость. формул»изобретения Устройство для исследования сетей Петри, содержащее два блока памяти, группу блоков схем сравнения, регистр результатов сравнения и блок суы."!»торов, о т л и ч а !о щ е е с я тем, «то, с целью расширения класса решаемых задач за счет осуществления ана пиза сетей Петри на достижимость, в него введены третий блок памяти, блок регистров, блок вычитания матриц, б.!ок умножения матриц, блок сравнения с нулем и блок синхронизации, причем выход блока регистров подключен к входу первого слагаемого блока сумматоров и первым информациО1п!!.!и входам блоков схем сравнения группы, с первого I!o k-й выходы первого блока памяти, rpe k — количество строк в исходных матрицах, подклю-! ены .к входу вычитаемого блока вычитания матриц и вторым информационным входам с первого по k-й блоков схем сравнения группы, выходы признаков неотрицательного результата которых подключены к информационному входу регистра результатов сравнения, выход которого подключен к входу первого сомножителя блока умножения матриц и информационному входу блока сравнения с нулем, выход признака равенства нулю которого подключен к входу останов» блока синхронизации и является информационным выходом устройства, выход второго блока памяти подк;почен к входу уменьшаемого блока вычит»ния матриц, выход которого подключен к информационному входу третьего блока памяти, выход которого подкл!очен к входу второго сомножителя блока умножения матриц, выход которого подключен к входу второго слагаемого блока сумматоров, выход ко1322312 2f Риг. 2 Составитель А.Мишин Техред Л.Олийнык Корректор Г.Решетник Редактор Н.Рогулич Заказ 2867/47 Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,4 торого подключен к информационному входу регистров, вход начальной установки блока синхронизации подключен к входам начаЛьной установки регистра результатов сравнения и третьего блока памяти и является входом начальной установки устройства, вход пуска блока синхронизации является входом пуска устройства, с первого по седьмой выходы блока синхронизации под в 10 ключены к входам признака чтения первого и второго блоков памяти и входу признака записи третьего блока памяти, к входу опроса блока сумматоров, к входу признака записи блока регистров, к входам опроса блоков схем сравнения группы и блока вычитания матриц, к входу признака записи регистра результатов сравнения, к входу опроса блока умножения матриц и к входу признака чтения третьего блока памяти соответственно. 
