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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических республик (6l ) Дополнительное к авт. свнд-ву (22) Занвлено 20.10.77(2l) 2531ЭЭЗД,8-24 с прнсоеднненнем заявки J% (23) Приоритет

Опубликовано 5.02.8р Бюллетень М 6

Дата опубликования описания >8,02 8р (5! )М. Кл.

0 06 г 15/20

Всуюрстеекннй кекнтет

СССР ав лелен кзебретеннй к открытей (53) УДК 68m.З (088,8) i (72) Авторы изобретения

С. В. Назаров и В. А. Титов (7I) Заявитель

1 (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

: СЕТЕВЫХ ГРАФОВ

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

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

О триггера соединены с выходом блока управления, Наиболее близким техническим решением к изобретению является устройство для определения кратчайшего пути в

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

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

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

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

Устройство содержит матрицу 1 фо!— мирователей дуг, блок 2 упр rusi.пня, 43 j блоках 9. Это свидетельствует о том, что все узлы исследуемого графа распределены по рангам. Блок управления 2 при этом прекращает подачу импульсов на входы элементов 6 и 8. Максимальное число последовательных шагов при вычислительном процессе не превышает числа вершин в графе.

Число импульсов, зафиксированное на, регистрирующих счетчиках 7, соответствует номеру ранга каждой вершины графа.

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

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

3 7160 нератор 3 импульсов, триггеры 4 формирователей дуг, элементы ИЛИ 5, элементы И 6, регистрирующие счетчики 7, счетчик 8 числа импульсов, блоки 9 сравнения.

Устройство работает следующим образом.

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа сети. При этом триггеры 4 фор- 10 мирователей дуг, моделирующих ветви графа, .устанавливаются в единичное состояние. Соответ твующий триггер формирователей дуг определяется йересечением строки с номером, равным номеру началь- 15 ного узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. После занесения исходной информации на выходах элементов 5, объединяющих выходы триггеров 4 формирова- 20 телей дуг в столбцах, соответствукнцих начальным узлам моделируемого графа, имеются низкие потенциалы, так как в однонаправленном графе без циклов и петель начальные узлы не содержат вход.ящих ветвей и триггеры формирователей дуг, находящихся в этом столбце, будут в нулевом состоянии. Регистрирующие счетчики 7 и счетчик 8 числа импульсов в исходном состоянии сброшены в нулевое состояние.

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

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

После этого блок управления разрешает прохождение очередного импульса с выхода генератора 3 на управляющие входы всех элементов 6 и счетчик 8 числа

55 импульсов.

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

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

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

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

Источники информации, принятые во внимание при экспертизе

6043 б

1, Авторское свидетельство ССС1

М. 491132, кл. G 06 Г 15/20, 1974.

2. Авторское свидетельство СССР

¹ 525954, кл. 6 06 Р 15/20, 1 374 (прототип) .

Составитель Л; Яицков

Редактор Т. 0рчикова Техред g. Дегеза Корректор С. Шекмар

Заказ 9528/43 Тираж 75 1 Подписное

UHHHHH Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4