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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ЕТЕДЬСТВУ Союз Сфветскнк Соцнаанстнчеснна Ресттублнк(22) Заявлено 01, 09. 78 (21) 2683352/18-24с присоединением заявки Нов(51)М. Кл З С 06 Г 15/20 Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 230131(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВИзобретение относится к вычислительной технике и может быть исполь- зовано при исследовании параметров сетевых графов.Известно устройство для определения критического пути в графе , содержащее модель сети, блок управления, генератор импульсов, формирователь весов дуг, по числу столбцов матрицы элементы ИЛИ, И, триггеры 1.Однако устройство позволяет определить только величину кратчайшего пути, численно равную числу импульсов, отсчитываемому в блоке управле" ния.15 Наиболее близким по техническойсущности к предлагаемому являетсяустройство для моделирования сетевых граФов, содержащее блок управле"ния,импульсный вход которого соединен с выходом генератора импульсов,элементы И по числу столбцов матричной модели сети, цепочки из последовательно соединенных счетчика итриггера по числу строк и столбцовматричной модели сети. Выход триггера каждого столбца подключен к инФормационному вхрду элемента И соответствующего столбца 2,Недостатком этого устройства является малая точность моделирования.Цель изобретения - повышение точности.Указанная цель достигается тем, что в устройство для моделирования сетевых граФов, содержащее матрицу формирователей весов дуг, каждый из которых содержит триггер и счетчик, выход которого подключен к входу триггера, выход триггера каждого столбца матрицы формирователей дуг соединен с информационным входом соответствующего элемента И первой группы, генератор тактовых импульсов, выход которого подключен к входу распределителя импульсов, введены элементы НЕ, группы элементов И, группы счетчиков, схемы сравнения и триггеры, счетные входы каждого иэ которых подключены к выходу соответствующей схемы сравнения, первые входы каждой из которых соединены с ,первым выходом распределителя импульсов, второй выход которого подключен к первым входам элементов И второй группы, вторые входы которых соединены с выходами элементов НЕ, входы которых подключены к выходам соответствующих элементов И первой группыУи к первым входам элементов И третьей группы, выходы которых подключены к входам счетчиков соответствующей строки матрицы формирователей весов ,цуг и к первым входам элементов И. четвертой группы, вторые входы которых соединены с третьим выходом распределителя импульсов, четвертый выход которого подключен к вторым входам элементов И третьей группы и к третьим входам элементов И второй группы, выходы элементов И второй и четвертой группы соединены через соответствующие счетчики с. вторыми и третьими входами соответствующих схем сравнения.4 а чертеже представлена структурная схема устройства.Устройство содержит матричную модель 1 сети, распределитель 2 импульсов, генератор 3 тактовых импульсов, по числу строк и столбцов матрицы 20 формирователи 4 весов дугвключающие счетчики 5 и триггеры-б, по числу столбцов матрицы первую группу элементов И 7, элементы НЕ 8, третью группу элементов И 9, вторую группу 25 элементов И 10 и четвертую группу элементов И 11, группы счетчиков 12 и 13, схемы 14 сравнения и триггеры 15.Модель 1 сети представляет собой матрицу однородных ячеек Формирователей весов дуг размером пхп,где и- максимальное число узлов моделируемого графа.Устройство работает следующим об- разом.В исходном состояниИ все триггеры 15, счетчики 12 и 13 находятся в нулевом состоянии. Распределитель 2 подает разрешающий сигнал на управляющий вход элемента И 10. Первона чально в модель 1 заносится информация о топологии моделируемого графа сети. При этом триггеры б Формирователей 4,моделирующих ветви графа, устанавливаютсяв единичное состоя ние. Соответствующий формирователь 4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков. После занесения исходной информации на входах элементов И 7, Б объединяющих выходы Формирователей 4 в столбцах, соответствующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе ,.без циклов и петлей начальные узлы не содержат входящих ветвей, а, следовательно, и триггеры б формирователей 4, находящихся в этом столбце,будут в нулевом состоянии элементы И 7 соединены нулевыми входами триггеров б. Определение вершин граАа, образующих критический путь, осуществляется в три этапа.На первом этапе осуществляется определение наиболее равных моментов начала свершения событий для вершин исследуемого графа. Для этого с появлением пускового сигнала распределитель 2 разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов И 9 и 10. При этом импульсы проходят на входы тех счетчиков 5, соответствующие столбцы матрицы 1 которых моделируют веса дуг, исходящих из начальных узлов. Эти же импульсы через элементы И 10 проходят на счетчики 12 всех вершин граФа, кроме начальной, так как на выходе соответствующего элемента НЕ 8- высокий потенциал.Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, устанавливает в нулевое состояние соответствующий триггер б, и на вход соответствующего элемента И 7 поступает разрешение с нулевого. выхода этого триггера. Если на остальных входах этого элемента И 7 - разрешающие потенциалы, то на его выходе появляется разрешающий сиг. нал, Это свидетельствует о том, что веса дуг, входящих в узел, номер которого соответствует номеру столбца Формирователей 4, объединенных этим элементом И 7, сФормированы.При этом Формируется разрешение.поступления импульсов на входы счетчиков 5 Формирователей 4, моделирующих ветви графа, исходящих из сформированного узла. Одновременно с этим на вход элемента столбца подается высокий потенциал, а с его выхода - низкий, следовательно, подача импульсов на вход счетчика 12 через элемент И 10 прекращается и на выходе счетчика 12 заФиксируется время наиболее раннего момента начала свершения события для данной вершины исследуемого графа. Вычислительный процесс продолжается до тех пор, пока на входах всех элементов И 7 не будут присутствовать высокие потенциалы. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Распределитель 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 соответствуют вершинам графа, образующих максимальный критический путь.Из-за введенных блоков и связей между ними повышается точность моде- лирования,5 16 15 20 25 30 35 40 45 Формула изобретенияУстройство для моделирования сетевых графов, содержащее матрицуформирователей весов дуг, каждая изкоторых содержит триггер и счетчик,выход которого подключен к входутриггера, выход триггера каждогостолбца матрицы Формирователей дугсоединен с информационным входомсоответствующего элемента И первойгруппы, генератор тактовых импульсов,выход которого подключен к входураспределителя импульсов, о т л ич а ю щ е е с я тем, что, с цельюповышения точности, в устройствовведены элементы НЕ, группы элементов И, группы счетчиков, схемы сравнения и триггеры, счетные входы каж"дого из которых подключены к выходусоответствующей схемы сравнения,первые входы каждой из которых соединены с первым выходом распределителя импульсов. второй выход которого подключен к первым входам элементов И второй группы, вторые входыкоторых соединены с выходами элементов НЕ, входы которых подключены квыходам соответствующих элементовИ первой группы и к первым входамэлементов И третьей группы, выходыкоторых подключены к входам счетчиков соответствующей строки матрицыФормирователей весов,дуг и к первымвходам элементовИ четвертой группы, вторые входы которых соединеныс третьим выходом распределителя импульсов, четвертый выход которогоподключен к вторым входам элементовИ третьей группы и к третьим входымэлементов И второй группы, выходыэлементов И второй и четвертой группы соединены через соответствующиесчетчики с вторыми и третьими входами соответствующих схем сравнения.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 525954, кл.О Об Г 15/20, 1976.2. Авторское свидетельство СССРР 491132, кл.6 Об Г 15/20, 1974798854Составитель И.Дубинина Редактор Л.Кеви Техред Н. Ковалева КорректорН.Стец Заказ 10057/б 8 Тираж 75 б Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д.4/5 Филиал ППП "П,тент", г.ужгород, ул.Проектная,4