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

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

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

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

I

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

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

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

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

Блок 6 памяти (фиг.2) содержит регистр 22, оперативное запоминающее устройство i3, коммутатор 24 и счетчик 25.

Блок 8 сравнения (фиг.З) содержит группу элементов ИС1ШЮЧАЮЩЕЕ ИЛИ 26,- группу инверторов 27, группу инверторов 28, группу элементов И 29, 5 элемент ИЛИ 30 и элемент И 31.

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

0 «, О, О, 1, О, 1, О, О 1. 1. 1).Цифра О на первом месте обозначает, что первое место р не содержит метку, 1 на втором указывает, что во вто-ром месте р находится метка. При

5 составлении сети Петри уставнавливается ее топология и начальная разметка и,„ Каждая вершина перехода t моделирует время выполнения какогото действия в процессе. Говорят, что

jj переход Ц срабатывает, если во всех местах р ,дуги от которых направлены к t. , находятся меТкй. Так, например, переходы tj и t могут, сра6oTatb. В переход t входят две дуги от йест PJ и р , в которых находятся метки. Это является условием начала моделирования действия а2. которое характеризуется.временем л Ц В момент начала выполнения действия р убираютметки из мест ся и через время в места, к t2(pj я которым направлены дуги от ), записываются. Каждый переход t характеризуется частичными вход ным разметочным вектором ei Г и выходным разметочным вектором ai /и Векторы записываются в транспонированной форме. В векторе егД( 1,1) 1 на первом месте говорит о том, что в вершине места р находится метка. При составлении частичных векторов предварительно расстанав.ливаются по возрастанию индексов места вершин. Так, для е2(л расстановка соответствующих ему мест р., р , а для а2/ - pj, Pi . На фиг, 4 представлен иллюстрати ньгй пример моделир уемой сети Петр для примера моделирования управления поездами метрополитена. Три поезда непрерывно едут по кольцу, ост навливаясь на каждой из восьми стан ций. Система управления обеспечивает максимальную пропускную способность (зеленый свет) наибольшему числу поездов и запрещает попадание двух поездов одновременно на одну станцию, что приводит к их столкновению. Вершины мест р РЙ лируют станции, а наличие меток в PV (1 ) моделирует наличие Наличие мепоездов на станциях р-(9 п i 16) моделиток в местах рует наличие зеленого света для соответствующих поездов. Каждый из переходов t (I i 8) моделирует время iJt- , включающее переезд с одной станции на другую и остановку на последующей станции. Моделирование построенной сети Петри в устройстведля моделирования сетей Петри позволяет определить оптимальные скорости поездов и время их остановки при различной наг рузке метрополитена. Устройство работает следующим образом. В блок 16 памяти предварительно записывается топология моделируемой сети. Для этого графическое изображение сети Петри заносится в таблицу топологии (фиг.4). В таблицу заносятся все переходы t сети Петри, причем каждой вершине перехода t соответствуют входной ei и выходной разметочные вектора. Так, например, переходу. t соответствует e1/w« (1, О, О, О, О, О, о, о, о, 1, о, о, о, о, о. a1/u (О, 1, О, О, О, О, 0, О, 1, О, о, о, о, о, о, о ) в частичных разметочных векторах 1 стоит в том столбце i , вершина места Р.(1 ) которого содержит метку. Входной разметочный вектор e1|U показывает, что ему соответствует наличие меток в местах р и р при моделировании сети Петри. В блок 16 памяти записывается также начальная разметка nf и время моделирования .ati . Для этого вводится соответствующее число Ni , 4 log V которое определяете N, iti PZ Устройство позволяет моделировать время в каждой вершине перехода t. в пределах О 4t- 6,5 мин с точгностью 0,2 с. При моделировании сетей Петри коммутатор 24 в блоке 6 памяти подключает к адресному входу устройства 23 выход соответствующего адреса из блока 16 памяти.и записывает в него данные о топологии моделируемой сети. После окончания режима перезаписи начинает работу моделирующая часть устройства. Для этого в блоке 6 памяти выбираются, начиная t 1-го, выходные разметочные векторы ei Д и анализируются группой элементов И 29 на принадлежность их вектору начальной разметки и« или вектору текущей разметки (ei ) . Если это имеет место, то с помощью элемента ИЛИ 30 и элемента И 31 формируется сигнал включения соответствующей модели вершины t и моделируется время At. в блоке 3 моделей вершин. Одновременно группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 26 и группа инверторов 27 обеспечивают вычитание вектора eiju,- в регистре 9 и позволяют установить в нем следующий вектор текущей разметки jff( m,- eijf . Вместе с сигналом включения, формируемым элементом И 31, в блоке моделей вершин из счетчика 2 поступает адрес ячейки ОЗУ (значение), в которой хранится опрашиваемый входной разметочный вектор eiju . Блок 3 моделей вершин начинает моделировать время 4t- , а блок 8 сравнения опрашивает принадлежность

следующего входного разметочного вектора e(i+1)|tr вектору т Если e(i+1 )|с7б m , то выполняются действия, описанные вьппе. Если e(i+1) . , то в счетчике 2 формируется следующий адрес i+2. Блок 3 моделей вершин работает следующим образом. При перезаписи топологии сети в i -м регистре группы регистров 17 и в i -м счетчике группы счетчиков 5 устанавливается время йЦ , т.е. устанавливается число N .При формировании сигнала на моделирование в блоке 8 сравнения и значения индекса i в счетчике 2 дешифратор 20 и регистр 18 формируют сигнал включения соответствующего i -го счетчика в группе счетчиков 5. Счетчик 5,( работает в режиме вычитания и при установке в О всех его. выходов, что соответствует появлению 1 в последнем (V + 1) разряде, формирует сигнал окончания моделирования 4t. . По этому сигналу в i -м разряде регистр 18 устанавливается О и содержимое 17 i -го регистра из труппы регистров 17 переписывается в 5 i -и счетчик группы счетчиков 5. Одновременно с этим на выходе элемента И-1ШИ 21 формируется сигнал, включающий

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

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

ФигЗ

О