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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

СОюз СОВ4тсхий

Соцнаанстнч вских

9oc3l+IINK оп 798854 (61) Дополнительное к авт. свид-sy— (22) Заявлено 01. 09. 78 (21) 2683352/18-24 с присоединением заявки Нов

{23) Приоритет—

Опубликовано 23.01.81. Бюллетень N9 3 (51)М. Кл З

G 06 F 15/20

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

СССР по делам изобретений и открытий (53) УДК 681. 333 (088. 8) Дата опубликования описания 230131 (72) Авторы изобретения

В.А.Титов, В.Л.Гайдуков, Е.А.Дроздов и С.В.Назаров (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ

ГРАФОВ

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

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

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

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

Недостатком .этого устройства является малая точность моделирования.

Цель изобретения — повышение точности

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

798854

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

Устройство содержит матричную модель 1 сети, распределитель 2 импульсов, генератор 3 тактовых импульсов, по числу строк и столбцов матрицы 20 формирователи 4 весов дуг,, включающие счетчики 5 и триггеры-б, по числу столбцов матрицы первую группу элементов И 7, элементы НЕ 8, третью группу элементов И 9, вторую группу элементов И 10 и четвертую группу элементов И 11, группы счетчиков 12 и 13, схемы 14 сравнения и триггеры

15.

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

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

В исходном состоянии все триггеры 15, счетчики 12 и 13 находятся в нулевом состоянии. Распределитель Z подает разрешающий сигнал на управляющий вход элемента И 10. Первона- 40 чально в модель 1 заносится информация о топологии моделируемого графа сети. При этом триггеры б формирователей 4, моделирующих ветви rpaAa, устанавливаются в единичное состоя- 4 ние. Соответствующий формирователь

4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков. После занесения исходной информации на входах элементов И 7, объединяющих выходы формирователей

4 в столбцах, соответствующих начальным узлам моделируемого граФа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе ,.без циклов и петлей начальные узлы не содержат входящих ветвей, а, следовательно, и триггеры 6 формирователей 4, находящихся в этом столбце, будут в нулевом состоянии (элементы

И 7 соединены. нулевыми входами триггеров б . Определение вершин rpaAa, образующих критический путь, осуществляется в три этапа.

На первом этапе осуществляется определение наиболее равных моментов начала свершения событий для вершин исследуемого графа. Для этого с появлением пускового сигнала распределитель 2 разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов И 9 и 10. При этом импульсы проходят на входы тех счетчиков 5, соответствующие столбцы матрицы 1 которых моделируют веса дуг, исходящих из начальных узлов. Эти же импульсы через элементы И 10 проходят на счетчики 12 всех вершин граФа, кроме начальной, так как на выходе соответствующего элемента PE 8высокий потенциал.

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

И 7 — разрешающие потенциалы, то на

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

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

И 10 прекращается и на выходе счетчика 12 зафиксируется время наиболее раннего момента начала свершения события для данной вершины исследуемого графа. Вычислительный процесс продолжается до тех пор, пока на входах всех элементов И 7 не будут присутствовать высокие потенциалы. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Распределитель 2 при этом прекращает подачу импульсов на входы элементов И 9 и

10. Число импульсов, зафиксированное на счетчиках 12, соответствует моментам наиболее раннего начала свершения событий. На этом первый этап работы предлагаемого устройства заканчивается.

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

С появлением пускового сигнала распределитель 2 разрешает прохождение импульсов с выхода генератора

3 на входы всех элементов И 9 и далее на входы элементов И 11 соответствующего столбца и счетчиков 5 одноименной строки матрицы. Кроме этого распределитель 2 подает разрешающий сигнал на управляемый вход элементов И 11,поэтому импульсы далее поступают на счетные входы счетчиков

13. Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, и на вход соответствующего элемента И 7 поступает разрешающий сигнал с этого триггера.

Если на остальных входах элемента

И 7 — разрешающие потенциалы, то на выходе элемента И 9 появляются импульсные сигналы, которые поступают на счетчики 5 одноименной строки матрицы и через элементы И 11 на счетчики 13 и т.д. Вычислительный процесс на втором этапе продолжается до тех пор, пока на выходах всех элементов

И 7 не будут присутствовать высокие потенциалы.

Третий этап работы устройства заключается в сравнении показаний счетчиков 12 и,13, соответствующих наиболее ранним и наиболее поздним моментам свершения событий, путем подачи распределителем 2 управляющего сигнала на схемы 14 сравнения.

С выхода схем 14 сигнал сравнения перебрасывает триггеры 15 в единичное состояние. Единичные состояния триггеров 15 соответствуют вершинам графа, образующих максимальный критический путь.

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

t6

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

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

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

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

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

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

Р 525954, кл.G 06 F 15/20, 1976.

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

Р 491132, кл.G 06 F 15/20, 1974 (прототип).

798854

Составитель И. Дубинина

Редактор Л.Кеви Техред Н. Ковалева КорректорН.Стец

Заказ 10057/б8 Тираж 75б Поднисное

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

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

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