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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН САНИЕ ИЗОБРЕТЕН ПЬСТВУ.8)е свидетельство СС06 Р 15/20, 1980.свидетельство СССР06 Г 15/20, 1982 юинеи сторогоходамгрупп. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИ(54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее матричную модель графа,-й узел которой вкл чает триггер, первый и второй элементы И, причем выход триггера подключен к первым входам первого и второго элементов И, первую и вторуЮ группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор тактовых импульсов, счетчик, причем выход-го ( я) .триггера первой группы подключен к вторым входам .первых элементов И-й строки матрич 1ной модели графа, выход-го триггера второй группы соединен с вторыми входами вторых элементов И-го столбца матричной модели графа, выЯОА ход первого элемента И 1 -го узла матричной модели графа подключен к соответствующему входу-го элемента ИЛИ первой группы, выход второго элемента И ) -го узла матричной модели графа соединен с соответствующим входом-го элемента ИЛИ второй группы, выход-го элемента ИЛИ первой группы подключен к единичному входу-го триггера первой группы, выход-го элемента ИЛИ второй группы соединен с единичным входом -го триггера второй группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены дешифратор и элемент задержки, выход которого подключен юР к нулевым входам триггеров первой и второй групп, выход генератора тактовых импульсов соединен с первым входом элемента И, второй вход кото- С рого является входом запуска устройства, выход элемента И подключен к ф входу элемента задержки и входу счетчика, выход которого соед входом дешифратора, выходы ко подключены соответственно к в элементов ИЛИ первой и второйИзобретение относится к вычисли-тельной технике и может быть использовано при исследовании параметров сетевых графов, а также при аппаратной реализации в специализированных процессорах макрокоманды определения вершин, образующих транзитивное и обратное транзитивное замыкание для всех вершин моделируемого граФа.1 0Известно устройство для моделирования сетевых графов, содержащее блок упранления, первый вход которого соединен с выходом генератора тактовых импульсов, счетчик импульсов, тригге ры формирователей дуг по числу строк и столбов матричной модели сети, по числу столбцов матричной модели сети элементы ИЛИ, элементы И, регистрирующие счетчики, схемы сравнения, выходы каждой из которой подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы - к выходам регистрирующих счетчиков, вторые входы схем сравнения подключены к выходу счетчика импульсов, вход которого подключен к выходу блока управления, первые входы элементов И подключены к выходу блока управления, вторые входы элементов И подключены ЗО к выходам элементов ИЛИ, входы которых подключены к выходам триггеров формирователей дуг одиоименного столбца матричной модели сети 1 .Известное устройство обеспечивает 35 только возможность распределения вершин графа цо рангам и не позволяет определять вершины, образующие транзитивное и обратное транзитивное замыкания для отдельных вершин моде лируемого графа.Наиболее близким к изобретению является устройство для моделирования сетевых графов, содержащее блок управления, первый вход которого 45 соединен с выходом генератора тактовых импульсов, счетчик импульсов, триггеры Формирователей дуг по числу строк и столбцов матричной модели сети, по числу столбцов матричной модели сети первые элементы ИЛИ, элементы И, регистрирующие счетчики, схемы сравнения, входы каждой из которых подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы - к выходам регистрирукщих счетчиков, вторые входы схем сравнения подключены к выходу счетчика импульсов, вход которого подключен к выходу блока управления, первые вхо ды элементов И подключены к выходу блока управления, вторые входы элементов И подключены к выходам соответствующих первых элементов ИЛИ, входы которых подключены к выходам 5 триггеров формирователей дуг одноименного столбца матричной моделисети, элемент НЕ, элемент И, выходкоторого через элемент НЕ подключенк управляемому входу блока управлевя, по числу столбцов матричноймодели сети вторые и третьи элементы ИЛИ, триггеры прямого и обратного отображения, управляющие триггеры, по числу строк и столбцов матричной модели сети первые и вторыеэлементы И, информационные входыкаждого из которых подключены к входу соответствующего триггера формирэвателя дуг, входы каждого второгоэлемента ИЛИ подключены к выходампервых элементов И одноименногостолбца матричной модели сети, авыходы - к входам соответствующихтриггеров прямого отображения, выходы которых подключены к управляемьМвходам первых элементов И одноименной строки матричной модели сети,входы каждоготретьего элемента ИЛИподключены к выходам вторых элементов И одноименной строки матричноймодели сети, а выходы - к входам соответствующих триггеров обратногоОтображения, выходы которых подключены к управляемым входам вторых элементов И одноименного столбца матричной модели сети, входы каждого управляющего триггера подключены квыходам соответствующей схемы сравнения, а выходы - к одноименным входам первого элемента И 2,Недостатком известного устройстваявляется низкое быстродействие приопределении вершин, образующих транзитивное и обратное транзитинное замыкания для всех вершин моделируемого графау из-за необходимости дополнительного сбрасывания триггеровпрямогО и обратного отображения, атакже установки триггеров очереднойвершины в единичное состояние.Целью изобретения является повышение быстродействияПоставленная цель достигаетсятем, что в устройство для моделирования сетевых графов, содержащее матричную модель графа, 11 -й узел которой включает триггер, первый и второй элементы И, причем ныход тригге-,ра подключен к первым входам перного и второго элементов И, первую ивторую группы элементов ИЛИ, первуюи вторую группы триггеров, элемент И,генератор. тактовых импульсов, счетчик, причем выход-го =1, ,п)триггера первой группы подключенко вторым входам первых элементов И 1-й строки матричной модели графа, выход-го триггера второй группы соединен со вторыми входами вторых элементов И 1 -го столбца матричной модели графа, выход первого60 65 Определение вераин графа, обра- зующих транзитивное замыкание, а так. же обратное транзитивное замыкание для всех вершин графа начинается после занесения исходной информации элемента И (1 -го узла матричной модели графа подключен к соответствующему входу 1 -го элемента ИЛИ первойгруппы, выход второго элемента И-го узла матричной модели графа5соединен с соответствукщим входом-го элемента ИЛИ второй группы, выход-го элемента ИЛИ первой группы подключен к единичному входу-готриггера первой группы, выход-гоэлемента ИЛИ второй группы соедине н 10сединичным входом 1 -го триггера,второй группы введены дешифратор иэлемент задержки, выход которогоподключен к нулевым входам триггеровпервой и второй групп, выход генератора тактовых импульсов соединен спервым входом элемента И, второйвход которого является входом запуска устройства, выход элемента И подключен к входу элемента задержки ивходу счетчика, выход которого соединен с входом дешифратора, выходы которого подключены соответственно квходам элементов ИЛИ первой и второйгрупп. 25На чертеже представлена структурная схема устройства,Устройство .содержит матричную модель 1 графа, триггеры 2 (Формирователей дуг), первые 3 и вторые 4 элементы И, по числу столбцов матричноймодели графа первые 5(,5 о ивторые 6, , б элементы ИЛИ, первые 7 7 и вторые 8(, , 8 дтриггеры, дешифратор 9, счетчик 10,элемент 11 задержки, элемент И 12,генератор 13 тактовых импульсов,вход 14 запуска, выходы 1515 йю 161 фю 16 п и 17.,Матричная модель 1 графа представляет собой матрицу яхт, 40где и - максимальное число вершин вграфе, однородных ячеек в составетриггера 2, первого 3 и второго 4элементов И.Устройство для моделирования сетевых графов работает следукщимобразом.Первоначально в нулевое положение.устанавливаются все триггеры 7, 8и счетчик 10. ИнФормация о топологии 50моделируемого графа заносится путемустановки соответствующих триггеров 2 в единичное состояние. Соответствующий триггер 2, ,)= 1, ,и)формирователя дуги определяется55пересечением ( -й строки ( ( - номерначальной вершины моделируемой ветвигрифа) с-м столбцом ( - номер конечной вершины моделируемой ветвиграфа). на соответствукщие триггеры 2 и обнуления триггеров 7 и 8, а также счетчика 10. После подачи управляющего сигнала на вход 14 импульсы с генератора 13 начинают поступать через элемент И 12 на вход счетчика 10 и элемента 11 задержки. С выхода счетчика 10 код (первоначально 001) поступает на вход дешифратора 9, на выходе которого возбуждается только одна шина (вначале первая), после чего единичный сигнал через элементы ИЛИ 5 и б перебрасывает в единичное состояние соответствующие триггеры 7 и 8 (вначале триггеры 71 и 8 .Единичный сигнал с выхода триггера 7( : 1 й ) поступает на вторые входы элементов, И 3-й строки матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход - к од. ноименному входу элемента ИЛИ 5), (1= 1я) единичным сигналом с выхода которого устанавливается в единичное состояние триггер 7, и т.д. Так определяются все вершины, образукщие транзитивное замыкание для-й вершины. Таким вершинам соответствует единичное состояние триггеров 7, и соответствукщий код снимается с выходов 15 устройстваВ этом коде единица в ) -м разряде соответствует номеру вершины, входящей в транзитивное замыкание для -й вершины моделируемого графа.Одновременно единичный сигнал с выхода триггера 8 (=1п) по" ступает на вторые входы элементов И 4-го столбца матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход - к одноименному входу элемента б : 1п), единичным сигналомс выхода которого устанавливается в единичное состояние триггер 8), и т .д. Так определяются все вершины, образующие обратное транзитивное замыкание для 1 -й вер шины. Таким вершинам соответствует единичное состояние триггеров 8, а соответствующий код снимается с выходов 16 устройства.Далее, после завершения всех переходных процессов по определению транзитивного и обратного транзитивного замыканий, единичный сигнал с выхода элемента 11 задержки перебррсывает все триггеры 7 и 8 в нулевое состояние. На вход счетчика 10 поступает очередной импульс, и транзитивное и обратное транзитивное замыкания определяются для второй вершины моделируемого графа и так далее, до тех пор, пока на счетчике не зафик1075268 ль И.ДубиГергель: остави ехредМ едактор Н.ПушненкТ 7,еевЩ Е Ю а 699 Подписное ного комитета СССР ений и открытий Раушская наб., д. 4/5 аказ 50 ПП фПатентф, г.ужгород, ул.Проектн и сируется код числа И, после чего с приходом очередного импульса счетчик 10 переполняется, о чем свидетельствует единичный сигнал на Вы- ходе 17 устройства. 43 Тираж ВНИИПИ Государстве. по делам изобре35, Москва, Ж,Таким образом, устройство обеспе- чивает определение транзитивного и обратного транзитивного замыканий одновременно для всех вершин моделируемого графа. на КорректорГ,Решетни