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

СП

О

ч1

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2 - (функциональная схема блока сравнения .:зходных векторов; на фиг. 3 - функциональная схема блока сравнения вы- чодных векторов; на фиг. А - функциональная схема первого преобразойател кода; на фиг 5 - функциональная |;хема второго преобразователя кода; на фиг. 6 - моделируемая сеть Петри. Устройство (фиг. 1) содержит блок йамяти текущей разметки, блок 2 сравнения входных векторов, блок 3 (равнения выходных векторов, блок 4 1:шожения по модулю два, блок 5 логического сложения, блок 6 моделей вер 1шн, реверсивный счетчик 7, мульти- ллексор 8, первьй преобразователь 9 кода, второй преобразователь 10 кода

Блок 2 сравнения входных векторов фиг, 2) содержит m узлов сравнения |2 .)( -0 1 ,, ., эШ, где m - количество вер Йин переходов в .графе), каждый из ко- |торых содержит набор элементов И . ;П. ,lJ. 1-1 1 .Tj.n (где п - число вершин Иест графа Петри), набор элементов И 1 2 .. 1-1.2. 0 .п, элемент ИЛИ 13, кро- :ме того, в состав блока 2 входят на- бор из п т-входовых элементов ИЛИ 14в1 (...,n)s п-входовый элемент :ИПИ 15, двухвходовый элемент И 16,

Блок 3 сравнения выходных векторов (фиг, 3) содержит m наборов из двух- |входовых элементов И 17.-,l-17.V.n5 щабор из п т-входовых элементов ИЛИ 18.1, т-входовьй элемент ИЛИ 19, элемент И 20.

. Блок 4 сложения по модулю два состоит из п элементов ИСКЛЮЧАЩЕЕ ИЛИ 4.1.

Блок 5 логического сложения содержит п двухвходовых элементов ИЛИ 5.1.

Блок 6 моделей вершин содержит m моделей 6, л) вершин, каждая из которых

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

Преобразователь 9-кода (фиг. 4) содержит элемент НЕ 21, элемент И-НЕ 22, г-разрядньй () счетчик 23, дешифратор 24, набор элементов ИЛИ- НЕ 25.-25.т, т-входовый элемент ИЛИ 26, набор из m RS-триггеров 27.V.

Преобразователь 10 кода (фиг. 5) содержит набор из m RS-триггеров 28.J, набор из m элементов ИЛИ-НЕ 29. О, набор из m RS-триггеров 30, и, т-входовьй элемент ИЛИ 31, дешифратор 32, счетчик 33, элемент НЕ 34,

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

Пусть необходимо смоделировать параллельный алгоритм, описанный графом Петри (фиг. 6). Здесь, в чаЬт- ности, могут одновременно выполняться ветви алгоритма, описанные переходами t, t, tj.

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

Значения входных разметочных векторов переходов t,) подаются на входы наборов элементов И 11.V для сравнения со значением вектора текущей разметки, подаваемой в инверсном коде. Например, для перехода t

m,

ьИ

111000000

о о 0111111

elrj 1 о о о о о о о о

000000000

в результате на выходе элемента ИЛИ 13.1 появляется О, разрешающий запуск перехода t на текущем цикле работы устройства. Аналогично разрешается запуск переходов t и tj ,0 с выхода элемента ИЛИ 13, -О подается на первьй вход элемента ИЛИ-НЕ 25,А. По приходу сигнала Ф1 и в случае наличия положительного числа свободных процессоров в реверсивном счетчике 7 (в данном случае в первом цикле работы устройства содержится какое-, либо начальное значение, большее нуля) на выходе элемента И-НЕ 22 появляется логический О, разрешающий работу дешифратора 24, который начинает поочередно выдавать О на вторые входы элементов ИЛИ-НЕ 25.V, причем значение--J зависит от двоичного кода, подаваемого с выходов постоянного работающего счетчика 23, По совпадению логических О на входах элементов ИЛИ-НЕ 25.л) на их выходах появляются логические 1, разрешаютиплексор 8 в блок 1 памяти текущей разметки. По спаду импульса Ф1 все RS-триггеры 27.V приводятся в состояние логического О. В результате по окончанию первой фазы первого цикла работы устройства в реверсивном счетчике 7 содержится О - нет свободных процессоров, а в блоке 1 - новое

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

щие начало имитации срабатывания пе- -JQ значение вектора текущей разметки

реходов t на текущем цикле работы устройства, устанавливающие в состояние 1 RS-триггеры 27. д) и инициm

(2)

(0,0,0,0,0,0,0,0,0).

Указанное верно для случая, ко первоначально занесенное число св ных процессоров три. Если.число дв 15 то после генерации сигналов разреш ния запуска, например, переходов t и tj реверсивный счетчик 7 устанав

Указанное верно для случая, когда первоначально занесенное число свободных процессоров три. Если.число два, 15 то после генерации сигналов разрешения запуска, например, переходов t и tj реверсивный счетчик 7 устанавлиа на выходе элемента И-НЕ 22 появляется 1, которая заирующие через элемент ИЛИ 26 вычитание единицы из числа свободных процессоров, хранящихся в счетчике 7 (считается, что один из процессоров загружается выполнением фрагмента вается в О алгоритма, описанного переходом t).

Логические 1 на выходах RS-триг-2о прещает работу дешифратора 24. В ре- геров 27. л) запускают л1-е модели вер- зультате на элементе ИПИ-НЕ 25.3 раз- шин, кроме того, логические 1 пода- решающий сигнал запуска перехода ta ются на вторые входы элементов И не формируется, имитация изъятия ме- 12.л) и, таким образом, разрешают ток из входного места перехода tj прохождение входных разметочных век- 25 не проводится, а в блоке 1 по спаду торов e- jfiia входы элементов ИЛИ 14 сигнала Ф1 хранится содержимое вектора текущей разметки (0,0,1,0, 0,0,0,0) и сигнал запуска модели вершины 6.3 не формируется. . 30 Предположим, что в условиях задачи введены следующие продолжительности срабатывания переходов dt - 10, t - 25, 4t3 -20 моментов модля формирования суммарного входного вектора, вычитаемого из вектора текущей разметки на данном цикле работы устройства. В данном случае

-м

е2;

еЗД

se;

100000000 01 0000000 001000000

1 1 1000000

дельного времени. Тогда в течение де- qg вяти циклов работы устройства каких- либо изменений не происходит за исключением того, что с приходом каждого импульса Ф2 содержимое счетчиков в запущенных моделях верщин 4 сложения по модулю два, на второй о уменьщается на 1. Если на текущем :

С выходов элементов 14 значение . j подается на первый вход блока

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

t,, tj и tjшо 1 1 1 О О О .0 О О 1 1 1000000 m7 000000000 Одновременно логические 1

с выходов RS-триггеров 27. % подаются на входы элемента ИЛИ 15, на выходе которого формируется логическая 1, разрешающая изменение содержимого бл ка памяти текущей разметки. Эта 1 через элемент И 16 разрешает занесение нового значения вектора текущей разметки с выхода блока 4 через муль

значение вектора текущей р

m

(2)

(0,0,0,0,0,0,0,0,0).

Указанное верно для случая, когда первоначально занесенное число свободных процессоров три. Если.число два, то после генерации сигналов разрешения запуска, например, переходов t и tj реверсивный счетчик 7 устанавливается в О

а на выходе элемента И-НЕ 22 появляется 1, которая завается в О

прещает работу дешифратора 24. В ре- зультате на элементе ИПИ-НЕ 25.3 раз решающий сигнал запуска перехода ta не формируется, имитация изъятия ме- ток из входного места перехода tj не проводится, а в блоке 1 по спаду сигнала Ф1 хранится содержимое вектора текущей разметки (0,0,1,0, 0,0,0,0) и сигнал запуска модели вершины 6.3 не формируется. . Предположим, что в условиях задачи введены следующие продолжительности срабатывания переходов dt - 10, t - 25, 4t3 -20 моментов мо5

цикле работы устройства число свободных процессоров равно нулю, то не ра- ботаюш 1й в результате этого дешифратор 24 не позволяет генерировать управ- 5 ляющие сигналы разрешения запуска переходов, а если ни для одного из переходов t,i не выполняется условие

0.1 -, -(и)

juem -, то не на одном из элементов ИЛИ 13.-О не формируется признак g запуска перехода на текущем цикле. По приходу десятого импульса Ф2 счетчик 6.1 обнуляется и на его де появляется логический О, RS- триггер 27.1 приводится в состояние

1, а на его инверсном выходе появляется О.

По приходу фронта импульса Ф2 на вход элемента НЕ 34, на его выходе появляется О, подаваемый на стробирующий вход дешифратора 32. Дешифратор 32 начинает выдавать поочередно в зависимости от двоичного кода в

непрерывно работающем счетчике 33.

логические О на свои выходы, с которых они подаются на вторые входы элементов ИЛИ-НЕ 29. т). По совпадению нулей на входах элемента ИПИ- НЕ 29,1 на его выходе появляется сиг-ю нал уровня логической I, устанавливающий триггер 30.1 в состояние 1 и через элемент ИЛИ 31 инициирующий прибавление единицы к числу свободных процессоров в счетчике 7 (процес- 15 copj занятый выполнением фрагмента алгоритма, представленного переходом

t 5 освободился). Логическая 1 с выхода триггера 30.1 поступает на первые входы элементов И 17.vi и позволяет подачу вектора Т на входы элементовИЛИ 18J где формируется суммарный выходной вектор ° ju из выходных разметочных векторов переходов t 3 моделирование срабатывания которых оканчивается на данном цикле работы устройства. Так как в данном случае оканчивается только t , то 5° /Г (0,0,0,1,0,0,0,0,0)Р. Далее подается в блок 5 логического Ьложения для сложения со значением вектора текущей разметки. Если срабатывают все три перехода

20

25

30

ч

t

35

45

то

mo yO .00000000 f f7 000100000

m

.(1)

000100000

Кроме того, логическая 1 с выхоа RS-триггера 30.1 подается на первый вход элемента ИЛИ 19, где формируется управляющий сигнал уровня логической 1, разрешающей изменение вектора текущей разметки, который через элемент И 20 подается на второй вход признака записи блока 1. В результате новое значение вектора теку- щей разметки с выхода блока 5 заносится в блок 1. По спаду импульса Ф2 наборы BS-триггеров 28 и 30 устанавливаются, в О. В результате после спада десятого импульса Ф2 в блоке памяти текущей разметки содержится gg значение вектора текущей разметки

;(o,o,o,i.o,o,o,o,o;

в

чике один

а в счет7 число свободных процессоров , Еще через десять циклов работы

45

50

-ю- 15

20

25

30

5

-я gg

устройства аналогично оканчивается моделирование перехода tj , после чего значение вектора текущей разметки в блоке 1 т о (0,0,0, 1,0,1,0,0,0) , в счетчике 7 содержитсячисло свободных процессоров два. В результате возникает возможность запуска на 21 цикле работы устройства перехода tg.

Если начальное число свободных процессоров два, и вначале запущены переходы t и t, то после окончания моделирования перехода t значение текущей разметки ( 0,0, 1 ,1,0,0,0, OjO) , а число свободных процессоров один, следовательно, на одиннадцатом цикле работы устройства запускается переход tg. Далее устройство функционирует аналогично.

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

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

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

Устройство для моделирования графов Петри, содержащее блок сравнения входных векторов, блок сравнения выходных векторов, блок сложения по модулю два, блок логического сложенияj, мультиплексор, блок памяти текущей разметки и блок моделей, причем й информационньй вход блока сравнения входных векторов (,...,m, где m - количество вершин переходов в графе) является входом задания входного вектора графа Петри устройства, 45 информационньй выход блока сравнения входных векторов подключен к первому входу блока сложения по модулю два, выход которого подключен к первому информационному входу мультиплексора, )-й информационный вход блока сравнения выходных векторов является входом задания л}-го. выходного вектора графа Петри устройства, информацион- ный выход блока сравнения выходных . векторов подключен к первому входу блока логического сложения, выход которого подключен к второму информационному входу мультигшексорЯ} выход которого подключен к информаци-.

35

40

50

онному входу блока памяти текущей разметки, выход которого подключен к-(т+1)-му информационному входу блока сравнения входных векторов и к вторым входам блока сложения-по модулю два и блока логического сложения, выход признака окончания операций сравнения блока сравнения входных векторов подключен к первому управляющему входу мультиплексора и к первому входу признака записи блока памяти текущей разметки, выход признака окончания операции сравнения блока сравнения выходных векторов подключен к второму управляющему входу мультиплексора и к второму входу признака записи блока памяти текущей разметки, установочньй вход которого является входом задания начальной разметки устройства, установочньй вход блока моделей является входом задания параметров моделей устройства, тактовый вход блока сравнения входных векторов является первым тактовым входом устройства, тактовьй вход блока сравнения выходных векторов соединен с тактовым входом блока моделей и является вторым тактовым входом устройства, отличающееся тем, что, с целью расщире ния функциональных возможностей устройства путем обеспечения возможности измерения количества вершин переходов, которые могут быть выполнены параллельно, в него введены два преобразователя кода и реверсивньй счетчик , установочньй вход которого является входом задания количества параллельно выполняемых вершин переходов, причем V-й выход признака равенства блока сравнения входных векторов подключен к г)-му разряду информационного входа первого преобразователя кода, тактовьй выход которого подключен к вычитающему входу реверсивного счетчика, выход которого подключен к входу разрешения работы первого преобразователя кода, V-й разряд информационного выхода которого подключен к V-му входу синхронизации блока сравнения входных векторов и к V-МУ входу пуска блока моделей , V-и выход признака окончания моделирования которого подключен к V му

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

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

устройства подключен к вторым тактовым входам первого и второго преобразователей кода, л)-и. разряд информационного выхода второго преобразова- . теля кода додключен к i)-My входу сиН 7

хронизации блока сравнения выходных векторов.

-JL-I

moffmoSiiil бмд

in

TV;

Sn)

и;

1

(mt2}

jW.

IM ;

itirtj IZm)

Ш.

fZ

(1

Ь

ТШ

i

«

(f)

(v;«

(Ц

T§

(t; fi

ГтК

(

tiL 77

r-j(/

5-tf

(tntif

(mi-Z)

тактоб ve Входы

{in)

f

(z.v

IJ)

w

/,

s

(г)

fj;

W

.

Huh CZJ

cm(

aw

ГЫ

Jii K;;

;/7

t2.y; fgg)

W

(

K

(2/

ns

Ш

Ж1з;

TJ

Физ.Э