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

Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов. Известно устройство для определения критического пути в графе , содержащее модель сети, блок управлени генератор импульсов, формирователь весов дуг, по числу столбцов матрицы элементы ИЛИ, И, триггеры l. Однако устройство позволяет определить только величину кратчайшего пути, численно равную числу импульсов , отсчитываемому в блоке управления. Наиболее близким по технической сущности к предлагаемому является устройство для моделирования сетевых гра.фов, содержащее блок управления, импульсный вход которого соединен с выходом генератора импульсов, элементы И по числу столбцов матрич ной модели сети, цепочки из последо вательно соединенных счетчика и. триггера по числу строк и столбцов матричной модели сети. Выход тригге ра каждого, столбца подключен к информационному входу элемента И соответствующего столбца 2, Недостатком -этого устройства является малая точность моделирования. Цель изобретения - повышение точности. Указанная цель достигается тем, что в устройство для моделирования сетевых граЛ)Ов, содержащее матрицу формирователей весов дуг, каждый из которых содержит триггер и счетчик, выход которого подключен к входу триггера, выход триггера ка;кдого столбца матрицы Формирователей дуг соединен с информационным входом соответствующего элемента И первой группы, генератор тактовых импульсов , выход которого подключен к входу распределителя импульсов, введены элементЕ, НЕ, группы элементов И, группы счетчиков, схемы сравнения и триггеры, счетные входы каждого из которых подключены к выходу соответствующей схемы сравнения, первые входы каждой из которых соединены с .первым выходом распределителя импульсов , второй выход которого подключен к первым входам элементов И второй группы, вторые входы которых соединены с выходами элементов НЕ, вхохИ которых подключены к выходам соответствующих элементов И первой группы

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

,ia чертеже представлена-структурная схема устройства.

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

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

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

В исходном состоянии все триггеры 15, счетчики 12 и 13 находятся в нулевом состоянии. Распределитель 2 подает разрешающий сигнал на управляющий вход элемента И 10. Первоначально в модель 1 заносится информация о топологии моделируемого графа сети. При этом триггеры б формирователей 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 определяется пepece Jeниeм строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков. После занесения исходной информации на входах элементов И 7, объединяющих выходы формирователей 4 в столбцах, соответствующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петлей начальные узлы не содержат входящих ветвей, а, следовательно, и триггеры 6 формирователей 4, находящихся в этом столбце, будут в нулевом состоянии (элементы

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

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

Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, устанавливает в нулевое состояние соответствуюший триггер б, и на вход соответствуюгцего элемента И 7 поступает разрешение с нулевого- выхода этого триггера. Если на остальных входах этого элемента И 7 - разрешающие потенциалы, то на его выходе появляется разрешающий синал. Это свидетельствует о том, что веса дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных этим элементом И -1, сформированы. При этом формируется разрешение, поступления импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исходящих из сформированного узла. Одновременно с этим на вход элемента столбца подается высокий потенциал, а с его выхода - низкий, следовательно, подача импульсов на вход счетчика 12 через элемент И 10 прекращается и на выходе счетчика 12 зафиксируется время наиболее раннего момента начала свершения события для данной вершины исследуемого графа. Вычислительный процесс продолжается до тех пор, пока на входах всех элементов И 7 не будут присутствовать высокие потенциошы. Это свидетельствует о том, что все узлы исслеjjyeMoro графа сформированы. Распределитель 2 при этом прекращает подачу импульсов на входы элементов И 9 и 10. Число импульсов, зафиксированное насчетчиках 12, соответствует моментам наиболее раннего начала свершения событий. На этомпервый этап работы предлагаемого устройства заканчивается. /

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

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

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

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

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

O выход которого подключен к входу распределителя импульсов, о т л и -. чающееся тем, что, с целью повышения точности, в устройство введены элементы НЕ, группы элемен5тов И, группы счетчиков, схемы сравнения и триггеры, счетные входы каждого из которых подключены к выходу соответствующей схемы сравнения, первые входы каждой из которых сое0динены с nepBfcJM выходом распределителя импульсов. второй выход которого подключен к-первым входам элементов И второй группы, вторые входы которых соединены с выходами элементов НЕ, входы которых подключены к

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

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

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

0 счетчики с вторыми и третьими входами соответствующих схем сравнения.

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

1.Авторское свидетельство СССР № 525954, кл.С Об F 15/20, 1976. .

5

2.Авторское свидетельство СССР № 491132, кл.б Об F 15/20, 1974

(прототип).