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

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

Иллюстрации

Показать все

Реферат

 

Союз Советсккк

Социалистнческнх

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ (63) Дополнительное к авт, сеид-ву (22) Заявлено 070180 (2J)2865035/18-24 (5 )М. Етт. с присоединением заявки Ио (23) Приоритет

G 06 Р 15/20

Государствеииый комитет ссср по делам изобретений и открытий

Опубликовано 071181. Бюллетень М 41

Дата опубликовання описания 071181 (53) УДК 681.333 (088. 8) (72) Авторы изобретения

Э.А. Баканович, В.И. Новиков; Л.Г. Лопато и H.È. Мельник (71) Заявитель

Минский радиотехнический институт (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

1 РАФОВ

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

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

Наиболее близким техническим решением к .изобретению является устройство для моделирования графов (2), содержащее счетчик импульсов, генератор импульсов, блок моделей вершин и блок формирования топологии.

Недостатком таких устройств явля- 15 ется их сложность.

Цель изобретения — упрощение устройства.

Эта цель достигается тем, что устройство для моделирования графов, со- 20 держащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, выходы которого со-, единены с группой входов блока моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства и дешифратор, выход которого соединен с группой входов блока формирования топологии, содержит 30 блок памяти и датчик случайных чисел, выход которого подключен к первому входу блока моделей вершин, второй вход которого соединен с выходом генератора импульсов. Третий вход блока моделей вершин соединен с входом устройства и входом установки в нуль счетчика, первый выход блока модейей вершин подключен к входу дешифратора, выход которого соединен с адресными входами блока памяти. Второй выход блока моделей вершин подключен к входу генератора импульсов, а также тем, что блок моделей вершин содер" жит т моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти и коммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И. Выход последнего подключен к счетному входу первого счетчика, выходы которого соединены с группой входов элемента ИЛИ-НЕ, выход которого подключен к счетному входу второго счетчика, к первому входу элемента.ИЛИ, к первому входу блока памяти, к входу сброса триггера и к входу разрешения приема ин8 19594

Таблица тья модель 5

° 1! !!!2I! 8 4 3 9 ! 6!! 9 !!9!!

60 формации первого счетчика, информационный вход которого янляется первым входом блока моделей вершин, вторым входом которого является второй вход элемента И. Третьим входом блока моделей вершин являются входы устанонки в нуль первого и второго счетчиков. Входы коммутатора являются группой входов блока моделей вершин. Выход второго счетчика соединен с адресным входом блока памяти, выход которого является первым выходом блока моделей вершин. Вторым выходом модели вершин является выход элемента ИЛИ, второй вход которого соединен с входом элемента ИЛИ-HE u четвертым входом модели вершин. Вход .!и-й модели вершин подключен к шине логического нуля, четвертый вход каждой другой модели вершин — со вторым выходом (rn-1) модели вершин, а второй выход первой модели вершин является вторым выходом блока моделей вершин. Структурная схема устройства для моделирования графов приведена на фиг. 1; на фиг. 2 дана структурная схема модели вершин; на фиг. 3 — граф, на примере моделиро-. вания которого рассматривается работа устройства.

Устройство содержит блок моделей вершин 1, блок формирования топологии 2, счетчик 3, являющийся таймером модели, генератор импульсов 4, блок памяти 5, датчик 6 случайных чисел и дешифратор 7. Блок моделей вершин 1 содержит m моделей вершин 8,-8, каждая из которых содерБлок формирования топологии 2 предназначен для моделиронания топологии графа. Каждому входу и выходу блока 2 ставится в соответствие определенная вершина графа. Если íà i -м входе блока 2 возникает сигнал Х; =1, то это значит,что в некбторой: модели нершин 8 окончено моделирование предыдущей согласно назначению вершины графа и может быть начато моделирование вершины с номером . Если на !-м выходе блока 2 возникает сигнал

Y =1, то блок моделей вершин 1 должен начать моделирование вершины с номером . Процесс функционирования блока 2 описывается системой логичесжит блок памяти 9, коммутатор ) П, триггер 1, элемент И ) 2, элемент

ИЛИ 13, элемент ИЛИ-НЕ 14, первый счетчик 15, второй счетчик 16.

Входом устройства является вход

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

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

Блок моделей вершин 1 предназначен для моделирования времени выполнения вершин графа. Каждой модели 8 перед началом моделирования назначается ряд вершин графа. Коммутаторы

10 моделей 8 настраиваются на ком С э мутацию входов, номера которых соответствуют номерам вершин графа, назначенным данной модели. В блок памяти 9 .моделей 8 записываются номера назначенных вершин. Так, для

Щ графа, приведенного на фиг. 3, нерся первой модели 8, вершины 2, шины 5, 8 — третьей модели 8. Исследуемый граф содержит вершины 1 †8, вершины 9 введены дополнительно.для фиксирования момента окончания моделирования.

Коммутатор 10 первой модели 8 коммутирует входы вершин 1, 3, 6, .коммутатор 10 второй модели

8 -входы вершин 2 4 7, коммутатор 10 третьей модели 8 — входы вершин 5, 8 . Структура загрузки блоков памяти 9 моделей 8 для этого случая приведена н таблице. ких выражений Ч;= П Хх, причем сигналы

Х могут не совпадать во времени.

Так для графа, приведенного на фиг.3, значения определяются выражениf ями (1) . (=.X„> 4 Х лХ4 М7 — X7 (ц- Х4 л Х, (9= Хь Х8 (1 ) !

М -х лх4, чь= хьлх7 f9 = Xg

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

Датчик случайных чисел б формирует случайные времена выполнения вершин графа. Значения вероятностей

879594 )), настраивающие датчик 6 на формирование случайного времени выполнения вершины графа с номером записываются в -ю страницу блока памяти 5.

Генератор 4 вырабатывает импульсы с фиксированным периодом следования при нулевом сигнале на входе.

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

Рассмотрим работу устройства на примере моделирования графа, приведенного на фиг. 3.

Перед началом моделирования в блоки 9 моделей 8 записываются номера вершин графа. В блок памяти 5 записываются значения вероятностей Р (t)).

Выполняется настройка блока формирования топологии 2.

По сигналу, поступающему на вход 20

17 устройства, начинается моделирование одной реализации графа. Устанавливаются в нуль счетчик 3, счетчики 15 и 16 моделей 8, приводится в исходное состояние блок формирова- 5 ния топологии 2.

Так как на вход третьей модели поступает нулевой сигнал и содержимое счетчика 15 модели — нулевое, на выходе элемента ИЛИ-НЕ 14 вырабатывается единичный сигнал, устанавливающий в счетчике 16 код 1. Одновременно по сигналу с выхода элемента

ИЛИ-НЕ 14 сбрасывается триггер 11 модели, из первой ячейки блока памяти 9 считывается код 5 . На входы запрета первой и второй модели 8 поступают единичные сигналы, следовательно, на выходах элементов ИЛИ-НЕ 14 этих моделей присутствуют нулевые сигналы, и считывание кодов из блоков 9 не выполняется. Единичный сигнал с выхода первой модели 8 поступает на вход генератора 4 и запрещает его работу.

Код ™ 5 поступает на вход де- 45 шифратора 7, который вырабатывает сигнал на пятом выходе. В датчик 6 из пятой страницы блока памяти 5 считываются значения (Fg (e) ) . Датчик 6 вырабатывает случайное число 1, кото-р() рое поступает на информационные входы счетчиков 15 всех моделей 8. Однако только в третьей модели 8 код 1 запишется в счетчик 15, так как толь- ко в этой модели на вход разрешения у приема информации поступает разрешающий сигнал с выхода элемента ИЛИНЕ 14.

Сигнал с пятого выхода дешифратора

7 поступает на пятый вход блока фор- 60 мирования топологии 2. М принимает значение 1, и так как ни для одной из вершин графа не выполнены условия (1), сигналы на выходах блока 2 не вырабатываются.

Как только в счетчике 15 третьей модели 8 установится код, отличный от нуля, на выходах элементов ИЛИ-HE 14, ИЛИ 13 и на выходе модели вырабатываются нулевые сигналы. ТепЕрь во второй модели 8 на всех входах элемента ИЛИ-НЕ 14 присутствуют нулевые сигналы, поэтому на его выходе вырабатывается единичный сигнал, по которому сбрасывается триггер 11 модели, устанавливается код 1 в счетчике 16, разрешается запись информации в счетчик 15. При этом на выходе второй модели сохраняется единичный сигнал.

Из блока памяти 9 второй модели 8 считывается код 2 . Дешифратор 7 вырабатывает сигнал на втором выходе °

Аналогично предыдущему датчик 6 вцрабатывает число 1, которое поступает в регистр счетчика 15 второй модели 8. Так как X =1, то в соответствии с формулой (1) Yg= 1 и на втором выходе блока 2 вырабатывается сигнал, который поступает на входы коммутаторов 10 всех моделей 8.Вторая вершина графа назначена второй модели 8, поэтому срабатывает коммутатор

10 только этой модели, выходной сигнал которого устанавливает триггер 11.

Как только в счетчике 15 второй модели 8 устанавливается код ty,на выходах элементов ИЛИ-HE 14, ИЛИ 13 и на выходе модели устанавливается нулевой сигнал. АнаЛогично предыдущему изменяется состояние первой модели 8. В счетчик 15 записывается код в счетчик 16 — код 1, устанавливается триггер 11, так как Х„ =1, (< =1, на выходе модели вырабатывается нулевой сигнал, поступающий на вход генератора 4 и разрешающий его работу.

Импульсы генератора 4 поступают на входы всех моделей 8, однако только в первой и второй моделях 8 они проходят на счетные вычитающие входы счетчиков 15, так как только в этих моделях установлены в единичное состояние триггера 11 и открыты элементы И 12. Одновременно импульсы генератора 4 поступают на вход счетчика 3, являющегося таймером модели °

Начинается собственно моделирование первой и второй вершин графа.

Пусть в некоторый момент времени содержимое счетчика 15 второй модели 8 стало равно нулю. Переключаются элементы ИЛИ-HE 14, ИЛИ 13, на выходе модели вырабатывается единичный сигнал, который проходит через элемент И 12 первой модели 8 и останавливает генератор 4. Во второй модели

8 сбрасывается триггер 11, в счетчик

16 добавляется 1, и в нем устанавливается код 2, из ячейки блока памяти

9 считывается код 4. Дешифратор 7 вырабатывает сигнал на четвертом выходе, датчик 6 формирует число 1 которое записывается в счетчик 15

879594

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

Содержимое счетчика 15 второй модели 8 равно 4 и отлично от нуля, поэтому на выходах элементов ИЛИ-НЕ

14, ЯЙИ 13, а также на выходах всех моделей 8 вырабатываются нулевые сигналы. Запускается генератор 4. Продолжается моделирование первой вершины графа,и начинается моделирование пятой вершины графа.

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

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

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

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

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

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок моделей вершин содержит m моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики, элемент ИЛИ, триггер, элемент ИЛИ-HE блок памяти и коммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И, выход которого подключен к счетному входу первого счетчика, выходы которого соединены с группой входов элемента

ИЛИ-НЕ, выход которого подключен к счетному входу второго счетчика, к первому входу элемента ИЛИ, к первому входу блока памяти, к входу сброса триггера и к входу разрешения приема информации первого счетчика, информационный вход которого является первым входом блока моделей вершин, вторым входом которого является второй вход элемента И, третьим входом блока моделей вершин являются входы .установки в нуль первого и второго счетчиков, входы коммутатора являются группой входов блока моделей вершин, выход второго счетчика соединен с адресным входом блока памяти, выход которого является первым выходом блока моделей вершин, вторым выходом модели вершин является выход элемента ИЛИ, второй вход которого соединен с входом элемента ИЛИ-НЕ и четвертым входом модели вершин, причем четвертый вход м-й модели вершин подключен к .шине логического нуля, четвертый вход каждой другой модели вершин соединен со вторым выходом (w-1)модели вершин, второй выход первой модели вершин является вторым выходом блока моделей вершин;

Источники информации, принятые во внимание при экспертизе . 1. Авторское свидетельство СССР

9 422002, кл. 6 06 G 7/48, 1972.

2. Авторское свидетельство СССР по заявке 9 2670963/24, кл. G 06 G 7/122, 20.04.79 (прототип).

879594 г ! (l

1 !

l

1 (! I

<с5> i(5l $ фиг. 2

ВНИИПИ Заказ 9722/20 Тираж 748 Подписное

Филиал ППП "Патент", r.Óæroðoä, ул.Проектная, 4