Устройство для моделирования сетей Петри Советский патент 1992 года по МПК G06F15/173 

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

Известны методы моделирования СП на ЭВМ с расчетом всех достижимых маркировок. . (

Однако моделирование на ЭВМ динамики СП связано с трудностями разработки и отладки программ и достаточно большей длительностью моделирования. Кроме того, управляющее устройство, реализованное на основе СП с помощью ЭВМ, обладает низким быстродействием и требует значительных затрат памяти.

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

Недостатком данного устройства является то, что оно пригодно для исследования на достижимость узкого класса СП, а именно обычных (или оригинальных) СП. Обычные СП используются при построении моделей систем взаимодействующих обьектов и представлении причинно-следственных связей между ними без учета временных характеристик моделируемых событий. В обычной СП срабатывание перехода рассматривается как мгновенное событие,, занимающее нулевое время, моделируемое таким образом событие называется примитивным. При построении моделей реальных систем очень важным является учет временных характеристик моделируемых событий/ Это обстоятельство существенно сужает ббласть применения устройства, В реальном мире большинство событий занимают некоторое ненулевое время, т.е. они не являются примитивными и не могут моделироваться переходами обычных СП. Это явилось причиной разработки различных подклассов СП для моделирования реальных систем с непримитивными событиями и с учетом всех временных характеристик. К таким подклассам относятся временные СП и сети Мерлина, тайм-аутные и временные СП, Есети.

На практике для составления модели необходимо иметь как примитивные, так и непримитивнь1е переходы Cfl что требует выбора подкласса СП. Таким подклассом являются модифицированно-временные СП (МВСП).

МВСП - это двупольный граф, характеризуемый четверкой

N(P,T,1,0),

где Р {pi,...,pn} конечное MHoxedTBO позиций, п 0;/

Т Тпр Твр - конечное множество временных Твр и простых Тпр переходов, Твр {tbitbn}- n 0; Тпр {tni,...,tni}, I 0:

РПТ(Й,

входная функция, ставящая в соответствие каждой паре (pi.tj) некоторое количество (вес) дуг, ведущих из pibtj,- i 1 ,п, j 1,n+l;

rv(pi, tj), если PI является входной

позицией перехода; i(tj)Jpi etj; V (pi, tj) О,0, если PI и tj не связаны дугой, -Pi tj - множество входных позиций (1ерехода,

О : - выходная функция, ставящая в соответствие каждой паре (tj, pi) некоторое количество (вес) дуг, ведущих из tjbpi;

rw(pj, ti), если pi является выходной позицией перехода;

0(tj)tj; PI etj;

, если ti И PI не связаны дугой,

tj - множество выходны-х позиций перехода tj.

Топология МВСП описывается функциями 1 и О, представленными как правило матрицами.

Динамические свойства МВСП, как и любого другого подкласса СП, определяются с-помощью понятия Маркировка. Маркировка /л - это функция, отображающая множество позиций Р в множество неотриг цательных целы,х ицг.ел;

г {m(pi),m(p7jm(pn)}.

Маркировка СП N изменяться в результате срабатыпйнич переходов. В МВСП задаются следуюьсС правила срабатывания переходов. Простой (примитивный) переход становится активным и срабатывает, , если,

Ypietj m(pi)S v(pi,tj),(-1)

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

0 происходит мгновенно. Временной переход становится активным и срабатывает при одновременном вьтолнении двух условий. Первое условие - это условие активности для простого перехода, второе - временной

5 переход может срабатывать в определен. ные моменты времени, §i, , ...,

т.е. временной переход имеет свой случайный закон распределения времен срабатывания. При наступлении Момента времени § и

0 наличии необходимого числа меток во всех

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

Новая разметка МВСП находится по правилу

0 X(pi)/(pi)-Ktj) + o(tj).

, -./

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

5 маркировкой, образуют множество достижимых маркировок. Маркировка, не порож- . дающая ни одной последовательности срабатывания переходов, называется тупиковой. Обычно задается интервал моделирования Тмод,, .в течение которого .исследуется достижимость вектора разметки МВСП., Целью изобретения является расширение функциональных возможностей устройства за счет моделирования временных сетей Петри.

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

0 переходов k элементов И, где k - количество строк в исходных матрицах, блок выбора времени, элемент задержки, причем информационные выходы первого регистра результата сравнения подключены соответ5 ственно к первым входам k элементов. И, вторые входы хоторых соединены соответственно с информационными выходами ре- . гистра признака типа переходов, выходы k элементов И соединены с информационными входами второго регистра результата сравнения, Е1ыход которого подключен к входу первого сомножителя блока умножений матриц к информационному входу бл,ока сравнения с нулем, входы регистра признака типа перехода, соответствующие временным переходам МВСП, соединены соответственно с информационными выходами блока выбора времени, вход которого соединен с выходом признака равенства нулю блока сравнения с нулем, выход Пуск блока выбора времени соединен с входом пуска устройства, выход Превышение блока выбора времени является информационным выходом устройства. Число информационных выходов блока выбора времени равно числу временных переходов в сети. Согласно изобретению сначала в МВСП срабатывают переходы, принадлежащие к множеству простых. Так происходит до тех пор, пока не возникнет тупиковая маркировка - ни один из множества простых переходов не может сработать. Затем определяется ближайшее время срабатывания перехода, принадлежащего к множеству временных. Если к этому моменту для него выполняется условие (1), то дранный переход срабатывает, измейяется маркировка в сети, увеличивается модельное время на величину At (где At - интервал между предыдущим и настоящим ближайшим моментами активности переходов), определяется следующий момент срабатывания сработавшего временного перехода. Далее вновь срабатывают переходы из множества простых. Если условие (1) хе выполняется, то переход не срабатывает, вектор разметки остается прежним, модельное время увеличивается на At, определяется следующий момент срабатывания этого перехода и вновь определяется переход из множества временных с ближайшим временем срабатывания.

На фиг.1 приведена функциональная схема устройства; на фиг.2 - алгоритм его работы; на фиг.З - схема реализации блока выбора времени; на фиг.4 - рассматриваемая МВСП.

Устройство для моделирования на основе сетей Петри содержит три блока 1-3 памяти, блок 4 регистров, группу 5 блоков 5.1,.,..5.kcxeM сравнения, где k-количество строк в исходных матрицах, регистры б и 24 результатов сравнения, блок 7 вычитания .матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства, вход 13 начальной установки, вход 14 пуска устройства, семь выходов 15-21 блока синхронизации, блок 22 выбора времени, регистр 23 признака типа переходов, группу 25 из k элементов И, элемент 26 задержки, группу быходов 27 Запрос, группу входов 28 Число, причем выход блока 4 регистров подключен к еходу первого слагаемого блока 9 сумматоров и первому информационному входу каждого блока 5.15.k схем сравнения .

0 группы, с первого по k-й выходы первого блока 1 памяти подключены к входу вычитаемого блока 7 вычитания матриц и вторым входам с первого по k-й блоков 5.1

5.k схем сравнения группы 5, выходы признаков неотрицательного результата которых подключены к информационному входу первого регистра 6 результатов сравнения, информационные выходы которого подключены соответственно к первым входам k элементов И группы 25, выходы которых подключены к соответствующим информационным входам второго регистра 24 результатов сравнения, выход которого подключен к входу первого сомножителя, блока 8 умножения матриц и информационному вход у блока 10 сравнения с нулем, выход признака равенства нулю которого подключен к входу О блока 22 выбора времени и входу останова блока 11

0 синхронизации, выход второго блока 2 памяти подключен к входу уменьшаемого блока 7 вычитания матриц, выход которого подключен к информационному входу третьего блока 3 памяти, выход которого

5 подключен к входу второго сомножителя блока 8 умножения матриц, выход которого подключен к входу второго слагаемого блока 9 сумматоров, выход которого подключен . к информационному входу блока 4 регистров, вход начальной установки блока 11 синхронизации подключен к.входам начальной установки регистров 6 и 24 результатов сравнения и третьего блока памяти 3 и является входом 13 начальной установ5 ки устройства, вход пуска блока синхронизации является входом 14 пуска устройства и соединен с выходом Пуск . блока выбора времени, с первого по седьмой выходы 15г21 блока 11 синхронизации подключены к входам признака чтения первого и второго блоков 1 и 2 памяти и входу признака записи третьего блока 3 памяти, входу опроса блока 9 сумматоров, входу признака записи блока .4 регистров,

5 входам опроса каждого блока 5.15.k

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

входу опроса блока 8 умножения матриц и входу признака чтения третьего блока 3 памяти соответственно, вторые входы k элементов И группы 25 соединены с соответствующими выходами регистра 23 признака типа переходов, число входов которого равно числу h временных переходов в сети, входы регистра 23 результатов сравнения соединены с информационными выходами блока 22 выбора времени, выходы 27 запроса которого образуют группу выходов устройства для подключения к входам запроса соответствующих датчиков случайных чисел (ДСЧ), входы 28 Число которого образуют группу входов устройства для подключения к выходам соответствующих ДСЧ.

Схемы блоков предлагаемого устройства, кроме блока 22 выбора времени, известны.

Блок 22 выбора времени содержит генератор 37 тактовых импульсов, три элемента ИЛИ 30,36 и 38, триггер 40, элемент 29 задержки, элемент И 39, группу h регистров 31 хранения моментов ближайших времен, где h-число временных переходов в сети, группу h 33 реверсивных счетчиков, группу h сумматоров 32, группу h RS-триггеров 34, группу h элементов 35 задержки.

Схемы элементы И, ИЛИ, RS-триггеров, генератора тактовых импульсов, сумматоров, реверсивных счетчиков, регистров и элементов задержки.

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

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

11000 00010

00100 00010

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

10000 02100 00010 00001

в регистре признаков 23 типа переходов записано 1010, т.е. данная МВСП имеет пять позиций и четыре перехода, причем первый и третий переходы принадлежат к множеству простых, а второй и четвертый - к множеству временных, о чем свидетельствуют соответственно единицы и нули в регистрепризнака переходов, Перг воначальная маркировка находится в блоке 4 и имеет вид / (1,0,1,0,0).

Требуется определить достижима ли маркировка ju из маркировки /г.

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

(2)

ц /f +XD,

где D D - составная матрица изменеНИИ.

Если /г/достижима из/г, уравнение (2) имеет решение в неотрицательных целых, если уравнение (1) не имеет решения, то /г не достижима из W .

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

начальной маркировки, поступающей на.

первые входы всех б/юков 5.15.k. Если

результат сравнения больше или равен нулю по всем сравниваемым элементам строки матрицы D, в соответствующий разряд

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

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

выполняется условие (1). Для этого информация с регистра 6 поступает на первые входы соответствующих элементов И 25, на вторые входы которых поступает информация с регистра признака типа переходоэ, в котором записано (1,0,1,0),т.е. в

МВСП ti и t3 - простые переходы, а t2 и t4 временные. В результате во второй регистр 24 результата сравнения записывается (0,0,1,0), т.е. в данный момент в МВСП

активен и срабатывает ta. Параллельно информация из блока 2 поступает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация с блока 1. Блок 7 под действием управляющих сигналов с блока 11-реализует операцию вычитания матриц по формуле 0 D. Значение полученной составной матрицы изменений D записывается в блох 3. Она имеет вид 0-1000 021-10 00-1+10 000-11 Дальше работа схемы направлена на реализацию формулы (1), Подставляя полученные значения, она имеет вид: 0-1 000 О 21-10 /г (1.0,1.0,0) + (0,0.1.0)х О 0-1+1 О О О О 1 Под действием управляющих сигналов с блока 11 информация с блока 3 поступает в блок 8 и перемножается. Результат умножения (0,0,-1il,0) поступает в блок 9, в котором происходит сложение результата произведения со значением маркировки, в результате чего получается новая маркиров ка МВСП (1, 0,0,1,0) , которая заносится в блок 4 также по сигналу из блока 11. Процесс работы устройства повторяется. На втором шаге в регистр 6 сравнения записывается (0.1,0,l)i т.е. для t2 и t4 выполняется условие (1). Во второй регистр 24 результата сравнения записывается (0,0,0,0), так как t2 и t4 - временные переходы и пока сработать не могут. .Необходимо определить, у какого из них момент срабатывания наступает раньше. На каждом шаге работы устройства происходит проверка кода, находящегося в блоке 24, т.е. последовательности запуска переходов на нуль в блоке 10. Если информация равна О, как в данной ситуации, то блок 10 вырабатывает на своем выходе сигнал 0, т.е. МВСП достигла такого состояния, когда все простые переходы запрещены. Сигнал с выхода 0 временно останавливает работу блока синхронизации vi поступает на вход блока 22 выбора времени. Блок 22 определяет, из какого из всех временных переходов сети наступит ближайший момент времени его срабать)еания. После определения такого перехода блок 22 на время продолжительности одного шага работы устройства в cooTaetCTвующем разряде регистра 23 признака типа перехода устанавливает 1, вырабатывает сигнал Пускдля повторного пуска блока 11 и делает приращение к модельному текущему времени Ттек. Пусть у перехода t2 момент очередного срабатьшания наступает раньше, тогда в регистре 23 перед очередным шагом работы устройства записывается {1,1,1,0). Вновь запускается блок 11, после чего в регистр 6 опять записывается (0.1.0,1). В регистр 24 записывается соответственно (0,1,0,0), т.е. теНерь активен и срабатывает временной переход tz. При этом устройство работает так же, как и при срабатывании на первом шаге. После срабатывания t2 в регистре признака типа перехода восстанавливается (1,0,1,0). После срабатывания ta имеется разметка (1,2,1,0,0). На очередном шаге активны простые переходы ti и 1з, они срабатывают и образуется новый вектор разметки (1,1,0,1,0). Далее срабатывает ti; вектор разметки принимает вид (1,0,0,1,0). Блок 22 вновь определяет временной переход с ближайшим временем срабатывания, так как ни один из множества простых переходов не может сработать. Пусть теперь срабатывает t4 и вектор разметки изменяется (1,0,0,0,1). Процесс работы устройства повторяется но при зтом уже не может сработать ни один переход, так как полученная разметка является тупиковой. При превышении текущим модельным временем Ттек заданного Тмод блок 22 выдает сигнал на выход Превышение, являющийся информационным выходом устройства. В регистре 4 записан достигнутый за время Тмод вектор разметки МВСП. Устройство и работа блоков 1-11,24 идентичны устройству и работе блоков 1-11 устройства для исследования сетей Петри. Блок 22 вь1бора времени работает следующим образом. Первоначально все его триггеры установлены в О, в регистрах 31 хранения записаны числа, соответствующие очередным моментам срабатывания временных переходов сети. Записанные числа все разные, . так как вероятность срабатывания двух и более временных переходов одновременно равна нулю. При поступлении сигнала 0 на вход 41 блока, информация с регистров 31 переписывается в реверсивные счетчики 33 и одновременно поступает на вход первого слагаемого соответствующих сумматоров 32. Параллельно с задержкой на Г1, необходимой для записи информации .в счетчики 33, устанавливается в 1 RSтриггер 40, разрешая поступление через элемент И 39 тактовых импульсов-с генератора 37 на вычитающие входы реверсивных счетчиков 33. На выходе признака обнуления того счетчика, в котором записано наименьшее число, единица появляется раньше. Она устанавливает соответствующий триггер 34 в единицу и че- ; рез элемент ИЛИ 36 сбрасывает триггер 40 в О, прекратив поступление импульсов на вычитающие входы реверсивных счетчиков. Она же поступает на вход запроса от ДСЧ ,

очередного случайного числа. ДСЧ генерирует числа по закону распределения времен срабатывания соответствующего временного перехода. Случайное число поступает на второй вход слагаемого соответствующего сумматора 32 и следующий момент срабатывания дднного перехода, равный результату суммиров ания, заносится в регистр 31 хранения. При появлении 1 в самом старшем разряде регистра 31 хранения, что соответствует превышению текущим модельным временем заданного Тмод, вырабатывается сигнал, который через элемент ИЛИ 38 поступает на выход Превышение блока 22 и соответственно на информационный выход устройства, обеспечивая конец работы

Появившаяся единица на выходе триггера 34 поступает на соответствующий выход 42 для установки соответствующего разряда регистра 23 признака типа переходов в 1 на время задержки элемента 35 Тш (где .Тш - длительность одного шага работы усгройства). Одновременно через элемент ИЛИ 30 вырабатывается сигнал Пуск для повторного пуска блока 11 синхронизации.

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

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

Устройство для моделирования сетей Петри, содержащее три блока памяти, группу блоков сравнения, первый регистр результатов сравнения, блок сумматоров, блок регистров, блок вычитания матриц, блок умножения матриц, блок сравнения с нулем и блок синхронизации, причем эыход блока регистров подключен к входу первого слагаемого блока сумматоров и к первым информационным входам всех блоков сравнения группы, с первого по k-й выходы первого блока памяти (где k - количество строк в исходных матрицах входной и выходной разметки вершин переходов сети) подключены к входам задания соответствующих элементов вычитаемого блока вычитания матриц и вторым информационным входам с первого по k-й блоков сравнения группы, выходы признаков неотрицательного результата крторых подключены к соответствующему разряйу информационного входа первого регистра результатов сравнения, выход признака равенства нулю блока сравнения с нулем подключен к входу останова блока синхронизации, выход второго блока памяти подключен к входу уменьшаемого блока вычитания матриц, выход которого подключен к информационному входу третьего блока памяти, выход которого подключен к входу множителя блока умножителя матриц, выход которого подключен к входу второго, слагаемого блока сумматоров, выход которого подключен к информационному входу блока регистров, вход начальной установки блока синхронизации подклкзчен к входам начальной установки первого регистра результатов сравнения и третьего блока памяти и является входом начальной установки устройства, вхбд пуска устройства подключен к входу пуска блока синхронизации, с первого по седьмой выходы которого подключены к входам признаков чтения первого и второго блоков памяти и признака записи третьего блока памяти, входу опроса блока сумматоров, к входу признака записи блока регистров, входам опроса всех блоков сравнения группы и блока вычитания матриц, входу признака записи первого регистра результатов сравнения, входу опроса блока умножения матриц и входу признака чтения третьего блока памяти соответственнб, о тличающееся тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения моделирования временных сетей Петри, в него введены второй регистр результатов Сравнения, регистр типа переходов, группа из k элементов И, блок, выбора времени и элемент задержки, причем вход признака записи первого рег-истра результатов сравнения подключен к входу элемента задержки, выход которого подключен к входу признака записи второго регистра результатов сравнения, вход начальной установки которого подключен к входу начальной установки устройства, с первого по k-й разряды информационного выхода первого регистра результатов сравнения подключены к первым входам соответствующих элементов И группы, в.ыходы которых подключены к соответствующим разрядам информационного входа второго регистра результатов сравнения, выход которого подключен к входу множимого блока умножения матриц и информационному входу блока сравнения с нулем, вторые входы с первого по k-й элементов И группы подключены к соответствующим разрядам информационного выхода регистра признака типа 1ерехадов, информационный вход которого подключен к информационному выходу блока выбора времени, выход Пуск которого подключен к входу пуска устройства, выход признакга равенства нулю блока сравнения с нулем подключён к одноименному входу блока выбора времени, выход Превышение которого является информационным выходом устройства, входы для подключения датчиков случайныхчи- 5 Сёл группы jcoToporo подключены к cboteetf ствуюцилмвх М1ам Чй сую группы блока вы-: бора времени;: выходы заггроса rj)ynпы которого являются одноименными выхбдд t ми группы устройства.

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

ш

()

Опред-е перелодод, для /fomopbix M(j) V(l.J)

70

Да множество gcmoL

Опред-е 5/iuffauuce го времени срао.

Тгм Ттек -i-ut ; запись Г

BoccmaffodMHue

через Сш ПрвЖ.иНф.

в регистре признана

{ Конец

Фиг. 2.

СЦ

П

НИНta28

1709348

Ч1

9 и

7 1

гНМИ:01Л

Ц

27

28

М

fu8.3

Фиг. 4