Устройство для моделирования сетевых графов Советский патент 1980 года по МПК G06F15/173 G06G7/122 

I

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

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

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

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

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

Структурная схема устройства nt n5ijдена ни чертеже.

Устройство содерх ит матрицу 1 (fiopмирователей дуг, блок 2 yiip.iruiMiii,, гг-лератор 3 импульсов, триггеры 4 формирочателей дуг, элементы ИЛИ 5, эле менты И 6, регистрирующие счетчики 7,, счетчик 8 числа импульсов, блоки 9 сравнения. Устройство работает следующим образом. Пе|эвоначально в матрицу 1 заносится информация о топологии моделируемого графа сети. При этом триггеры 4 формирователей дуг, моделируюших ветви графа, -устанавливаются в единичное состояние. Соответствующий триггер формирователей дуг определяется пересечением строки с номером, равным номеру началь ного узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. После занесения исходной информации на выходах элементов 5, объединяющих выходы триггеров 4 формирова телей дуг в столбцах, соответств тоших начальным узлам моделируемого графа, имеются низкие потенциалы, так как в однонаправленнЪм графе без и петель начальные узлы не содержат входящих ветвей и триггеры формирователей дуг, находящихся в этом столбце, будут в нулевом состоянии. Регистрирующие счетчики 7 и счетчик 8 числа импуль сов в исходном состоянии сброщены в нулевое состояние.

С появлением пускового сигнала блок управления 2 разрешает прохождение им- пульсрв с выхода генератора 3 на управляющие входы всех элементов 6 и счетчик числа импульсов. При этом импульсы не проходят через элементы 6 на счетчики 7 тех столбцов, все триггеры 4- которых находятся в нулевом состоянии. Далее содержимое счетчиков 7 поступает на один вход блока 9 сравнения соответствующего столбца, а на другие входы этих блоков сравнения поступает информация со счетчика 8. При несовпадении показаний счетчиков 7 и 8 блок 9 вырабатывает импульс, который сбрасывает в нулевое состояние триггеры 4 формирователей дуг строки с номером, равным номеру столбца, в блоке сравнения которого не произошло сравнения. После этого блок управления разрещает прохождение очередного импульса с выхода генератора 3 на управляющие входы всех элементов 6 и счетчик В числа импульсов.

Вычислительный процесс продолжаетс до тех пор, пока - происходит сравнение в

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

Устройство для моделирования сетевых графов, содержащее генератор импульсов, выход которого подключен к вхо ду блока управления, матрицу формирователей дуг, причем выходы формирователей дуг каждого столбца соединены с входами соответствующего элемента ИЛИ, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет распределения узлов графов по рангам, в него введены по числу столбцов элементы И, регистрирующие счетчики, блоки сравнения и счетчик числа импульсов, вход которого соединен с первыми входами элементов И и подключен к выходу блока управления, при этом выход счетчика числа импульсов соединен с первыми входами блоков сравнения, выход каждого элемента ИЛИ подключен к второму входу соответствующего элемента И, выход которого соединен с входом соответствующего регистрирующего счетчика, блоках 9. Это свидетельствует о том, что все узлы исследуемог-о графа распределены по рангам. Блок управления 2 при этом прекращает подачу импульсов на входы элементов 6 и 8. Максимальное число последовательных шагов при вычислительном процессе не превьшгает числа вёрщин в графе. . Число импульсов, зафиксированное на , регистрирующих счетчиках 7, соответствует номеру ранга каждой вершины графа. Задача распределения узлов графов по рангам возникает при решении задач планирования организации выполнения некоторого множества работ, представляемых сетевыми графиками. В этом случае необходимо определить множество узлов (множество работ), готовых в данный момент времени Для выполнения. Другим примером является задача организации вычислительного процесса в мультипроцессорных вычислительных системах, где в оперативном режиме необходимо установить задачи, которые могут выполняться независимо друг от друга. Благодаря введению в устройство новых блоков и связей расширяются его функциональные возможности за счет способности оперативного .распределения узлов графов по рангам.

5 7160436

выход которого подключен к второму1. Авторское свидегсльстпо CCCl

входу соответствующего блока сравнения,№ 49И32, кл. G 06 Г 15/20, 1П74. выход которого соединен с входами фор-.

мирователей дуг соответствующей строки.2. Авторское свидетельстпо СССР

Источники информации,j 525954, кл. G 06 f 15/20, 1974

принятые эо внимание при экспертизе(прототип).