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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(5)М. Кл,О 06 Р 15/20 Всудврствекнвй квинтет Р ав делан кзебретеннй и открытей(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВИзобретение относится к вычислительной технике. Устройство может быть использовано при исследовании сетевыхграфов.Известно устройство для исследованияграфов 11, содержащее блок управления,5импульсный вход которого соединен свходом генератора импульсов, триггерыформирователей дуг по числу строк истолбцов модели, причем входы каждого0триггера соединены с выходом блока управления,Наиболее близким техническим решением к изобретению является устройство для определения кратчайшего пути в35графе 23, содержащее генератор импульсов, выход которого подключен к входублока управления, матрицу формирователей дуг, причем выходы формирователейдуг каждого столбца соединены с входами соответствующего элемента ИЛИ.Недостатком известных устройств является невозможность распределения узлов 1 рафо 11 ло рангам,2Цель изобретения - расширение функциональных возможностей устройства засчет распределения узлов графов ло рангам. Это достигается тем, что в устройство введены по числу столбцов элементы И, регистрирующие счетчики, блоки сравнения и счетчик чисда импульсов, вход которого соединен с первыми входами элементов И и подключен к выходу блока управления, причем выход счетчика импульсов соединен с первыми входами блоков сравнения, выход каждого элемента ИЛИ подключен к второму входу соответствующего элемента И, выход которого соединен с входом соответствующего регистрирующего счетчика, выход последнего подключен к второму входу соответствукнцего блока сравнения, выход которого соединен с входами форм 11- рователей дуг соответствующей строки,Структурная схема устройства прию.- дена ла чертеже.Устройство содержит матрицу 1 фо - мирователей дуг, блок 2 уирагие 11 и 11,43блоках 9. Это свидетельствует о том,что все узды исследуемого графа распределены по рангам. Гзлок управления 2при этом прекращает подачу импульсовна входы элементов 6 и 8, Максимальное число последовательных шагов привычислительном процессе не превышаетчисла вершин в графе.Число импульсов, зафиксированное на,регистрирующих счетчиках 7, соответствует номеру ранга каждой вершиныграфа,Задача распределения узлов графов порангам возникает при решении задач планирования организации выполнения некоторого множества работ, представляемыхсетевыми графиками. В этом случае необхоцимо определить множество узлов(множество работ), готовых в данныймомент времени цля выполнения. Другимпримером является задача организациивычислительного процесса в мультипроцессорных вычислительных системах, гдев оперативном режиме необходимо установить задачи, которые могут выполняться независимо друг от друга.Бпагодаря введению в устройство новых блоков и связей расширяются егофункциональные возможности за счет способности оперативного распределенияузлов графов по рангам. 3 7160нератор 3 импульсов, триггеры 4 формирователей цуг, элементы ИЛИ 5, элементы И 6, регистрирующие счетчики 7,счетчик 8 числа импульсов, блоки 9сравнения.5Устройство работает следующим образом,Первоначально в матрицу 1 заноситсяинформация о топологии моделируемогографа сети, При этом триггеры 4 формирователей дуг, моделирующих ветвиграфа, устанавливаются в единичное состояние. Соответствующий триггер формирователей дуг определяется йересечениемстроки с номером, равным номеру начального узда моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. После занесения исходной информации на выходах элементов 5, объециняющих выходы триггеров 4 формирователей дуг в столбцах, соответствукнцихначадьным уздам моделируемого графа,имеются низкие потенциалы, так как воднонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей и триггеры формирователейдуг, находящихся в этом стодбце, будутв нулевом состоянии, Регистрирующиесчетчики 7 и счетчик 8 числа импульсов в исходном состоянии сброшены внулевое состояние.С появлением пускового сигнала блок управления 2 разрешает прохождение импульсов с выхоца генератора 3 на управ- З 5 ляющие входы всех элементов 6 и счетчик числа импульсов. При этом импульсы не проходят через элементы 6 на счетчики 7 тех столбцов, все триггеры 4 которых находятся в нулевом состоянии, Далее содержимое счетчиков 7 поступает на один вход блока 9 сравнения соответствующего столбца, а на другие входы этих блоков сравнения поступает информация со счетчика 8, При несовпадении показаний счетчиков 7 и 8 блок 9вырабатывает импульс, который сбрасывает в нулевое состояние триггеры 4 формирователей дуг строки с номером, равным номеру столбца, в блоке сравнения которого не произошло сравнения.После этого блок управления разрешает прохождение очередного импульса с выхода генератора 3 на управляющие входы всех элементов 6 и счетчик 8 числа55 импульсов.Вы шслительный процесс продолжается до тех пор, пока происходит сравнение в Формула изобретения1Устройство для моделирования сетевых графов, содержащее генератор импульсов, выходкоторого подключен к вхо-, ду блока управления, матрицу формирователей дуг, причем выходы формирователей дуг каждого столбца соединены с входами соответствующего элемента ИЛИ, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет распределения узлов графов по рангам, в него введены по числу столбцов элементы И, регистрирующие счетчики, блоки сравнения и счетчик числа импульсов, вход которого соединен с первыми входами элементов И и подключен к выходу блока управления, при этом выход счетчика числа импульсов соединен с первыми входами блоков сравнения, выход каждого элемента ИЛИ подключен к второму входу соответствующего элемента И, выход которого соединен с входом соответствующего регистрирующего счетчика,6043 б 1, Авторское свидетельство СССР Мо 491132, кл, Ь 06 Г 15/20, 1974. тавитель Л; Яицковехред О, Дегеза Коррек едактор Т. 1 Срчикова Шекма 43 Тираж 751 ЦНИИПИ Государственного по делам изобретений и о , Москва, Ж, Раушска Заказ 9528/ 1130 шиал Г 1 ПП "Патент", г. Ужгород, ул. Проектная выход которого подключен к второмувходу соответствующего блока сравнения,выход которого соединен с входами фор-.мирователей дуг соответствующей строки,Источники информации,принятые во внимание при экспертизе 2, Авторское свидетельство СССРМ 525954, кл. 6 06 115/20, 1974