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

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

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

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

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

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

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

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

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

Блок 5 сравнения входных векторов предназначен для определения вершин переходов /V, У которых выполнены условия срабатывания и формирования управляющих сигналов вычитания соответствующих входных разметочных векторов от вектора текущей разметки графа Петри.

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

Блок 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ предназначен для реализации вычи- тания V-X входных разметочных векторов из вектора текущей разметки при выполнении условия разрешения срабатывания переходов /V.

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

Блок 9 сравнения выходных векторов предназначен для определения вершин переходов /V, моделирование которых окончено, и формирования управляющих сигналов, 0 позволяющих прибавлять соответствующие v-e выходные разметочные вектора к вектору текущей разметки.

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

Блок 11 коммутации предназначен для

формирования текущего значения| ектора

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

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

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

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

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

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

Опорный генератор 17 предназначен для

формирования непересекающейся двухфазо0 вой последовательности сигналов Ф 1 и Ф2.

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

Блок 2, представленный на фиг. 2, пред- 5 ставляет собой набор из т (по числу т моделируемых вершин переходов /v) п-раз- рядных (по числу п моделируемых вершин мест PS) регистров 2v ()

5

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

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

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

Блок сравнения входных векторов, схема которого приведена на фиг. 3, содержит первую группу из m подгрупп элементов И I9.V. 1...19.v./i (v l,...,m), m элементов ИЛИ-НЕ 20.V, вторую группу из т подгрупп элементов И 21.v. 1,..., 21.v.л, группу из п элементов ИЛИ 22.1,...,22, я, элемент И ЛИ 23

и элемент И 24.

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

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

шГ

A t)

V-M входным разметочным вектором |л, указывающей на то, что т .

Элементы И 21.v, l,...,21.v.« предназначены для формирования сигналов вычитания из вектора текущей разметки тех входных разметочных векторов и, для которых выполнено условие jl С mo

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

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

.

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

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

Блок 8 элементов ИЛИ, схема которого приведена на фиг. 4, предназначен д.чя прибавления V-X выходных разметочных векто; ров 1 к вектору текущей разметки после окончания моделирования срабатывания перехода /v, что позволяет реализовать появление меток в выходных местах перехода /V.

Блок 9 сравнения выходных векторов, схема которого приведена на фиг. 5, содержит группу из m подгрупп элементов И 25.v.l,...,25.v./, группу элементов ИЛИ 26.126./г, элемент ИЛИ 27, элемент И 28.

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

5

0

5

сложению

Шо , по окончанию

вектором текущей разметки моделирования ве)- шин /V.

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

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

Эле.мент И 28 нредназначен для синхронизации сигнала управления изменением век /.ч

по частоте (.

тора текущей разметки

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

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

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

0

5

0

5

Группы эле.ментов И30.1-30.ог предназначены для разрешения или запреп 1,ения в зависимости от состояния соответствующего v-ro разряда счетчика 29. подачи входных разметочных векторов, хранящихся в блоке 2, в блок 5 сравнения входных векторов.

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

Блок 12 контроля живого свойства, схема которого приведена на фиг. 6, содержит элементы НЕ 33, группу триггеров 34.1,...,34, /п, элемент И-НЕ 35, элементы И 36,...,39, элементы ИЛИ 40, 41. индикаторный элемент 42, элемент ИЛИ 43, элемент НЕ 44, регистр 45, счетчик 46.

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

одного активного перехода /v, для

ei -t. с -д, х)

которого выполняется условие р, то

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

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

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

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

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

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

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

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

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

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

Элемент НЕ 44 предназначен для формирования управл яющего сигнала «не все разряды вектора X находятся в состоянии лог. «Ь.

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

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

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

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

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

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

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

1 00,...,0 О 1 0,...,0 00 1,...,0

5

0

5

5

0

5

0

5

flOO,...,i т

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

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

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

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

Блоки 54.е предназначены для хранения признаков возникновения небезопасных разметок мест Ре. При моделировании графа Петри, содержащего т вершин переходов v и п вершин мест ре, в каждом е-м ПЗУ 54.е используются первые m-f-1 адресных входов (1), (2), ..., (т) (m-1-l). При этом в каждом кристалле ПЗУ по адресу

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, записан «О.

1 О О,...,00

О 1 000

00 1,...,00

000,..., О .0 О 0,...,0 О, т+

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

Элемент ИЛИ-НЕ 55 предназначен для формирования сигнала останова устройства 25 в случае обнаружения небезопасного свойства в любом из мест pf графа Петри.

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

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

Моделирование построенного графа ПетОсобенностью графов Петри является на- 30 ри в устройстве для моделирования графов

личие двух типов верщин: переходов t-,-, и мест р,., а также наличие меток, которые показывают, какие вершины при обходе графа устройство моделирует в данный момент времени. Метки располагаются в верщинах

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

Построенный граф Петри, представляющий собой параллельный алгоритм, может

мест PJ (фиг. 7) и моделируют в дина- 35 обладать критическими свойствами, наличие

мике окончание реальных действии, в соответствии с заданным алгоритмом, представленным графом Петри. Местонахождение меток в графе Петри отображается вектором разметки /п (0,1,0,1,1,0,0,0,1,0,1,0,0, l,,). Цифра «О на первом месте обозначает, что первое место pi не содержит метку, и «1 на втором указывает, что во втором месте р2 находится метка. При составлении графа Петри устанавливается ее топо40

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

полнения какого-то действия в процессе. Го-Правильно построенный (реализуемый)

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

ны к v, находятся метки. Так, например.Остановимся подробнее на определениях

переходы ti и t могут сработать. В пере- 50 критических свойств в графах Петри.

Конфликтное свойство. Безконфликтным называется такой граф Петри, который при его обходе не содержит конфликтных разметок вершин мест р,., т е. если при всех разметках графа т-о 6М не наступает ситуации, при которой

ход t2 входят две дуги от места рг и pi i, в которых находятся метки. Это является условием начала моделирования действия 32, которое характеризуется временем А/2. В момент начала выполнения действия аз метки из мест р2 и pii убираются и через время в места, к которым направлены дуги от /2 (РЗ и РЮ) записываются. Каждый переход t. характеризуется частич55

срабатывание одного из возбужденных переходов tj ведет к запиранию других возбужденных переходов Л-.

ным входным вектором р и вы.чодным разметочным вектором ji- Вектора записываются в трансформированной форме. В векторе 1 (1,1) «1 на первом месте говорит о том, что в верщине р находится метка. При составлении частичных векторов предварительно расстанавливаются по возрастанию индексов мест верщин. Так для «-i.ft расстановки соответствующих ему мест р,, ,

- а для R-рз, РЮ.

5

5

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

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

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

Построенный граф Петри, представляющий собой параллельный алгоритм, может

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

55

срабатывание одного из возбужденных переходов tj ведет к запиранию других возбужденных переходов Л-.

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

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

Пример небезопасного графа Петри приведен на фиг. 86. При последовательности срабатываний переходов т t, t, ts в место

10

15

ка 12 контроля живого свойства. Все раз ряды счетчика 29 находятся в состоянии «1 Ввод данных осуществляется при помощи блока 1 ввода следующим образом.

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

Для загрузки топологии графа и началь ной разметки составляется таблица тополо гии графа Петри (см. табл.). Причем каж дой вершине перехода t. соответствует вход ной fl и выходной р, разметочные век тора. Все переходы t-,. графа Петри зано сятся в колонку «Обозначение переходов Например, переходу i соответствует ц (1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0) и - j (0.1,0,0,0,0,0,0,1,0,0,0,0,0,0,0) . В V-X вход

РЗ попадают две метки

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

Возможны два случая несрабатывания переходов t.. В первом случае (фиг. 8в) не существует последовательностЕ) срабатываний переходов (Г, при которой переход /4 может сработать. Это обуславливается тем, что одновременно по одной метке в местах Р2 и РЗ быть не может. Во втором случае (фиг. 8г) срабатывание перехода приводит к тому, что переходы t и /э не могут сработать. Для анализа графа Петри на некритические свойства вводится вектор добавочного условия X { А:, ,..., х,...,, позволяющий моделировать самые различные последовательности срабатываний переходов (Г.

Таким образом, для срабатывания переходов /V при проверке их на живость необходимо совпадение двух условий: р- б m ;

-J (К)ч

X 1.

Последовательное изменение значения вектора проверочных сигналов от {1,1,1, ...,} до (0,0,0, ..., 0) позволяет реализовать полный перебор всех последовательностей срабатываний переходов графа Петри (Г для данной начальной разметки то. Для определения любого критического свойства достаточно двухкратного срабатывания каждого из переходов ,.

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

Записывается топология моделируемого графа Петри в блоки 2, начальная разметка - в регистры 3 и 13, необходимое число циклов работы устройства на одном шаге моделирования - в регистр 45 блот (рз)2. 20 ных (выходных) разметочных векторах «1:

25

стоят в тех 8-х столбцах, которым соот ветствуют места РЕ, являющиеся входными (выходными) для перехода t-,.

Режим моделирования графа Петри включается после подачи сигнала «Пуск на вход установки триггера 50 и подключе нием к устройству опорного генератора 17

На первом шаге моделирования все раз ряды счетчика 29, имитирующего вектор до полнительных условий л, находятся в состоя 30 НИИ «1 и, следовательно, значение всех входных разметочных векторов, хранящихся в блоке 2, подаются через группы элемен тов И 30.1,...,30.т на схему блока 5 срав нения входных векторов, где они одновре менно анализируются в узлах 5.1,...,5.т на

35

40

45

принадлежность к вектору текущей размет ки то ( (: т о). Выполнение условия ц то говорит о том, что переход под лежит запуску на данном цикле моделиро вания, и 1 необходимо вычесть из то Векторы текущей разметки jl, подлежащие вычитанию из то на данном щаге модели рования, через подгруппы элементов 21.1,... 21.m подаются на элементы ИЛИ 22.1,...,22п группы для формирования суммарного вход ного вектора, вычитаемого из вектора то в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ.

-

Одновременно значение всех ji шо через соответствующие выходы подаются на блок 16 для анализа конфликтных ситуаций. Кон фликтная ситуация возникает в случае нали чия «1 в каком-либо е-м разряде более

5Q чем одного вектора |1 С т о . Тогда соответ ствующий блок 50.8 выдает признак конф ликтной ситуации, индицируемый соответст вующим е-м элементом индикации группы 51 а на элементе ИЛИ-НЕ 52 формируется ин версный управляющий сигнал, прекращаю

55 щийподачутактирующихсигналовФ 1 иФ2от генератора 15. Устройство прекращает рабо ту и на блоке 4 индикации индицируется текущая разметка, при которой возникла

0

5

ка 12 контроля живого свойства. Все разряды счетчика 29 находятся в состоянии «1. Ввод данных осуществляется при помощи блока 1 ввода следующим образом.

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

Для загрузки топологии графа и начальной разметки составляется таблица топологии графа Петри (см. табл.). Причем каждой вершине перехода t. соответствует входной fl и выходной р, разметочные вектора. Все переходы t-,. графа Петри заносятся в колонку «Обозначение переходов. Например, переходу i соответствует ц (1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0) и - j (0.1,0,0,0,0,0,0,1,0,0,0,0,0,0,0) . В V-X вход0 ных (выходных) разметочных векторах «1:

ных (выходных) разметочных векторах «1:

тоят в тех 8-х столбцах, которым соответствуют места РЕ, являющиеся входными (выходными) для перехода t-,.

Режим моделирования графа Петри включается после подачи сигнала «Пуск на вход установки триггера 50 и подключением к устройству опорного генератора 17.

На первом шаге моделирования все разряды счетчика 29, имитирующего вектор дополнительных условий л, находятся в состоя- НИИ «1 и, следовательно, значение всех входных разметочных векторов, хранящихся в блоке 2, подаются через группы элементов И 30.1,...,30.т на схему блока 5 сравнения входных векторов, где они одновременно анализируются в узлах 5.1,...,5.т на

5

0

5

принадлежность к вектору текущей разметки то ( (: т о). Выполнение условия ц то говорит о том, что переход подлежит запуску на данном цикле моделирования, и 1 необходимо вычесть из то . Векторы текущей разметки jl, подлежащие вычитанию из то на данном щаге моделирования, через подгруппы элементов 21.1,..., 21.m подаются на элементы ИЛИ 22.1,...,22п группы для формирования суммарного входного вектора, вычитаемого из вектора то в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ.

-

Одновременно значение всех ji шо через соответствующие выходы подаются на блок 16 для анализа конфликтных ситуаций. Конфликтная ситуация возникает в случае наличия «1 в каком-либо е-м разряде более

Q чем одного вектора |1 С т о . Тогда соответствующий блок 50.8 выдает признак конфликтной ситуации, индицируемый соответствующим е-м элементом индикации группы 51, а на элементе ИЛИ-НЕ 52 формируется инверсный управляющий сигнал, прекращаю5 щийподачутактирующихсигналовФ 1 иФ2от генератора 15. Устройство прекращает работу и на блоке 4 индикации индицируется текущая разметка, при которой возникла

конфликтная ситуация. Если конфликтная ситуация не обнаружена на элементе И 24 по совпадению признака наличия запускаемых переходов, формируемым элементом ИЛИ 23, и тактового импульса Ф1, вырабатывается управляющий сигнал, разрешающий через коммутатор 6 запись нового значения вектора текущей разметки определенного в блоке 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, в регистр 3 задания текущей разметки.

Приход сигнала Ф1 инициирует вычитание «1 из значения, хранящегося в счетчике 46. В случае отсутствия на первом шаге моделирования при логическом сигнале «все разряды вектора X в состоянии «1 переходов /v, для которых бы выполнялось условие ц Е , в блоке контроля живого свойства 12 по совпадению сигнала уровня «1 на выходе элемента И 31 и «О на выходе элемента И 24 на элементах И 37 и ИЛИ 41, 43 формируется управляющий сигнал обнаружения неживого свойства, прекращающий подачу тактовых импульсов Ф 1 и Ф2, и индицируемый элементом 42. Если неживое свойство не обнаружено, то логические единицы с выходов элементов ИЛИ-НЕ 20.V (для которых Г g тГ) подаются соответственно на входы блока 9 сравнения выходных векторов и одновременно запоминаются в v-x триггерах группы триггеров 34.1-34.т. Так как для проверки на критические свойства предполагается мгновенное срабатывание переходов (в на- щем случае время срабатывания переходов равно промежутку между появлением сигнала Ф 1 и Ф2), то необходимо на этом же цикле работы устройства промоделировать окончание работы только что запущенных переходов. Значения выходных разметочных векторов I переходов ., запущенных на длинном цикле моделирования, через v-e группы элементов И25.1-25.т подаются на схему формирования суммарного вь ходного вектора (группа элементов ИЛИ 26.1 -26.п), подлежащего сложению с вектором текущей разметки то в блоке 8 элементов ИЛИ. Кроме тог значения всех PL, прибавляемых к то на данном цикле моделирования, и значение подаются на схему блока 18 для контроля безопасного свойства. Небезопасное свойство имеет место при наличии «I в каких либо е-х разрядах объединенного вектора, объединяющего вектор и набор векторов }i, прибавляемых к т(Г на данном цикле работы устройства . Тогда соответствующий блок 54.8 выдает признак конфликтной ситуации, индицируемой соответствующим е-м элементом индикации группы 56 и на элементе ИЛИ-НЕ 55 формируется инверсный управляющий сигнал, прекращающий подачу тактовых импульсов Ф 1 и Ф2 на схему устройства. Если небезопасное свойство не обнаружено, то по приходу тактового импульса Ф 2 на выходе элемента И 28 форм11. ся управляющий сигнал, разрешаюпип ;.:i сение нового значения вектора текуикч :,;,. метки , определенного в блоке 8 -i, ic

ментов ИЛИ, через коммутатор б в регистр задания текущей разметки. Новое значении вектора текущей разметки гпо заносится в регистр 3 и работа устройства повторяется -до установления «О во всех разрядах счетчика 46, что свидетельствует об окончании тага моделирования. Счетчиком 46 вырабатывается управляющий сигнал начала нового щага моделирования, по которому число, хранящееся в регистре 45, заносится в счетчик 46, в регистр 3 через ком5 мутатор 6 заносится значение вектора начальной разметки из регистра 13, все триггеры набора 34 устанавливаются в состояние «О, из счетчика 29, имитирующего вектор дополнительных условий л о вычитается «1. Условием начала нового тага моде0 лирования может быть отсутствие запускаемых переходов . на очередном цикле моделирования, если все разряды счетчика 29 находятся в состоянии «1 (управляющий сигнал формируется на элементах НЕ 44,

5 НЕ 33, И 36, ИЛИ 40). Шаги моделирования повторяются до появления «О во всех разрядах счетчиков 29 и 46, на основании которого элементами И 39, ИЛИ 43 формируется сигнал окончания работы устройства без обнаружения критических

0 свойств.

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

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

40

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

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

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

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

торых соединены с первым и вторым информационными входами коммутатора соответственно, выход признаков сравнения блока сравнения входных векторов подключен к второму входу блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый выход блока регистров задания выходных векторов подключен к первому информационному входу блока сравнения выходных векторов, выход признаков сравнения которого подключен к второму входу блока элементов ИЛИ, выход сопровождения инфорации блока сравнения выходных векторов подключен к второму управляющему входу коммутатора, отличающееся тем, что, с целью расширения функциональных возможностей за счет контроля наличия критических свойств в графах, в него введены регистр начальной разметки, б. юк коммутации, блок контроля конфликтных ситуаций, блок контроля безопасного свойства, блок контроля живого свойства, элемент ИЛИ, выход регистра нача; ьной разметки подключен к третьему информационному входу коммутатора, с второго по ш-й выходы блока регистров задания выходных векторов (где m - число моделируемых вершин переходов) подключены к второму по т-й информационным входам блока сравнения выходных векторов соответстенно, с первого но я-й информационные выходы которого (где п - число моделируемых верн,1ин мест) подключены к первому по п-й информационным входам блока контроля безопасного свойства соответственно, (п-|-1)-й информационный вход блока контроля безопасного свойства подключен к прямому выходу регистра задания текушей развертки, с нер- вого по т-й выходы блока регистров задания входных векторов подключены к первому но т-й информационным входам блока коммутации соответственно, с первого но т-й выходы которого подключены к второму по (т+1)-й информационным входам блока сравнения входных векторов соответственно, с первого по т-й информацион- ные выходы которого подключены к первому по т-й информационным входам блока контроля конфликтных ситуаций, выход признака конфликтной ситуации которого подключен к первому входу останова генератора тактовых импульсов, первый выход которого подключен к входам синхронизации блока контроля живого свойства и блока сравнения входных векторов, с первого по т-й выходы признака перехода которого подключены к первому но т-й одноименным входам блока сравнения выходных векторов и блока контроля живого свойства, выход признака неживого свойства которого подключен к второму входу останова генератора тактовых импульсов, третий вход останова-которого подключен к выходу признака небезопасной разметки блока контроля безопасного свойства, выход признака нового цикла блока контроля живого свойства подключен к перво

0

0

5

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

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

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

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

0

5

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

0

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

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

элемента И ,...,n,) р-й подгруппы группы является р-м разрядом k-ro информационного выхода блока и соединен с р-м входом k-ro элемента ИЛИ группы, выходы элементов ИЛИ группы образуют выход признаков сравнения блока,

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

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

US.

PA

фиг. 7

х-х J

.О bps

и

2

фиг. 8

и

«