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

(50 4 С 06 Г 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(71) Минский радиотехнический институт(56) Авторское свидетельство СССРВ 756421, кл. С 06 С 7/122, 1978.Авторское свидетельство СССРУ 034048, кл С 06 6 7/122, 1982,(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано при стохастическом моделировании сложных систем, представляемых вероятностными графами. Цель изобретения состоит В расширении фунК- циональных возможностей эа счет выборки, упорядочения и накопления информации о заданных вершинах графа. Устройство содержит блок моделей вершин, удел формирования топологии, первый счетчик, генератор импульсов, первый блок памяти, датчик случайных чисел, второй блок памяти, регистр, третий блок памяти, второй счетчик. Блок моделей вершин состоит из и моделей вершин (и " число вершин графа) . Блок формирования топологии содержит пер-. вый, второй.и третий блоки памяти, элемент ИЛИ, коммутатор. Выборка, упорядочение и накопление информациий о заданных вершинах графа осуществля-. ются непосредственно в процессе моделирования вероятностного графа при ограниченном числе контролируемых вершин графа. 4 ил., 4 табл.23ячеек, расположенных последовательнов порядке возрастания адресов. Числоячеек в "й области блока 13 соответствует числу дуг, выходящих из х-йвершины, -я ячейка блока 12 содержитадрес А, начала -й области ячеек вблоке 13, признак М устанавливающий условия контроля состояния выходад-й вершины, и адрес С ячейки блока9, являющейся конечной в цепочке, со Оответствующей признаку к, . Если М; == О, то цепочка не строится и С; = 0Блок 12 при наличии на его адресномвходе номеравершины и единичногосигнала на его входе считывания работает в режиме чтения и выдает на выходы соответственно ы, , Си А;.При К; = 1 блок 12 переходит в режим записи информации в поле С х-йячейки, содержимое полей А которой не изменяется,В х-й области блока памяти 13 магазинного типа каждой дуге (, 3),исходящей из вершины , отводитсяотдельная ячейка, в которую записывается номервершины, в которую входит дуга (, 3), номер 1 входа в д-ювершину дуги Я, 3), признак 1;устанавливающий условия контроля состояния Е-го входа 1-й вершины, ипризнак г , значение которого равноединице для послецней ячейки -й об-.,ласти блока 13 и нулю для всех остальных ячеек -й области,35Блок 14 предназначен для хранения адресов Сконечных ячеек цепочек в блоке 9, соответствующих признакам 1 к =При= О цепочка ле строится и соответствующий адрес Ск = О. 40 При поступлении единичного сигйала, на вход считывания блока 14 (= 1)1 к и адреса (1, Е) на адресный вход из блока 14 считывается значение Ск, По заднему фронту сигнала на входе 45 считывания блока 4 он переключается в режим записи, а в ячейку с адресом (1, 1 с) записывается новое значение С 1.50Коммутатор 16 при наличии единичного сигнала на первом управляющем входе передает на выход сигналы с втовторога информационного входа. При единичном сигнале на втором управляющем входе коммутатор 16 передает на выход сигналы с первого информационного входа. 509 4Генератор 4 вырабатывает импульсы с фиксированным периодом следования только при нулево сигнале на входе.Датчик 6 формирует случайные времена выполнения вершин графа, Значения вероятностей 1 Р,(с), настраивающие датчик 6 на формирование случайного времени Г;, подчинающегося фунфункции распределения Г, И) выполнения вершины графа с номером , записываются в -ю страницу блока 5.Блок 7 содержит п ячеек по числу моделей 11. Каждой модели 1 в блоке 7 соответствует определенная ячейка, в которую в процессе моделирования записываются номера вершин, которым назначается данная модель 11, Блок 7 работает в режиме записи информа- ции, поступающей на его информационный вход, если на вход записи поступает единичный сигнал, при нулевом сигнале он работает в режиме считывания информации, Адрес, по которому производится обращение к блоку 7, поступает на его адресные входы в унитарном коде.Счетчик 1 О является счетчиком адреса блока 9 и увеличивает содержимое на единицу по заднему фронту входного единичного сигнала.Рассмотрим функционирование устройства на примере моделирования графа, приведенного на фиг, 3.Перед началом работы блок 13 загружается информацией о связях вершин, Для дуг, вхождение которых в вершины графа необходимо контролировать, в разряды признаказаписываются единицы. Признак г " ра-. вен единице в последней ячейке 1-й области блока 13. Структуры загрузки блоков 12 и 13 для моделируемого графа представлены в табл. 1 и 2 В блоке 12 для каждой -й вершины отводится д-я ячейка, куда помещается адрес А; начальной ячейки в блоке 13, содержащей информацию о связях -й вершины, признак М; для контролируемых вершин, равный единице, и адрес С На. графе контролируемые входы и выходы вершин обозначены точками. Адреса С; в блоках 12, 14 перед началом моделирования нулевые, В блок 5 заносятся значения вероятностей 1 Р (С) для всех вершин, Обнуляются блок 9 и счетчик 3, В счетчик 10 записывается единица. В п-ю ячейку блока 7 записывается единица, а в ос 1231509тальные ячейки - нули, Модель 11 в блока 1 устанавливается в состояние "Заблокирована", остальные модели 11в состояние "Свободна",На информационном выходе модели11 вырабатывается сигнал, поступающий на соответствующий адресныйвход блока 7, Поскольку в блоке 1имеется и-я модель, готовая к освобождению, то на выходе выполнениявершины блока 1 также присутствуетединичный сигнал, по которому запрещается работа генератора 4 и начина-ется работа узла 2, Одновременно из15а-й ячейки блока 7 считывается врегистр 8 номер начальной вершины.Пусть номер начальной вершины 1 иона связана дугами с вершинами 2 и3, а информация о связях, содержащая 20номера вершин 2 и 3, номера их входов1 и 1 признаки 1; = 1, , = Опризнаки г, = О, г1, помещенав блоке 13, начиная с адреса А, = 1.Тогда номер вершины 1 из регистра 8 25поступает на адресный вход блока 12,из первой ячейки которого считываются на выходы признак= 1 адресС = О, адрес А= 1, Так как Ко1, то С, = 0 по разрешающему сигна" ЗОлу на втором управляющем входе коммутатора 16 поступает на выход коммутатора 16, а также выдается признаквершины. В блок 9 в ячейку с адресом,.равным 1, который поступает на адресный вход блока 9 со счетчика 1 О,озаписывается адрес С, -= О, поступающий на информационный вход цепочкиблока 9. Одновременно в ту же ячейкублока 9 записывается по информационНому входу текущего времени значениегО. По заднему Фронту сигнала навыходе признака контроля блока 12 вячейку по адресу на его адресном входе, равному 1, в поле С записывается 45значение кода счетчика 10, равное 1(С,1), поступающее на вход записиадреса цепочки блока 12, По заднемуфронту сигнала на выходе элементаИЛИ 15 узла 2 в счетчик. О прибавля Оется единица. При поступлении навход блока 13 адреса первой областиА, = 1 иэ ячейки с адресомвыдаются признак г, = О,= 1, иомервершины 3-2 и номер ее входа 1-1, а 55также сигнал назначения вершины. Номер вершины 1-2 передается на входыблоков 5 и 7, а сигнал назначения вершины - на соответствующие входыблоков 1, 7. Блок 7 переключается врежим записи.В блоке 1 выбирается свободная модель 11 на информационном выходекоторой вырабатывается сигнал, покоторому в (и)-ю ячейку блока 5записывается номер вершины "2, Темсамым второй вершине назначается модель 11,Одновременно из второй страницыблока 5 в датчик 6 считываются значения вероятностей Р(Г), по которымдатчик 6 формирует случайное времявыполнения второй вершины, которое поприсутствующему в настоящий моментсигналу н,а входе назначения вершиныблока 1 записывается в модель 11 ,В то же время по единичному сигналу на выходе номера. вершины блока 13(1,= 1) на выход блока 14 выдаетсяадрес С О для второй вершины и еепервого входа из ячейки с адресом,поступившим на адресный вход блокао14. Адрес С, выдается через коммутатор 16 при единичном сигнале на егопервом управляющем входе. По сигналус выхода элемента ИЛИ 14 в блок 9 вячейку с адресом, равным 2, которыйпоступает на вход блока 9 со счетчика 10,.записывается адрес С, = О,опоступаюший на информационный входцепочки, и значение кода йО, поступающее на информационный вход текущего времени. По заднему фронту сигнала на входе считывания блока 14 вячейку с адресом на его адресном входе, равным (2,1), записывается значение кода счетчика 10, равное 2 (С,2). По заднему Фронту сигнала навыходе элемента ИЛИ 15 в счетчик 10прибавляется единица. Этим заканчивается отработка дуги (1,2), Так какпри этом на выходе блока 13 имеется .признак г, = О, то в блоке 13 считывается ячейка, равная 2. На выходыблока 13 .выдаются признак г = 1признак м:= О, номер третьей вершиныи номер ее первого выхода, а такжесигнал назначения вершины, Блок 7 переключается в режим записи.В блоке 1 выбирается (и)-я свободная модель 11, на (и)-м информационном выходе блока 1 вырабатываетсясигнал, по которому в (и)-ю ячейкублока 5 записывается номер вершины3, тем самым третьей вершине назначается (и)-я модель,11, 1231509Одновременно из третьей страницыблока 5 в датчик 6 считываются значения вероятностей Р (й), по которым датчик 6 формирует случайное вре 5мя выполнения третьей вершины ГзЗначение 7 по присутствующему в назстоящий момент сигналу на входе назначения вершины блока 1 записывается в (п)-ю модель 11. Этим закан- Очивается отработка дуги (1,3), Таккак считанное значение г= 1, тона выходе последней дуги блока 13возникает сигнал, поступающий в блок1, по которому и-я модель из состояния "Заблокирована" переходит в состояние Свободна , Так как в блоке1 нет больше ни одной модели в состоянии "Заблокирована", то на выходевыполнения вершины сбрасывается еди- . 20ничный сигнал; но которому разрешаетс,я работа генератора 4, импульсы которого начинают поступать на входымоделей 11 блока. 1, а в узле 2 запрещается работа блока 12, Так как 25в блоке 1 только (и)-я и (и) -ямодели находятся в состоянии Занята", то только они воспринимают импульсы генератора 4, по каждому изкоторых записанные в моделях временные интервалы с иуменьшаютсяна единицу,Пусть= 5, Гз = 3, тогда черезтри такта генератора 4 (и) -я модель 11 перейдет в состояние "Заблокирована". На (п)-м выходе блока 1вырабатывается сигнал, по которомуиз (и)-й ячейки блока 7 считывается в регистр 8 номер вершины 3, поступающий в узел 2. Анапогично предыдущему узел 2 последовательно вырабатывает на выходе номера вершин 1 и6, для каждой из которых блок 1 вы- .деляет свободнуюмодель 11, соответственно и-ю и (п) - ю, а датчик 6 .-45формирует случайные временные интерВалы 61 иТак как при моделировании дуги(3,1) считывается из блока 13 признак1, то аналогично предыдущему в %блок 9 по адресу 3, равному состояниюосчетчика 1 О, записывается С = О,считанный из блока 14, и значенией3,. Затем в блок 14 для первойвершины и первого ее входа записывается новый адрес Сп = 3, а в счетчик10 прибавляется единица и его состояРние становится равным 4. По сигналу на выходе последней ду -ги блока 3 в блоке 1 (и)-я модельве и11 переходит в состояние СвободнаНа выходе выполнения вершины блока 1сбрасывается единичный сигнал, разрешается работа генератора 4, импульсы которого поступают в блок 1, ипроисходит модификация временных интервалов в п-й, (и)-й и (и)-ймоделях 11, Пусть 21 = 3, Г = 3, ав (п)-й модели текущее с = 2. Вэтом случае через 2 такта генератора4 (и)-я модель 11 переходит в состояние Заблокирована", На (и)-мвыходе блока 1 вырабатывается сигнал,по которому из (п)-й ячейки блока7 считывается в регистр 8 номер вершины 2, поступающий в блок 2, и процессмоделирования графа продолжается аналогично изложенному,По окончании моделирования графа вблоке 9 записана информация о процессе моделирования вершин, у которыхпризнаки к; или Р; равны единице.В полях С; блока 12 (для вершин, укоторых контролируются выходы, , = 1)и С; блока 14 (для вершин, у которыхконтролируются входы, Р = 1) в этотмомент записаны адреса блока 9, начиная с которых можно для кажцой контролируемой вершины развернуть временную диаграмму моментов их выполненияв сторону уменьшения модельного времени. Момент окончания процесса моделирования хранится в счетчике 3,Алгоритм построения временных диаграмм выполнения вершин рассмотримна следующем примере.Допустим, что содержимое блока 9на момент окончания моделированияграфа представлено в табл, 3, адресаС и С для контролируемых точек ссРг 1и Ф г, хранимые в блоках12 и 14, соответствуют табл. 4, а содержимое таймера 3 равно= 16,Рассмотрим процесс построения временной диаграммы изменения состояниявершины 1 (с,).Прочитав из ячейки 1 блока 12 адрес С, = 13, читаем из ячейки 13 блока 8 время последнего срабатыванияпервои вершины с = 14 и предыдущиимадрес С, = 9. По этому адресу в блоке 9 хранится время срабатывания первой вершины= О и С, = 5 и так далее, пока по адресу С, = 1 из блока 9 не будет прочитан адрес С, = 0231509 1 О олжение табл. 2 Адрес памят 0 ес 1 О 0 1 Таблица 3 0 000 1 000 0 О Адре памя одержимое пам Адреса С; Тайм или С 4 к 1 м 0 0 О 0 о а 1Т а ц и 8 нак Признак1 г; 0 0 4Табл онтрольная нли С 1 13 0 и время срабатывания первой вершины ФаО, На этом процесс построения временной диаграммы для первой веригин заканчивается.В табл. 1 и 2 приведена структурная загрузка блоков 12 и 13 соответственно; в табл. 3 - структурная загрузка блока 9; в табл. 4 - структурная загрузка блока 14.Т а б л и ц а 1 10 9 11 1 О 12 11 13 2 14 10 15 12логии. Формула изобретения Устройство для моделирования графов, содержащее блок моделей вершин, 5 генератор импульсов, первый с летчик, датчик случайных чисел, первый и второй блоки памяти и узел формирования топологии, состоящий из первого и второго блоков памяти и коммутатора, первый управляющий вход которого соединен с выходом признака контроля второго блока памяти узла формирования топологии, в блоке моделей вершин первый й второй управляющие входы п"й модели вершины объединены и подключены к шине нулевого потенциала, выходы выполнения вершины и высвобождения модели вершины каждой 1-й (1 = 2, Зп), модели вершины 20 соединены соответственно с первым и вторым управляющими входами (1-1)-й модели вершины, а выход выполнения вершины первой модели вершины подключен к входу запуска генератора импульсов и входу считывания первого блока памяти узла формирования топологии, выход генератора импульсов соединен со счетными входами моделей вершин блока моделей вершин, инфор- З 0 мационные выходы которых подключены к соответствующим адресным входам второго блока памяти, выход которого соединен с йнформационным входом регистра, выход которого подключен к 35 адресному входу : рвого блока памяти узла формирования топологии, выход номера вершины второго блока памяти узла формирования топологии соединен с информационным входом второго бло ка памяти и адресным входом первого блока памяти, выход которого подключен к входу запуска датчика случайных чисел, выход которого соединен с входами зацания времени моделей 45 вершин блока моделей вершин, выход назначения вершины второго блока памяти узла формирования топологии подключен к входу записи второго блока памяти и входам назначения вершинывсех моделей вери, н блока моделейвершин, выход последней дуги второгоблока памяти узла формирования топологии соединен с установочными входами моделей вершин блока моделей вершин, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей за счет выборки,упорядочения и накопления информациио заданных вершинах графа, в устройство введены второй счетчик, третийблок памяти, а в узел формированиятопологии - третий блок памяти иэлемент ИЛИ, причем в узле формирования топологии первый вход элементаИЛИ соединен с вторым управляющимвходом коммутатора и выходом признакаконтроля первого блока памяти, выходпризнака контроля второго блокаамяти подключен к входу считывания третьего блока памяти, второму входуэлемента ИЛИ и первому управляющемувходу коммутатора, выход текущего адреса цепочки вершин первого блока памяти соединен с первым информационнымвходом коммутатора, к второму информационному входу которого подключенвыход третьего блока памяти, адресныйвход которого соединен с выходом номера вершины второго блока памяти,адресный вход которого подключен ксоответствующему выходу первого блока памяти, выход элемента ИЛИ узлаформирования топологии соединен свходом записи третьего блока памятии входом второго счетчика, выход ко-.торого подключен к адресному входутретьего блока памяти и к входам записи адреса цепочки вершин первого итретьего блоков памяти узла формирования топологии, выход первого счетгчика соединен с информационным входомтекущего времени третьего блока памяти, к информационному входу цепочкивершин которого подключен выход коммутатора узла формирования топо 1235091231509 Коиецодея ира 3 ания Составитель А. ЩеренковТехред И. Гайдош Коррек Пилипенк Редактор М. Келе Заказ 2652 52 3035 роизводстве еское предприятие, г, Ужгород,лиг роек Тираж 671 Подписное ИИПИ Государственного комитета СССР делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5