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

 

УСТРОЙСТВО ДЛЯ МОЛЕЛИРОВАНИЯ ГРАФОВ, содержащее датчик случайных чисел , счетчик, блок моделей вершин, состоящий из первого дешифратора и группы счетчиков, первый блок памяти, первый выход которого соединен с входом датчика случайных чисел, вых.од которого подключен к первым управляющим входам счетчиков группы, четырехфдзный генератор тактовых импульсов , отличающееся тем, что, с целью расширения класса решаемых задач путем формирования сетей Петри, в него введены блок сравнения, .регистр, блок индикации, блок элементов ИЛИ, коммутатор, шифраторы, одновибратор и второй блок памяти, а блок моделей вершин дополнительно содержит группу регистров, регистр, шифратор , второй дешифратор и элемент И-ИЛИ, выход которого соединен с входом перезаписи первого блока памяти и с первым управляющим входом коммутатора , выход которого подключен к информационному входу регистра, выходы старших разрядов которого соединены с группой входов блока сравнения и первыми входами блока элементов ИЛИ, выход которого подключен к первому информационному входу коммутатора , выход счетчика соединен с входом управления считыванием первого блока памяти и с входом второго дешифратора, выход которого соединен с первым управляющим входом регистра блока моделей вершин, второй управляющий вход которого соединен с вторым управляющим входом коммутатора и подключен к первому выходу блока сравнения, первый выход четырехфазi ного генера.тора тактовых импульсов (Л соединен с управляющим входом регистра , выходы младших разрядов которого подключены к входам блока индикации, второй выход четырехфазного генератора тактовых импульсов соединен с входом управления записью первого блокад памяти и с первЫм входом блока сравнения, первый выход второго ка памяти подключен к входу первого шифратора, выход которого подклюOP чен к первому адресному входу перового блока памяти и к управляющим 00 входам регистров группы,выходы которых соединены с информационными входами счетчиков группы, выход каждого из которых подключен к своему входу перезаписи, к соответствующему информационному входу регистра блока моделей вершин, к соответствующим входам шифратора блока моделей вершин и группы входов элемента И-ШШ дополнительный вход которого соединен с третьим выходом четьфехфазного генератора тактовых импульсов, вход которого подключен к второму выходу

f l 9) (! I) СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН (5))4 С 06 F 15 20

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

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ я,, „.13 фМ ® д ЪА

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 36,19809/24-24 (22) 13.07.83 (46) 07.08.85. Бюл. ¹ 29 (72) В.В.Васильев, С.В.Гудыменко, В.В.Кузьмук, А.В.Праховник и В.Г.Хо" лявенко (71) Институт проблем моделирования в энергетике АН Украинской ССР и

Киевский ордена Ленина политехнический институт (53) 681.333(088.8) (56) Авторское свидетельство СССР № 422002, кл. С 06 G 7/48, 1974.

Авторское свидетельство СССР № 879594, кл. G 06 F 15/20, 1981. (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ, содержащее датчик случайных чисел, счетчик, блок моделей вершин, состоящий из первого дешифратора и группы счетчиков, первый блок памяти, первый выход которого соединен с входом датчика случайных чисел, выход которого подключен к первым управляющим входам счетчиков группы, четырехфазный генератор тактовых импульсов, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач путем формирования сетей

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

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

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

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

Особенностью сетей Петри является наличие двух типов вершин: переходов t; и мест р1,а также наличие

10 меток, которые показывают, какие вершины при обходе графа устройство мЬделирует в данный момент времени. Метки располагаются в вершинах мест р (фиг.4) и моделируют в динамике окончание реальных действий в соответствии с заданным алгоритмом, представленным сетью Петри. Местонахождение меток в сети Петри отображается вектором разметки m — (О, 1,, О, 1, I (%)

2Я О, О, О, 1, 0, 1„0, 0, 1, 1, 1) Цифра

О" на первом месте обозначает, что первое место р не содержит метку, tt II

1 на втором указывает, что во вто.ром месте р находится метка, При

25 составлении сети Петри уставнавливается ее топология и начальная разметка i5,. Каждая вершина перехода моделирует время выполнения какогото действия в процессе. Говорят, что переход t срабатывает, если во всех т местах р„,дуги от которых направлены к t., находятся метки. Так, нап1 ример, переходы t и t> могут.сработать. В переход t входят две ду33 ги от мест р и р, в которых х находятся метки. Это является условием начала моделирования действия а, 1

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

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

На фиг. 1 представлена схема устройства для моделирования графов; на фиг. 2 — схема первого блока памяти; на фиг. 3 — схема блока сравнения; на фиг. 4 — пример моделируемой сети Петри, иллюстрирующий рабо- ту устройства.

Устройство (фиг.1) состоит из датчика 1 случайных чисел, счетчика 2, .,блока 3 моделей вершин, первого дешифратора 4, группы счетчиков 5, первого блока 6 памятЪ, четырехфазного генератора 7 тактовых импульсов» блока 8 сравнения, регистра 9, блока 10 индикации, коммутатора 11, блока 12 элементов ИЛИ, первого шифратора 13 и второго шифратора 14, одновибратора 15, второго блока 16 памяти, группы регистров,17, регистра 18, шифратора 19, второго дешифратора 20, второго элемента И-ИЛИ 21

Блок 6 памяти (фиг.2) содержит регистр 22, оперативное запоминающее устройство 23, коммутатор 24 и счетчик 25. входам блока элементов ИЛИ и к второму входу блока сравнения, второй выход которого соединен с вторым информационным входом коммутатора, третий выход второго блока памяти через одновибратор подключен к второму входу второго шифратора, чет- вертый выход второго блока памяти соединен с вторым входом управления считыванием первого блока памяти, выходы регистра блока моделей вершин подключены к вторым управляющим входам счетчиков группы.

Блок 8 сравнения (фиг.3) содержит группу элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ 26, группу инверторов 27, группу инверторов 28, группу элементов И 29, элемент ИЛИ 30 и элемент И 31.

1803 4

ei p. и выходной aiP разметочные вектора. Так, например переходу. срответствует е1 (1« 0, 0, частичных разметочных векторах "1" стоит в том столбце i,,вершина места р (1 4 1 с 16) которого содержит метку. Входной разметочный вектор е1,й показывает, что ему соответствует наличие меток в местах р и р„, при моделировании сети

Петри. В блок 16 памяти записывается

f также начальная разметка ш„ и время моделирования,rlti . Для этого вводится соответствующее число Ni которое определяется N дС

4 lo8 Ч р

Устройство позволяет моделировать время в каждой вершине перехода 1 в пределах 0 < дс; 6,5 мин с точ -. ностью 0,2 с.

3 111 которое характеризуется временем д

В момент начала выполнения действия а2 метки из мест р и р убирают2 11 ся и через время д t в места к г

1 которым направлены дуги от t<(p«} р, ), записываются. Каждый переход

t; характеризуется частичными входным разметочным вектором ei ра и выходным разметочным вектором а р °

Векторы записываются в транспониро- 10 ванной форме. В векторе еI p =(1,1)"

Ч 11

1 на первом месте говорит о том, что в вершине места р находится

2 метка. При составлении частичных векторов предварительно расстанавливаются по возрастанию индексов места вершин. Так, для е2р расстановка соответствующих ему мест р 2 1 р„„,- а для а2У вЂ” р, р „, На фиг. 4 представлен иллюстративный пример моделируемой сети Петри для примера моделирования управления поездами метрополитена. Три поезда непрерывно едут по кольцу, останавливаясь на кажцой из восьми станций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что приводит к их столкно" вению. Вершины мест р — р моде1 }} лируют станции, а наличие меток в р„ (1 1b V 8) моделирует наличие поездов на станциях 4 Наличие ме- 35 ток в местах р (9 4 q 16) модели% рует наличие зеленого света для соответствующих поездов. Каждый из переходов t< (I a i 8) моделирует время дС;, включающее переезд с одной станции на другую и остановку на последующей станции.

Моделирование построенной сети

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

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

В блок 16 памяти предварительно записывается топология моделируемой сети. Для этого графическое изображение сети Петри заносятся в таблицу топологии (фиг.4). В таб- Ю лицу заносятся все переходы t„ сети Петри, причем каждой вершийе перехода t соответствуют входной

При моделировании сетей Петри коммутатор 24 в блоке 6 памяти подключает к адресному входу устройства 23 выход соответствующего адреса из блока 16 памяти.и записывает в него данные о топологии моделируемой сети. После окончания режима перезаписи начинает работу моделирующая часть устройства. Дпя этого в блоке 6 памяти выбираются, начиная с 1-го, выходные разметочные векторы

ei 1 и анализируются группой элементов И 29 на принадлежность их вектору начальной разметки И или вектору текущей разметки п1 " е p,g m (ei y e m, ). Если это имеет место, "F et (11 } то с помощью элемента ИЛИ 30 и элемента И 31 формируется сигнал включения соответствующей модели вершины t< и моделируется время dt s бло1 ке 3 моделей вершин. Одновременно группа элементов ИСКЛЮЧА}0ЩЕЕ ИЛИ 26 и группа инверторов 21 обеспечивают

° ет вычитание вектора е р- в регистре

9 и позволяют установить в нем следующий вектор текущей разметки

° (11+1}

m <" } m," - е1.p, . Вместе с сягналом включения, формируемые элементом

И 31, в блоке моделей вершин из счет. чика 2 поступает адрес ячейки ОЗУ (значение), в которой хранится îIIðàшиваемый входной разметочный вектор

° ф

ei p . Блок 3 моделей вершин начинает моделировать время dt, а блок

8 сравнения опрашивает нринадаезяость

1171803 следующего входного разметочного вектора е(i+1)с вектору m " "1 . ЕсМ1 о ли e(i+1)p е m (1, то выполняются действия, описанные выше. Если e(i+1)Pa > ш " "1., то в счетчике 2 формируется следующий адрес i + 2. Блок 3 моделей вершин работает следующим образом. При перезаписи топологии сети в i --м регистре группы регист- lg ров 17 и в i -м счетчике группы счетчиков 5 устанавливается время т.е. устанавливается число

Н. .При формировании сигнала на мо1 делирование в блоке 8 сравнения и значения индекса i в счетчике 2 дешифратор 20 и регистр 18 формируют сигнал включения соответствующего

-го счетчика в группе счетчиков 5.

Счетчик 5„ работает в режиме вычи- 20 тания и при установке в "0" всех

его . выходов, что соответствует появлению 1 в последнем (4 + 1) разряде, формирует сигнал окончания моделирования дй . По этому 25 сигналу a i --м разряде регистр 18 устанавливается "0" и содержимое

17 i -го регистра из группы регистров 17 переписывается в 5 i -й счетчик группы счетчиков 5. Одновременно с этим на выходе элемента И-ИЛИ

21 формируется сигнал, включающий коммутатор 11 на сложение и через шифратор 19 на коммутатор 24 подается значение i . .Блок 6 памяти по значению i формирует значение соответствующего выходного раэметочного вектора а,по которому в регистре 9 устанавливается следующее значение вектора текущей разметки if",,+ ш " " + ад с, Датчик 1 случайных чисел позволяет моделировать изменение времени at; в заданных пределах, т.е. моделировать случайные изменения заданных значений at;, Заданные пределы реализуются с помощью регистра 22 и счетчика 25, в которых содержится заданный в коэффициент пересчета.

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

1 ачаться моделирование других вершин переходов t „(4 Ф i). На иллюстративном примере показана возможность моделирования время движения поездов в метрополитене одновременно и независимо, т.е. моделировать параллельные процессы управления.

1171803

1171803

1171803

Составитель И.Загорбинина

Редактор В.Иванова ТехредЛ.Мартяшова Корректор И.Эрдейн

Заказ 48б4!41 Тираж 710 Подписное

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

113035, Москва, Ж-35, Раушская иаб., д. 4!5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4