Устройство для моделирования сетевых графов Советский патент 1984 года по МПК G06F15/173 

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

блока управления, входы третьего элемента ИЛИ блока управления соединены с выходами элементов ИЛИ блока определения рангов вершин графа, а выход - с входом второго элемента НЕ блока управления, выходы реверсивного счетчика блока регистрации соединены с информационными входами элементов и группы блока регистрации, выходы которых подключены к информационным входам сумматора, третьи входы элементов И первой группы блока счетчиков длительности соединены с выходами соответствующих схем срав)Нения блока определения рангов вершин графа, первые входы элементов И второй группы блока счетчиков длительности являются инфррмационными входами устройства, вторые входы объединены и являются управляющим входом/устройства, а выходы объединены С выходами соответствующих элементов И первой группы блока счетчиков длительности и подключены к суммирующим входам счетчиков блока счетчиков длительности, выходда которых соединены через соответствующие элементы И третьей группы с входами элемента ИЛИ блока счетчиков длительности, выход которого соединен с нулевым входом . второго триггера блока управления.

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор импульсов, блок определения рангов вершин графа, состоящий из матрицы формирователей дуг,каждый формирователь дуг которой содержит триггер, п элементов ИЛИ, п элементов и, п счетчиков , п схем сравнения по числу столбцов матрицы (-« - число вершин графа), блок управления, включающий реверсивный счетчик, выходы триггеров j-x столбцов (, п) формирователя дуг соединены с входами j-x элементов ИЛИ, выходы которых соединены с информационными входами соответствующих элементов И, выходы элементов И подключены к информационным входам соответствующих счетчиков, выходы которых соединены с первыми входами схем сравнения, вторые входы которых объединены и соединены с выходом реверсивного счетчика блока управления, выход каждой j-й ( схемы сравнения подключен к входам триггеров j-й строки (,n) матрицы формирователей дуг, выход генератора импульсов соединен с управляющим входом блока управления, управляклций выход которого соединен с управляющими входами h элементов И блока определения рангов вершин графа, отличающее с.я тем, что, с целью расширения функциональных возможностей устройства путем определения длительности -поярусного выполнения сетевого графа, в него введены блок регистрации, содержащий реверсивный счетчик, группу элементов И и сумматор, блок счетчиков длительности, содержащий три группы из п элементов И, п счетчиков и элемент ИЛИ, а блок управления дополнительно содержит.пять элементов и, три элемента ИЛИ, два триггера,два элемента НЕ и формирователь импульсов, причем первый управляющий вход блока управления соединен с первыми входами первого, второго третьего и четвертого элементов И блока управления и первыми входами i элементов И первой группы блока счетчиков длительности, вторые вхо(Л ды первого и второго элементов И блока управления объединены и подключены к единичному выходу первого триггера блока управления и вторым входам элементов И первой группы блока счетчиков длительности,третий вход первого элемента И блока , управления соединен с единичным выходом второго триггера блока управления , а выход - с вычитакицим входом реверсивного счетчика блока, регистрации, третий вход второго элеСП мента И и первый вход пятого элеменО) та И блока управления объединены и подключены к нулевому выходу второго триггера блока управления и к управляющим входам элементов И группь блока регистрации, выход второго элемента И блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления, вторые входы третьего и четвертого элементов И блока управления объединены и подключены к нулевому выходу первого триггера блока управления, выход третьего элемента И блока управления соединен с суммирующим входом реверсивного счетчика блока управления, выход четвертого элемента И

1

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

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

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

выход счетчика числа имяульсов соединен с первыми входами блоков сравнения, выход каждого элемента ИЛИ подключен к второму входу соответствующего элемента И, выход которого соеj HHeH с входом соответствующего регистрирующего счетчика, Жаход кото- рого подключен к второму входу соответствующего бйока сравнения, выход

которого соединен с входами формирователей дуг соответствующей строки С2}.

Недостатком известных устройств является невозможность определения

длительности поярусного выполнения сетевого графа.

Цель изобретения - расширение функциональных возможностей устройства путем определения длительности поярусного выполнения сетевого

графа.

Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, блок определения рангов вершин графа, состоящий

из матрицы формирователей дуг, каждый формирователь дуг которой родержит триггер, п элементов ИЛИ, n элементов И, n счетчиков, n схем сравнения по числу столбцов матрицы (. г - число вершин графа), блок управления, включакнций реверсивный счетчик, выходы триггеров j-x стобцов (,n) формирователя дуг соединены с входами j-x элементов ИЛИ, выходы которых соединены с ин формационными входами соответствующих элементов И, выходы элементов И подключены к информационным входам соответствующих счетчиков,выходы которых соединены с первыми входами схем сравнения, вторые входы которых объединены и соединены с выходом реверсивного счетчика бло ка управления, выход каждой j-й (,n) схемы сравнения подключен к входам триггеров j-й строки (j 1,n } матрицы формирователей дуг выход генератора импульсов соединен с управляющим входом блока управления, управляющий выход которого сое динен с управляющими входами n элементов И блока определения рангов вершин графа,дополнительно введены блок регистрации, содержащий реверсивный счетчик, группу элементов И и сумматор, блок счетчиков длител ности, содержащий три группы из n элементов И, n счетчиков и элемент ИЛИ, а блок управления дополнительно содержит пять элементов И, три элемента ИЛИ, два триггера, два элемента НЕ и формирователь импульсов, причем первый управляющий вход блока управления соединен с первыми входами лервого, второго, третье го и четвертого элементов И блока управления и первыми входами элементов И первой группы блока счетчиков длительности, вторые входы первого и второго элементов И блока управления объединены и подклю.чены к единичному выходу первого триггера блока управления и вторым входам элементов и первой группы блока счетчиков длительности, третий вход первого элемента И блока управления соединен с единичным выходом второго триггера блока упра ления, а выход - с вычитающим входом реверсивного счетчика блока регистрации, третий вход второго элемента И и первый вход пятого эле мента И блока управления объединены и подключены к нулевому выходу второго триггера блока управления и к управляющим входам элементов И груп пы блока регистрации, выход второго элемента И блока управления соединен с первыми входами первого и вто рого элементов ИЛИ блока управления, вторые входы третьего и четвертого элементов И схемы управления объединены и подключены к нулевому выходу первого триггера блока управления, выход третьего элемента И блока управления соединен с суммирующим входом реверсивного счетчика блока управления, выход четвертого элемента И блока управления является управляющим выходом блока управления, второй вход пятого элемента И блока управления через первый элемент НЕ; блока управления соединен с выходом реверсивного счетчика блока управления, а выход - с первым входом генератора импульсов, второй вход которого является пусковым входом устройства, второй вход первого элемента ИЛИ блока управления является входом установки исходного состояния устройства, и соединен с нулевым входом первого триггера блока управления, управляющими входами реверсивного счетчика блока управления, сумматора блока регистрации, счетчиков блока счетчиков длительности и счетчиков блока определения рангов вершин графа, выход первого элемента ИЛИ блока управления подключен к единичному входу второго триггера блока управления и суммирующему входу реверсивного счетчика блока регистрации, второй вход второго элемента ИЛИ блока управления соединен через формирователь импульсов с выходо°м второго элемента НЕ и единичным входом первого триггера блока управления, а выход - с вычитающим входом реверсивного счетчика блока управления, входы третьего элемента ИЛИ блока управления соединены с выходами элементов ИЛИ блока определения рангов вершин графа, а выход - с входом второго элемента НЕ блока управления, выходы реверсивного счетчика -блока регистрации соединены с информационными входами элементов И группы блока регистрации, выходы которых подключены-к информационным входам сумматора, третьи входы элементов И первой группы блока счетчиков длительности соединены с выходами соответствующих схем сравнения блока определения рангов вершин графа, первые входы элементов И второй группы блока счетчиков длительности являются информационными входами устройства, вторые входы объединены и являются управляющим входом устройства, а выходы объединены с выходами соответствующих элементов И первой группы блока счетчиков длительности и подключены к суммирующим входам счетчиков блока счетчиков длительности, выходы которых соединены через соответствующие элементы И третьей группы с входами элемента ИЛИ блока счетчиков длительности, выход которого соединен с нулевьм входом второго триггера блока управления. 1 На чертеже приведена структурная схема устройства. Устройство содержит блок 1 регистрации, блок 2 управления, блок 3 счетчиков длительности, блок 4 определения рангов вершин графа, генератор 5 импульсов, вход 6 установки исходного состояния устройства, пусковой вход 7 устройства, информационные входы 8 и 9 устройства и управляющий вход 10 устройства. Блок 1 регистрации включает реверсивный счетчик 11, группу элементов И 12 и сумматор 13. Блок 2 управления содержит элемент И 14, элемент ИЛИ 15, триггер 16, реверсивный счетчик 17, элемент И 18, элемент ИЛИ 19, элемент И 20, i формирователь 21 импульсов, элемент И 22, триггер 23, элемент НЕ 24, элемент ИЛИ 25, а также элементы НЕ 36 и И 37. Блок 3 счетчиков длительности состоит из элемента ИЛИ 2.6, группы элементов И 27, группы счетчиков 28, группы элементов И 29 ч группы элементов И 30. Блок 4 определения рангов вершин графа содержит группу схем 31 сравнения, группу счетчиков 32,. группу элементов И 33, группу элементов ИЛИ 34 и матрицу из триггеров 35 фо мирователей дуг. Устройство работает следующим об разом. Первоначально в блок 4 заносится информация о топологии моделируемог графа сети. При этом сигналы, посту пакядие на входы триггерюв 35 формирователей дуг, моделирующих ветви графа, устанавливают их в единичное состояние. Соответствующий триггер формирователей дуг определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. После занесения исходной информации на вы ходах элементов 34, объединяющих выходы триггеров 35 формирователей дуг в столбцах, соответствующих начальным узлам моделируемого графа, имеются низкие потенциалы, так как в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей и триггеры формирователей дуг, находящиеся в этом столбце, будут в нулевом состоянии. Сигнал начальной установки, пост пающий на вход б устройства, подает ся далее на управляющие входы сумматора 13, счетчиков 17, 28 и 32, н левой ВХОД триггера 23 и обнуляет и Этот же сигнал поступает на первый вход элемента ИЛИ 15, а с его выхода - на единичный вход триггера 16 и на суммирующий вход счетчика 11. При этом на соответствующих выходах 0 триггеров 23 и 16 появляется единичный потенциал, а на счетчике 11 устанавливается единичный код во всех разрядах. Сигнал на входе 10 разрешает прием на счетчик 28 прямого кода длительностей соответствующих узлов графа, поступающих на Входы 9 устройства. Сигнал на входе 10, поступая на управляющие входы элементов И 29, разрешает прохождение через них сигналов с входов 9 прямого кода длительности счета соответствующего узла графа, который поступает на вторые входы элементов И 29. С выходов элементов И 29 код коступает на информационные входы счетчиков 28, где и запоминается. С поступлением пускового сигнала с входа 7 на первый вход генератора 5 импульсов на его выходе появляются сигналы, синхронизирующие работу устройства. Единичный потенциал с первого выхода триггера 23 подается на вторые входы элементов И 22 и 20 и разрешает прохождение поступающих на первые их входы сигналов с выхода генератора импульсов. Сигнал с выхода элемента И 2О,поступающий на суммирующий вход счетчика 17, прибавляет к его содержимому 1. Одновременно сигнал с выхода элемента И 22 поступает на управляющие входы элементов И 33, Нри этом сигналы не проходят через элементы И 33 на входы счетчиков 32 тех столбцов, все триггеры 35 которых находятся в нулевом состоянии. Далее содержимое счетчиков 32 поступает на первые входы схем 31 сравнения соответствующего столбца, на вторые входы которых подается информация со счетчика 17. При несовпадении показаний счетчиков 17 и 32 схема 31 сравнения вырабатывает импульс, который сбрасывает в нулевое состояние триггеры 35 формирователей дуг строки с HC iepoM, равным, .номеру столбца, в схеме сравнения которого не произошло сравнения. С появлением очередного сигнала на Ьыходе генератора импульсов процесс повторяется. Вычислительный процесс продолжается до тех пор/ пока все триггеру 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, разрешает прохождение через него кода со счетчика j1 на входы сумматора 13. В этом случае на сумматоре оказывается код, равный максимальной длительности из длительностей узлов наивысшего ранга.

Кроме того, единичный потенциал с выхода триггера 16 подается на третий вход элемента И 18 и вместе с единичным потенциалом с выхода триггера 23, который подается на

второй вход, разрешает прохождение через элемент И 18 поступившего на его первый вход импульса с генератора 5 импусов. Сигнал с выхода элемента И 18 поступает на

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

с выхода элемента И 18 подается также на первый вход элемента ИЛИ 19 и с его выхода на вычитающий вход счетчика 17. Вычитание единицы из содержимого счетчика 17 (счетчика

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

длительностью в следующем ранге и подсуммирование соответствующего кода к содержимому сумматора.

По окончании этого процесса при обнулении счетчика 17 в сумматоре

13 оказывается код, равный времени счета по графу, узлы которого предварительно распределены по рангам. Этот процесс оканчивается тогда, когда к содержимому сумматора 13 подсуммируется длительность максимального узла нулевого ранга и код в нем становится равнь1м времени счета по графу, узлы которого предварительно распределены по рангам.При -STOM генератора 5 импульсов будет

остановлен сигналом с выхода элемента И 37, на первый вход которого подается единичный сигнал с нулевого выхода триггера 16, а .на второй вход - сигнал с выхода второго элемента НЕ 36, который инвертирует сигнал с выхода счетчика 17.

Таким образом, устройство предварительно распределяет граф по рангам а затем для всех рангов выявляет

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