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

 

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

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

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

РЕСПУБЛИК (ц 4 G 06 F 15/20

Ф л

j ю

Уу

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

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

Мвй

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 4150088/24-24 (2) 21.11.86 (46) 23.06.88. Бюл. И 23 (7!) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев, В.В.Кузьмук, Е.Б.Лисицин и В.А.Шумов (53) 681,333(088.8) ю (56) Авторское свидетельство СССР

В 879594, кл. G 06 F 15/20, 1980.

Авторское свидетельство СССР

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

1405070

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

Целью изобретения является расшиение функциональных возможностей стройства путем обеспечения возмож- 10 ости изменения количества вершин ереходов, которые могут быть выолнены параллельно, На фиг. 1 представлена функциоальная схема устройства; на фиг.2 — 15 ункциональная схема блока сравнения ходных векторов; на фиг. 3 — функци нальная схема блока сравнения выодных векторов; на фиг. 4 — функциоальная схема первого преобразователя 20 ода; на фиг. 5 — функциональная хема второго преобразователя кода; а фиг. 6 — моделируемая сеть Петри.

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

Блок 2 сравнения входных векторов (фиг. 2) содержит m узлов сравнения .1(Я=1,...,m, где m — количество вер1пин переходов в,графе), каждый из которых содержит набор элементов И

11,4,1-11.4.п (где и — число вершин мест графа Петри), набор элементов

Я 12.4.1-1.2.4 .п, элемент ИЛИ 13, кроме того, в состав блока 2 входят набор из и ш-входовых элементов ИЛИ

14.1 (1=1,...,п), и-входовый элемент

ИЛИ 15, двухвходовый элемент И 16.

Блок 3 сравнения выходных векторов (фиг. 3) содержит m наборов из двух входовых элементов И 17,4.1-17,4.п, набор из n m-входовых элементов ИЛИ

18.1, ш-входовый элемент ИЛИ 19, эле50 мент И 20. . Блок 4 сложения по модулю два состоит из п элементов ИСКЛЮЧАЮЩЕЕ ИЛИ

4.1.

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

5.1.

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

Преобразователь 9 кода (фиг. 4) содержит элемент НЕ 21, элемент И-HE

22, г-разрядный (2" =тп) счетчик 23, дешифратор 24, набор элементов ИЛИНЕ 25.1-25.m, m-входовый элемент

ИЛИ 26, набор из m RS-триггеров

27. д.

Преобразователь 10 кода (фиг. 5) сопепжит набор из m RS-триггеров

28.4 набор из m элементов ИЛИ-НЕ

29.4, набор из m RS-триггеров 30.4

m-входовый элемент ИЛИ 31 дешифратор

32, счетчик 33, элемент НЕ 34.

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

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

Для загрузки топологии графа и начальной разметки составляется таблица топологии графа Петри (фиг, 6).

Причем каждой вершине перехода 1„ соответствуют входной и выходной разметочные векторы, a4.

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

Например, для перехода t ш„111000000

1т, 0001 1 ) 1 1 1 е1 1 0 0 0 0 0 0 0 0

Р

000000000

В результате на выходе элемента

ИЛИ 13,1 появляется "0", разрешающий запуск перехода t на текущем цикле работы устройства. Аналогично разрешается запуск переходов t g u t, 0 " с выхода элемента ИЛИ 13. 4 подается на первый вход элемента ИЛИ-НЕ 25,4.

По приходу сигнала Фl и в случае наличия положительного числа свободных процессоров в реверсивном счетчике 7 (в данном случае в первом цикле работы устройства содержится какое-, либо начальное значение, большее нуля) на выходе элемента И-HE 22 появляется логический "0", разрешающий работу дешифратора 24, который начи3 1405070

4 нает поочередно выдавать "О" на вто- типлексор 8 в блок рые входы элементов ИЛИ-НЕ 25.1, при- разметки. По спаду чем значение 4 зависит от двоичного RS-триггеры 27. и кода подаваемого с выходов постоянно- ние логического 0

Ф

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

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

12.р и, таким образом, разрешают ток из входного ме прохождение входных разметочных век- 25 не проводится, а в торов е на входы элементов ИЛИ 14 сигнала Ф1 хранитс

/ для формирования суммарного входно- тора текущей разме го вектора, вычитаемого из вектора 0,0,0,0) и сигнал

F текущей разметки на данном цикле ра- вершины 6.3 не фор боты устройства. В данном случае ЗО Предположим, чт

el 1 О О О О О О О О е2010000000

Р еЗр 001000000

". 111ОООООО ш О О О О О О О О О ве- 111000000

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

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

Происходит имитация удаления меток входных мест запускаемых переходов

Ь, tg H ш р 1 1 1 О О О О О О

Одновременно логические "1" с выходов RS-триггеров 27. 4 подаются на входы элемента ИЛИ 15 на выходе которого формируется логическая "1", разрешающая изменение содержимого бло ка памяти текущей разметки. Эта "1" через элемент И 16 разрешает занесение нового значения вектора текущей разметки с выхода блока 4 через муль1 памяти текущей импульса Ф1 все риводятся в состояВ результате по азы первого цикла в реверсивном счет О" — нет свободв блоке 1 — новое екущей разметки ,о,о) . для случая, когда сенное число свободи. Если число два, сигналов разрешемер, переходов t четчик 7 устанавливыходе элемента

"1", которая заифратора 24, В рете ИЛИ-НЕ 25.3 разпуска перехода t,q митация изъятия места перехода t3 блоке 1 по спаду я содержимое вектки ш =(0,0,1,0, запуска модели мируется. о в условиях задачи введены следующие продолжительности срабатывания переходов Dt <—

10, dt — 25, 8t — 20 моментов модельного времени. Тогда в течение девяти циклов работы устройства какихлибо изменений не происходит за исключением того, что с приходом каждого импульса Ф2 содержимое счетчиков в запущенных моделях вершин до уменьшается на "1". Если на текущем цикле работы устройства число свобод-. ных процессоров равно нулю, то не работающий в результате этого дешифратор 24 не позволяет генерировать управ45 ляющие сигналы разрешения запуска переходов, а если ни для одного из переходов tq не выполняется условие рр е m,", то не на одном из элементов ИЛИ 13,4 не формируется признак запуска перехода на текущем цикле.

По приходу десятого импульса Ф2 счетчик 6,1 обнуляется и на его выхо де появляется логический 0, В$t1

1 триггер 27.1 приводится в состояние

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

По приходу фронта импульса Ф2 на вход элемента HE 34, на его выходе появляется "О", подаваемый на строби70

5 ЙОЗ0 ! рующий вход дешифратора 32. Дешифра. тор 32 начинает выдавать поочередно в зависимости от двоичного кода в непрерывно работающем счетчике 33, логические "0" на свои у-е выходы, с которых они подаются на вторые вхо дыы элементов ИЛИ-HE 29.3. По совпа, дению нулей на входах элемента ИЛИI НЕ 29.1 íà его выходе появляется сиг- 10

I Hàë уровня логической "1", устанавливающий триггер 30.1 в состояние "1" и через элемент ИЛИ 31 инициирующий прибавление единицы к числу свободных процессоров в счетчике 7 (процес- 15 сор, занятый выполнением фрагмента алгоритма, представленного переходом освободился). Логическая "1" с выхода триггера 30.! поступает на первые входы элементов И 17.4 и по- 20 зволяет подачу вектора р на входы элементов ИЛИ 18, где формируется суммарный выходной вектор э" р из выходных разметочных векторов переходов t< моделирование срабатывания 25 .которых оканчивается на данном цикле работы устройства. Так как в данном случае оканчивается только t „, то р = g=(1) 0,0,1,0,0,0,0,0) . Далее

Э"р подается в блок 5 логического 30 сложения для сложения со значением вектора текущей разметки, Если срабатывают все три перехода t< tg

TG устройства аналогично оканчивается моделирование перехода t» после чего значение вектора текущей разметки в блоке 1 m (0,0,0,1,0,1,0,O,O)F, в счетчике 7 содержится число свободных процессоров два. В результате возникает воэможность запуска на 21 цикле работы устройства перехода t<.

Если начальное число свободных процессоров два, и вначале запущены переходы t и t< то после окончания моделирования перехода С„ значение текущей разметки m " =(0,0, I 1,0,0,0, 0,0), а число свободных процессоров

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

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

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

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

Устройство для моделирования гра- фов Петри, содержащее блок сравнения

40 ш о 0 0 0 0 0 0 0 0 0

". o o o i o c o o o (ш 000100000

Кроме того, логическая "1" с выхода BS-триггера 30.1 подается на первый вход элемента ИЛИ 19, где формируется управляющий сигнал уровня логической "1", раэрешаюшей изменение вектора текущей разметки, который через элемент И 20 подается на второй ..вход признака записи блока 1. В результате новое значение вектора текущей разметки m "! с выхода блока 5 заносится в блок 1. По спаду импульса

Ф2 наборы RS-триггеров 28 и 30 устанавливаются в "0". В результате после спада десятого импульса Ф2 в блоке памяти текущей разметки содержится значение вектора текущей разметки

m "" =(0,0,0,1,0,0,0,0,0), а в счетчйке 7 — число свободных процессоров один, Еще через десять циклов работы входных векторов, блок сравнения выходных векторов, блок сложения по модулю два, блок логического сложения, мультиплексор, блок памяти текущей раз ме тки и блок моделей, причем -й информационный вход блока сравнения входных векторов (4 =1,...,m, где m— количество вершин переходов в графе) является входом задания g-ro входного вектора графа Петри устройства, информационный выход блока сравнения входных векторов подключен к первому входу блока сложения по модулю два, выход которого подключен к первому информационному входу мультиплексора, -й информационный вход блока сравнения выходных векторов является входом задания 9-ro выходного вектора графа Петри устройства, информацион- ный выход блока сравнения выходных векторов подключен к первому входу

1 блока логического сложения, выход которого подключен к второму информационному входу мультиплексора, выход которого подключен к информаци1405070 онному входу блока памяти текущей разметки, выход которого лодключен к (оп+1)-му информационному входу блока сравнения входных векторов и к вторым входам блока сложения по модулю два и блока логического сложения, выход признака окончания операций сравнения блока сравнения входных векторов подключен к первому уп- 10 равляющему входу мультиплексора и к первому входу признака записи блока памяти текущей разметки, выход признака окончания операции сравнения блока сравнения выходных векторов 15 подключен к второму управляющему входу мультиплексора и к второму входу признака записи блока памяти текущей разметки, установочный вход которого является входом задания начальной 20 разметки устройства, установочный вход блока моделей является входом задания параметров моделей устройства, тактовый вход блока сравнения входных векторов является первым так- 25 товым входом устройства, тактовый вход блока сравнения выходных векторов соединен с тактовым входом блока моделей и является вторым тактовым входом устройства, о т л и ч а ю — ЗО щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения возможности измерения количества вершин пере- . ходов, которые могут быть выполнены параллельно, в него введены два пре. образователя кода и реверсивный счетчик, установочный вход которого является входом задания количества параллельно выполняемых вершин переходов, причем 4-й выход признака равенства блока сравнения входных векторов подключен к 1-му разряду информационного входа первого преобразователя кода, тактовый выход которого подключен к вычитающему входу реверсивного счетчика, выход которого подключен к входу разрешения работы первого преобразователя кода, 4-й разряд информационного. выхода которого подключен к 4-му входу синхронизации блока сравнения входных векторов и к 1-му входу пуска блока моделей, -й выход признака окончания моделирования которого подкжочен к 4 -му разряду информационного входа второго преобразователя кода, тактовый выход которого подключен к суммирующему входу реверсивного счетчика, первый тактовый вход устройства подключен к первому тактовому входу первого преобразователя кода, второй тактовый вход устройства подключен к первому тактовому входу второго преобразователя кода, третий тактовый вход устройства подключен к вторым тактовым входам первого и второго преобразователей кода, 4 -й разряд информационного выхода второго преобразова- . теля кода подключен к -му входу син-, хронизации блока сравнения выходных векторов.

1405070

1405070!

405070! 405070

Фиг.4 4О507О

Составитель А.Мишин

Редактор И.шулла Техред y,дидык Корректор И;Муска

Тираж 704 П одп исно е

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

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

Заказ 3104/54

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