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

Союз Советсккк Социалистическнв Республик(61) Дополнительное к авт, сенд-ву(22)Заявлено 070180 (23)2865035/18-24 (51)М, Кй. с присоединением заявки Ио(23) Приоритет 6 Об Р 15/20 Государствеиицй комитет ссср по делам изобретений и открытий(71) Заявитель Минский радиотехнический институт(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВИзобретение относится к вычислительной технике,а именно к специализированным стохастическим моделям.Известно устройство, содержащееблок моделей вершин, блок формирования топологии, блок управления, генератор импульсов, триггеры, элементы И и элементы ИЛИ 11.Наиболее близким техническим решением к изобретению является устройство для моделирования графов 2,содержащее счетчик импульсов, генератор импульсов, блок моделей вершини блок формирования топологии,Недостатком таких устройств является их сложность.Цель изобретения - упрощение устройства.Эта цель достигается тем, что устройство для моделирования графов, содержащее генератор импульсов, выходкоторого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, выходы которого со-,единены с группой входов блока моделей вершин, управляющий вход блока формирования топологии подключен к входуустройства и дешифратор, выход которого соединен с группой входов блока формирования топологии, содержит 30 блок памяти и датчик случайных чисел,выход которого подключен к первомувходу блока моделей вершин, второйвход которого соединен с выходом генератора импульсов. Третий вход блока моделей вершин соединен с входомустройства и входом установки в нульсчетчика, первый выход блока модейейвершин подключен к входу дешифратора,выход которого соединен с адреснымивходами блока памяти. Второй выходблока моделей вершин подключен квходу генератора импульсов, а такжетем, что блок моделей вершин содер"жит в моделей вершин, каждая из которых содержит элемент И, первый ивторой счетчики, элемент ИЛИ, триггер, элемент ИЛИ-НЕ, блок памяти икоммутатор, выход которого подключен к входу установки триггера, выход которого соединен с первым входом элемента И. Выход последнегоподключен к счетному входу первогосчетчика, выходы которого соединеныс группой входов элемента ИЛИ-НЕ,выход которого подключен к счетномувходу второго счетчика, к первомувходу элемента ИЛИ, к первому входублока памяти, к входу сброса триггера и к входу разрешения приема ин8 79594 Таблица тья модель 5 1 Ф 2 4 3 9 7 9 9 50 60 фармации первого счетчика, информационный вход которого является первым входом блока моделей вершин, вторым входом которого является второй вход элемента И. Третьим входом блока моделей вершин являются входы установки в нуль первого и второго счетчиков. Входы коммутатора являются группой входов блока моделей вершин. Выход второго счетчика соединен с адресным входом блока памяти, выход которого является первым выходом блока моделей вершин. Вторым выходом модели вершин является выход элемента ИЛИ, второй вход которого соединен с входом элемента ИЛИ-НЕ и четвертым входом модели вершин. Вход .и-й модели вершин подключен к шине логического нуля, четвертый вход каждой другой модели вершин - со вторым выходом (тп) модели вершин, а второй выход первой модели вершин является вторым выходом блока моделей вершин. Структурная схема устройства для моделирования графов приведена на фиг. 1; на фиг. 2 дана структурная схема модели вершин; на фиг. 3 - граф, на примере моделиро-. вания которого рассматривается работа устройства.Устройство содержит блок моделей вершин 1, блок формирования топологии 2, счетчик 3, являющийся таймером модели, генератор импульсов 4, блок памяти 5, датчик 6 случайных чисел и дешифратор 7. Блок моделей вершин 1 содержит и моделей вершин 8,-8, каждая из которых содерБлок формирования топологии 2 предназначен для моделирования топологии графа. Каждому входу и выходу блока 2 ставится в соответствие определенная вершина графа. Если на-м входе блока 2 возникает сигнал Х, =1, то это значит,что в некбторой:модели вершин 8 окончено моделирование предыдущей согласно назначению вершины графа и может быть начато моделирование вершины с номером , Если на -м выходе блока 2 возникает сигнал У, =1, то блок моделей вершин 1 должен начать моделирование вершины с номером. Процесс функционирования блока 2 описывается системой логичес" жит блок памяти 9, коммутатор ) П, триггер )1, элемент И )2 элемент ИЛИ 13, элемент ИЛИ-НЕ 14, первый счетчик 15, второй счетчик 16.Входом устройства является вход 17, на который подается сигнал запуска моцели.Рассмотрим функции, выполняемые структурными элементами устройства. Блок моделей вершин 1 предназначен для моделирования времени выполнения вершин графа. Каждой модели 8перед началом моделирования назначается ряд вершин графа. Коммутаторы10 моделей 8 настраиваются на ком 1 с5 мутацию входов, номера которых соответствуют номерам вершин графа,назначенным данной модели, В блокпамяти 9 .моделей 8 записываются номера назначенных вершин. Так, для20 графа, приведенного на фиг. 3, верся первой модели 8, вершины 2,шины 5, "8 - третьей модели 8. Исследуемыйграф содержит вершины 1 в 8, вершины 9 введены дополнительно.для фиксированиямомента окончания моделирования.Коммутатор 10 первой модели 8 коммутирует входы вершин 1, 3,6, .коммУтатор 10 второй модели8 -входы вершин 2, 4,коммутатор 10 третьей модели 8 - входы вершин 5, 8, Структуразагрузки блоков памяти 9 моделей 8для этого случая приведена в таблице. ких выражений Ч;= П Х , причем сигналыХ могут не совпадать во времени.Так для графа, приведенного на фиг.З,значения У определяются выражениями (1) .У= Х л Х 4 Ч 7 - Х 7,( =Х=Х 4 лХ Чв- ХьлХ 8 (1)М-ХЛХ 4 Ч =Х ЛХ 9=Ха,В данном устройстве и в прототипе 2 назначение входов и выходови функциональные схемы блоков формирования топологии аналогичны.Датчик случайных чисел б формирует случайные времена выполнения вершин графа. Значения вероятностей1; , настраивающие датчик 6 на Формирование случайного времени выполнения вершины графа с номером записываются в-ю страницу блока памяти 5.Генератор 4 вырабатывает импульсы с Фиксированным периодом следования при нулевом сигнале на входе. Счетчик 15 имеет вход установки в нуль, счетный вычитающий вход, информационны" входы приема кода и вход разрешения приема кода.Рассмотрим работу устройства на примере моделирования графа, приведенного на фиг. 3.Перед началом моделирования в блоки 9 моделей 8 записываются номера вершин графа. В блок памяти 5 записываются значения вероятностей Р И. Выполняется настройка блока Формирования топологии 2.По сигналу, поступающему на вход 20 17 устройства, начинается моделирование одной реализации графа. Устанавливаются в нуль счетчик 3, счетчики 15 и 16 моделей 8, приводится в исходное состояние блок формирова ния топологии 2.Так как на вход третьей модели поступает нулевой сигнал и содержимое счетчика 15 модели - нулевое, на выходе элемента ИЛИ-НЕ 14 вырабатывается единичный сигнал, устанав. ливающий в счетчике 16 код 1Одновременно по сигналу с выхода элемента ИЛИ-НЕ 14 сбрасывается триггер 11 модели, из первой ячейки блока памяти 9 считывается код ф 5. На входы запрета первой и второй модели 8 поступают единичные сигналы, следовательно, на выходах элементов ИЛИ-НЕ 14 этих моделей присутствуют нулевые сигналы, и считывание кодов 4 О из блоков 9 не выполняется. Единичный сигнал с выхода первой модели 8 поступает на вход генератора 4 и запрещает его работу.Код ф 5 поступает на вход де шифратора 7, который вырабатывает сигнал на пятом выходе. В датчик б из пятой страницы блока памяти 5 считываются значения Г( . Датчик б вырабатывает случайное число 1, кото-рО рое поступает на информационные входы счетчиков 15 всех моделей 8. Однако только в третьей модели 8 код 1 запишется в счетчик 15, так как только в этой модели на вход разрешения 55 приема информации поступает разрешающий сигнал с выхода элемента ИЛИНЕ 14. Сигнал с пятого выхода дешифратора 7 поступает на пятый вход блоха Фор мирования топологии 2. Х принимает значение 1, и так как ни для одной из вершин графа не выполнены условия (1), сигналы на выходах блока 2 не вырабатываются. Как только в счетчике 15 третьеймодели 8 установится код, отличный отнуля, на выходах элементов ИЛИ-НЕ 14,ИЛИ 13 и на выходе модели вырабатываются нулевые сигналы. ТепЕрь вовторой модели 8 на всех входах элемента ИЛИ-НЕ 14 присутствуют нулевые сигналы, поэтому на его выходевырабатывается единичный сигнал, покоторому сбрасывается триггер 11 модели, устанавливается код ф 1 ф всчетчике 16, разрешается запись инФормации в счетчик 15. При этом навыходе второй модели сохраняется единичный сигнал,Из блока памяти 9 второй модели 8считывается код 2. Дешифратор 7вырабатывает сигнал на втором выходеАналогично предыдущему датчик б вырабатывает число 1, которое поступает в регистр счетчика 15 второй модели 8. Так как Х 1=1, то в соответствии с Формулой (1) (: 1 и на втором выходе блока 2 вырабатываетсясигнал, который поступает на входыкоммутаторов 10 всех моделей 8.Втораявершина графа назначена второй модели 8, поэтому срабатывает коммутатор10 только этой модели, выходной сигнал которого устанавливает триггер 11.Как только в счетчике 15 второймодели 8 устанавливается код 11,на выходах элементов ИЛИ-НЕ 14, ИЛИ 13 ина выходе модели устанавливается нулевой сигнал. АнаЛогично предыдущему изменяется состояние первой модели 8, В счетчик 15 записывается кодв счетчик 16 - код 1, устанавливается триггер 11, так как Х =1, 3 =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вырабатывает сигнал на четвертом выходе, датчик б формирует число 1 4которое записывается в счетчик 15второй модели 8. Так как У =1 и ранее Мр =1, то в соответствии с формулой (1) 1 =1 и на пятом выходе блока 2 вырабатывается единичный сигнал, который проходит через коммутатор 10 третьей модели 8, устанавливает триггер 11. В результате разрешается прохождение импульсов генератора 4 через элемент И 12 на вход счетчика 15 модели. Причем, так как Х =О,Ч=Чр 0.Содержимое счетчика 15 второй модели 8 равно 4 и отлично от нуля, поэтому на выходах элементов ИЛИ-НЕ 14, ЙЙИ 13, а также на выходах всех моделей 8 вырабатываются нулевые сигналы. Запускается генератор 4Продолжается моделирование первой вершины графа,и начинается моделирование пятой вершины графа.Процесс моделирования оканчивается при выполнении вершин ф 61, ф 71, 8 фф графа.Код в счетчике 3 в момент возбуждения 1-го выхода блока формирования топологии 2 соответствует времени начала выполнения 3 -й вершины графа. Код в счетчике 3 в момент возбуждения -го выхода дешифратора 7 соответствует времени окончания выполнение 1 -й вершины графа, В момент окончания выполнения последней вершины графа содержимое счетчика 3 соответствует полному времени моделирования граФа.Благодаря введенным блокам и связям между ними упрощена схема устройства. Формула изобретения. 1, Устройство для моделирования графов, содержащее генератор импульсов, выход которого соединен с входом счетчика, блок моделей вершин, блок формирования топологии, выходы которого соединены с группой входов блока моделей вершин, управляющий вход блока формирования топологии подключен к входу устройства и дешифратор, выход которого соединен с группой входов блока формирования топологии, о т л и ч а ю щ е е с я тем, что, с целью. упрощения устройства, оно содержит блок памяти и датчик случайных чисел, выход которого подключен к первому входу блока моделей вершин, второй вход которого соединен с выходом генератора им" 50 15 20 25 30 35 40 45 50 пульсов, третий вход блока моделейвершин соединен с входом устройстваи входом установки в нуль счетчика,первый выход блока моделей вершинподключен к входу дешифратора, выход которого соединен с адресными входами блока памяти, второй выход блока моделей вершин подключен к входугенератора импульсов2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок моделей вершин содержит в моделей вершин, каждая из которых содержит элемент И, первый и второй счетчики,элемент ИЛИ, триггер, элемент ИЛИ-НЕ,блок памяти и коммутатор, выход которого подключен к входу установкитриггера, выход которого соединен спервым входом элемента И, выход которого подключен к счетному входу первого счетчика, выходы которого соединены с группой входов элементаИЛИ-НЕ, выход которого подключен ксчетному входу второго счетчика, кпервому входу элемента ИЛИ, к первому входу блока памяти, к входу сброса триггера и к входу разрешения приема информации первого счетчика, инФормационный вход которого являетсяпервым входом блока моделей вершин,вторым входом которого является второй вход элемента И, третьим входомблока моделей вершин являются входы,установки в нуль первого и второгосчетчиков, входы коммутатора являются группой входов блока моделейвершин, выход второго счетчика соединен с адресным входом блока памяти,выход которого является первым выходом блока моделей вершин, вторым выходом модели вершин является выходэлемента ИЛИ второй вход которогосоединен с входом элемента ИЛИ-НЕ ичетвертым входом модели вершин, причем четвертый вход а-й модели вершинподключен к .шине логического нуля,четвертый вход каждой другой моделивершин соединен со вторым выходом(и)модели вершин, второй выход первой модели вершин является вторым выходом блока моделей вершин;Источники информации,принятые во внимание при экспертизе. 1. Авторское свидетельство СССР9 422002, кл. 6 06 0 7/48, 1972.2. Авторское свидетельство СССРпо заявке Р 2670963/24,кл. С 06 С 7/122, 20,04.79 (прототип).879594НИИПИ Заказ 9722/20 Тираж 748 Подписно Филиал ППП "Патентф, г,Ужгород, ул.Проектная, 4