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

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

Иллюстрации

Показать все

Реферат

 

- Изобретение относится к вычис- . лительной технике и может быть использовано для исследования сетей Петри, Цель изобретения - расширение области применения. Цель изобретения достигается за счет дополнительного введения в состав устройства четвертого блока памяти 15, второй группы блоков схем сравнения , 16-k и группы элементов И 17 1 . «о,17-k. 2 ило

Саоэ СОЕЕТСНИХ

ОС@ МО

РЕСПУБЛИН (g1)g г 06 F 1 5/347 15/419

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ГЮ ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ fHHT СССР

1 (61) 1322312 (21). 4855206/24 (22) 31.07.90 . (46) 23.05.92. Бюл. и 19 (72) А.Г. Янковский, А.В. Падерин и В.В. Дороаенко (53) 681 325 (088.8) (56) Авторское свидетельство СССР

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

СЕТЕЙ ПЕТРИ

„„SU„„1735869 А 2

2 (57). Изобретение относится к вычислительной технике и может быть использовано для исследования сетей

Петри. Цель изобретения - расширение области применения. Цель изобретения достигается за счет дополнительного введения в состав устройства четвертого блока памяти 15, второй группы блоков схем сравнения 16т1, ....,16-k и группы элементов"517ò1... ..;17-k. 2 ил.

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

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

"равило запуска переходов по сравнению с обычными СП изменяется следующим образом.

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

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

C =CP, Т, D, D ) где P — Р „Р,...,Р,„- конечное непустое множество

ПОЗИЦИЙр

m,тО >

Т = t,,t,: t < — конечное непу тое множество переходов, 1с)0;

РПТ

D u D - матрицы, представляющие собой входную и выходную функции.

35869

Каждая матрица имеет k строк (по одной на. переход) и m столбцов (по одному на позицию). где D — определяет входы в переход

Ф

10 D — определяет выходы из переходов, Ч матричном описании СП со сдерживающими дугами добавляется матрица сдерживаюц(их (ингибиторных) дуг

15 D, содержащая также k строк и m

Yl столбцов. Элемент матрицы D Pl,ß =

= 1 тогда и только тогда, когда из позиции Р), в переход tl ведет сдерживающая дуга. Правила запуска переходов для СП со сдерживаюц(ими дуга" ми определены выше.

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

З0 СП (СП со сдерживающими дугами).

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

5 по k-й выходы четвертого блока памяти, где k - количество строк в исходных матрицах, подключены к вторым информационным входам блоков схем сравнения второй группы, выходы 0 признаков неотрицательного результата которых подключены к первым входам соответствующи элементов И группы, вторые входы которых соединены с выходами признаков неотрицательно- . го сравнения первой группы, выходы элементов И группы подключены к информационному входу регистра резуль татов сравнения, вход признака чтения четвертого блока памяти, вход, 50 и блока 7 вычитания матриц, к входу признака записи регистра 6 результатов сравнения, к входу опроса блока

8 умножения матриц и к входу признака чтения третьего блока 3 памяти

55 соответственно.

Схемы введенных четвертого блока

15 памяти и блоков 16-1,, °...16-k схем сравнения второй группы являются известными и могут быть выполнены

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

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

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

° своего решения возможности моделирования ситуации различных приоритетов, арбитров, прерываний и т.д.

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

На фиг.1 представлена функциональная схема устройства; на фиг.2рассматриваемая СП.

Устройство содержит четыре блока

1-3, 15 памяти, блок 4 регистров для хранения начальной маркировки первую группу 5 блоков 5-1...,,5-k схем сравнения, где k - количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства, вход 12,начальной установки, вход

14 пуска устройства, вторую группу

15 блоков 16-1, 16-k, схем сравнения, группу 17 элементов И 17-1, 17"2,...

17-k, причем выход блока 4 регистров подключен к входу первого слагаемого блока 9 сумматоров и к первым информационным входам блоков 5-1,...5-k„

16-1,...,16-Е схем сравнения первой. и которой группы, с первого по k-й выходы первого блока 1 памяти подключены к входу вычитаемого блока

7 вычитания матриц и вторым информационным входом с первого по М-й блок 5-1,...,5-k схем сравнения первой группы 5, выходы признаков не" отрицательного результата которых

Г 869

6 под ключ ены к п ер вым входам соот ве т с твующих элементов И группы, вторые входы которых подключены к выходам, 5 признаков неотрицательного результата сравнения соответствующих блоков

16-1,,...,16-k схем сравнения группы

16, вторые входы которых соединены . с первым по k-й соответствующими выходами четвертого блока 15 памяти, Соответствующие выходы элементов И группы 17 подключены к информационному входу регистра 6 результатов сравнения, выход которого подключен к входу первого сомножителя блока 8 умножения матриц к информационному входу блока 10 сравнения с нулем, выход признака равенства нулю которого подключен к входу останкова блока

2О 11 синхронизации и является информационньм выходом 12 устройства,. Выход, второго блока 2 памяти подключен к входу уменьшаемого блока 7 вычитания матриц, выход которого подключен к

g5 информационному входу третьего блока 3 памяти. Выход блока 3 памяти подключен к входу второго сомножите" ля блока 8 умножения матриц, выход которого подключен к входу второго

30 слагаемого блока 9 сумматоров. Выход блока 9 подключен к информационному входу блока 4 регистров. Вход начальной установки блока 11 синхронизации подключен к входам начальной установки регистра 6 результатов

35 сравнения и третьего блока 3 памяти и являются входом 13 начальной установки устройства. Вход пуска блока синхронизации является входом 14 пуска устройства. С первого по седь4 .мой выходы блока 11 синхронизации подключены к входам признака чтения первого 1, второго 2 и четвертого

15 блоков памяти и входу признака записи третьего блока 3 памяти, к

45 входу опроса блока 9 сумматоров, к входу признака записи блока 4 регистров, к входам опроса каждого блока 5-1,...,5-k, 16-1,..., 16-k схем сравнения первой и второй групп!

735(6

0 1 1 О

D = 0001

0010

1 ООО

00 ОО

ОООО и

02 1О

0001 ) 25

+xD„

Я

SS аналг.гично описанным R прототипе, Элементы !7-1,...,!7-k И группы 17 являются известными, Устройство работает следующим образом (фиг.2).

В исходном состоянии схемы в блоке 1 находится матрица входов D например в блоке 15 - матрица входов для сдерживающих дуг:

+ а в блоке 2 - матрица выходов D, нап" ример т.е. данная СП имеет четыре позиции, три перехода. Сдерживающая дуга соединяет р(и t(. Первоначальная маркировка находится в блоке 4 и имеет вид 1ц = (1,0,1,0).

Требуется определить, достижима ли маркировка р из маркировки jll (Предполагаем, что маркировка Pl достижима из маркировки p . Тогда существуеу последовательность (возможно пустая) запусков переходов G, ( которая приводит из (о к P . Это оз« начает, что f ((>) является неотрицательным целым решением следующего матричного уравнения для х: (Если 1 достижима из Р, уравнение (1) имеет решение в неотрицательных целых, если уравнение (1) не имеет решения, р не достижима из рА, Под дейстьием синхросигналов с блока 11 информация с выхода блока

1 поступает на вторые входы блоков

5тl 5-k схем сравнения группы, где происходит ее сравнение со значе-. нием начальной маркировки, поступающей на первые входы всех типов 5-1, ...,5-k. Если результат сравнения больше или равен нулю по всем срав9

8 ниваемым элементам (-й строки матри цы D (что соответствует тому, что для перехода t во всех его входных позициях, соединенных с ним обычными дугами, число фишек не меньше, чем кратность соединяющих дуг, т.е. выполняется правило запуска по обычным входам,на вторые входы соответствующих элементов И 17-1,...,17-k группы поступает единица, иначе нуль.

Одновременно с этим, под действием синхросигналов с блока 11 информация с выхода блока 15 поступает на вторые входы блоков 16-1...,,16-k схем сравнения группы, где происходит ее сравнение со значениями начальной маркировки, поступающей на первые входы всех блоков 16-1,...,16-k. Ec п ли результат сравнения меньше нуля по всем сравниваемым элементам i-й . строки матрицы D на первые входы соответствующих элементов И 17-1,..., 17-k поступает единица (т.е. для перехода t; в его сдерживающих входных позициях отсутствуют фишки, стало быть, выполняется правило запуска по его сдерживающим (ингибиторным) входам.

В случае отрицательного сравнения

З записывается нуль.

Таким образом, при сравнении первоначальной маркировки (1, О, 1, О) со строками матрицы D только третья строка удовлетворяет правилу срав5 нения. Это означает, что потенциально разрешено срабатывание по обычным входам третьего перехода. На вторые

l входы группы элементов И 17-1,..., 17-k поступают сигналы (0,0,1) соответственно.

Одновременно при сравнении первоначальной маркировки (1,0,1,0) со строками матрицы D удовлетворяют правилу сравнения вторая и третья строки. Это означает потенциально разрешение срабатывания по сдерживающим дугам для переходов второго и третьего, На первые входы групп элементов И соответственно поступают следующие значения (0,1,1), В результате с выходов групп элементов l7 И в

РегистРе 6 запишетсЯ (0,0,1). Парад- . лельно информация из блока 2 посту- пает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация с блока 1. Блок 7 под действием управляющих сигналов с блока 1I реализует операцию вычита9 1735869 10 ния матриц по формуле рониэации работает аналогично блоку синхронизации прототйпа и поэтом

D=D+-D, его работу не рассматривают, Таким образом, предлагаемое устЗначение .полученной составной мат- . Ройство позволяет производить анарицы изменений D записывается в блок лиэ достижимости не только обычных

3. Она имеет вид СП, но и их мощного расширения - СП со сдерживающими дугами. Это сущест0 венно (1,2,4) расширяет класс. Решаемых задач и соответственно область применения данного устройства.

1-1-1 0

D--A 2 1-1

0 1 "1 1

Дальше работа схемы направлена на. реализацию формулы (1). При подстановке полученных значений она имеет вид: (1,0,1,0) + (0,0,1) х

1 -1 -1 0

0 2 1-1

0 0-l 1

Под действием управляющих сигналов с блока 11 информация иэ.блока, 3 поступает в блок 8, где происходит. сложение результата произведения со ,значением маркировки, в результате получается новая маркировка СП (1,0;

О,1) которая заносится в блок 4.

Процесс работы устройства повторяется.

На каждом шаге работы устройства происХодит проверка кода, находящегося в блоке 4, т.е. последовательнос, .ти выпуска переходов на нуль в блоке 10; Если информация больше нуля, процесс работы продолжается. Если последовательность запуска переходов равна нулю, блок !О вырабатывает сигнал, свидетельствующий о том, что

СП при данной начальной маркировке . достигла передела выполнимости, т.е. достигла такого состояния, когда все переходы эапрещ1ены. Блок 11 синх(формула изобретения

Устройство для исследования сетей Петри по авт.св. 8 1322312, о т л и ч а ю щ е е с я тем, что, с целью расширения области примене"

1 ния; дополнительно введены четвертый . блок памяти, вторая группа блоков схем сравнения, rpynna элементов И, причем выход блока регистров подключен к первым информационным входам блоков схем сравнения второй группы

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

ЗО первым входам соответствующих элементов И группы, вторые входы" которых со-. единены с выходами йриэнаков неотрицательного результата сравнения соответствующих блоков схем сравнения

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

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

1735869

Составитель А, Янковский

Редактор Н. Гунько Техред M.M preaTaa

Корректор M. Самборская юююю ю ее ююю ю ю ю юююю юююю юююююююЮююююююююю юююю ю ю ю

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

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

113035, Иосква, 3-35, Рауаская наб., д. 4/5

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