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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 19) 01) 6 Р 15 ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТЪ ПИС ИЗОБРЕТЕНИ Н АВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРО ГРАФОВ ПЕТ (57) Изобр вой вычисл к устройст ции специа ности для ОДЕЛИРО цифроа именно информав частетях Петтся ихе етение отно ительной те вам для обр аботкиаченияач на ного на шения э(71) Институт проблв энергетике АН УССР(56) Авторское свиде879594, кл. С 06 ЕАвторское свидетеВ 1171803, кл. С 06 ри, и может быть применено в различ-ных отраслях промьппленности для моделирования параллельных процессов.Целью изобретения является повышениеточности, Для этого в устройство вве"дены группы блоков сравнения, блокэлементов ИЛИ, блок элементов ИЛИ-НЕ,два элемента ИЛИ, два элемента И,блок задания временных параметров иблок моделей вершин, причем каждаямодель вершины содержит регистр, счетчик и элемент И. Данное устройствопозволяет моделировать различные сетиПетри, реализующие параллельные алгоритмы и описываемые ими параллельныепроцессы. Параллельность моделирования различных операций и их последо"вательностей реализуется в устройствепутем одновременного срабатываниятребуемого числа переходов. 3 ил.Изобретение относится к вычислительной технике, а именно к устройствам для обработки информации специального назначения, в частности,для решения задач на сетях Петри, 5и может быть применено в различныхотраслях промьппленности для моделирования параллельных процессов.Цель изобретения - повьппение точности и быстродействия моделированияпараллельных процессов.На фиг.1 представлена схема устройства; на фиг.2 и 3 - пример моделируемой сети Петри.Устройство состоит иэ двух групп1 и 2 регистров памяти, коммутатора3, блока 4 памяти, элемента ИЛИ 5,генератора 6 тактовых импульсов, блока 7 индикации, двух групп блоков 8и 9 сравнения, блока 10 элементов ИЛИ,20блока 11 элементов ИЛИ-НЕ, элементовИЛИ 12 и 13, элементов И 14 и 15,блока 16 задания временных параметров, блока 17 моделей вершин, состоящего иэ регистра 18, счетчика 19и элемента И 20,Особенностью графов Петри является наличие двух типов вершин: переходови мест Р , а также наличие меток, которые показывают, какие вершины при.обходе графа устройство моделирует в данный момент времени.Метки располагаются в вершинахмест Р (фиг,2) и моделируют й динамике окончание реальных действий 35в соответствии с заданным алгоритмом,представленным графом Петри.1Местонахождение меток в графе Петри отображается вектором разметки 40первом месте обозначает, что первоеместо Р, не содержит метку, "1" навтором указывает, что во втором месте Р находится метка. При составлении графа Петри устанавливается еетопология и начальная разметка шоКаждая вершина переходамоделирует время выполнения какого-то дейст 50вия в процессе. Говорят, что переход Т срабатывает, если во всех местах Р , дуги от которых направлены кнаходятся метки. Так, например,переходы й и 1 могут сработать.В период 1 входят две дуги от местР и Р, в которых находятся метки,Зто является условием начала моделирования действия а, которое характериэуется временем И. В момент начала выполнения действия а метки из мест Р иРч убираются и через время 11 в места, к которым направлены дуги от С.(Р и Р ), записываются. Каждый переход 1 характеризуется частичнымивходным е 1и выходным разметочными векторами а)- . Векторы записываютсяв трансформированной форме. В векторесе 2-= (1, 1) на первом месте говорито том, что в вершине Р находитсяметкаПри составлении частичных векторов предварительно расстанавливаются по возрастанию индексы мест вершин. Так для е 2. расстановка соответствующих ему мест Р, Р , а для -а 2 ц Р Рю фНа фиг.3 представлен пример моделируемого графа Петри для примера моделирования управления поездами метрополитена. Три поезда непрерывноедут по кольцу, останавливаясь накаждой из восьми станций. Система управления обеспечивает максимальнуюпропускную способность (зеленый свет)наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что приводит ких столкновению. Вершины мест Р, - Рмоделируют станции, а наличие метокв Р (1 й Я8) моделирует наличиепоездов на станциях. Наличие метокв местах о (9- 16) моделируетналичие зеленого света для соответствующих поездов. Каждый из переходовТ(1 й 8) моделирует время И,включающее переезд поезда с однойстанции на другую и остановку на последующей станции.Моделирование построенного графа(сети) Петри в устройстве для моделирования графов Петри позволяет определить оптимальные скорости поездови время их остановки при различнойнагрузке метрополитена,Устройство работает следующим образом. В первуюи вторую 2 группу регистров памяти записывается топология моделируемого графа Петри. Для этого прежде всего составляется таблица топологии (фиг,2)., В таблицу заносятся все переходы С, сети Петри, причем каждой вершине перехода т, соответствует входной еи выходной аразметочные векторы. Так, например, переходу 1, соответствует е= =(1,О,О,О,О,О,О,О,О,1,О,О,О,О,О,О"1357972 Устройство для моделирования графов Петри, содержащее два регистра памяти, коммутатор, блок памяти, первый элемент ИЛИ, генератор тактовых импульсов и блок индикации, о т л ии а 1- =(0,1,0,0,0,0,0,0,1,0,0,0,0, 0,0,0. В частичных разметочных векторах "1" стоит в том столбцевершина места Р (1 116) которо 5 го содержит метку. Входной разметочный вектор е 1 показывает что емуЭ соответствует наличие меток в местах Р и Р, при моделировании данной сети Петри, В первую группу 1 регистров 10 памяти записывается множество входных разметочных векторов е= е 1- ,е 2 р, ,ешь, а во вторую группу 2 регистров памяти - множество выходных разметочных векторов а- = а 1- Ц . )15 а 2 аш 1. В блок 4 памяти заноситФся начальная разметка ш сети Петри.оВ блок задания временных параметров записываются времена моделирования Ьт.; Е 6 для каждой вершины перехода. 2 пПри моделировании сетей Петри в момент начала работы системы в первой группе блоков 8 сравнения (фиг.1) одновременно опрашивается возможность срабатывания всех тп переходов Т , из 25У которых построен исследуемый граф. При этом в каждом блоке 8.д опрашивается выполнение условия принадлежности ет-Е тп . Если хотя бы для одноМ ого перехода т.; имеет место ет Е г , 308 -й управляющий сигнал поступает на соответствующий вход блока моделей вершин и включает соответствутпщую -ю модель вершины перехода С, . Начинается срабатывание перехода 1 и моделирование соответствующей переходуоперации а характеризуемой длительностью модельного времени ЬС;. Срабатывание перехода ; имитируется счетчиком 19.д, работающим в режиме 40 вычитания. Одновременно с формированием д-го управляющего сигнала моделирования в элементах ИЛИ 13 и И 15 формируется сигнал установки и через коммутатор 3 в блоке 4 памяти уста навливается следующее значение вектора текущей разметки. Вектор после-д О 1дующей разметки ш формируется в блоке 11 элементов ИЛИ-НЕ путем вычитания всех входных разметочных век торов ет. в , для которых выполнено усЦловие е- е тп,из вектора начальной- и -фразметки тп =тп - г еп.-. Вычитаниео орсуммы входных разметочных векторовет. обеспечивает исключение пов 7торного моделирования вершины ;, не предусмотренного параллельным алгоритмом, реализуемым в построенной сети Петри. При окончании срабатыванияперехода 1 на всех выходах счетчика19. устанавливаются "0" и формируется сигнал окончания моделирования вершин ;(а ). По обратной связи этотсигнал разрешает запись содержимогорегистра 18,1. в счетчик 19. и подготавливает таким образом 1.-ю модельвершины перехода к следующему этапумоделирования. Одновременно с этимво второй группе блоков 9 сравненияв 9,ь выбирается соответствующий выходной разметочный вектор а-, который через блок 1 О элементов икоммутатор 3 реализует прибавлениеа. - к вектору текущей разметки-а -л 21 - )о 11тп (тп =пт +, а 1.- ). Новое значео о о, Оние вектора текущей разметки записывается в блок 4 памяти. Вычитаниевекторов ет.- и прибавление векторов1 пат.-7 сопровождается на блоке 7 индикации удалением меток иэ вершинмест Р , входящих ви появлением1 1меток в местах Р, дуги к которымнаправлены от ЕТаким образом, предлагаемое устройство для моделирования графовПетри позволяет моделировать различные сети Петри, реализующие параллельные алгоритмы, и описываемые имипараллельные процессы. Параллельностьмоделирования различных операций а,и их последовательностей реализуется в устройстве для моделированияграфов путем одновременного срабатывания требуемого числа переходов С.При этом одновременность срабатывания не противоречит началу срабатывания нескольких перегодовво время моделирования операций ат,-а б-соответствующих запущенным переходом С Й. Напримере (фиг,3) показана возможностьмоделирования времени движения поездов в метрополитене, двигающихся одновременно и в основном независимо,т.е. моделировать параллельные про- .цессы управления,Формула изобретениячающее ся тем, что, сцелью повышения точности, в него введены первая и вторая группы блоков сравнения, блок элементов ИЛИ блок элеФ5 ментов ИЛИ-НЕ, два элемента ИЛИ, два элемента И, блок задания временных параметров и блок моделей вершин, причем каждая модель вершины содержит регистр, счетчик и элемент И, 10 первый выход генератора тактовых импульсов соединен с первыми входами первого и второго элементов И, с первыми входами элементов И моделей вершин и входами синхронизации счетчи ков моделей вершин, выходы счетчиков моделей вершин соединены со своими входами перезаписи и с первыми входами одноименных блоков сравнения второй группы, выходы которых подклю чены к входам первого элемента ИЛИ, выход которого соединен с вторым входом первого элемента И, выход которого подключен к первому входу второго элемента ИЛИ и первому управля ющему входу коммутатора, выходы которого соединены с первой группой инрмационных входов блока памяти, выходы которого подключены к входам блока индикации и первым входам бло ков сравнения первой группы, вторые входы кОторых соединены с соответствующими выходами первого регистра памяти, выходы блоков сравнения первой группы подключены к входам третьего элемента ИЛИ, выход которого соединен с вторым входом второго элемента И, выход которого подключен квторому входу второго элемента ИЛИ.и второму управляющему входу коммутатора, выходы блоков сравнения первой и второй групп соединены с первыми группами входов блока элементовИЛИ-НЕ и блока элементов ИЛИ соответственно, выходы которых подключены к первой и второй группам информационных входов коммутатора, входвторого элемента ИЛИ соединен с входом управления записью блока памяти,вторая группа информационных выходовкоторого подключена к вторым группам входов блока элементов ИЛИ-НЕ иблока элементов ИЛИ, выходы блоказадания временных параметров соединены с информационными входами регистров моделей вершин, разрядные выходыкоторых подключены к информационнымвходам, кроме входов младших разряов, счетчиков одноименных моделейвершин, выходы блоков сравнения первой группы соединены с вторыми входами элементов И одноименных моделейвершин, выход элемента И в каждой модели вершины подключен к входу младшего разряда счетчика, 1357972357972 оставитель И.Загорбинин ехред Л,Сердюкова К ктор Л.П нко Редактор Н,Бобкова каз 6000/50 ткрытии кая наб изводственно-полиграфическое предприятие,г.ужгород,ул,Проектная,4 ВНИИП по 1 303