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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК б У 15 20 ЕН детельс15/20тельств15/20,ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЭОБР Н АВТОРСКОМУ/ СВИДЕТЕЛЬСТ(56) 1, Авторское сви тво СССРР 525954, кл. С 06 Р 1974.2. Авторское свиде о СССРР 716043, кл. 0 06 Р 1977(54)(57) УСТРОИСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащеегенератор импульсов, блок определения рангов вершин графа, состоящийиз матрицы формирователей дуг,каждый формирователь дуг которой содержит триггер, и элементов ИЛИ, иэлементов И, и счетчиков, . и схемсравнения по числу столбцов матрицы(-и - число вершин графа), блок управления, включающий реверсивный счетчик выходы триггеров )-х столбцов=1, и) формирователя дуг соединены с входами )-х элементов ИЛИ,выходы которых соединены с информационными входами соответствующихэлементов И, выходы элементов Иподключены к информационным входамсоответствующих счетчиков, выходыкоторых соединены с первыми входамисхем сравнения, вторые входы которых объединены и соединены с выходом реверсивного счетчика блокауправления, выход каждой )-й=1, и) схемы сравнения подключенк входам триггеров )-й строки =1,и)матрицы формирователей дуг, выходгенератора импульсов соединен суправляющим входом блока управления, управляющий выход которогосоединен с управляющими входами иэлементов И блока определения рангов вершин графа, о т л и ч а ю щ ее с.я тем, что, с целью расширения функциональных возможностейустройства путем определения дли,801070560 А тельности,поярусного выполнения сетевого графа, в него введены блок регистрации, содержащий реверсивный счетчик, группу элементов И и сумматор, блок счетчиков длительности, содержащий три группы из и элементов И, и счетчиков и зле"г мент ИЛИ, а блок управления дополнительно содержит. пять элементов И, три элемента ИЛИ, два триггера,два элемента НЕ и формирователь импульсов, причем первый управляющий вход блока управления соединен с первыми входами первого, второго третьего и четвертого элементов И блока управления и первыми входами элементов И первой группы блокаФ счетчиков длительности, вторые вхое ды первого и второго элементов И блока управления объединены и подключены к единичному выходу первого триггера блока управления и вторым входам элементов И первой группы блока счетчиков длительности, третий вход первого элемента И блока , управления соединен с единичным выходом второго .триггера блока управления, а выход - с.вычитающим входом реверсивного счетчика блока, регистрации, третий вход второго элемента И и первый вход пятого элемен та И блока управления объединены и подключены к нулевому выходу втррого триггера блока управления и к .управляющим входам элементов И груп блока регистрации, выход второго зл мента И блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления, вто рые входы третьего и четвертого элементов И блока управления объединены и подключвны,к нулевому выходу первого триггера блока управления, выход третьего элемента И блока управ-. ления соединен с суммирующим входом реверсивного счетчика блока управления, выход четвертого элемента И1070560 блока управления является управляющим выходом блока управления, второй вход пятого элемента И блока управления через первый элемент НЕ блока управления соединен с выходом реверсивного счетчика блока управления, а выход - с первым входом генератора импульсов, второй вход которого является пусковым входом устройства, второй вход первого элемента ИЛИ блока управления является входом установки исходного состоя, ния устройстваи соединен с нулевым". входом первого триггера блока управления, управляющими входами реверсивного счетчика блока управления, сумматора блока регистрации, счетчиков блока счетчиков длительности и счетчиков блока определе. ния рангов вершин графа, выход первого элемента ИЛИ блока управления подключен к единичному входу второго триггера блока управления и суммирующему входу реверсивного блока регистрации, второй вход второго элемента ИЛИ блока управления соединен через формирователь импульсов с выходом второго элемента НЕ и единичным входом первого триггера блока управления, а выход -с вычитающим входом реверсивного счетчика 1Изобретение относится к вычисли,тельной технике и может быть использовано при исследовании сетевых граФов.Известно устройство для опреде ления кратчайшего пути в графе, содержащее генератор импульсов, выход которого подключен к входу блока управления, и матрицу формирователей дуг, причем выходы формировате лей дуг каждого столбца соединены с входами соответствующего элемента ИЛИ Г 13.Наиболее близким по технической сущности к предлагаемому является устройство для моделирования сетевых графов, содержащее генератор,:импульсов, выход которого подключен к входу блока управления, матрицу формирователей дуг, выходы формирователей дуг каждого столбца соединены с входами соответствующего элемента ИЛИ, элементы И по числу столбцов, регистрирующие счетчики, блоки сравнения и счетчик числа импульсов, вход которого соединен с первыми 25 входами элементов И и подключен к выходу блока управления, при этом блока управления, входы третьегоэлемента ИЛИ блока управления соеди-,нены с выходами элементов ИЛИ блокаопределения рангов вершин графа, авыход - с входом второго элементаНЕ блока управления, выходы реверсивного счетчика блока регистрации соединены с информационными входами элементов И группы блока регистрации,выходы которых подключены к информационным входам сумматора, третьивходы элементов И первой группы блока счетчиков длительности соединеныс выходами соответствующих схем сравнения блока определения рангов вершин графа, первые входы элементов Ивторой группы блока счетчиков длительности являются инфррмационными входами устройства, вторые входы объединены и являются управляющим входом,устройства, а выходы объединеныс выходами соответствующих элементов И первой группы блока счетчиковдлительности и подключены к суммирующим входам счетчиков блока счетчиков длительности, выходы которыхсоединены через соответствующие элементы И третьей группы с входами элемен-та ИЛИ блока счетчиков длительности, выход которого соединен с нулевым входом, второго триггера блока управления,2выход счетчика числа импульсов соеди нен с первыми входами блоков сравнения, выход каждого элемента ИЛИ подключен к второму входу соответствующего элемента И, выход которого соединен с входом соответствующего регистрирующего счетчика,йход кото- - рого подключен к второму входу соот ветствующегоблока сравнения, выход которогосоединен с входами формирователей дуг соответствующей строки 121.Недостатком известных устройств является невозможность определения длительности поярусного выполнения сетевого граФа.Цель изобретения - расширение функциональных возможностей устройства путем определения длительности поярусного выполнения сетевого графа.Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, блок определения рангов вердин графа, состоящий из матрицы формирователей дуг, каждый Формирователь дуг которой родержит. триггер, и элементов ИЛИ,и элементов И, и счетчиков, и схемсравнения по числу столбцов матрицы (.ь - число вершин графа), блокуправления, включающий реверсивныйсчетчик, выходы триггеров )-хстобцов (3=1,п) формирователя дугсоединены с входами )-х элементовИЛИ, выходы которых соединены с информационными входами соответствующих элементов И, выходы элементовИ подключены к информационным входам соответствующих счетчиков,выходы которых соединены с первымивходами схем сравнения, вторые входы которых объединены и соединеныс выходом реверсивного счетчика бло 20 блока управления соединен с первыми входами лервого, второго, третье 40 входам элементов И первой группы 45блока счетчиков длительности, третий вход первого элемента И блокауправления соединен с единичнымвыходом второго триггера блока управ 50 65 ка управления, выход каждой 1-й=1,п) схемы сравнения подключенк входам триггеров 3-й строки=1,п) матрицы формирователей дуг,выход генератора импульсов соединенс управляющим входом блока управления, управляющий выход которого соединен с управляющими входами и элементов И блока определения ранговвершин графа, дополнительно введеныблок регистрации, содержащий реверсивный счетчик, группу элементов И и сумматор, блок счетчиков длительности, содержащий три группы из иэлементов И, и счетчиков и элементИЛИ, а блок управления дополнительно содержит пять элементов И, триэлемента ИЛИ, два триггера, дваэлемента НЕ и формирователь импульсов, причем первый управляющий вход го и четвертого элементов И блокауправления и.первыми входами элементов И первой группы блока счетчиков длительности, вторые входыпервого и второго элементов И блока управления объединены и подклю,чены к единичному выходу первоготриггера блока управления и вторым ления, а выход - с вычитающим входом реверсивного счетчика блокарегистрации, третий вход второго элемента И и первый вход пятого элемента И блока управления объединены и подключены к нулевому выходу второго триггера блока управления и куправляющим входам элементов И группы блока регистрации, выход второго элемента И блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления, вторые входы третьего и четвертого элементов И схемы управления объединены и подключены к нулевому выходу первого триггера блока управления, выход третьего элемента И блока управления соединен с суммирующим входом реверсивного счетчика блока управления, выход четвертого элемента И блока управления является управляющим выходом блока управления, второй вход пятого элемента И блока управления через первый элемент НЦ блока управления соединен с выходом реверсивного счетчика блока управления, а выход - с первым входом генератора импульсов, второй вход которого является пусковым входом устройства, второй вход первого элемента ИЛИ блока управления является входом установки исходного состояния устройства, и соединен с нулевым входом первого триггера блока управления, управляющими входами реверсивного счетчика блока управления, сумматора блока регистрации, счетчиков блока счетчиков длительности и счетчиков блока опре. деления рангов вершин графа, выход первого элемента ИЛИ блока управления подключен к единичному входу второго триггера блока управления и суммирующему входу реверсивного счетчика блока регистрации, второй вход второго элемента ИЛИ блока управления соединен через формирователь импульсов с выходом второго элемента НЕ .и единичным входом первого триггера блока управления, а выход - с вычитающим входом реверсивного счетчика блока управления, входы третьего элемента ИЛИ блока управления соединены с выходами элементов ИЛИ блока определения рангов вершин графа,а выход - с входом второго элемента НЕ блока управления, выходы реверсивного счетчика блока регистрации соединены с информационными входами элементов И группы блока регистрации, выходы которых подключены к информационным входам сумматора, третьи входы элементов И первой группы блока счетчиков длительности соединены с выходами соответствующих схем сравнения блока определения рангов вершин графа, первые входы элементов И второй группы блока счетчиков длительности являются информационными входами устройства, вторые входы объединены и являются управляющим входом устройства, а выходы объединены с выходами соответствующих элементов И первой группы блока счетчиков длительности иподключены к суммирующим входам счетчиков блока счетчиков длительности, выходы которых соединены через соответствующие элементы И третьей группы с входами элемента ИЛИ блока счетчиков длительности, выход которого соединен с нулевым входом второго триггера блока управления.На чертеже приведена структурная схема устройства.Устройство содержит блок 1 регистрации, блок 2 управления, блок 3 счетчиков длительности, блок 4 определения рангов вершин графа, ге нератор 5 импульсов, вход б установки исходного состояния устройства,.пусковой вход 7 устройства, информационные входы 8 и 9 устройства и управляющий вход 10 устройства. 10 Блок 1 регистрации включает реверсивный счетчик 11, группу элементов И 12 и сумматор 13.Блок 2 управления содержит элемент И 14, элемент ИЛИ 15, триггер16, реверсинный счетчик 17, элементИ 18, элемент ИЛИ 19, элемент И 20,формирователь 21 импульсов, элементИ 22, триггер 23, элемент НЕ 24,элемент ИЛИ 25, а также элементы НЕ36 и И 37. Блок 3 счетчиков длительности состоит нз элемента ИЛИ 26,группы элементов И 27, группы счетчиков 28, группы элементов И 29 игруппы элементов И 30.Блок 4 определения рангов вершинграфа содержит группу схем 31 сраннения, группу счетчиков 32,.группуэлементов И 33, групйу элементовИЛИ 34 и матрицу из триггеров 35 фор.мирователей дуг.Устройство работает следующим образом,Первоначально в блок 4 заноситсяинформация о топологии моделируемого З 5графа сетиПри этом сигналы, поступающие на входы триггеров 35 формирователей дуг, моделирующих ветвиграфа, устанавливают их в единичноесостояние, Соответствующий триггер 40формирователей дуг определяется пересечением строки с номером, равнымномеру начального узла моделируемойветви, и столбца с номером, равнымномеру ее конечного узла. После 45занесения исходной информации на выходах элементов 34, объединяющихвыходы триггеров 35 формирователейдуг в столбцах, соответствующих начальным узлам моделируемого гРафа, 50имеются низкие потенциалы, так какв однонаправленном графе без циклови петель начальные узлы не содержат входящих ветвей и триггеры Формирователей дуг, находящиеся н этомстолбце, будут в нулевом состоянии,Сигйал начальной установки, поступающий на вход б устройства, подается далее на управляющие входы сумматора 13, счетчиков 17, 28 и 32, нулевой вход триггера 23 и обнуляет их.60Этот же сигнал поступает иа первыйвход элемента ИЛИ 15, а с его выхода - на единичный вход триггера 16и на суммирующий вход счетчика 11.При этом на соответствующих выходах 65 триггеров 23 и 16 появляется единичный потенциал, а на счетчике 11устанавливается единичный код новсех разрядах,Сигнал на входе 10 разрешает прием на счетчик 28 прямого кода длительностей соответствующих узловграфа, поступающих на входы 9 устройства. Сигнал на входе 10, поступаяна управляющие входы элементов И 29,разрешает прохождение через них сигналов с входов 9 прямого кода длитель.ности счета соответствующего узлаграфа, который поступает на вторыевходы элементов И 29. С выходов элементов И 29 код коступает на информационные входы счетчиков 28, гдеи запоминается.С поступлением пускового сигналас входа 7 на первый вход генератора5 импульсов на его выходе появляютсясигналы, синхронизирующие работуустройства, Единичный потенциал спервого выхода триггера 23 подаетсяна вторые нходы элементов И 22 и 20и разрешает прохождение поступающихна первые .их входы сигналов с выходагенератора импульсов. Сигнал с выхода элемента И 20,поступающий насуммирующий вход счетчика 17, прибавляет к его содержимому "1". Одновременно сигнал с выхода элементаИ 22 поступает на управляющие нходыэлементов И 33, при этом сигналы непроходят через элементы И 33 навходы счетчиков 32 тех столбцов, всетриггеры 35 которых находятся в нулевом состоянии. Далее содержимоесчетчиков 32 поступает на первыевходы схем 31 сравнения соответствующего столбца, на вторые входыкоторых подается информация сосчетчика 17. При несовпадении показаний счетчиков 17 и 32 схема 31сравнения вырабатывает импульс, который сбрасывает в нулевое состояние триггеры 35 Формировтелей дугстроки с номером, равным .номерустолбца, в схеме сравнения которогоне произошло сравнения. С появлением очередного сигнала на йыходегенератора импульсов процесс повторяется.Вичислительный процесс продолжается до тех пор, пока все триггеры 35 не будут обнулены. Как только последний из них обнулится, нулевые сигналы с выхсдов элементов ИЛИ 34 поступят на входы элемента ИЛИ 25, а с еМ выхода - на вход элемента НЕ 24. Пояиншийся на его выходе единичный сигнал поступит на единичный вход триггера 23 и переведет его в единичное состояние . Сигнал с выхода элемента НЕ 24 поступит также на вход формирователя 21 импульсов, с его выхода - на вход элемента ИЛИ 19, с выхода которого -на вычитающий вход счетчика 17. Это необходимо для получения на счетчике 17 кода, равного номеру максимального ранга. При появлении данного кода на счетчике 17 на вы.ходах схем 31 сравнения, соответствующих узлам графа максимального г ранга, появится единичный сигнал. который поступит на входы выбранных элементов И 30 на вторые входы которых поступит единичный потенциал. с единичного выхода триггера 23, поэтому поступающие на первые входы этих элементов сигналы с выхода генератора импульсов будут проходить через них на суммирующий вход счетчиков 28, увеличивая их содержимое на единицу. Этот же импульс с генератора импульсов, поступая на вычитающий вход счетчика 11 через элемент И 14, вычтет из его содержимого единицу. Импульс с генератора импульсов, поступив на первый вход элемента И 14 про ходит через него, так как на два других входа поданы разрешающие погенциалы: на второй вход - с выхода триггера 23, а на третий - с выхода триггера 16.Процесс предсуммирования единицы к содержимому счетчиков 28, соответствующих узлам графа, входящим в наивысший ранг, и одновременное вычитание единицы из содержимого счетчика 11 продолжается до тех пор, пока не будет заполнен первый из счетчиков 28 этой группы. При этом на счетчике 11 будет .зафиксирован код, равный длительности выполнения узла графа, у которого она максимальна в данном ранге. Фиксация содержимого счетчика 11 происходит за счет того, что единичный код, поступивщий на входы одного из элементов И 27, вызывает появлениесигнала на его выходе, котбрый через элемент ИЛИ 26 поступает напервый вход триггера 16 и.переводитего в нулевое состояние. При этомпоявившийся на выходе триггера 16единичный сигнал, поступив на управляющие входы элементов И 12, разре- шаег прохождение через него кодасо счетчика 11 на входы сумматора13. В этом случае на сумматоре оказывается код, равный максимальнойдлительности из длительностей узловнаивысшего ранга. Кроме того, единичный потенциалс выхода триггера 16 подается натретий вход элемента И 18 и вместес единичным потенциалом с выходатриггера 23, который подается навторой вход, разрешает прохождение через элемент И 18 поступившего на его первый вход импульсас генератора 5 импусов, Сигнал свыхода элемента И 18 поступает навторой вход элемента ИЛИ 15 и с еговыхода на суммирующий вход счетчика11, устанавливая на нем вновь единичный код во всех разрядах, и наединичный вход триггера 16. Сигнал 15 с выхода элемента И 18 подается также на первый вход элемента ИЛИ 19и с его выхода на вычитающий входсчетчика 17. Вычитание единицы изсодержимого счетчика 17 (счетчика 20 номера ранга) и перевод в единичноесостояние триггера 16 позволяют сприходом очередного импульса с генератора импульсов начать процессвыявления узла графа с максимальной 25 длительностью в следующем рангеи подсуммирование соответствующегокода к содержимому сумматора.По окончании этого процесса приобнулении счетчика 17 в сумматоре13 оказывается код, равный времени счета по графу, узлы которогопредварительно распределены по рангам. Этот .процесс оканчиваетсятогда, когда к содержимому сумматора13 подсуммируется длительность максимального узла нулевого ранга и кодв нем становитсяравным времени счета по граФу, узлы которого предварительно распределены по рангам.Приэтом генератора 5 импульсов будет 40 остановлен сигналом с выхода элемента И 37, на первый вход которогоподается единичный сигнал с нулевого выхода триггера 16, а .на второйвход - сигнал с выхода второго эле мента НЕ 36, который инвертируетсигнал с выхода счетчика 17.Таким образом, устройство предварительно распределяет граф по рангама затем для всех рангов выявляетФ 5 О узлы с максимальной длительностьювыполнения и суммирует коды длительностей, им соответствующие, что расширяет функциональные возможностиустройства путем определения длительности поярусного выполнения сетевого граФа.1070560 Составитель С. Назароведактор Т. Мермелштейн Техред В.Далекорей Хоррект тяга илиал ППП "Патент", г, Ужгород, ул. Проектная Заказ 11683/46 ВНИИП по 113035