Устройство для моделирования задач о длиннейшем пути в сетях

,02.88.ститутетике АНА. КотлЩетинин1.333(0торское51, кл,(61) 11 (21) 41 (22) 03 (46) 15 (71) Ин пись информ ительности вет 24 Бюл, У роблем УССР ренко,елировани в энер (72) А и А.М. (53) 6 (56) Ав В 1161 В.П. Приймачу 8.8)свидетС 06 Р ьство ССС 5/20, 198 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ 54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВА АДАЧ О ДЛИННЕИПЕМ ПУТИ В СЕТЯ(57) Изобретение относится к области вычислительной техники, может быть использовано для определения длиннейшего пути в сети и позволяет определять максимальный разрез в сети с учетом временных характеристик ветвей сети. Для определения длиннейшего пути в заданной сети строится ее модель. Так как в известном уст. ройстве использовано динамическое закрепление моделей ветвей за ветвями сети, то в начальный момент для ветвей, выходящих из начального узла сети, ставятся в соответствие свободные модели ветвей, С этой целью по-. следовательно вводят информацию о длительности каждой ветви, выходящей из начального узла, в свободные модели ветвей. При этом в узле памяти номеров моделируемых ветвей запоминается соответствие номера ветви сети и используемой модели ветви, Если модель ветви занята, то осуществляется обращение к следующей свободной модели ветви. Так осуществляется завей, выходящих из начального узла,которые вместе образуют первый фронтсети. При этом под фронтом понимаетсямножество ветвей, обрабатываемыходновременно в каждый момент времени.После занесения информации о длительности для всех ветвей, принадлежащихпервому фронту, осуществляется временное моделирование сетиВ этомслучае подается сигнал Пуск в начальный узел сети (в подготовленныемодели ветвей), который, распространяясь по сети, задерживается в каждой модели на величину, пропорциональную времени выполнения моделируемой ветви. Временное моделированиекаждой моделью ветви выполняется путем заполнения заданного временногоинтервала импульсами генератора, Когда будет сформирован временной интервал хотя бы одной моделью ветви, сигнал об окончании этого интервала осуществит прерывание временного моделирования и позволит перейти к моделированию топологии исследуемой сети,При этом модель ветви, закончив моделирование заданной длительности, обнуляется и становится свободной. Однако в работе этого устройства возможен случай, когда все модели ветвейблока моделей ветвей включены в процесс временного моделирования и на момоделирование следующих ветвей по то"пологии сети свободных моделей ветвейне хватает. Зто свидетельствует отом, что в сети имеется такой разрез,число ветвей которого превышает количество моделей ветвей в блоке моде-"лей ветвей устройства. 3 ил.17 1374239 лирование длительностей ветвей и ана-,1 лиз ветвей, закончивших процесс временного моделирования, чередуются в указанном порядке и повторяются до тех нор, пока не будет сформирован заданный конечный узел сети и выдана информация о величине длиннейшего пути из узла блока 12 измерения длиннейшего пути и величине количества ветвей в максимальном разрезе сети из регистра 13В случае, если при подготовке какой-либо ветви к процессу временного моделирования не обнаружится , свободная модель ветви, процесс моделирования сети останавливается. При этом на выходном полюсе 10 б блока 3 моделей ветвей, который соединен с выходом элемента 94(М) последней мо О дели ветви 89(М), формируется сигнал высокого уровня, сигнализирующий об .отсутствии свободных моделей ветвей. Ф о р м у л а и 3 обретенияУстройство для моделирования задач о длиннейшем пути в сетяхпо авт.св. В 1161951, о т л и ч а ю - щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения максимального разреза сети с учетом временных характеристик ветвей, блок управления дополнительно содержит четвертый и пятый узлы памяти, счетчик реверсивный счетчик, регистр, схему сравнения, второй триггер, с третьего по пятый элементы И, узел элементов И, четвертый элемент задержки, второй элемент ИЛИ, два узла элементов ИЛИ и элемент НЕ, причем вход признака чтения узлапамяти длительности ветвей подключен к первому входу второго элемента ИЛИ и суммирующему входу реверсивного счетчика, выход которого подключен к пер 45 вому информационному входу схемысравненчя и информационному входу регистра, выход которого подключен к первому входу узла элементов И и второму информационному входу схемы сравнения, выход признака больше ко торой подключен к первому входу тре" тьего элемента И, выход которого подключен к входу признака записи , регистра и входу установки в "1" второго триггера, прямой выход кото рого подключен к первому входу четвер.ого элемента И и первому входу пятого элемента И, выход которого подключен к суммирующему входу счетчика, выход признака переполнения которого подключен к входу установки11в, О триггера, инверсный выход ко"4 торого подключен к третьему входупервого элемента И, первый тактовый вход блока управления подключен к второму входу пятого элемента И, вход прерывания блока управления подключен к вычитающему входу реверсивного счетчика, входу элемента НЕ и входу первого элемента задержки, выход которого подключен к второму входу второго элемента ИЛИ,. выход которого подключен к входу признака записи четвертого узла памяти, вход. Установки в "1" триггера прерывания подключен к второму входу третьего элемента И, выход элемента НЕ подключен к третьему входу третьего элемента И и информационному входу четвертого узла памяти, второй вход первого элемента И подключен к второму входу четвертого элемента И, выход которо". го подключен к входу признака чтения четвертого узла памяти и входу чет-вертого элемента задержки, выход которого подключен к входу признака записи пятого узла памяти, информационный выход узла памяти номеров моделируемых ветвей подключен к первому входу первого узла элементов ИЛИ, адресный. вход узла памяти длительности ветвей поцключен к второму входу первого узла элементов ИЛИ, выход которого подключен к адресному входу четвертого узла памяти, выход которого подключен к информационному вхо ду пятого узла памяти, вход опроса блока управления подключен к входу признака чтения пятого узла памяти 1 информационный выход которого является выходом признака принадлежности ветви к максимальному разрезу сети, информационный выход счетчика подключен к первому входу второго узла элементов ИЛИ, вход блока управления для задания кода номера опрашиваемой ветви подключен к. второму входу второго узл 3 элементов ИЛИ, выход которого подключен к третьему входу первого узла элементов ИЛИ и адресному входу пятого узла памяти, второй вход второго элемента И подключен к второму входу узла элементов И, выход которого является выходам блока управленияиндикации количества ветвей в максимальном разрезе сети,1374239 эш а МФЬ меы ив юав ююйЬГ Составитель А. МищиТехред Л. Сердюкова ктор Б. Гирняк Копч акт 70 з б 04/46 13035,оизводственно-полиграфическое предприятие, г. Ужгород, ул, Проектная,ТирГосударсделам изосква, Жвенного ретенийРаущс Подпкомитета СССРи открытийая наб д, 4/51 13742Изобретение относится к вычислительной технике, может быть использовано для решения задач на графах и . является дополнительным к авт.св., Р 1161951.Целью изобретения является расширение Функциональных возможностей устройства за счет определения максимального разреза сети с учетом временных характеристик ветвей.На Фиг.1 представлена Функциональная система устройства: на фиг.2 - Функциональная схема варианта.выполнения блока формирования топологии сети: на фиг.3 - Функциональная схема варианта выполнения блока моделей ветвей.Устройство состоит из блока 1 управления, блока 2 Формирования топо К логии, блока 3 моделей ветвей и генератора 4 импульсов.Блок 1 управления содержит. узел 5 памяти длительностей ветвей, блок 6 памяти номеров моделируемых ветвей,25 узел 7 памяти меток свершения ветвей, узел 8 памяти меток моделируемых ветвей, узел 9 памяти ветвеч максимального разреза сети, реверсивный счетчик 10 количества моделируемых ветвей 30 счетчика 11 адреса меток ветвей мак" симального разреза сети, узел 12 измерения длиннейшего пути, регистр 13 количества ве".вей в максимальном разрезе сети, триггер 14 форьаюрова- ния меток ветвей максимального разреза сети узла, триггер 15 прерывания, узел 16 элементов И, элементы И 17- 21, ИЛИ 22, узлы 23 и 24 элементов тов ИЛИ, элемент ИЛИ 25, элементы 26-29,задержки, элемент НЕ 30, схему 31 сравнения кодов.Выход 32 номера подготавливаемой к моделированию ветви блока 2 Формирования топологии соединен с адресным входом блока 5 памяти, с информационным входом узла 6 памяти и через элемент ИЛИ 23 с адресным входом ,узла 8 памяти Выход 33 поиска свободной модели ветви блока 2 форми 5 О рования топологии соединен с входом признака чтения узла 5 памяти; через элемент 27 задержки с входом признака записи узла 6 памяти, через элемент ИЛИ 22 с входом признака записи55 узда 8 памяти, с суммирующим входом счетчика 10 и с входом 34 поиска номера анализируемой ветви, через элемент ИЛИ 25 соединен с адресным вхо 19 2дом узла 7 памяти, Выход 36 проверкисовершения ветви соединен с входом признака чтения узла 7 памяти. Выход 37 поиска прерывания блока формирования топологии соединен с входом установки в "1" триггера 15 прерыва- ния, с входом элемента И 18 и с входом 38 поиска прерывания блока 3 моделей ветвей. Выход 39 индикации расчета блока 2 Формирования топологии соединен с входами элементов И 16 и 21.Выход 40 номера модели ветви блока 3 соединен с адресным входом блока б памяти. Выход 41 прерывания. блока 3 моделей ветвей соединен. с входом признака чтения узла б памяти, с входом установки в "0".триггера 15.прерывания, .с входом элемента 28 задержки, с входом элемента НЕ 30,. с вычитающим входом счетчика 10Выход номера свершившейся ветви узла 6 памяти блока 1 управления соединен с входом 42 блока 2 формирования топологии. Выход. метки свершения ветви узла 7 памяти соединен с входом 43 блока 2 формирования топологии, Выход начала анализа свершения ветви элемента 29 задержки блока 1 управления соединен с входом 44 блока 2 Формирования топологии. Выход кода длительности ветви узла 5 памяти блока. 1 управления соединен с входом 45 блока 3 моделей ветвей. Выход измерительной серии. элемента И 20 блока 1 управления соединен с входом 46 блока 3 моделей ветвей.Входной полюс 47, блока 2 Формирования топологии предназначен для приема импульсов серии ГИ 1, поступающих с. генератора 4 импульсов. Вход" ной полюс 48 блокаФормирования топологии предназначен для приема импульсоз серии ГИ 2, поступающих с генератора 4 импульсов. Входной полюс 49 блока 1 управления предназначен для приема импульсов серии ГИ 1, поступающих с генератора 4 импульсов. Входной полюс 50 блока 1 управления предназначен для приема импульсов серии ГИ 2, поступающих с генератора 4 импульсов, Входными полюсами устройства являются полюса 51 и 52 блока 2 формирования топологии и полюса 53 и 54 блока 1 управления. Выходными полюсами устройства являются полюс 55 блока 1 управления, соединен-ный с выходом элемента И 16, полюс56 блока 1 управления, соединенныйс выходом узла 9 памяти, полюс 57блока 1 управления, соединенный с вы"ходом элемента И 21.Блок 2 формирования топологии содержит блок 58 памяти номеров начальных узлов ветвей сети блок 59 памяти номеров конечных узлов ветвей сети, узел 60 памяти номеров выходящихветвей узлов сети, узел 60 памяти номеров входящих ветвей узлов сети 61,узел 62 памяти номеров первой выходящей ветви узлов 62 сети, узел 63памяти номеров первой входящей ветви 15узлов сети, регистр 64 номера входящей ветви, регистр 65 номера входящей ветви, регистр 66 номера конечного узла ветви, регистр 67 номераконечного узла сети, триггеры 68 и69, дешифраторы 70 и 71, схему 72сравнения кодов, элементы 73 и 74 задержки, элементы ИЛИ 75-81, элементыИ .82-87; элемент НЕ 88,Блок 3 моделей ветвей содержит М 25моделей 89(1)-89(М), и узел 90 поиска. моделей ветвей (здесь и далее цифрамив скобках обозначены порядковые но, мера одинаковых по своему конструк".тивному исполнению и функцнональномуназначению блоков, узлов, элементови полюсов) .Каждая модель 89 ветви состоитиз Формирователя 91 временных интервалов, триггеров 92 и 93,. элементовИ 94-99, элемента ИЛИ 100.и элемен 35тов 101 и 102 задержки,Узел 90 поиска моделей ветвей содержит шифратор 103.адреса и элементы ИЛИ 104 и 105.Устройство работает следующим образомВ узлы 58-63 памяти блока 2 формирования топологии в виде списков заносится информация О тополОгии моде 45лируемой сети. Регистры 64-66 ,предварительно обнуляются, а в регистр 67заносится код номера конечного узласети, Триггеры 14 и 15 блока 1 управ.ления триггеры 68 и 69 блока 2 ФормиЭ50рования топологии и триггеры 92(1)92(М) и 93(1)-.93(М) блока 3 моделейветвей устанавливаются в нулевое состояние. В блох 5 памяти длительностей ветвей по адресу каждой ветвисети записывается код ее длительности, а узлы 6-9 памяти, счетчик 10количества моделируемых ветвей,счетчик 11 адреса меток ветвей максимальнага разреза сети и узел 12 измерения длиннейшего пути предварительно обнуляются.После начального установа на полюс 52 блока 2 формирования топологии подается код номера ветви, выходящей из узла, принятого при данном решении за начальный. В некоторый момент времени сигнал пуска, поступающий на полюс 51, проходит через элемент ИЛИ 81 и устанавливает триггер 69 в единичное состояние. Единичное состояние триггера 69. разрешает прохождение серии импульсов ГИ 1 и ГИ 2 через элементы И 86 и 87. Кроме этого, сигнал пуска с полюса 51 поступает на вход элемента 73 задержки и на вход признака чтения блока 58.памяти начальных узлов. При поступлении признака чтения в блоке 58 памяти про- . исходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 52. Так как ветвь выбрана как выходящая из начального узла сети,. то на выходе узла 58 памяти появляется код начального узла сети, который через элемент ИЛИ 76 поступает на адресный вход узла 62 памяти первой выходящей ветви. Через время задержки, достаточное для считывания информации иэ узла 58 памяти, сигнал пуска появляется на выходе элемента 73 задержки и поступает через элемент ИЛИ 75 на вход узла 62 признака чтения памяти, По этому сигналу из узла 62 памяти, по адресу начального узла считывается код номера ветви, являющейся первой в списке ветвей, выходящих иэ начального узла сети, Код первой, выходящей ветви с выхода узла 62 памяти через элемент ИЛИ 77 поступает на информационный вход регистра 64 выходящей ветви к записывается в него по первому импульсу ГИ 1, поступающему на управляющий вход регистра с.выхода элемента И 86.Записанный код первой выходящей ветви с выхода регистра 64 блока 2 формирования топологии поступает на адресный вход узла 60 памяти и через выходной полюс 32 - на адресный вход узла 5 памяти длительностей, информационный вход узла 6 памяти номеров моделируемых ветвей и через узел 23 элемента ИЛИ - на адресный вход узла 8 памяти меток моделируемых ветвей.Затем импульс ГИ 2, сдвинутый относительно импульса ГИ 1, поступает наВКОд признака чтения узла 60 памяти и по адресу первой выходящей из начального узла ветви считывается код второй ветви, выходящей из того же узла.Одновременно сигнал поиска свободной модели ветви с выхода элемента И 87 через выходной полюс 33 поступает на вход признака. чтения узла 5 памяти длительностей, на элемент 27 задержки, через элемент ЮИ 22 на вход признака записи узла 8 памятиметок моделируемых ветвей и на суммирующий вход счетчика 10 количествамоделируемых ветвей, а также на вход34 поиска свободной модели ветви блока 3 моделей ветвей, По этому сигналуи адресу номера первой выходящей изузла ветви поступающему с полюса 32, 20осуществляется чтение кода длитель,ности этой ветви из узла 6 памяти длительности, запись метки моделируемой ветви в узел 8 памяти и увеличение на 1 кода счетчика 10 количества моделируемых ветвей. Одновременно. сигнал поиска .свободной модели ветви с полюса 34 поступает на входы элементов И 96(1) и 97(1) первой модели 89(1) ветви. Так как в рассматриваемый момент все модели ветвей свободные, то триггер 92(1) находится в нулевом состоянии, и сигнал с выхода элемента 97(1) через элемент 102(1) задержки поступает на вход установки единичного состояния триггера 92(1),35 Триггер 92(1) устанавливается в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви, первой модели ветви. Кроме того, сигнал е выхода элемента И 97(1) поступает на первый вход элемента И 98(1) и черезэлемент ИЛИ 100(1) на вход шифратора103 адреса узла 90 поиска моделейветвей, На второй вход элементаИ 98(1). первой модели 89(1) ветви через полюс 45 поступает код длительности ветви, который заносится в качестве исходной информации в формирователь 91(1) временного интервала, По сигналу, который с выхода элемента И 97(1) через элемент ИЛИ 100(1) и полюс (1,3) поступает на вход шифратора 103 адреса, формируется код номера модели ветви, Этот код через полюс 40 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления. На вход признака записи узла 6 памяти поступает сигнал с выхода элемента 27 задержки, Осуществляется запись по адресу номера выбранной модели ветви (в данном случае первый) номера ветви, длительность которой уже внесе.На в формирователь 91(1) временного интервала данной модели 89(1) ветви, блока 3 моделей ветвей.На этом заканчивается подготовка первой ветви, выходящей из начального узла сети, к процессу временного моделирования длительности. При подготовке к моделированию ветви осуществляется считывание номера данной ветви, считывание ее длительности, запись метки моделирования ветви по ее адресу, увеличение на "1" кода счетчика количест-,1 ва моделируемых ветвей, поиск сво- бодной от вычислений модели ветви, запись кода длительности ветви в формирователь временного интервала найденной свободной модели ветви, формирование кода найденной свободной модели ветви и запись номера подготавливаемой ветви сети по адресу номера модели в узел памяти номеров моделируемых ветвей.Далее считанный по адресу номера первой выходящей ветви из узла 60 памяти выходящих ветвеи блока 2 формирования топологии номер следующей ветви из списка выходящих из узла ветвей поступает на информационный Вход регистра 64 и с приходом второго импульса ГИ 1 записывается в указанный регистр 64. Записанный в регистр 64 код вновь поступает на адресный вход узла 60 памяти и через полюс 32 на адресный вход узла 5 памяти, на информационный вход узла 6 памяти. С приходом второго импульса ГИ 2 на входном полюсе 33 блока 1 управления появляется сигнал поиска сВОбОДЯОЙ модели, по которому Осуществляется чтение длительности ветви из узла 5 памяти, запись метки моделирования ветви в узел 8 памяти и увеличение на " 1" кода счетчика 10; Код длительчости ветви с выхода узла .5 памяти через полюс 45, поступает на входы элементов И 98(1)-98(М) всех моделей ветвей блока 3.Кроме того, сигнал поиска свободной модели ветви с полюса 33 через полюс 34(1) посту" пает на входы элементов И 96(1) и 98(1) первой модели 89(1) ветвей. Так как триггер 92(1) находится вединичном состоянии, означающем занятость первой модели ветви, то сигнал с выхода элемента 96(1) через полюс 34(2) поступает на входы элементов И 96(2) и 97(2) второй модели5 89(2) ветви. Так как триггер 92(2) .находится в нулевом состоянии, то сигнал с выхода элемента И 97(2) поступает на вход элемента И 98(2),и в формирователь 91(2) временных интервалов вводится информация о.коде длительности ветви. Одновременно сигнал с выхода элемента И 97(2) через элеф мент 102(2) задержки устанавливает триггер 92(2) в единичное состояние. Кроме того, сигнал с выхода элемента И 97(2) через элемент ИЛИ 100(2) и полюс (2,3) поступает на вход шифратора 103 адреса узла 90 поиска моделей 20 ветвей. По этому сигналу формируется код номера второй модели ветви, который через полюс 40 поступает на адресный вход узла блока 6 памяти номеров моделируемых ветвей. На вход признака 25 записи узла 6 памяти поступает сигнал с выхода элемента 27 задержки. происходит запись кода номера второй ветви, выходящей иэ начального узла сети, по адресу номера найденной свободной мо дели ветви.Так осуществляется подготовка ветвей, выходящих из начального узла, к процессу временного моделирования их длительности. Это происходит до тех пор, пока не будет считана последняя35 ветвь из списка выходящих из начального узла ветвей. После этого по адресу, который определяется номером последней выходящей ветви, иэ узла 60 40 памяти блока 2 формирования топологии будет считан код К, который записывается в регистр 64. Выход регистра64 подключен к дешифратору 70 К-состояния, поэтому в результате сравнения кодов на выходе дешифратора 70 формируется сигнал, означающий конец списка выходящих из узла ветвей. Сигнал с выхода дешифратора 70 поступает на вход установки в "0" триггера 69. Кроме этого, сигнал с выхода дешифратора 70 через элемент ИЛИ 78 поступает на выходной полюс 87.С полюса 37 сигнал поиска прерывания поступает на вход установки в "1" триггера 15 прерывания, устанавливая его в единичное состояние, и на вход элемента И 18. Кроме того, сигнал поиска прерывания с полюса 37 через полюс 38 поступает в блок 3 моделей ветвей. С полюса 38 сигнал поиска прерывания через элемент ИЛИ 104 узла 90 поиска моделей ветвей и полюс (1, 1) первой модели 89(1) модели поступает на вход элементов И 94(1) и 95(1). Так как в рассматриваемый момент под. готовлены к моделированию все ветви, выходящие из начального узла сети, и моделей ветвей, закончивших процесс моделирования, нет, то триггеры 93 всех моделей ветвей находятся в нулевом состоянии. Поэтому на,выходе элементов И 95 всех моделей ветвей присутствует потенциал низкого уровня, что дает потенциал низкого уровня на выходе элемента ИПИ 105 узла 90 поиска моделей ветвей. Этот потенциал через полюс 41 поступает в блок 1 управленияВ блоке 1 управления потенциал низкого уровня с полюса 4.1 поступает на вход установки в "0 триггера 15, Кроме этого, сигнал с полюса 41 через элемент НЕ 30 поступает на вход элемента И 18. На другой вход этого элемента поступает сигнал с выхода схемы 31 сравнения кодов. Так как в рассматриваемый момент код счетчика 10 количества моделируемых.- ветвей (количество ветвей, выходящих из начального узла сети). больше кода регистра 13 количества ветвей в максимальном разрезе сети (нулевой код) то на выходе схемы 31 сравнения кодов.формируется сигнал высокого уровня. Этот сигнал формирует на выходе элемента И 18 сигнал высокого уровня, который, поступая на вход . триггера 14, устанавливает его в единичное состояние и, поступая на вход признака записи регистра 13, записывает в него код из счетчика 10, Потенциал низкого уровня с инверсного выхода триггера 14 поступает на вход элемента И 20, запрещая прохождениеимпульсов серии ГИ 2 на вход узла из-мерения длиннейшего пути. Потенциалвысокого уровня с прямого выхода триггера 14 поступает на вход элемента И 19, на другой вход которого поступают импульсы серии ГИ 1 с полюса 49. С приходом первого после установки в единичное состояние триггера 14 импульса ГИ 1 на выходе элемента И 19формируется сигнал, который поступает на суммирующий вход счетчика 11 адреса меток ветвей максимального9 137423 сечения сети, увеличивая на "1" его код. С выхода счетчика 11 код через элементы ИЛИ 24 подается на адресный вход узла блока 9 памяти меток ветвей максимального сечения сети, а5 через блоки 23 и 24 элементов ИЛИ - на адресный вход блока 8.памяти меток моделируемых ветвей На вход признака чтения узла блока 8 памяти посту" 10 пает сигнал с выхода элемента И 17, на входы которого подаются сигналы с прямого выхода триггера 14 и сигналГИ 2 с полюса 50. Происходит чтение ячейки памяти узла 8 памяти по адре 5 су, который определяется кодом счетчика 11. Сигнал с выхода узла 8 памяти поступает на информационный вход узла 9 памяти. На вход признака записи узла 9 памяти поступает сигнал с элемента 26 задержки, задержанный на время, достаточное для считывания информации из узла 8 памяти. Происходит перезапись информации с узла 8 памяти в узел 9 памяти. С приходом на вход элемента И 19 второго импульса серии ГИ 1 на выходе элемента 19(20) формируется сигнал, который увеличивает на " 1" код счетчика 11, с выхода которого код опять поступа 30 ет на адресные входы узлов 8 и 9 памяти. Происходят перезапись информации с узла З,памяти в узел 9 памяти но новому адресу. Описанный процесс формирования адресов.и перезапись информации с узла 8 памяти в узел 935 памяти происходит до тех пор, пока счетчик 11 не выработает сигнал переполнения, что означает конец перебора всех адресов, соответствующих номерам всех возможных ветвей сети. При этом в узле 9 памяти формируются метки по тем адресам, которые соот ветствуют номерам ветвей, выходящим из начального узла сети.45Сигнал переполнения, выработанный счетчиком 11 блока 1 управления, поступает на вход установки в "0" триггера 14. Потенциал низкого уровня с прямого выхода триггера 14 поступает на вход элемента И 19, запрещая прохождение импульсов серии ГИ 1 на входсчетчика 11 и на вход элемента И 17,запрещая прохождение импульсов серииГИ 2 на вход признака чтения узла 9памяти и на вход признака записи. узла 9 памяти. Потенциал высокого уровня с инверсного выхода триггера 14поступает на первый вход элемента1 О 9И 20, на другой вход которого поступает потенциал высокого уровня с выхода триггера 15. Импульсы серии ГИ 2, поступающие с полюса 50 на третий вход элемента И 20, проходят на вход узла 12 измерения длиннейшего пути и на входной полюс 46 блока 3 моделей ветвей. С входного полюса 46 импульсы серии ГИ 2 поступают на вход элементов И 99 всех моделей 89 ветвей. У тех моделей ветвей, триггеры 92 которых находятся в единичном состоянииЭ на второй вход элементов 99.поступает разрешающий потенциал с единичного выхода триггера 92, и импульсы серии ГИ 2 с выхода элементов И 99 поступают на суммирующий вход формирователей 91 временного интервала. Так продолжается до тех пор, пока хотя бы один из формирователей 91 временного интервала не выдаст сигнал об оконча- нии процесса временного моделирования длительности ветви.Сигналы с выхода формирователей 91(1)"91(М) поступают на входы установки в " 1" триггеров 93(1)-93(М) и устанавливают их в единичное состояние. Одновременно сигналы с выходов формирователей 91(1)-91(М) через полюса (1,2), (2,2)-(М,2) поступают на входы элемента ИЛИ 104 узла 90 поиска моделей ветвей, С выхода элемента ИЛИ 104 сигнал прерывания через полюс (1,1) поступает на входы элементов И 94(1) и 95(1) первой модели 89(1) ветви, Если триггер 93(1) первой модели 89(1) находится в единичном состоянии, сигнал прерывания с выхода элемента 95(1) через полюс (1,4) и элемент ИЛИ 105 поступает на входной полюс 41 блока 1 управления. Кроме того, сигнал с выхода элемента 95(1) поступает на вход установки в "0" триггера 92, через элемент ИЛИ 100(1) и полюс (1,3) - на вход шифратора 103 адреса узла 90 поиска моделей ветвей, а через элемент 101(1) задержки в . на вход установки в "0" триггера 93(1). По сигналу, который поступил на вход шифратора 103 адреса, формируется код номера данной модели ветви. Этот код с выхода шйфратора 103 адреса черезполюс 40 поступает в блок 1 управления.Б блоке 1 управления код номера модели ветви с полюса 40 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей, На вход13742 признака трения узла памяти поступает сигнал прерывания с входного полюса 41, Происходит чтение из узла памяти по адресу номера модели ветви, номера ветви сети. Этот код через элемент ИЛИ 25 поступает на адресный вход уз-, .ла 7 памяти меток свершения ветвей., а через элемент 23 ИЛИ - на адресный вход узла 8 памяти меток моделируемых 10 ветвей, Через время, достаточное для считывания номера. ветви из узла 6 памяти, на выходе элемента 28 задержки формируется сигнал прерывания, который поступает на вход признака записи 15 узла 7 памяти и через элемент ИЛИ 22- на вход признака записи узла 8 памяти.Записывается единичная метка в узел 7памяти по адресу номера свершившейся ветви, характеризующая завершение процесса моделирования длительности данной ветви. В узел 8 памяти записывается нулевая метка по адресу номера ветви, а из счетчика 10 вычитаетсяединица, характеризующая исключение , данной ветви из списка ветвей, входящих в следующий разрез сети. Через время, достаточное для. записи метки свершения в узел 7 памяти, на выходе элемента 29.задержки появляется сигнал, который через полюс 44 поступает в блок 2 формирования топологии. Через полюс 42 в блок 2 формирования топологии, с выхода узла 6 памяти поступает код номера свершившейся ветви сети.35В блоке 2 формирования топологии код номера свершившейся. ветви с полюса 42 поступает на адресный вход узла 59 памяти номеров конечных узлов ветвей сети. На вход признака чтения узла 59 памяти поступает сигнал начала анализа с входного полюса 44. Кроме этого, сигнал с полюса 44 поступает на вход установки в "1" триггера и на вход элемента 74 задержки. Единичное состояние триггера 68 разрешает прохождение импульсов серии ГИ 1 и серии ГИ 2 через элементы И 84 и 85 соответственно. По сигналу начала анализа, который поступил на вход признака чтения узла 59 памяти, происходит чтение ячейки памяти, в которой записан номер конечного узла свершившейся ветви. Код считанного номера узла с выхода узла 59 памяти 55 поступает на адресный вход узла 63 памяти первой входящей ветви и на информационньй вход регистра 66 ко 39 12нечного узла. По этому сигналу происходит запись кода номера конечного узла ветви в регистр 66 и считывания первой ветви, входящей в этот узел, из узла 63 памяти. Код номера первойвходящей ветви с выхода узла 63 памяти через элемент ИЛИ 79 поступает на информационный вход регистра 65 входящей ветви и записывается в него по первому импульсу серии ГИ 1, поступающему на вход признака записи регистра с выхода элемента И 84, С выхода регистра 65 код номера первой входящей ветви через полюс 35 поступает на адресный вход узла 7 памяти свершения ветвей на адресный вход узла 61 памяти номеров входящих ветвей; По первому импульсу ГИ 2, поступающему с выхода элемента 85 через полюс 36 на вход признака чтения узла па" мяти меток свершения, происходит чтение метки свершения по адресу первой входящей ветви. Сигнал считанной метки с выхода узла 7 памяти через полюс 43 поступает в блок 2 формирования топологии, Если метка отсутствует, что означает несвершение процесса моделирования ветви с данным номером, то нулевой сигнал метки с полюса 43 через элементы НЕ 88 и ИЛИ 80 устанавливает триггер 68 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 88 поступает через элемент ИЛИ 78 на выход 37 поиска прерывания. Наличие нулевого сигнала метки свершения ветви означает, что хотя бы одна из ветвей; входящих в рассматриваемый узел, не свершилась, а следовательно, в дан ." ном узле не сформировалась функцияИ для всех входящих в него ветвей. В этом случае сигнал с входа 37 пос-,тупает на вход установки в "1" триггера 15 прерывания и на вход элемента И 18 блока 1 управления. Кроме , того, сигнал поиска прерывания с выхода 37 через вход 38 поступает на вход элемента ИЛИ 104 узла поискамоделей ветвей. С выхода элемента ИЛИ 104 сигнал поступает на входыэлементов И 94(1) и 95(1) первой модели ветви. Если в блоке 3 моделей ветвей имеется еще модель ветви, которая окончила процесс моделированиядлительности, то триггер 9 Э такой модели ветви находится в единичномсостоянии. В этом случае сигнал с1374239 13через элемент ИЛИ 100 вновь поступает на вход шифратора 103 адреса для Формирования кода номера данной модели ветви устанавливает в нулевое5 состояние триггеры 92 .и 93 и через элемент ИЛИ 105 выдает сигнал прерывания в блок 1 управленияБлок 1 управления, получив номер модели ветви и сигнал прерывания, повторяет 10 все описанные операции, связанные с анализом свешения ветви. Если же в блоке 3 моделей ветвей не имеется . моделей у которых триггер 93 находится в единичном состоянии, то про цесс анализа не проводится и импульсы измерительной серии поступают через элемент И 20 блока 1 управления в узел 12 определения длиннейшего пути и в блок 3 моделей ветвейЕсли же сигнал метки свершения ветви с входа 43 блока 2 формирования топологии имеет единичное значение, т.е. процесс Формирования длительности данной ветви закончился то этот 25 сигнал дает разрешение на прохождение импульсов серии ГИ 2 на вход признака чтения узла 61 памяти входящихветвей. На адресный вход узла 61 памяти в это время поступает код номе ра первой входящей ветви с выхода регистра 65. По адресу первой входящей ветви из узла 61 памяти считывается код номера вто.:ай, входящей в рассматриваемый узел ветви, Считанный35 код через элемент ИП 1 79 поступает на информационный вход регистра 65 и записывается в него с приходом второ, го импульса ГИ 1 с выхода элементаИ 8 ч. Далее осуществляется опрос метки свершения считанной ветви и переход к следующей ветви из списка входящих в рассматриваемый узел ветвейОписанный процесс анализа входящих в рассматриваемый узел ветвей продолкается до тех пор, пока не будут опрошены все ветви, входящие в рассматриваемый узел. Это соответствует выполнению Функции конъюнкции относительно входящих ветвей рассматриваемого узла, В этом случае но адресу номера последней ветви в списке из узла 61 памяти считывается код К, определяющий конец списка. Код К записывается в регистр 65 входящей ветвии с него поступает на вход дешифра 55 тора 71 состояния К, который путем сравнения кодов вырабатывает сигнал : конца списка. Полученный сигнал про 14ходит через элементы ИЛИ 80 и 81 и устанавливает триггеры 68 и 69 соответственно в нулевое и еднничное состояние. Кроме того, сигнал с выхода дешифратора 7 1 поступает на вход элемента И 63, второй вход которого связан с выходом схемы 72 сравнения кодов, которая сравнивает коды, хранящиеся в регистре 67 конечного узла сети и в регистре 66 конечного узла ветви. Регистр 67 хранит код конечного узла сети, а регистр 66 - код рассматриваемого узла сети, сформировавшего функцию конъюнкции в данный момент времени. Если значения этих кодов совпадают (сформирована логическая функция конъщнкции для конечного узла сети), то схема 72 сравнения кодов вьдает разрешение на прохождение сигнал конца списка с выхода дешифратора 1 через элемент И 83 на выход 39 блока 2 формирования топологии, что соответствует концу моделирования заданной сети; С выхода 39 блока 2 управления сигнал разрешения индикации расчета поступает на вход элемента И 21 и разрешает вьдачу на внешнее устройство величины длиннейшего пути сети, накопленной к данному моменту в узле 12 формирования длиннейшего пути.Кроме того, сигнал с выхода 39 поступает на вход элемента И 16 разрешая вьдачу на внешнее устроиство величины количества ветвей в максимальном разрезе сети, сформированной к данному моменту в регистре 13; Для получения информации о номерах ветвей, которые принадлежат максимальному разрезу сети, необходимр подать; сигнал на вход 53 блока 1 управления, который поступает на вход признака чтения считывания узла памяти меток ветвей максимального сечения сети. На вход 5 ц поочередно подаются коды из всего диапазона номеров ветвей исследуемой сети. Эти коды поступают на адресный вход блока 9 памяти. Считанная из узла 9 памяти единичная метка соответствует ветви, которая принадлежит максимальномуразрезу -етд.В случае, если конечный узел сети не сформирован, сигнал с выхода дешифратора 71 блока 2 формирования топологии через элемент ИЛИ 75 поступает на вход признака чтения блока 62 памяти первой выходящей ветви.13742На адресный вход узла 62 памяти в этот момент поступает код номера сформированного узла сети. Происходит чтение кода номера первой ветви выходящей из сформированного узла сети,5 Этот код через элемент ИЛИ 77 посту.пает на информационный вход. регистра 64 и записывается в него по первому импульсу ГИ 1, поступающему на вход признака записи регистра с выхода элемента 86 И. Записанный код номера первой выходящей ветви с выхода регистра 64 поступает на адресный вход узла ЬО памяти номеров выходящих ветвей и через выход 32 - в блок 1 управления. Далее импульс ГИ 2. с выхода элемента И 87 блока 2 формирования топологии поступает на вход признака чтения считывания блока 60 памяти. 20 Происходит считывание второй ветви, выходящей из сформированного узла Кроме того, импульс ГИ 2 с выхода элемента И 87 через выход 33 поступает в блок 1 управления. По этому сигналу и адресу номера первой выходящей из узла ветви осуществляется считывание кода длительности этой ветви из узла 5 памяти запись метки моделируемой ветви в узел Ы памяти и увеличе ние на "1" кода счетчика 10, Одновременно сигнал поиска свободной модели ветви с выхода 33 через вход 34 поступает в блок 3 моделей ветвей. По этому сигналу осуществляется поиск свободной модели ветви, формирование ее кода и запись длительности ветви. Код свободной модели ветви через выход 40 поступает в блок 1 управления. Осуществляется запись номера подготавливаемой ветви в узел 6 памяти, по адресу номера выбранной свободной модели ветви. На этом заканчивается подготовка к временному моделированию первой ветви, выходящей.из сформированного узла сети. Аналогичным образом осуществляется подготовка остальных ветвей, выходящих из данного узла.После подготовки к процессу моделирования всех ветвей, выходящих50 из сформированного узла, на выходе дешифратора 70 формируется сигнал . поиска прерывания, который через элемент ИЛИ 78 и выход 37 поступает в блок 1 управления, где поступает на вход установки в "1 триггера 15 прерывания и на вход элемента И 1 Ы. Кроме того, сигнал поиска прерывания 39 36с выхода 37 поступает в блок 3 моделей ветвей. По этому сигналу осуществляется поиск очередной модели ветви, окончившей процесс моделирования. Если такая модель обнаружится, то сигнал прерывания с выхода элемента ИЛИ 105 узла 90 поиска моделей ветвей через вход 41 поступает в блок 1 управления, устанавливая триггер 15; прерывания в нулевое состояние. Про-. изводится обработка очередного прерывания описанным образом. Это происходит до тех пор, пока не обработаются прерывания от всех моделей ветвей,окончивших к настоящему моменту процесс моделирования. После этого сигнал поиска прерывания с выхода дешифратора 70 через выходной полюс 37 поступает в блок 1 управления и устанавливает триггер 15 прерывания в единичное состояние и через выход 38 поступает в блок 3 моделей ветвей. Так как в рассматриваемый момент в блоке 3 моделей ветвей нет необработанных моделей ветвей, которые окончили моделирование, то сигнал низкого уроВНя с выхода элемента ИЛИ 105 узла 90 поиска моделей ветвей через вход 41 поступает на вход установки в "0" триггера 15 и, кроме того, через элемент НЕ 30 - на вход элемента И 18. На другой вход триггера 15 поступает сигнал поиска прерывания с входа 37. На третий вход элемента поступает сигнал с выхода схемы 31 сравнения. В том случае, если код счетчика 10 (количество ветвей в рассматриваемом разрезе сети) больше кода регистра 13 количество ветвей в максимальном предыдущем разрезе сети), сигнал с выхода схемы 31 сравнения, имеет высокий уровень, что разрешает установку триггера 14 в единичное состояние. Единичное состояние триггера 14 обуславливает перезапись меток моделируемых ветвей из узла блока 8 памяти в узел блока 9 памяти и кода счетчика 10 в регистр 13. Так осуществляется анализ величины разреза сети перед каждым отрезком моделирования длительности ветвей и формирование нового разреза сети в случае, если новый разрез больше максимального предыдущего разрезаОписанные процессы подготовки ветвей к временному моделированию длительностей, анализ величины и формирование разреза сети, временное моде