Устройство для определения характеристик сетей

(21) 3806351/24-24 (22) 25.10.84 (46) 07.01.87. Бюл. (71) Институт пробл в энергетике АН УСС (72) А.Г. Додонов, С.П. Пелехов и Н.М. (53) 681.333(088.8) (56) Авторское свид В 422002, кл. С 0 САвторское свидет В 1024930, кл, С 06 В 1ем моделированияР(54) УСТРОЙСТВО РАКТЕРИСТИК СЕТЕ РЕДЕЛЕ НИЯ областстности рмаци чки з ния,конструкци ройства. Целью ычислительного ус обретения являетс оставл ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРпо делАм изоБРетений и ОткРытий ОПИСАНИЕ ИЗОБРЕ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 57) Изобретение относитсяычислительной техники, в чустройствам обработки инфпециального назначения с т повышение быстродеиствия прлении характеристик сетей. ная цель достигается эа счет дополнительного введения операционного блока, содержащего блок памяти номеров свершившихся событий в узлах, вычитатель, регистры, элементы И, ИЛИ, НЕ и элементы задержки, регистр номера конечного узла сети, дешифратор нулевого состояния, блок сравнения кодов коммутатора, триггеры, блок памяти количеств входящих в узлы ветвей, два блока расчета характеристик, содержащего два блока памяти ранних окончаний событий в узлах, сумматор, регистры и элементы И, ИЛИ, блок памяти кодов весов длительности ветвей. В блок моделирования тополо гни введены два коммутатора, регистр фр номера начального узла сети и элемент ф ф задержки, Быстродействие при расчете характеристик сетей увеличиваетсяпо крайней мере в 1,5 - 2 раза по срав- Д нению с известными устройствами за м счет изменения процедур обработки Ь 1 исходной информации. 3 ил, 00Ю17 12821 триггера. блока моделирования топологии, вторые входы третьего и четвертого элементов И блока моделирования топологии соединены соответственно с третьим и четвертым выхода" ми генератора тактовых импульсов, выход третьего элемента И блока моделирования топологии соединен с первым входом первого элемента И и с входом записи блока памяти количеств 10 входящих в узлы ветвей операционного блока, выход которого соединен с первым входом вычитателя операционного блока, второй вход которого подключен к источнику постоянного единичного сигнала, а выходы соединены с информационным входом первого регистра операционпого блока, выход которого подключен к информационному блоку памяти количеств входящих 20 в узлы ветвей операционного блока, адресный вход которого соединен с информационным входом второго регистра операционного блока, с первым25 входом первого коммутатора операционного блока и с выходом блока памяти номеров конечных узлов ветвей блока моделирования топологии, выход четвертого элемента И блока моделирования топологии подключен к первому входу второго элемента И операционного блока, выход второго элемента И блока моделирования топологии соединен с входом считывания блока памяти количеств входящих в узлы 35 ветвей и входом первого элемента задержки операционного блока, выход подключен к входу разрешения записи первого регистра операционного блока, выход которого соединен с вхо дом дешифратора нулевого состояния операционпого блока, .выход которого соединен с вторыми входами первого и второго элементов И операционного блока, выход первого элемента И операционного блока подключен к входу записи блока памяти номеров свершившихся событий в узлах операционного блока, выходы и младших разрядов которого соединены с соответствующими информационными входами второго коммутатора операционного блока, управляющий вход которого. подключен к единичному выходу второго триггера операционного блока и к первым вхо дам третьего четвертого и пятого элементов И операционного блока, нуле-ой выход второго триггера операци 51 18онного блока соединен с первым входом шестого элемента И операционного блока, выход которого подключен к входу второго элемента задержки операционного блока, выход второго элемента задержки операционного блока соединен с нулевым входом первого триггера операционного. блока, выход дешифратора состояния блока моделирования топологии соединен с единичным входом первого триггера операционного блока, единичный выход которого соединен с вторыми входами третьего, четвертого-; пятого и шестого элементов И операционного блока, третьи входы третьего, четвертого и пятого элементов И операционного блока соединены соответственно с вторым, третьим и четвертым выходами генератора тактовых импульсов, третий вход шестого элемента И операционного блока подключен к третьему выходу генератора тактовых импульсов, выход второго элемента И операционного блока соединен с единичным входом третьего триггера операционного блока и с выходом разрешения записи второго регистра операционного блока, выход которого соединен с вторым информационным входом второго коммутатора операционного блока и с и младшими разрядами информационного входа блока памяти номеров свершивыхся событий в узлах, вход (п+1)-го разряда информационного входа которого соединен с нулевым выходом третьего триггера операционного блока, выход второго коммутатора операционного блока соединен с информационным входом третьего регистра операционного блока, выход которого подключен к второму информационному входу первого коммутатора операционного блока и второму информационному входу первого коммутатора блока моделирования, топологии, управляющий вход первого коммутатора операционного блока соединен с единичным выходом первого триггера блока моделирования топологии, выход первоо коммутатора операционного блока подключен к адресному входу блока памяти номеров свершившихся событий в узлах операционного блока, выход третьего элемента Е операционного блока соединен с входом-считывания блока памяти номеров свершившихся событий в узлахоперационного блока, выход (и+1)-го19,12821 разряда которого соединен с первым входом седьмого элемента И операционного блока, второй вход которого соединен с первым входом первого элемента ИЛИ операционного блока и с выходом четвертого элемента И операционного блока, выход седьмого элемента И операционного блока подключен к входу третьего элемента задержки операционного блока, выход кото рого соединен с нулевым входом второго триггера операционного блока, выход пятого элемента И операционного блока подключен к второму входу второго элемента ИЛИ блока модели рования топологии и входу четвертого элемента задержки операционного блока, выход которого соединен с единичным входом второго триггера операционного блока и с первым входом восьмого элемента И операционного блока, второй вход которого подключен к выходу элемента НЕ операционного блока, вход которого соединен с выходом блока сравнения кодов операционного25 блока, выход восьмого элемента И операционного блока соединен с вторым входом первого элемента ИЛИ блока моделирования топологии, выход шестого элемента И операционного блока подключен к нулевому входу третьего триггера операционного блока и к второму входу первого элемента ИЛИ операционного блока, выход которого соединен с входом разрешения 35 записи третьего регистра операционного блока, выход которого соединен с первым входом блока сравнения кодов операционного блока, второй вход которого подключен к выходу регистра номера конечного узла сети операционного блока, вход которого является вторым информационным входом устройства, выход блока сравнения кодов операционного блока соединен с пер-. выми входами элементов И группы блока расчета характеристик, вторые входы которых подключены к выходам первого регистра блока расчета характеристик, выход второго элемента ИЛИ блока моделирования топологии соединен с первым входом элемента ИЛИ блока расчета характеристик и входом элемента задержки блока моделирования топологии, выход которого подключен к входу разрешения записи первого регистра блока расчета характеристик, выход которого соединен с 51 20первым входом сумматора блока расчета характеристик, выход которого,подключен к информационному входу блока памяти ранних окончаний событий в узлах блока расчета характеристик, выход которого соединен с информационными входами первого и второго регистров блока расчета характеристик, выход блока памяти номеров конечных узлов ветвей соединен с первым информационным входом коммутатора блока расчета характеристик, второй информационный вход которого соединен с выходом первого коммутатора блока моделирования топологии и адресным входом блока памяти номеров первых выходящих иэ узлов ветвей блока моделирования топологии, единиЧный выход второго триггера блока моделирования топологии соединен с управляющим входом коммутатора блока расчета характеристик, выход которого подключен к адресному входу блока памяти ранних окончаний событий в узлах блока расчета характеристик, выход четвертого элемента И блока моделирования топологии соединен с первым входом элемента И блока расчета характеристик, выход которого подключен к входу записи блока памяти ранних окончаний событий в уз-, ,лах блока расчета характеристик, вход считывания которого соединен с выходом элемента ИЛИ блока расчета характеристик, второй вход которого соединен с выходом второго элемента И блока моделирования топологии и с входом считывания блока памяти кодов весов длительности ветвей блока расчета характеристик, выход которого соединен с информационным входом третьего регистра блока расчета характеристик, выход которого соединен с вторым входом сумматора блска расчета характеристик, выход которого подключен к первому входу схемы сравнения блока расчета характеристик, выход третьего элемента И блока моделирования топологии соединен с входами разрешения записи второго и третьего регистров блока расчета характеристик, выход второго регистра блока расчета характеристик соединен с вторым входом схемы сравнения блока расчета характеристик, выход которой подключен к второму входу элемента И блока расчета характепистик, выход регистра номеров вы 2 12821 ходящих ветвей блока топопогии соединен с адресным входом блока памяти кодов длительности ветвей блока расчета характеристик, а выходы 2251элементов И группы блока рас чета характеристик являются информацибнными выходами устройст ва.1282151 62/49 Тираж 670ВНИИПИ Государственного комипо делам изобретений и от 113035, Москва, Ж, Раушская Подписно ака та СССР аб.,5 полиграфическое предприятие,изводствен Состав актор С. Пекарь Техред12821Изобретение относится к вычислительной технике, в частности к устройствам для обработки информации,специального назначения и может бытьиспользовано при построении специализированных вычислительных устройствдля моделирования сетевых задач операционного управления.Цель изобретения - повышение быстродействия устройства при определении характеристик сетей.На фиг. 1 показана структурнаясхема устройства; на фиг. 2 - схемаблока моделирования топологии, на15фиг. 3 - схема блока расчета характеристик.Устройство содержит операционныйблок 1, блок 2 моделирования топологии, блок 3 расчета характеристик,генератор 4 тактовых импульсов,Входом устройства является полюс5 сигнала "Пуск" блока 2 моделирования топологии. Первый, второй,третий и етвертьк выходные полюсы 256-9 генератора 4 тактовых импульсовсоединены с соответствующими входами операционного блока 1 и блока 2моделирования топологии. Управляющий выход операционного блока 1 соединен с входным полюсом 10 блока 2моделирования топологии, Соответствующие выходы блока 2 моделирования топологии соединены с входными полюсами 11-16 операционного блока 1. Выхоцыоперационного блока 1соединены с входными полюсами 17-19блока 2 моделирования топологии и сполюсом 20 блока 3 расчета характеристик. Соответствующие выходы блока 402 моделирования топологии соединеныс входными полюсами 21-29 блока 3расчета характеристик. Выход блока 3расчета характеристик соединен с выходным полюсом 30 устройства, являющимся его информационным выходом.В устройстве (фиг.1) операционныйблок 1 предназначен для организациипроцесса моделирования сети, Блок 2моделирования топологии предназначендля определения множеств выходящихиз узлов ветвей и их конечных узлов,а также для выработки соответствующих сигналов и кодов, необходимых дляфункционирования других блоков устройства. Блок 3 расчета характеристик предназначен для определения,хранения и выдачи расчетных характеристик моделируемой сети. Генератор 51 24 тактовых импульсов предназначен для синхронизации работ всех блоков устройства. Первый, второй, третий и четвертый выходы генератора 4 тактовых импульсов, соединенные с его выходными полюсами 6-9, предназначены для подачи на соответствующие входы блоков устройства сдвинутых относительно друг друга серий тактовых импульсов соответственно ГИ 1, ГИ 2, ГИ 3 и ГИ 4.Операционный блок 1 (фиг.1) со.держит блок 31 памяти номеров свершившихся событий в узлах, блок 32 памяти количеств входящих в узлы ветвей, вычитатель 33, три регистра 34-36, регистр 37 номера конечного узла сети, дешифратор 38 нулевого состояния, блок 39 сравнения кодов, два коммутатора 40,41, первый 42, второй 43 триггеры, восемь элементов И 44-51, третий триггер 52, элемент ИЛИ 53, элемент НЕ 54, четыре элемента 55-58 задержки.Блок 2 моделирования топологии (фиг.2) содержит блок 59 памяти номеров выходящих из узлов ветвей, блок 60 памяти номеров первых выходящих из узлов ветвей, блок 61 памяти номеров конечных узлов ветвей, регистр 62 номера начального узла сети, регистр 63 номеров выходящих ветвей, дешифратор 64 состояния, два коммутатора 65 и 66, два триггера 67 и 68, четыре элемента И 69-72, два элемента ИЛИ 73 и 74, элемент 75 задержки;В блоке 2 моделирования топологии блок 59 памяти номеров выходящих из узлов ветвей предназначен для хранения списков номеров ветвей, выходящих из узлов моделируемой сети. Блок 60 памяти номеров первых выходящих из узлов ветвей предназначен для хранения номеров первых ветвей списков выходящих из узлов ветвей. Блок 61 памяти номеров конечных узлов ветвей предназначен для хранения номеров конечных узлов всех ветвей моделируемой сети. Регистр 62 номера начального узла предназначен для хранения кода номера начального узла молекулируемой сети. Регистр 63 номеров выходящих ветвей предназначен для записи, хранения и выдачи кодов номеров ветвей, выходящих иэ узлов сети, ДешиФратор 64 состояния предназначен для дешифраций кода Х Коммутаторы 65 и 66 предназначеныдля разделения во времени двух потоков данных, поступающих к одному и тому же вхору.Блок 3 расчета характеристик (фиг.3), содержит блок 76 памяти ранних окончаний событий в узлах, блок 77 памяти кодов весов длительностей ветвей, сумматор 78, три регистра 79;81, схему 82 сравнения, коммутатор 83, группу элементов И 84, элемент И 85, 10 элемент ИЛИ ЯГ.В блоке 3 расчета характеристик блок 76 памяти ранних окончаний событий в узлах предназначен для записи, хранения и выдачи промежуточных и окончательных кодов величин ранних окончаний событий каждого узла сети, Блок 77 памяти кодов весов длительностей ветвей предназначендля хранения исходных данных о величинах длительностей всех ветвей сети. Схема 82 сравнения кодов предназначена для сравнения двух кодов и формирования сигнала на выходе при наличии на втором входе кода большего, чем на первом. Группа элементов И 84 предназначена для подачи на информационный выход устройства Я-разрядного кода резултата. Все остальные триггеры, элементы И, ИЛИ,30 НЕ, элементы задержек в устройстве предназначены для организации правильной работы схемы и предотвращения явлений "гонок".Устройство предназначено для опре деления величины длиннейшего пути и других характеристик сетей. К числу этих характеристик относятся величины ранних начал и ранних окончаний ветвей, ранних свершений узлов, сво-,40 бодных резервов всех ветвей сети.Раннее свершение любого узла соответствует величине длиннейшего пути до этого узла от начального узла сети. Таким образом, устройство определяет величины длиннейших путей от начального узла до каждого узла ис следуемой сети.Характеристики ветвей сети: раннее начало, раннее окончание и свободный резерв определяются исходя из ранних свершений их начальных и конечных узлов. Величина раннего начала ветвей совпадает с величиной раннего окончания их начального узла, величины ранних окончаний ветвей определяются как суммы их ранних начал и их длительностей, а свободные резервы -как разности между величинами ранних свершений их конечных узлов и ранних окончаний данных ветвей,Оптимальным и функционально полным набором исходных данных для получения любой из перечисленных характеристик сети является множество величин длиннейших путей от начального до каждого узла сети и множество величин длительностей ветвей сети, Поскольку вторая составляющая этого набора присутствует в качестве исходных данных так же, как и топологическая информация об исследуемой сети то задача состоит в том, чтобы получить множество величин длиннейших путей от начального до каждого узла сети.Устройство работает следующим образом.Предварительно в блоки памяти номеров первых ветвей, выходящих из начальных узлов 60, номеров ветвей, выходящих из начальных узлов 59, и номеров конечных узлов ветвей 61 блока 2 моделирования топологии заносится исходная информация о топологии сети. В блок 59 памяти информация заносится в виде списков ветвей, выходящих из узлов сети, т.е. по адресу предыдущей ветви списка выходящих из узла ветвей записыва,ется номер последующей, а по адресу последней записывается кодовый набор Х, Номера первых списков хранятся в блоке 60 памяти по адресам номеров узлов, которые являются начальными для ветвей данных списков. В блоке 61 памяти по адресам ветвей хранятся номера их конечных узлов. Такой набор топологической информации достаточен для работы устройства по определению заданного набора характеристик. В регистре 62 хранится номер начального узла сети. В блок 77 памяти блока 3 расчета характеристик по адресам ветвей заносятся коды их длительностей, а в блок 32 памяти операционного блока 1 по адресам узлов предварительно заносится код количества ветвей, входящих в данный узел. В регистр 37 операционного блока 1 заносится код номера конечного узла сети. Остальные все регистры и узлы памяти устройства предварительно очищаются, а триггеры обнуляются.После выполнения описанных предварительных установок и ввода перечисленной исходной информации устройство начинает работу по сигналу "Пуск", который поступает с входного полюса 5 5 устройства в блок 2 моделирования топологии. Сигнал "Пуск" через элемент ИЛИ 74 устанавливает в единичное состояние триггер 67 управления и через элемент ИЛИ 73 устанавливает в единичное состояние триггер 68 и поступает на вход считывания блока 60 памяти номеров первых выходящих из узлов ветвей, Так как триггер 42 операционного блока 1 находится в ну левом состоянии, то через полюс 10 на управляющий вход коммутатора 65 .поступает нулевой сигнал, который разрешает поступление через коммутатор 66 на адресный вход блока 60 па мяти номера начального узла сети с выхода регистра 62 начального узла.В результате по сйгналу "Пуск" на выход блока 60 памяти считывается номер первой ветви, выходящей из данного узла, который через коммутатор 66, управляемый единичным состоянием триггера 68, поступает на информационный вход регистра 63, Одновременно с выхода коммутатора код номера начального узла через полюс 23 поступает в блок 3 расчета характеристик и через коммутатор 83, управляемый единичным сигналом, поступающим через полюс 24 с триггера 68, поступает на адресный вход блока 76 памяти ранних окончаний событий в узлах, Сигнал "Пуск" с выхоца элемента ИЛИ 73 блока 2 моделирования топологии через полюс 26 и элемент ИЛИ40 86 поступает на вход считывания этого же блока 76 памяти. На выходе блока 76 памяти считывается нулевой код, соответствующий величине раннего свершения события начального узла сети, Код раннего свершения события узла поступает на информационный вход регистра 80, куда и записывается по сигналу "Пуск", задержанному элементом 75. задержки блока 2 моделирования топологии, и поступающему на вход разрешения записи регистра 80 блока расчета характеристик через полюс 21.Триггер 67 управления блока 2 моделирования топологии, установленный в единичное состояние сигналом "Пуск", разрешает формирование на выходах элементов И 69-72,импульсов управления,синхронных импульсам ГИ 1-ГИ 4 тактового генератора, поступающим на входы этик элементов соответственно через полюсы 6-9.По импульсу ГИ 1 с выхода элемента И 69 код номера первой выходящей из начального узла ветви записывается в регистр 63, с выхода которого поступает на адресный вход блока 61 памяти номеров конечных узлов ветвей, в котором по этому же импульсу считывается номер конечного узла первой ветви, выходящей из начального узла, Код номера ветви с выхода регистра 63 через полюс 29 поступает на адресный вход блока 77 памяти длительностей ветвей блока 3 расчета характеристик. Считанный в блоке 61 памяти коц номера конечного узла рассматриваемой ветви через полюс 16 поступает в операционный блок 1 на адресный вход блока 32 памяти количества входящих в узлы ветвей и через полюс 22 поступает.на второй вход коммутатора 83 блока 3 расчета характеристик,По импульсу ГИ 2 с выхода элемента И 70 в блоке 59 памяти номеров выходящих из узлов ветвей считывается по адресу номера первой ветви, код номера которой с выхода регистра 63 поступает на адресный вход блока 59 памяти, код номера следующей выходящей из данного (начального) узла1ветви, По этому же сигналу триггер 68 устанавливается в нулевое состояние. Считанный в блоке 59 памяти код номера следующей ветви поступает на второй вход коммутатора 66, управляемого теперь нулевым сигналом триггера 68, и с выхода его поступает на информационный вход регистра 63. Нулевой сигнал с выхода триггера 68 через полюс.24 разрешает поступление кода номера конечного узла первой выходящей ветви, код которой пока еще находится в регистре 63, через коммутатор 83 на адресный вход блока 76 памяти ранних окончаний событий в узлах блока 3 расчета карактеристик. Управляемый импульс с выхода элемента И 70 блока 2 моделирования топологии через полюс 27 и элемент ИЛИ 86 поступает на вход считывания блока 76 памяти блока 3 расчета характеристик, По номеру конечного узла ветви считыва"7 12ется величина раннего свершения этого узла.Код считанной величины поступает на информационный вход регистра 79. Одновременно по тому же сигналу с полюса 27 в блоке 77 памяти кодов весов длительностей ветвей считывается код длительности рассматриваемой в регистре 63 ветви. Считанный код длительности ветви поступает на информационный вход регистра 81 блока 3 расчета характеристик. Одновременно импульс с элемента И 70 через полюс 15 поступает на вход считывания блока 32 памяти количества входящих в узлы ветвей операционного блока 1, где считывает записанный код, который поступает на первый вход вычитателя 33, на второй вход которого постоянно поступает код единицы.Вычитатель 33 уменьшает на единицу записанную в блоке 32 памяти величину количества входящих в узел ветвей. Код полученной разности поступает на информационный вход регистра 34, куда и записывается по этому же управляющему импульсу, который задерживается на соответствующее время элементом 55 задержки и поступает с его выхода на вход разрешения записи регистра 34. С выхода регистра 34 новый код количества входящих в узел ветвей поступает на информационный вход блока 32 памяти количеств входящих в узлы ветвей, а также на вход дешифратора 38, где сравнивается с кодом нуля. Если полученный в регистре 34 код равен нулю,то это означает, что все входящие в узел ветви рассмотрены и узел свершился.огда на выходе дешифратора 38 ноя- . вится единичный сигнал, который разрешит формирование управляющих импульсов на выходах элементов И 44 и 45. Если же код в регистре 34 не равен нулю, то на выходе дешифратора будет присутствовать нулевой сигнал.По тактовому импульсу ГИЗ с выхода элемента И 71 через полюс 28 выполнится запись имеющегося кода раннего свершения конечного узла рассматриваемой ветви в регистр 79 и кода длительности этой ветви в регистр 81 блока 3 расчета характеристик. Выход регистра 80, в котором к этому моменту хранится код раннего свершения начального узла рассматриваемой ветви, и выход регистра 81 соединены с 82151 8входами сумматора 78, на выходе которого в результате будет получен кодвеличины .раннего окончания даннойветви, который может быть равен повеличине коДу раннего свершения конечного узла данной ветви, если онмаксимальный среди всех входящих вданный узел ветвей. Для проверки этого полученный код с выхода сумматора 10 78 поступает на один из входов схемы82 сравнения, на другой вход которойпоступает код с выхода регистра 79,в котором записан код раннего свершения данного узла, равный максимальному-.из кодов ранних окончаний рассмотренных ранее входящих в этот узелветвей либо равный нулю, если такиеветви еще не рассматривались.Если код, полученный на выходесумматора 78, больше имеющегося в регистре 79, то на выходе схемы 82 сравнения появится единичный сигнал, который, поступив на вход элемента И 85,разрешит запись нового кода, которыйс выхода сумматора 78 поступает наинформационный вход узла 76 памяти,на следующем такте ГИ 4 по управляющему сигналу, который поступит , сэлемента И 72 через полюс 25, Такимобразом, в блоке 76 памяти по адресуномера узла будет записана максимальная величина раннего окончания из.рассмотренных входящих в данный узелветвей. Когда будут рассмотрены все 35 входящие в узел ветви, записаннаяпо номеру данного узла величина автоматически станет величиной раннегосвершения этого узла. Если же код,полученный на выходе сумматора 78,не превышает код, имеющийся в регистре 79, то на выходе схемы 82 сравнения будет нулевой сигнал, которыйне разрешит запись нового значения,и в блоке 76 памяти по номеру узласохранится прежнее значение, попрежнему большее из всех рассмотренных ранее.Как уже рассматривалось, по тактовому сигналу ГИ 2 в регистр 34 операционного блока 1 заносится уменьшенный на единицу код количества ветвей, входящих в конечный узел анализируемой ветви. Полученный код с выхода регистра 34 поступает на инфор-мационный вход блока 32 памяти количеств входящих в узлы ветвей, кудаи записывается по адресу номера конечного узла анализируемой ветви,который поступает через полюс 16 с выхода блока 6 1 памяти конечных узлов ветвей блока 2 моделирования топологии. Сигнал записи формируется на выходе элемента И 71 блока 2 моде лирования топологии синхронно тактовому импульсу ГИЗ и через полюс 13 поступает на вход записи блока 32 памяти количеств входящих в узлы ветвей операционного блока 1. 10Если код, сформированный в регистре 34, больше нуля, то это означает, что не все ветви, входящие в данный узел, проанализированы и тогда по тактовому импульсу ГИ 4 операционный блок 1 никаких действий не выполняет, так как нулевой сигнал на выходе дешифратора 38 нулевого состояния блокирует формирование управляющих сигналов на выходе эле мента И 45. В этом случае по тактовому импульсу выполняются лишь описанные операции н блоке 3 расчета характеристик.Если полученный в регистре 34 код равен нулю, то это означает, что все ветви, входящие в данный узел, проанализированы, т.е. величины их длительностей учтены в блоке расчета характеристик и, следовательно, их 30 конечный узел свершился. Свершение узла предполагает переход к анализу выходящих из начального (либо любого другого) узла ветвей, поэтому номер свершившегося узла необходимо запом нить. Так как в процессе текущего анализа выходящих ветвей может свершиться некоторое множество узлов, то необходимо организовать определенный порядок хранения номеров таких узлов. 40Номера свершившихся узлов записываются в виде списков в блок 31 памяти номеров свершившихся событий в узлах. Этот процесс организуется следующим образом, Нулевой код в регист ре 34 преобразуется дешифратором 38 нулевого состояния в единичный сигнал на его выходе, который поступил на входы элементов .И 44 и 45, разрешает 1формирование на их выходах управляющих сигналов. По управляющему сигналу с полюса 13 от блока 2 моделирования топологии на выходе элемента И 44 формируется сигнал, который поступает на вход записи блока 31 памя ти номеров свершившихся ветвей. На адресный вход этого блока памяти с полюса 16 от блока 2 моделирования. 1282151 10топологии через коммутатор 40 операционного блока 1 поступает код номера конечного узла анализируемой вет-.ви. Управление коммутатором 40 вданном случае осуществляет единичныйсигнал, поступающий с единичного входа триггера 67 блока 2 моделированиятопологии через полюс 14, На информационный вход блока памяти поступаетсодержимое регистра 35 и на входстаршего (и+1)-го разряда входа -сигнал с инверсионного выхода тригге.ра 52. В исходном состоянии триггер52 находится в нулевом состоянии, арегистр 35 очищен. При появлении сигйала с дешифратора 38 о свершениипервого узласети по сигналу с элемен та И 44 в блок 31 памяти по номерусвершившегося узла записывается содержимое регистра 35 и единица встарший (и+1)-й разряд, которая является меткой конца списка.По управляющему сигналу, синхронному ГИ 4, поступающему с блока 2моделирования топологии, через полюс12 на выход элемента И 45 операционного блока поступает сигнал, по которому на выходе элемента И 45 формируется также управляющий сигнал.Управляющий сигнал с элемента И 45поступает на вход разрешения записирегистра 35, на информационный входкоторого поступает код номера свершившегося узла. Этот код записывается в регистр 35, а триггер 52 темже управляющим сигналом устанавливается в единичное состояние. В результате к концу тактового сигнала ГИ 4 врегистре 35 запоминается номер первого свершившегося узла, а в блоке 31памяти по адресу номера этого узла в(и+1)-м старшем разряде записываетсяметка конца списка. При свершениив процессе продолжающегося анализавыходящих ветвей следующего узла се,ти номер этого узла через полюс 16поступает на вход коммутатора 40, который по-прежнему управляется единичным сигналом с полюса 14, и черезкоммутатор 40 - на адресный вход блока 31 памяти.По управляющему сигналу, синхронному ГИЗ, с элемента И 44 операционного блока в блок памяти по адресу.номера нового свершившегося узла записывается номер предыдущего свершившегося в процессе данного анализавыходящих ветвей узла, хранящегося11 1282 в регистре 35. В старшем (и+1)-м раэ. ряде этого же информационного слова метка отсутствует, так как триггер 52 находится уже в единичном состоянии и на вход (и+1)-го разряда поступает нулевой сигнал. По тактовому сигналу ГИ 4 на выходе элемента И 45 формируется управляющий сигнал, по которому выполняется запись кода номера вновь свершившегося узла в ре гистр 35 и подтверждается единичное состояние триггера 52. В результате к окончанию тактового сигнала ГИ 4 в регистре 35 хранится код номера последнего свершившегося узла сети, 15 а в блоке. 31 памяти по адресу номера последующего свершившегося узла сети хранится код номера предыдущего свершившегося узла. По адресу номера первого свершившегося узла . 20 записывается метка в (и+1)-м разряде. При получении сигнала с дешифратора 38 о свершении очередного узла описанные операции повторяются.Анализ ветвей, выходящих из начального узла сети, оканчивается по сигналу, поступаюшему через полюс 11 из блока 2 моделирования топологии, Этот сигнал вырабатывается дешифратором 64, который определяет 30 очередной код в регистре 63 выходящих ветвей как код Х который является признаком окончания списка ветвей, выходящих из начального узла. Сигнал с выхода дешифратора 64 уста навливает триггер 67 в нулевое состо. яние и прекращает работу блока 2 моделирования топологии по анализу выходящих из узла ветвей. На этом заканчивается этап анализа ветвей, 40 выходящих из начального узла сети. После этого устройство переходит к анализу ветвей, выходящих из улов, свершившихся в процессе предыдущего этапа. Так как все множество свер шившихся узлов записано в виде списка в блоке 31 памяти номеров свершившихся узлов операционного блока 1, то необходимо провести анализ ветвей, выходящих из каждого узла этого списка, и лишь после этого перейти к анализу ветвей, выходящих из вновь свершившихся узлов, которые также будут записаны в блоке 31 памяти опера/ ционного блока в виде нового списка. 55По сигналу с полюса 11 от блока 2 моделирования топологии триггер 42 операционного блока 1 устанавливается в единичное состояние. Триггер 43 151 12метки обработки в исходном состоянии находится в нулевом состоянии и, следовательно, лишь на выходе элемента И 49 по тактовому сигналу ГИЗ будет сформирован управляющий сигнал, который установит в нулевое состояние триггер 52 метки и через элемент ИЛИ 53 поступит на вход разрешения записи регистра 36. На информационный вход этого регистра через коммутатор 41, управляемый в данный момент нулевым сигналом триггера 43 метки обработки, поступит содержимое регистра 35, в котором в данный момент времени находится код номера узла, который является начальным в списке свершившихся узлов, хра нящихся в блоке 31 памяти. По тактовому сигналу ГИЗ код номера этого узла будет записан в регистр 36, Затем задержанный на определенное время этот же управляющий сигнал, пройд через элемент 58 задержки, установи в единичное состояние триггер 43 мет ки обработки. Тогда (уже по тактовом сигналу ГИ 4) на выходе элемента И 48 будет сформирован управляющий сигнал, который через полюс 18 поступит,в блок 2 моделирования топологии и выполнит почти все функции, выполняемые сигналом "Пуск".Исключения будут в следующем. Номер узла в блок 2 моделирования топологии поступает с выхода регистра 36 операционного блока 1 через полюс 17, С полюса 17 код номера узла поступает на второй вход коммутатора 65, который управляется в данный момент единичным сигналом с полюса 10, куда он поступает с единичного выхода триггера 42 операционного блока. Следовательно, на выходе коммутатора 65 присутствует не содержимое регистра 62 номера начального узла сети, а код номера свершившегося узла, записанный в регистре 36 операционного блока 1.Триггер 67 блока 2 моделирования топологии устанавливается в единичное состояние сигналом с полюса 19, куда он приходит с выхода элемента И 51 операционного блока. Так на входы элемента И 51 приходят задержанный элементом 57 задержки управляющий сигнал по ГИ 4 с элемента И 48 и инверсный сигнал с блока 39 сравнения кодов, который вырабатывает сигнал в случае совпадения кода свершившегося узла в регистре 36128и кода конечного узла сети в регистре 37, то на выходе элемента И 51 и полюсе 19 сигнал появится несколько позже, чем на полюсе 18, и только в том случае, если узел, анализ выходящих ветвей которого предстоит сделать, не является конечным узлом сети.Одновременно сигнал с выхода элемента 57 задержки сбрасывает триггер 42 в нулевое состояние и прекращает работу операционного блока 1, Дапее повторяются описанные операции этапа анализа выходящих из узла ветвей. Никаких отличий, кроме отмеченных, от приведенного описания нет. Лишь по окончании этапа в связи с. тем, что триггер 43 метки обработки нахо" дился все это время в единичном состоянии, на выходе элемента И 46 по тактовому сигналу ГИ 2 будет сформирован управляющий сиг ал, который поступит на вход считывания блока 31 памяти, на адресный вход которого через коммутатор 40, управляемый в данный момент нулевым сигналом с полюса 14 (так как триггер 67 блока 2 моделирования топологии по окончании этапа. анализа списка ветвей, выходящих из узла, сбрасывается в нуль), поступит код номера узла, хранящийся в регистре 36. По этому адресу иэ блока 31 памяти будет считан код следующего в анализируемом списке свершившегося узла.Считанный код с вьхода блока 31 памяти через коммутатор 41, управляемый в данный момент единичным сигналом с триггера 43, поступает на информационный вход регистра 36 и записывается туда по тактовому сигналу ГИЗ с выхода элемента И 47. В случае, если считанный код является номером свершившегося узла анализируемого списка, то на выходе старшего (и+1)- го разряда снова будет присутствовать нулевой сигнал метки, который запретит формирование сигнала на выходе элемента И 50, Если же в (п+1)-м разряде будет единица, то этоозначает окончание обработки данного списка свершившихся узлов и на выходе элемента И 50 появится сигнал, который через элемент 56 задержки сбросит в нулевое состояние триггер 43 метки обработки. Тогда по тактовому сигналу ГИ 4, сформированному на выходе элемента И 48, сигнал не 2151 14будет сформирован, и лишь через тактвновь по тактовому сигналу ГИ 3 появится сигнал на выходе элемента И 49,который начнет описанный этап анали 5 за свершившихся узлов нового списка,начальный код которого будет находиться в регистре 35,1Такая последовательность по анализу списков свершившихся узлов и выходящих из них ветвей будет выполняться до тех пор, пока не будетсформирован и проанализирован последний список, состоящий из конечного15узла сети. То, что в списке будетлишь один элемент - очевидно, таккак поспедующие списки формируютсяна основе предыдущих, а для свершения конечного узла сети необходимосвершение всех ее узлов, так как устройство моделирует связные ориентированные сети с одним начальным иодним конечным узлами.При анализе этого последнего списка конечный узел сети будет занесен в регистр 36 и тогда на выходеблока 39 сравнения кодов появитсяединичный сигнал, являющийся результатом совпадения кодов в регистрах36 и 37, который через элемент НЕ54 и элемент И 51 запретит подачууправляющего сигнала через полюс 19и блок 2 моделирования топологии.В результате он не будет включен вработу по анализу выходящих из этогоузла ветвей (так как их нет) и в блок3 расчета характеристик с выходаблока 39 через полюс 20 поступит сигналразрешения выдачи кода величины длин 40нейшего пути в сети, который разрешит через группу элементов И 84 выдачу на выходной полюс устройства содержимого регистра 80, куда по сигналу. с полюса 21 будет считан код45раннего свершения данного узла, чтосоответствует по определению величине длиннейшего пути.К этому моменту времени в блоке31 памяти будет сформирована информация о величинах ранних свершенийсобытий всех узлов сети, т.е. кодывеличин длиннейших путей до каждого узла (от начального). В совокупности с исходной информацией овеличинах деятельностей ветвей в55 блоке 77 памяти это составит функционально полный набор исходных данных для быстрого определения любогоперечисленного набора рассчитывае 12821511615мых характеристик, а также их любой композиции. Использование новых блоков (операционного и расчета характеристик) позволяет в отличие от известных устройств существенно сокра тить время расчета и отказаться от использования блока моделей ветвей.При моделировании сети отсутствует процесс временного моделирования длительностей ветвей, а при оценке свер О шения узлов используется блок 32 памяти количества входящих в узлы ветвей. Это приводит к тому, что процесс анализа свершения узла суще 15 ственно сокращается, так как нет необходимости после свершения каждой входящей в узел ветви перебирать весь список входящих ветвей, проверяя свершения каждой. Достаточно проверитьго количество несвершившихся ветвей,которое в виде кода постоянно формиру" ется и корректируется в блоке 32 памяти.25формула изобретенияУстройство для определения характеристик сетей, содержащее генератор тактовых импульсов, блок моделирования топологии, включающий блок памяти номеров выходящих иэ узлов ветвей, блок памяти номеров конечных узлов ветвей, блок памяти номеров первых выходящих из узлов ветвей, регистр номеров выходящих ветвей, дешифратор состояния, два триггера, четыре элемента И и два элемента ИЛИ, причем вход пуска устройства соединен с первыми входами первого и второго элементов ИЛИ, выходы которых соединены соответственно с единичными входами первого и второго триггеров, единичный вход первого триггера под ключен к первым входам первого и второго элементов И, вторые входы которых соединены с первым и вторым выходами генератора тактовых импульсов, выход первого элемента И соединен с входом считывания блока памяти номеров конечных узлов ветвейи с входом разрешения записи регистра номеров выходящих ветвей, выход второго элемента ИЛИ соединен с входом считывания блока памяти номеров первых выходящих из узлов ветвей, выход второго элемента И соединен с входом считывания блока памяти номе-ров выходящих из узлов ветвей и снулевым входом второго триггера, выход регистра номеров выходящих ветвей соединен с адресными входами блока памяти номеров выходящих из узловветвей и номеров конечных узлов ветвей и входом дешифратора состояния,выход которого соединен с нулевымвходом первого триггера, о т л и ч аю щ е е с я тем, что, с целью повьппения быстродействия, в блок моделирования топологии введены два коммутатора, регистр номера начальногоузла сети и элемент задержки, операционный блок, содержащий блок памятиномеров свершившихся событий в узлах,блок памяти количеств .входящих вузлы ветвей, вычитатель, три регистра, регистр номера конечного уз-,ла сети, дешифратор нулевого состо-.яния, блок сравнения кодов, два коммутатора, три триггера, восемь элементов И, элемент ИЛИ, элемент НЕ,четыре элемента задержки и блок расчета характеристик, содержащий блокпамяти ранних окончаний событий вузлах, блок памяти кодов весов длительности ветвей, сумматор, три. регистра, схему сравнения, коммутатор,группу элементов И, элемент И и элемент ИЛИ, причем вход регистра номе- рра начального узла сети блока моделирования топологии является первыминформационным входом устройства, выход регистра номера начального узласети блока моделирования топологиисоединен с первым информационным входом первого коммутатора блока моделирования топологии, управляющий входкоторого подключен к единичному выходу первого триггера операционногоблока, единичный выход второго триггера блока моделирования топологиисоединен с управляющим вхсдом второго коммутатора блока моделированиятопологии, выход которого подключенк информационному входу регистра номеров выходящих ветвей, первый и второй информационные входы второго коммутатора блока моделирования топологии соединены соответственно с выходами блоков памяти номеров первыхвыходящих из узлов ветвей и номероввыходящих иэ узлов ветвей блока моделирования топологии, первые входытретьего и четвертого элементов Иблока моделирования топологии соединены с единичным выходом первого