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

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

Иллюстрации

Показать все

Реферат

 

-.стек тно-- .-.zi .4с,с:н-,. иблио..;..,1 д

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ (ii) 556460

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву № 422002 (22) Заявлено 30,01.76 (21) 2318861/24 с присоединением заявки № (23) Гриоритет

Опубликовано 30.04.77. Бюллетень № 16

Дата опубликования описания 31.05.77 (51) М. Кл.2 G 06G 7/48

G 06G 7/122

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

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.333(088.8) (72) Авторы изобретения

В. В. Васильев, О. Н. Голованова и Е. А. Ралдугин

Институт электродинамики АН Украинско" ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ

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

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

Каждая модель ветви содержит задатчики адресов начального и конечного узлов, формирователь временных интервалов, триггеры, элементы И, инвертор, элемент ИЛИ. Блок формирования топологии содержит элементы

И, инвертор и элементы ИЛИ. Все модели ветвей соединены с блоком формирования топологии и с генератором импульсов, который выдает импульсы двух серий (A и Б).

Устройство определяет величину критического пути сетевого графика, а также величину длиннейшего пути на сети (на взвешенном графе).

Однако оно не позволяет определять длиннейший путь на сети с обходом заданных запрещенных узлов.

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

Это достигается тем, что в предлагаемое устройство для моделирования сетевых графиков в каждую модель ветви введен дополнительный элемент И, в блок формирования то5 пологии введены триггер, сдвиговый регистр и счетчик, вход которого соединен с входом сдвигового регистра и с выходом первого элемента ИЛИ блока формирования топологии, а выход счетчика соединен с единичным вхо10 дом триггера блока формирования топологии, единичный выход которого подключен к одному из входов третьего элемента И блока формирования топологии, а нулевой выход триггера соединен с одним из входов второго эле15 мента ИЛИ блока формирования топологии, а выход сдвигового регистра подключен к первому входу дополнительного элемента И каждой модели ветви, второй вход которого соединен с выходом задатчика адреса начального

20 узла, а выход подключен к единичному входу второго триггера модели ветви.

Запрещение узлов осуществляется посредством исключения ветвей, исходящих из запрещенных узлов. Это исключение ветвей производится установкой вторых триггеров соответствующих моделей ветвей в единичное состояние и выполняется в течение подготовительного периода, измеряемого /у импульсами серии Б, где N — емкость задатчиков адресов и счетчика блока формирования то556460

35

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

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

Схема содержит блок 1 моделей ветвей, блок 2 формирования топологии, блок 3 управления, генератор импульсов 4.

Каждая модель ветви включает задатчики адресов 5, 6 начального и конечного узлов соответственно, формирователь 7 временных интервалов, триггеры 8, 9, элементы И 10, 11, 12, инвертор 13, элемент ИЛИ 14. Блок 2 формирования топологии содержит элементы И

15, 16, 17, элементы ИЛИ 18, 19, 20, инвертор

21, сдвиговый регистр 22, триггер 23 и счетчик 24.

Пусть устройство работает в режиме многократного отыскания длиннейших путей, т. е, последовательно отыскиваются длиннейшие пути между начальным узлом сети и некоторым подмножеством остальных узлов сети. К моменту окончания определения одного из искомых длиннейших путей в регистр 22 уже занесена информация о запрещенных узлах для следующего длиннейшего пути. По сигналу пуска блок управления устанавливает все триггеры моделей ветвей и триггер блока формирования топологии в нуль. Нулевой выходной сигнал элемента И 15 совместно с нулевым сигналом из блока управления через элемент ИЛИ 20 и первые элементы И всех моделей ветвей запрещает включение формирователей временных интервалов. Запреты снимаются с моделей ветвей, не исходящих из запрещенных узлов, после просчета N импульсов серии Б, где N — емкость счетчика блока формирования топологии. (Считаем, что отсчет импульсов в каждом периоде работы начинается с нуля).

Пусть после К импульсов серии Б сигнал перевыполнения появился на выходе задатчика адреса начального узла i-й модели ветви, изображенной на чертеже. Если К-й узел не отмечен в регистре 22 блока формирования топологии единицей, то на выходе третьего элемента И с-й модели ветви не появляется единичного сигнала, и триггер 9 этой модели ветви остается в нулевом состоянии, Если же

К-й узел является запрещенным, т. е, отмечен в регистре единицей, то на выходе элемента И 12 i-й модели ветви (и остальных моделей ветвей, исходящих из К-го узла), единичный сигнал появляется и соответствующий триггер 9 устанавливается в единичное состояние. Формирователь временных интервалов упомянутой ветви не включается, а с единичного выхода триггера 9 подается разрешающий сигнал на элемент И 11.

После и импульсов серии Б все и узлов моделируемой сети просматриваются аналогично, а в регистре 22 блока формирования топологии записываются нули. Импульсы серии Б продолжают поступать на задатчики адресов начальных и конечных узлов, так как триггер блока формирования топологии по-прежнему остается в нулевом состоянии. Единичный выходной сигнал элемента ИЛИ 18 блока формирования топологии через инвертор 21 запрещает подачу импульсов серии А на формирователи временных интервалов.

После просчета N импульсов серии Б на выходе счетчика блока формирования топологии появляется единичный сигнал, по которому триггер 23 блока формирования топологии переключается в единичное состояние.

После просчета N импульсов серии Б восстанавливается содержимое задатчиков адресов начальных и конечных узлов. Далее работа устройства протекает аналогично работе устройства по основному авт. св. № 422022.

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

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

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

Редактор Т. Рыбалова

Составитель И. Чичерюкина

Техред Е. Хмелева

Корректор О. Тюрина

Заказ 1118/17 Изд. № 414 Тираж 815 Подписное

ЦНИИПИ Государственного комитета Совета Мшшстров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская паб., д. 4/5

Типография, пр. Сапунова, 2