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

 

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

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

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

РЕСПУБЛИН

„„80„„1314350 А 1 (5ц 4 G 06 F 15 20

Qkr-., 1

1 .у ,/

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

К А STOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4016672/24-24 (22) 24.01.86 (46) 30.05.87. Бюл. № 20 (71) Институт проблем моделирования в энергетике АН УССР (72) В. В. Васильев, В. В. Кузьмук, Е. Б. Лисицин и В. А. Шумов (53) 681.325 (088.8) (56) Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984.

Авторское свидетельство СССР № 1171803, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ ПЕТРИ (57) Изобретение относится к вычислительной технике, а именно к устройствам для моделирования параллельных процессов, которые алгоритмически описаны с помощью сетей Петри. Устройство позволяет выявлять наличие критических свойств в графах

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

1314350

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

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

На фиг. 1 представлена схема устройства; на фиг. 2 — схемы блока регистров задания входных векторов и блока коммутации; на фиг. 3 — схема блока сравнения входных векторов; на фиг. 4 — схемы блока элементов ИСКЛЮЧАЮ1ЦЕЕ ИЛИ, блока элементов ИЛИ, блока контроля конфликтных ситуаций, блока контроля безопасного свойства; на фиг. 5 — схема блока сравнения выходных векторов; на фиг. 6 — схемы блока контроля живого свойства и генератора тактовых импульсов; на фиг. 7 — иллюстрированный пример моделируемого графа Петри; на фиг. 8 фрагменты графов Петри, иллюстрирующие критические свойства, анализируемые предлагаемым устройством.

Устройство (фиг. 1) содержит блок 1 ввода, блок 2 регистров задания входных векторов, регистр 3 задания текущей разметки, блок 4 индикации, блок 5 сравнения входных векторов, коммутатор 6, блок 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок 8 элементов ИЛИ, блок 9 сравнения выходных векторов, блок 10 регистров задания выходных векторов, блок 11 коммутации, блок 12 контроля живого свойства, регистр 13 начальной разметки, элемент ИЛИ 14, генератор !5 тактовых импульсов, блок 16 контроля конфликтных ситуаций, опорный генератор 17, блок 18 контроля безопасного свойства.

Блок 1 ввода предназначен для ввода в устройство топологии моделируемого графа

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

Блок 2 регистров задания входных векторов предназначен для хранения входных разметочных векторов для каждой вершины перехода (,. (1 (v (m).

Регистр 3 задания текущей разметки предназначен для хранения текущей разметки вершин мест в моделируемом графе

Петри.

Блок 4 индикации предназначен для вывода содержимого регистра 3 на индикационную панель.

Блок 5 сравнения входных векторов предназначен для определения вершин переходов t,„у которых выполнены условия срабатывания и формирования управляющих сигналов вычитания соответствующих вход5

f5

55 ных разметочных векторов от вектора текущей разметки графа Петри.

Коммутатор 6 предназначен для управления занесением информации в регистр 3 задания текущей разметки, а именно либо из блока 7 элементов ИСКЛЮЧАЮ1ЦЕЕ

ИЛИ, либо из блока 8 элементов ИЛИ, либо из регистра 13 начальной разметки.

Блок 7 элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ предназначен для реализации вычитания v-х входных разметочных векторов из вектора текущей разметки при выполнении условия разрешения срабатывания переходов t, Блок 8 элементов ИЛИ предназначен для прибавления v-х выходных разметочных векторов к вектору текущей разметки.

Блок 9 сравнения выходных векторов предназначен для определения вершин переходов t„ моделирование которых окончено, и формирования управляющих сигналов, позволяющих прибавлять соответствующие

v-e выходные разметочные вектора к вектору текучцей разметки.

Блок 10 регистров задания выходных векторов предназначен для хранения выход,— ных разметочных векторов для каждой вершины перехода.

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

Блок 12 контроля живого свойства предназначен для выявления и индикации неживого критического свойства в моделируемом графе Петри.

Регистр 13 начальной разметки предназначен для хранения начальной разметки моделируемого графа Петри.

Элемент ИЛИ. 14 предназначен для формирования сигнала, разрешающего изменение вектора текущей разметки, хранящегося в регистре 3.

Генератор 15 тактовых импульсов предназначен для формирования управляюгцих сигналов г1) 1 и Ф2 для тактирования устройства.

Блок 16 контроля конфликтных ситуаций предназначен для обнаружения и индикации конфликтного критического свойства в моделируемом графе Петри.

Опорный генератор 17 предназначен для формирования непересекающейся двухфазовой последовательности сигналов Ф! и Ф2.

Блок 18 контроля безопасного свойства предназначен для обнаружения и индикации небезопасного критического свойства в моделируемом графе Петри.

Блок 2, представленный на фиг. 2, представляет собой набор из m (по числу m моделируемых вершин переходов t,) n-разрядных (по числу и моделируемых вершин мест р,) регистров 2v (1 ((ъ (m) 1314350 (здесь и везде в дальнейшем цифрами после точки, стоящей после цифры, обозначены порядковые номера одинаковых по техническому исполнению блоков, узлов и элементов, а также входов и выходов блока, узла или элемента, которые объединены в общую шину) .

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

Блок 4 индикации может быть выполнен в виде индикаторной панели, в которой каждой вершине места в графе Петри соответствует элемент индикации.

Блок сравнения входных векторов, схема которого приведена на фиг. 3, содержит первую группу из m подгрупп элементов

И 19 v. 1...19л.п (ъ = l,...,rn), т элементов

ИЛИ-НЕ 20л, вторую группу из m подгрупп элементов И 21л. 1,..., 21л.и, группу из п элементов ИЛИ 22.1,...,22, п, элемент ИЛИ 23 и элемент И 24.

Элементы И 19л.1,...,19л.п предназначены для реализации функции конъюнкции над инверсными значениями векторов текущей разметки и значениями входных разметочных векторов.

Элементы ИЛИ-НЕ 20. предназначены для отыскания хотя-бы одной «1», получившейся в результате конъюнкции инверсного значения вектора текущей разметки mо с ъ-м входным разметочным вектором р., ev указывающей на то, что ц gmo .

Элементы И 21л, 1,...,21.v.n предназначены для формирования сигналов вычитания из вектора текущей разметки тех входных разметочных векторов "7г., для которых выполнено условие 7г g mo" .

Элементы ИЛИ 22.1,...,22.п предназначены для формирования обобщенного входного разметочного вектора, подлежащего вычитанию из вектора текущей разметки mo на данном цикле процесса моделирования.

Элемент ИЛИ 23 предназначен для формирования управляющего сигнала изменения текущей разметки при наличии хотя бы одного входного разметочного вектора е - - (кг

)г mo

Элемент И 24 предназначен для синхронизации формирования управляющего сигнала с фазой Ф 1.

Коммутатор 6 представляет мультиплексор с запоминанием подключаемого входа, до прихода следующего управляющего сигнала.

5

Блок 8 элементов ИЛИ, схема которого приведена на фиг. 4, предназначен для прибавления ъ-х выходных разметочных векто-р (к) ров -" Д к вектору текущей разметки «гч после окончания моделирования срабатывания перехода /,, что позволяет реализовать появление меток в выходных местах перехода t, Блок 9 сравнения выходHbIx векторов. схема которого приведена на фиг. 5, содержит группу из гп подгрупп элементов

И 25л.1,...,25.v«г, группу элементов ИЛИ

26.1,...,26.ll,, элемент ИЛИ 27, элемент И 28.

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

mo, по окончанию моделирования вершин t, Группа элементов ИЛИ 26, е (= 1,...,и) предназначена для стохастического, несинхронного вычитания выходных разметочных векторов 1г из вектора текущей разметки (x) то в непрерывном режиме работы устройства.

Элемент И 27 предназначен для формирования сигнала управления, разрешагощсго изменение вектора текущей разметки ггпу ".

Элемент И 28 предназначен для синхронизации сигнала управления изменением век-+ (кг тора текущеи разметки «io по частоте Ф2.

Блок 10 регистров задания выходных векторов представляет собой набор из гп «-разрядных регистров 10.v.

Блок 11, приведенный на фиг. 2, содержит i72-разрядный счетчик 29, гп групп элементов И 30л (1 (т (и), элемент И 31 и элемент ИЛИ-НЕ 32.

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

0,0,...,О.

Группы элементов И30.1 — 30.m предназначены для разрешения или запрещения в зависимости от состояния соответствующего

v-го разряда счетчика 29, подачи входных разметочных векторов, хранящихся в блоке 2, в блок 5 сравнения входных векторов.

Элемент И 31 предназначен для определения такого состояния счетчика 29, когда во всех его разрядах содержатся «1», элемент ИЛИ-HE 32 предназначен для определения такого состояния счетчика 29, когда во всех его разрядах содержатся «О».

Блок 12 контроля живого свойства, схема которого приведена на фиг. 6, содержит элементы HE 33, группу триггеров

34.1,...,34, т, элемент И-НЕ 35, элементы

И 36,...,39, элементы ИЛИ 40, 41, индикаторный элемент 42, элемент ИЛИ 43, элемент

НЕ 44, регистр 45, счетчик 46.

Элемент НЕ 33 предназначен для инвертирования сигнала признака наличия хо1314350

1 00,...,0

010,...,0

001,...,0

55 тя бы одного активного перехода t,, для которого выполняется условие " !z g то " .

Группа триггеров 34л предназначена для фиксации признака срабатывания перехода и хранения его до прихода сигнала сброса.

Элемент И-HE 35 предназначен для фиксации признака «лог. 1» и «не все переходы t, сработали».

Элемент И 36 предназначен для установки «флажка» начала следующего шага моделирования и ри новом значении вектора Л по совпадению признаков «нет активных переходов» и «не все разряды вектора Х находятся в состоянии лог. «1».

Элемент ИЛИ 37 предназначен для установки признака обнаружения неживого свойства по совпадению признаков «нет активных переходов» и «все разряды вектора Х находятся B состоянии лог. «1».

Элемент И 38 предназначен для установки признака обнаружения неживого свойства по совпадению признака «не все переходы t,. сработали» и признаки окончания моделирования графа, введенного в устройство.

Элемент И 39 предназначен для установки признака окончания моделирования по совпадению признака «все разряды вектора

Х находятся в состоянии логического «О» и сигнала установки в «О» счетчика 46.

Элемент ИЛИ 40 предназначен для формирования управляющего сигнала установки начальных условий нового цикла моделирования.

Элемент ИЛИ 41 предназначен для формирования управляющего сигнала останова устройства по признаку обнаружения неживого свойства.

Индикаторный элемент 42 предназначен для индикации условия обнаружения неживого свойства.

Элемент ИЛИ 43 предназначен для формирования управляющего сигнала останова устройства.

Элемент HE 44 предназначен для формирования управляющего сигнала «не все разряды вектора Х находятся в состоянии лог. «1».

Регистр 45 предназначен для хранения числа циклов работы устройства, составляк щих один шаг моделирующего эксперимента при фиксированном значении вектора Х.

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

Элемент ИЛИ 47 предназначен для формирования управляющего сигнала занесения в счетчик 46 числа, хранящегося в регистре 45.

Регистр 13 начальной разметки (фиг. 1) представляет собой п-разрядный (по числу моделируемых вершин мест р,.), каждый разряд которого предназначен для моделирования наличи («1») или отсутствия («О») метки в соответствующей вершине места р,. (т(р,.)=1) графа Петри.

Генератор 15, приведенный на фиг. 6, содержит элементы И 48, 49.1, 49.2 и триггер 50 для управления пуском-остановом генератора 15.

Блок 16 контроля конфликтных ситуаций, схема которого представлена на фиг. 4, выполнен содержащим набор из и (по числу вершин мест ро) узлов 53. е постоянной памяти (1 (в (zz) (ПЗУ) группу 51 элементов индикации и элемент ИЛИ-НЕ 52.

Каждый блок 53.е предназначен для хранения признаков конфликтных разметок вершин мест р, При моделировании графа Петри, содержащего m вершин переходов t,. и п вершин мест р,, в каждом блоке 53.е используются первые m адресных входов ((1), (2),,(т) ). При этом в ПЗУ 53.в по каждому адресу 1,0,0,...,0; 0,1,0,...,0;

0,0,0,...,1, содержащему лишь одну «1» (описывается ортогональным вектором), записаны «0». ооо, ., т

По всем остальным адресам записаны лог. «1», показывающие наличие конфликтной разметки в графе Петри.

Группа 51 элементов индикации выполнена содержащей и (по числу вершин мест р,.) индикаторных элементов, причем каждой вершине места р, соответствует е-й индикаторный элемент, подключенный к блоку

53.в, и предназначена для индикации возникновения конфликтной разметки мест р, Элемент ИЛИ-НЕ 52 предназначен для формирования сигнала останова устройства в случае возникновения конфликтной разметки мест р,, графа Петри.

Блок 18 контроля безопасного свойства, представленный на фиг. 6, выполнен содержащим набор из и (по числу вершин мест) блоков 54.в постоянной памяти, (ПЗУ) элемент ИЛИНЕ 55 и группу 56 элементов индикации.

Блоки 54.в предназначены для хранения признаков возникновения небезопасных разметок мест р,. При моделировании графа

Петри, содержащего m вершин переходов и п вершин мест р,, в каждом е-м

ПЗУ 54.в используются первые т+1 адресных входов (1), (2), ..., (т) (т+1). При этом в каждом кристалле ПЗУ по адресу

1314350

100,...,00

010,...,00

00 1,...,00

000,...,1 0

000....00 т+1

1,0,0,...,0,0; 0,1,0,...,0,0; ...; 0,0,0,...,0,1, содержащему лишь одну «1», записаны все «О».

По остальным адресам, кроме адреса

0,0,0,...,0,0, записаны лог. «1», показывающие наличие небезопасной разметки в сети

Петри. По адресу 0,0,0,...,0,0, записан «О».

Группа 56 элементов индикации выполнена содержащей и (по числу вершин мест р,.) индикаторных элементов, причем каждой вершине места р, соответствует в-й индикаторный элемент, подключенный к блоку 54.в, и предназначена для индикации обнаружения небезопасного свойства в вершинах мест р, Элемент ИЛИ-НЕ 55 предназначен для формирования сигнала останова устройства в случае обнаружения небезопасного свойства в любом из мест р,. графа Петри.

Рассмотрим основные положения теории графов Петри на конкретном примере графа Петри, приведенном на фиг. 7.

Особенностью графов Петри является наличие двух типов вершин: переходов t,, и мест р,, а также наличие меток, которые показывают, какие вершины при обходе графа устройство моделирует в данный момент времени. Метки располагаются в вершинах мест р,. (фиг. 7) и моделируют в динамике окончание реальных действий, в соответствии с заданным алгоритмом, представленным графом Петри. Местонахождение меток в графе Петри отображается вектором разметки mP = (0,1,0,1,1,0,0,0,1,0,1,0,0, l,1,l) . Цифра «О» на первом месте обозначает, что первое место pi не содержит метку, и «1» на втором указывает, что во втором месте р находится метка. При составлении графа Петри устанавливается ее топология и начальная разметка mo. Каждая вершина перехода t,. моделирует время выполнения какого-то действия в процессе. Говорят, что переход t,, срабатывает, если во всех местах р„ дуги от которых направлены к t,, находятся метки. Так, например, переходы t, и t, могут сработать. В переход 4 входят две дуги от места р и р ь в которых находятся метки. Это является условием начала моделирования действия аг, которое характеризуется временем Л4. В момент начала выполнения действия а метки из мест р и рц убираются и через время

At, в места, к которым направлены дуги от tz (рз и pro) записываются. Каждый переход t,, характеризуется частич30

55 ным входным вектором ц и выходным разметочным вектором " p. Вектора записываются в трансформированной форме. В векторе е - и = (1,1) «1» на первом месте говорит о том, что в вершине р находится метка.

При составлении частичных векторов предварительно расстанавливаются по возрастанию индексов мест вершин. Так для >p расстановки соответствующих ему мест р, р,, A Z а для p — !эз, pro.

На фиг. 7 представлен пример моделируемого графа Петри для примера моделирования управления поездами метрополитена. Три поезда непрерывно едут по кольцу, останавливаясь на каждой из восьми станций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что привело бы к их столкновению. Вершины мест рь...,р моделируют станции, а наличие меток в р,. (1 (v (8) моделируют наличие поездов на станциях х. Наличие меток в местах р„(9 (q (16) моделирует наличие зеленого света для соответствующих поездов. Каждый из переходов t, (1 (Y (8) моделирует время At, включающее переезд с одной станции на другую и остановку на последующей станции.

Моделирование построенного графа Петри в устройстве для моделирования графов

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

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

Различают три критических свойства в графах Петри: конфликтная разметка вершин мест р,; небезопасная разметка вершин мест р,; неживое свойство графов Петри.

Правильно построенный (реализуемый) граф Петри должен обладать безконфликтным, безопасным и живым свойствами.

Остановимся подробнее на определениях критических свойств в графах Петри.

Конфликтное свойство.

Безконфликтным называется такой граф

Петри, который при его обходе не содержит конфликтных разметок вершин мест р,, т. „„е. если при всех разметках графа т, !й не наступает ситуации, при которой срабатывание одного из возбужденных переходов t; ведет к запиранию других возбужденных переходов /, 1314350

На фиг. 8а показана конфликтная разметка подграфа в графе Петри. Разметка мест т (p)) = m (р ) = 1 и m (p ) == т (рз) = 1 ведет к тому, что переходы ti и 4 могут сработать. Но срабатывание одного из них, характеризующееся устранением меток из входящих в переход мест (например р) и р) для t)), ведет к запиранию другого (для

4 m(p ) = 0 и т(р.)) = 1.

Безопасное свойство. Безопасным называется такой граф Петри, который при его обходе не содержит небезопасных разме- (к) ток мест р, Разметка mo графа Петри называется безопасной, если разметка каждого места при перемещении меток является безопасной (m (р,.) (1). Если разметка хотя бы одного места р, „, (р,.) ) 1, то такой граф имеет небезопасное свойство.

Пример небезопасного графа Петри приведен на фиг. 8б. При последовательности срабатываний переходов т = t;, 4, t) в место р попадают две метки и m (рз) =2.

Живое свойство. Живым называется такой граф Петри, который содержит лишь живые вершины переходов t, В свою очередь переход t,, называется живым при заданном множестве возможных разметок

- x)

m gm, если существует такая последовательность срабатываний переходов g /), 4,...,/,,, в которой переход („ срабатывает хотя бы один раз и может сработать еще раз.

Возможны два случая несрабатывания переходов t, В первом случае (фиг. 8в) не существует последовательность срабатываний переходов б, при которой переход t4 может сработать. Это обуславливается тем, что одновременно по одной метке в местах р) и р:) быть не может. Во втором случае (фиг. 8г) срабатывание перехода приводит к тому, что переходы ti и t; не могут сработать. Для анализа графа Петри на некритические свойства вводится вектор добавочного условия х = (х, х,..., х,...," r), позволяющий моделировать самые различные последовательности срабатываний переходов () .

Таким образом, для срабатывания переходов t,, при проверке их на живость необходимо совпадение двух условий: p, g m

О ) х = 1.

Последовательное изменение значения вектора проверочных сигналов от 11,1,1, ...,1) до 10,0,0, ..., О) позволяет реализовать полный перебор всех последовательностей срабатываний переходов графа Петри Q для данной начальной разметки mp. Для определения любого критического свойства достаточно двухкратного срабатывания каждого из переходов t, Устройство работает следующим образом.

Записывается топология моделируемого графа Петри в блоки 2, начальная разметка -- в регистры 3 и 13, необходимое число циклов работы устройства на одном шаге моделирования — — в регистр 45 бло5

55 ка 12 контроля живого свойства. Все разряды счетчика 29 находятся в состоянии «1».

Ввод данных осуществляется при помощи блока 1 ввода следующим образом.

Для моделирования графа Петри, содержащего и вершин мест р, и m вершин переходов t,, требуется наличие m узлов в блоках 2, 5, 9, 10 m групп элементов И 30 v, m триггеров в группе 34, а все группы элементов — содержать по и элементарных схем.

Для загрузки топологии графа и начальной разметки составляется таблица топологии графа Петри (см. табл.). Причем каждой вершине перехода /,, соответствует входной " 1), и выходной )) )). разметочные вектора. Все переходы t,. графа Петри заносятся в колонку «Обозначение переходов».

Например, переходу l) соответствует p. =

= (1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0) и

= (0.1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)" . В v-x входных (выходных) разметочных векторах «1» стоят в тех е-х столбцах, которым соответствуют места р„являющиеся входными (выходными) для перехода /, Режим моделирования графа Петри включается после подачи сигнала «Пуск» на вход установки триггера 50 и подключением к устройству опорного генератора 17.

На первом шаге моделирования все разряды счетчика 29, имитирующего вектор дополнительных условий Х, находятся в состоянии «1» и, следовательно, значение всех входных разметочных векторов, хранящихся в блоке 2, подаются через группы элементов И 30.1,...,30.т на схему блока 5 сравнения входных векторов, где они одновременно анализируются в узлах 5.1,...,5.m на принадлежность к вектору текущей разметки т™)) " 1), (т )«) ) . Выполнение условия " 1). g то говоРит о том, что пеРеход tx подлежит запуску на данном цикле моделирования, и 1), необходимо вычесть из т о .

Векторы текущей разметки " 1),, подлежащие

- (x) вычитанию из mo на данном шаге моделирования, через подгруппы элементов 21.1,..., 21.m подаются на элементы ИЛИ 22.1,...,22n группы для формирования суммарного входного вектора, вычитаемого из вектора mo в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ.

eV - «

Одновременно значение всех p g mo через соответствующие выходы подаются на блок

16 для анализа конфликтных ситуаций. Конфликтная ситуация возникает в случае наличия «1» в каком-либо в-м разряде более чем одного вектора 1), g то) . Тогда соответствующий блок 50.в выдает признак конфликтной ситуации, индицируемый соответствующим е-м элементом индикации группы 51, а на элементе ИЛИ-НЕ 52 формируется инверсный управляющий сигнал, прекращающий подачу тактирующих сигналов Ф 1 и Ф 2 от генератора 15. Устройство прекращает работу и на блоке 4 индикации индицируется текущая разметка, при которой возникла

1314350

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

55 конфликтная ситуация. Если конфликтная ситуация не обнаружена на элементе И 24 по совпадению признака наличия запускаемых переходов, формируемым элементом

ИЛИ 23, и тактового импульса Ф1, вырабатывается управляющий сигнал, разрешающий через коммутатор 6 запись нового

- (к+ t) значения вектора текущей разметки m() определенного в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, в регистр 3 задания текущей разметки.

Приход сигнала Ф 1 инициирует вычитание «1» из значения, хранящегося в счетчике 46. В случае отсутствия на первом шаге моделирования при логическом сигнале «все разряды вектора 37 в состоянии «1» переходов t,, для которых бы выполнялось условие " !(5 то к), в блоке контроля живого свойства 12 по совпадению сигнала уровня

«1» на выходе элемента И 31 и «О» на выходе элемента И 24 на элементах И 37 и ИЛИ 41, 43 формируется управляющий сигнал обнаружения неживого свойства, прекращающий подачу тактовых импульсов (1) 1 и Ф2, и индицируемый элементом 42. Если неживое свойство не обнаружено, то логические единицы с выходов элементов

ИЛИ-НЕ 20л (для которых р, g m() ) подаются соответственно на входы блока 9 сравнения выходных векторов и одновременно запоминаются в v-x триггерах группы триггеров 34.1 — 34.т. Так как для проверки на критические свойства предполагается мгновенное срабатывание переходов (в нашем случае время срабатывания переходов равно промежутку между появлением сигнала Ф1 и Ф2), то необходимо на этом же цикле работы устройства промоделировать окончание работы только что запущенных переходов. Значения выходных разметочных векторов р. переходов t,, запущенных на длинном цикле моделирования, через v-e группы элементов И25.1 — 25.m подаются на схему формирования суммарного выходного вектора (группа элементов ИЛИ 26.1 — 26.n) подлежащего сложению с вектором теку-ъ (K+1) щеи разметки m() в блоке 8 элементов

ИЛИ. Кроме того значения всех р,, -+ (к+() прибавляемых к m() на данном цикле

-Ф (к+1) моделирования, и значение т) подаются на схему блока 18 для контроля безопасного свойства. Небезопасное свойство имеет место при наличии «1» в каких либо е-х разрядах объединенного вектора, объеди(к-о о няющего вектор m() и набор векторов

av -ъ (Wr) ц„ прибавляемых к m() на данном цикле работы устройства . Тогда соответствующий блок 54.е выдает признак конфликтной ситуации, индицируемой соответствующим в-м элементом индикации группы 56 и на элементе ИЛИ-НЕ 55 формируется инверсный управляющий сигнал, прекращающий подачу тактовых импульсов Ф1 и Ф2 на схему устройства. Если небезопасное свойство не обнаружено, то по приходу тактового импульса Ф2 на выходе элемента И 28 формн.:, ся управляющий сигнал, разреп аюньни сение нового значения вектора текунц и 1;.. метки m()""), определенного в блоке 8 -.:< ментов ИЛИ, через коммутатор 6 в реги«(i1 задания текущей разметки. Новое значение (к+г.) вектора текущей разметки (и() заносится в регистр 3 и работа устройства повторяется до установления «О» во всех разрядах счетчика 46, что свидетельствует об окончании шага моделирования. Счетчиком 46 вырабатывается управляющий сигнал начала нового шага моделирования, по которому число, хранящееся в регистре 45, заносится в счетчик 46, в регистр 3 через коммутатор 6 заносится значение вектора начальной разметки (т(() из регистра 13, все триггеры набора 34 устанавливаются в состояние «О», из счетчика 29, имитирующего вектор дополнительных условий х() вычитается «1». Условием начала нового шага моделирования может быть отсутствие запускаемых переходов f, на очередном цикле моделирования, если все разряды счетчика 29 находятся в состоянии «1» (управляющий сигнал формируется на элементах HE 44, НЕ 33, И 36, ИЛИ 40). Шаги моделирования повторяются до появления «О» во всех разрядах счетчиков 29 и 46, на основании которого элементами И 39, ИЛИ 43 формируется сигнал окончания работы устройства без обнаружения критических свойств.

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

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

1. Устройство для моделирования графов Петри, содержащее блок регистров задания входных векторов, блок регистров задания выходных векторов, регистр задания текущей разметки, блок сравнения входных векторов, блок сравнения выходных векторов, блок элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ, блок элементов ИЛИ и генератор тактовых импульсов, инверсный выход регистра задания текущей разметки является выходом текущей разметки устройства и соединен с первым информационным входом блока сравнения входных векторов, выход сопровождения информации которого соединен с первым управляющим входом коммутатора, выход которого соединен с информационным входом регистра задания текущей разметки, прямой выход которого соединен с первыми входами блока элементов ИЛИ и блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы ко13

1314350 торых соединены с первым и вторым информационными входами коммутатора соответственно, выход признаков сравнения блока сравнения входных векторов voäêëþ÷åí к второму входу блока элементов ИСКЛ10ЧАЮ1ЦЕЕ ИЛИ, первый выход блока регистров задания выходных векторов подключен к первому информационному входу блока сравнения выходных векторов, выход признаков сравнения которого подключен к второму входу блока элементов ИЛИ, выход сопровождения инфорации блока сравнения выходных векторов подключен к второму управляющему входу коммутатора, отличающееся тем, что, с целью расширения функциональных возможностей за счет контроля наличия критических свойств в графах, в него введены регистр начальной разметки, блок коммутации, блок контроля конфликтных ситуаций, блок контроля безопасного свойства, блок контроля живого свойства, элемент

ИЛИ, выход регистра начальной разметки подключен к третьему информационному входу коммутатора, с второго по m-й выходы блока регистров задания выходных векторов (где m — число моделируемых вершин переходов) подклк1чены к второму по

m-й информационным входам блока сравнения выходных векторов соответстенно, с первого ио и-й информационные выходы которого (где и — число моделируемых вершин мест) подключены к первому по п-й информационным входам блока контроля безопасного свойства соответственно, (и+1) -й информационный вход блока контроля безопасного свойства подключен к прямому выходу регистра задания текущей развертки, с первого tto m-й выходы блока регистров задания входных векторов подключены к первому по m-й информационным входам блока коммутации соответственно, с первого по m-й выходы ко" îðîãî подключены к второму ио (т+!)-й информационным входам блока сравнения входных векторов соответственно, с первого по m-й информационные выходы которого подключены к первому по m-й информационным входам блока контроля конфликтных ситуаций, выход признака конфликтной ситуации которого подключен к первому входу останова генератора тактовых импульсов, первый выход которого подключен к входам синхронизации блока контроля живого свойства и блока сравнения входных векторов, с первого ио m-й выходы признака перехода которого подключены к первому ио т-и одноименным входам блока сравнения выходных векторов и блока контроля живого свойства, выход признака неживого свойства которого подключен к второму входу останова генератора тактовых импульсов, третий вход останова — которого подключен к выходу признака небезопасной разметки блока контроля безопасного свойства, выход признака нового цикла блока контроля живого свойства подключен к перво5

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

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

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

2. Устройство по п. 1, отличающееся тем, что, с цельк1 повышения быстродействия, блок сравнения входных векторов содер15

1314350 жит две группы из т подгрупп по и элементов И, где и и и — число моделируемых вершин мест и переходов соответственно, т элементов ИЛИ-НЕ, группу элементов ИЛИ, элемент ИЛИ и элемент И, первые входы элементов И всех подгрупп первой группы поразрядно объединены и образуют первый информационный вход блока, выходы элементов И р-й подгруппы (р=1,..., m) первой группы подключены к входам р-го элемента ИЛИ-НЕ, выход которого подключен к первым входам элементов И р-й подгруппы второй группы, к р-му входу элемента ИЛИ и является р-м выходом признака перехода блока, вторые входы элементов И р-й подгруппы первой и второй групп поразрядно объединены и образуют (р+ 1)-й информационный вход бока, выход (k — 20)-го элемента И (/г= 1,...,n) р-й подгруппы второй группы подключен к р-му входу k-го элемента ИЛИ группы и к выходу р-го разряда k-го информационного выхода блока, выход элемента ИЛИ подключен к первому входу элемента И, второй вход и выход которого являются входом синхронизации и выходом сопровождения информации блока соответственно, выходы элементов

ИЛИ группы образуют выход признаков сравнения блока.

3. Устройство по п. 1, отличающееся тем, что, с целью повышения быстродействия, блок сравнения выходных векторов содержит группу из и подгрупп элементов И, группу элементов ИЛИ, элемент ИЛИ и эле10 мент И, первые входы элементов И р-й подгруппы элементов (р=1,...,rn) образуют р-й информационный вход блока, вторые входы элементов И р-й подгруппы группы соединены с р-м входом элемента ИЛИ и с р-м входом признака перехода блока, выход k-го элемента И (k=1,...,n) р-й подгруппы группы является р-м разрядом k-го информационного выхода блока и соединен с р-м входом k-го элемента ИЛИ группы, выходы элементов ИЛИ группы образуют выход признаков сравнения блока, 20 выход э е ента ИЛИ подключен к ерво у входу элемента И, второй вход и выход которого являются входом синхронизации и выходом сопровождения информации блока соответственно.

1314350

1314350

Диг, 9

1314350

l:3 4

Вз

1314350 ,- .О

Составитель А. Ушаков

Редактор А. Долинич Техред И. Верес Корректор А. Ильин

Заказ 2007/50 Тираж 673 Подписное

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

1 1 3035. Москва, (К 35, Рау шская наб., д. 4/5

Г!роизводственно-полиграфическое предприятие, г. Ужгород, ул. Г1роектная, 4