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

(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ Изобретение относится к вычисли-, тельной технике, а именно к специали зированным стохастическим моделям. Известно устройство, содержащее блок моделей вершин, блок формирования топологии, блок управле {йя, гене ратор импульсов, триггеры, элементы И и элементы ИЛИ 1, Наиболее близким техническим решением к -изобретению является устрой ство для моделирования графов 2, содержащее счетчик импульсов, генератор импульсов, блок моделей вершин и блок формирования топологии, Недостатком таких устройств является их сложность. Цель изобретения - упрощение устройства. Эта цепь достигается тем, что уст ройство для моделирования графов, со держащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей веражн, блок формирования топологии,выходы которого со единены с группой -входов блока моделей вершин,управляющий вход блока фо мирования топологии подключен к вход устройства и дииифратор, выход которого соединен с группой входов блока формирования топологии, содержит ГРАФОВ блок памяти и датчик случайных чисел, выход которого подключен к первому входу блока моделей вершин, второй вход которого соединен с выходом генератора импульсов. Третий вход блока моделей вершин соединен с входом устройства и входом установки в нуль счетчика, первый выход блока моделей вершин подключен к входу дешифратора, выход которого соединен с адресными входами блока памяти. Второй выход блока моделей вершин подключен к входу генератора импульсов, а также тем, что блок моделей веришн содержит wi моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти и коммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И. Выход последнего подключен к Ьчетному входу первого счетчика, выходы которого соединены с группой входов элемента ИЛИ-НЕ, выход которого подключен к счетному входу второго счетчика, к первому входу элемента-ИЛИ, к первому входу блока памяти, к входу сброса триггера и к входу разрешения приема инФлрмации первого счетчика, информационный вход которого является первым входом блока моделей вершин, вторым входом которого является второй вход элемента И. Третьим входом блока моделей вершин являются входы установки в нуль первого и второго счетчиков. Входы коммутатора являются группой входов блока моделей вершин. Выход вт;орого счетчика соеди- ней с адресным входом блока памяти, выход которого является первым выходом блока моделей вершин, Вторым выходом модели вершин является выход элемента ИЛИ, второй вход которого соединен с входом элемента и четвертым входом модели вершин. Вход w-й модели вершин подключен к шине логического нуля, четвертый вход каждой другой модели вершин - со вторым выходом (m-l) модели вершин, а второй выход первой модели вершин является вторым выходом блока моделей вершин. Структурная схема устройства для моделирования графов приведена на фиг. 1; на фиг. 2 дана структурная схема модели вершин; на фиг. 3 - граф, на примере моделирования которого рассматривается работа устройства.

Устройство содержит блок моделей вершин 1, блок формирования топологии 2, счетчик 3, являющийся таймером модели, генератор импульсов 4, блок памяти 5, датчик 6 случайных чисел и дешифратор 7. Блок моделей вершин 1 содержит т моделей вершин , каждая из которых содержит блок памяти 9, коммутатор 10, триггер 11, элемент И 2, элемент ИЛИ 13, элемент ИЛИ-НЕ 14, первый счетчик 15, второй счетчик 16.

Входом устройства является вход 17, на который подается сигнал запуска модели.

Рассмотрим функции, выполняемые структурными элементами устройства.

Блок моделей вершин 1 предназначен для моделирования времени выполнения вершин графа. Каждой модели 8 перед началом моделирования назначается ряд вершин графа. Коммутаторы 10 моделей 8 настраиваются на коммутацию входов, номера которых соответствуют номерам вершин графа, назначенным данной модели. В блок памяти 9 моделей 8 записываются номера назначенных вершин. Так, для графа, приведенного на фиг. 3, вершины , 3, б назначаются первой модели 8, вершины 2, 4, 7- второй модели 8, вер5, 8 - третьей модешиныли 8 Исследуемый граф содержит вер

8

вершины шины

введены дополнительно.для фиксирования момента окончания моделирования. Коммутатор 10 первой модели 8 коммутирует входы вершин , 3, б, .коммутатор 10 второй модели .8 -входы вершин 2, 4, 7, коммутатор 10 третьей модели 8 - входы вершин 5, 8. Структура загрузки блоков памяти 9 моделей 8 для этого случая приведена в таблице.

Таблица

Блок формирования топологии 2 предназначен для моделирования топологии графа. Каждому входу и выходу блока 2 ставится в соответствие определенная вершина графа. Если на i-м входе блока 2 возникает сигнал - 1, то это значит,что в некоторой- модели вершин 8 окончено моделирование предыдущей согласно назначению вершины графа и может быть начато моделирование вершины с номером i. Если на i-м выходе блока 2 возникает сигнал Y 1г то блок моделей вершин 1 должен начать моделирование вершины с номером i . Процесс функционирования блока 2 описывается системой логических выражений У, t причем сигнал Хц могут не совпадать во времени. Так для графа, приведенного на фиг.З значения определяются выражениями (1) .

. ,

х,,

,

14-Л4,,

()

V у

,

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

Датчик случайных чисел б формирует случайные времена выполнения вершин графа. Значения вероятностей F;-U5j, настраивающие датчик 6 на формирование случайного времени tвыполнения вершины графа с номером записываются в а-ю страницу блока п мяти 5. Генератор 4 вырабатывает импульсы с фиксированным периодом следова ния при нулевом сигнале на входе. Счетчик 15 имеет вход установки в нуль, счетный вычитающий вход, инфо мационные входы приема кода и вход разрешения приема кода. Рассмотрим работу устройства на примере моделирования графа, приведенного на фиг, 3. Перед началом моделирования в бл ки 9 моделей 8 записываются номера вершин графа. В блок памяти 5 записываются значения вероятностей F-Ct Выполняется настройка блока формиро вания топологии 2. По сигналу, поступающему на вход 17 устройства, начинается моделирование одной реализации графа. Устанавливаиотся в нуль счетчик 3, счетчики 15 и 16 моделей 8, приводится в исходное состояние блок формирова кия топологии 2. Так как на вход третьей модели поступает нулевой сигнал и содержимое счетчика 15 модели - нулевое, на выходе элемента ИЛИ-НЕ 14 вырабатывается единичный сигнал, устана ливающий Б счетчике 16 код 1. Однов ремо.нно по сигналу с выхода элемент ИЛИ-НЕ 14 сбрасывается триггер 11 модели, из первой ячейки блока памяти 9 считывается код 5. На входы запрета первой и второй модели 8 поступают единичные сигналы, следовательно, на выходах элементов ИЛИ-НЕ 14 этих моделей присутствуют нулевые сигналы, и считывание кодов из блоков 9 не выполняется. Единичный сигнал с выхода первой модели 8 поступает на вход генератора 4 и за прещает его работу. Код поступает на вход дешифратора 7, который вырабатывает сигнал на пятом выходе. В датчик 6 и пятой страницы блока памяти 5 считываются значения {F5(} . Датчик б вырабатывает случайное число ty , кот рое поступает на информационные входы счетчиков 15 всех моделей 8, Одна ко только в третьей модели 8 код -tj запишется в счетчик 15, так как толь ко в этой модели на вход разрешения приема информации поступает разрешающий сигнал с выхода элемента ИЛИНЕ 14. Сигнал с пятого выхода дешифратор 7 поступает на пятый вход блока формирования топологии 2.Х принимает значение 1, и так как ни для одной из вершин графа не выполнены условия (1), сигналы на выходах блока 2 не вырабатываются. Как только в счетчике 15 третьей модели 8 установится код, отличный от нуля, на выходах элементов ИЛИ-НЕ 14, ИЛИ 13 и на выходе модели вырабатываются нулевые сигналы. Теперь во второй модели 8 на всех входах элемента ИЛИ-НЕ 14 присутствуют нулевые сигналы,поэтому на его выходе вырабатывается единичный сигнал, по которому сбрасывается триггер 11 модели, устанавливается код в счетчике 16, разрешается запись информации в счетчик 15. При этом на выходе второй модели сохраняется единичный сигнал. Из блока памяти 9 второй модели 8 считывается код 2. Дешифратор 7 вырабатывает сигнал на втором выходе. Аналогично предыдущему датчик 6 вырабатывает число tfj, которое поступает в регистр счетчика 15 второй модели 8. Так как 1, то в соответствии с формулой (1) 2-1 и на втором выходе блока 2 вырабатывается сигнал, КОТОРЫЙ поступает на входы коммутаторов 10 всех моделей 8.Вторая вершина графа назначена второй модели 8, поэтому срабатывает коммутатор 10 только этой модели, выходной сигнал которого устанавливает триггер 11. Как только в счетчике 15 второй модели 8 устанавливается код tfL,Ha выходах элементов ИЛИ-НЕ 14, ИЛИ 13 и на выходе модели устанавливается нулевой сигнал. Аналогично предьадущем изменяется состояние первой модели 8. В счетчик 15 записывается код t , в счетчик 16 - код 1, устанавливается триггер 11, так как , 1, на выходе модели вырабатывается нулевой сигнал, поступающий на вход генератора 4 и разрешающий его работу. Импульсы генератора 4 поступают на входы всех моделей 8, однако только в первой и второй моделях 8 они проходят на счетные вычитающие входы счетчиков 15, так как только в этих моделях установлены в единичное состояние триггера .11 и открыты элементы И 12. Одновременно импульсы генератора 4 поступают на вход счетчика 3, являющегося таймером модели. Начинается собственно моделирование первой и второй вершин графа. Пусть в некоторый момент времени содержимое счетчика 15 второй модели 8 стало равно нулю. Переключаются элементы ИЛИ-НЕ 14, ИЛИ 13, на выходе модели вырабатывается единичный сигнал, который проходит через элемент И 12 первой модели 8 и останавивает генератор 4. Во второй модели 8сбрасывается триггер 11, в счетчик 16 добавляется 1, и в нем устанавливается код 2, из ячейки блока памяти 9считывается код 4. Дешифратор 7 вырабатывает сигнал на четвертом выоде, датчик 6 формирует число i. , оторое записывается в счетчик 15

второй модели 8, Так как 1( 1 и ранее KB 1/ то в соответствии с формулой (1) 1 и на пятом выходе блока 2 вырабатывается единичный сигнал, который проходит через коммутатор 10 третьей модели 8, устанавливает триггер 11. В результате разрешается прохождение импульсов генератора 4 через элемент И 12 на вход счетчика 15 модели. Причем, так как Х 0, .

Содержимое счетчика 15 второй модели 8 равно 4. и отлично от нуля, поэтому на выходах элементов ИЛИ-НЕ 14, ИЛИ 13, а также на выходах всех моделей 8 вырабатываются нулевые сигналы. Запускается генератор 4. Продолжается моделирование первой вершины графа,и начинается моделирование .пятой вершины графа.

Процесс моделирования оканчивается при выполнении вершин 6, 7, 8 графа.

Код в счетчике 3 в момент возбуждения i-ro выхода блока формирования топологии 2 соответствует времени начала выполнения -и вершины графа. Код в счетчике 3 в момент возбуждения -го выхода дешифратора 7 соответствует времени окончания выполнение -(й вершины графа. В момент окончания выполнения последней вершины графа содержимое счетчика 3 соответствует полному времени моделирования графа.

Благодаря введенным блокам и связям между ними упрощена схема устройства.

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

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

Источники ИНфОрМсЩИИ,

принятые во внимание при экспертизе

кл. G 06 G 7/122, 20.04.79 (прототип

0m

.s /latuvecKuu

I

т , I I

I I I I I I

I u/ I у I I V I

|ЛвЛ1 If oni

j IW; WJ

2

фиъ. 3