Устройство для определения длиннейшего пути в сетях

 

Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам для решения задач организационного управления и теории графов. Целью изобретения является расширение функциональных возможностей устройства за счет вычисления полного резерва времени для ветви. Устройство содержит блок 1 управления, два блока 2, 4 формирования топологии и блок 3 моделирования ветвей. 3 ил. (Л 00 00 со ел 00

союз советсних

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИН

А1

„„SU„,1 39581 д511 С 06 Е 15/20

ГосудАРстБенный номитет сссР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНЯТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1,.; фиг J (21) 40507927 24-24 (22) 07.04.86 (46) 23,09.87. Бюл. Ф 35 (71) Институт проблем моделирования в энергетике АН УССР (72) А.Г.Додонов, А,A,Êîòëÿðåíêî, С.П.Пелехов, В.П.Приймачук и A.М.Щетинки

{53) 681.3(088.8) (56) В.А,Бункин, Д;А.Колев, Б, Я. Курицкий и др . Справочник по оптимизационным задачам в АСУ. lI. Манив ностроение, 1984,. с ° 157.

Авторское свидетельство СССР

Р 1161951, кл. G 06 F 15,720, 1984, (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДЛИННЕЙШЕГО ПУТИ В СЕТЯХ (57) Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устрой. ствам цля решения задач организационного управления и теории графов, Целью изобретения является расширение функциональных возможностей устройства за счет вычисления полного резерва времени для ветви. Устройство содержит блок 1 управления, два блока

2, 4 формирования топологии и блок

3 моделирования ветвей, 3 ил.

1339581

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

На фиг,1 приведена блок-схема устройства; на фиг.2 — схема блока формирования топологии; на фиг.3 схема блока моделей ветвей, Устройство содержит блок 1 управления, первый блок 2 формирования топологии для моделирования сети в прямом направлении, блок 3 моделей ветвей, второй блок 4 формирования топологии (для моделирования сети в обратном направлении), генератор 5 импульсов.

Блок 1 управления содержит три узла 6-8 памяти, узел 9 измерения длиннейшего пути, триггер 10 прерыва- 25 ния, первый и второй элементы И 1.1 и

12, первый элемент ИЛИ 13, с первого по третий элементы 14-16 задержки, регистр 17, первый и второй дешифра торы 18 и 19, триггер 20 длиннейшего пути„ триггер 21 обратного хода, с третьего по шестой элементы И 22-25, с второго по шестой элементы ИЛИ

26-32, с четвертого по шестой элементы

33-35 задержки, выход 36 номера подго- 35 тавлив а е мой к мо дели ров анию в е тв и блок а

2, выход 37 поиска свободной модели ветви блока 2, вход 38 поиска свободной модели ветви блока 3, выход 39 номера анализируемой ветви блока 2, 40 выход 40 проверки прохождения ветви блока 2, выход 41 поиска прерывания блока 2, вход 42 поиска прерывания блока 3, выход 43 индикации результата расчета блока 2, выход 44 номера модели ветви блока 3, выход 45 прерывания блока 3, выход 46 номера подготавливаемой к моделированыо ветви блока 4, выход 47 поиска свободной модели ветви блока 4, выход 48 номера 50 анализируемой ветви блока 4, выход

49 проверки прохождения ветви блока

4, выход 50 поиска прерывания блока

4, вход 5) режима вычисления резерва времени,цля заданной ветви„

Входы 52 и 53 номера анализируемой ветви сети блоков 2 и 4, входы 54 и

55 признака прохождения ветви блоков

2 и 4, входы 56 и 57 признака начала анализа прохождения ветви блоков 2 и 4, вход 58 конца определения длиннейшего пути, выход 59 полного резерва блока 2, вход. 60 признака прямого прохода, выход 61 кода длительности ветви блока 3, вход 62 измерительной серии блока 3, входы 63 и 64 сброса моделей ветвей блоков 3 и 4, вход

65 признака обратного прохода блока

4, два тактовых входа 66 и 67 блока

2, два тактовых входа 68 и 69 блока

4, тактовый вход 70 блока 1 управления, вход 71 кода номера ветви, выходящей из начального узла моделируемой сети, вход 72 запуска, вход 73 кода номера ветви, входящей в конечный узел сети, выход 74 устройства и выход 75 индикации результата расчета, Блок 1 управления предназначен для организации взаимодействия между блоком 2 формирования топологHH HJIH блоком 4 формирования топологии с блоком 3 моделей ветвей устройства в процессе моделирования и определения длиннейшего пути в исследуемой сети или вычисления полного резерва времени выбранной ветви в исследуемой сети.

Блок 2 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети и номеров ветвей, выходящих из исследуемого узла сети, а также для определения момента окончания моделирования сети при прямом проходе (проход от начального узла сети к конечному узлу сети).

Блок 3 моделей ветвей предназначен для организации временного моделирова1 ния длительностей ветвей сети. Блок

4 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети и номеров ветвей, выходящих из исследуемого узла сети при моделировании сети в обратном направлении (от конечного узла к начальному), Генератор 5 импульсов предназначен для формирования серий импульсов ГИ 1 и ГИ 2, сдвинутых относительно друг друга, В блоке 1 управления (фиг,1) узел

6 памяти предназначен для хранения информации о величинах длительностей ветвей сети, а именно для хранения по адресу номера ветви кода длитель- ности данной ветви. Узел 7 памяти блока 1 управления предназначен для хранения информации о соответствии номера мадели ветви блока 3 моделей ветвей и номера моделирования ветви

4 выходящей ветви узлов сети, узел 81 памя ги адресов первой входящей ветви узлов сети, регистр 82 адреса выходящей ветви, регистр 83 адреса входящей ветви, регистр 84 адеса конечного узла ветви, регистр 85 конечного узла сети, триггеры 86 и 87, дешифраторы

88 и 89, дешифратор 90 сравнения кодов, элементы 91 и 92 задержки, элементы ИЛИ 93-101, элементы И 102-107 и элементы HE 108.

Узлы 76-81 памяти предназначены для хранения информации о топологии моделируемой сети: узел 76 памяти— для хранения номера начального узла ветви по адресу номера данной ветви; узел 77 памяти — для хранения номера конечного узла ветви по адресу номера данной ветви; у-зел 80 памяти — для хранения по адресу номера начального узла ветви номера ветви, первой в списке ветвей, выходящей из данного узла; узел 81 памяти — для хранения по адресу номера конечного узла ветви номера ветви. первой из списка ветвей, входящей в данный узел; узел 78 памяти — для хранения в виде списков номеров ветвей, выходящих из узлов сети, а узел 79 памяти — для хранения в ви,це списков номеров ветвей, входящих в узлы сети.

Регистр 82 адреса выходящей ветви и регистр 83 адреса входящей ветви в блоке 2 формирования топологии представляет собой регистры с параллельнь!м приемом информации.

Регистр 82 предназначен для промежуточного хранения номера ветви при определении ветвей, выходящих иэ узла, а регистр 83 — для промежуточного хранения номера ветви при определении ветвей, входящих в узел. Регистры 84 и

85 выполнены аналогичным образом и предназначены соответственно для хранения адреса рассматриваемого узла сети и для постоянного хранения конечного узла сети.

Дешифратор 90 сравнения кодов предназначен для поразрядного сравнения кодов, хранящихся в регистрах 84 и 85.

Дешифраторы 88 и 89 состояния х блока 2 формирования топологии предназначены для сравнения поступающих на них кодов с кодовой комбинацией состояний х, заданного постоянно в схеме, Триггеры 86 и 87 предназначены для разнесения во времени процесса

3

133958 сети в текущий момент времени. В узле 7 памяти по адресу номера модели ветви хранится номер моделируемой ветви сети, Узел 8 памяти блока 1 управления предназначен для хранения информации о завершении процесса временного моделирования длительностей ветвей сети, Узел 9 измерения длиннейшего пути 10 блока 1 управления предназначен для формирования величины длительности длиннейшего пути сети и для формирования величины полного резерва заданной ветви сети. 15

Регистр 17 блока 1 управления предназначен для хранения кода номера заданной ветви полного резерва, который необходимо определить, Дешифратор 18 сравнения кодов блока 1 20 управления предназначен для сравнения кода номера заданной ветви сети, хранящегося в регистре 17 номера заданной ветви, с кодом номера подготавливаемой к моделированию ветви, по- 25 ступающего с входного полюса 36 блока 1 управления, Дешифратор 19 сравнения кодов блока 1 управления предназначен для сравнения кода номера заданной ветви сети, хранящегося в регистре 17 номера заданной ветви, с кодом номера анализируемой ветви, поступающего с выхода узла 7 памяти блока 1 управления, Триггер 10 прерывания предназначен для организации временного разделения между процессом времейного моделирования длительностей ветвей сети и процессом анализа топологии моделируемой сети. Триггер 20 длинней- 40 ! шего пути .из режима суммирования в режим вычитания путем разрешения про, хождения импульсов ГИ 2, поступающих с полюса 70 блока 1 управления. Триггер 21 обратного хода предназначен 45 для организации временного разделения работы блока 2 формирования топологии (при прямом моделировании сети от начального узла к конечному) и работы блока 4 формирования топологии 50 (при обратном моделировании сети от конечного узла к начальному), Блок 2 содержит узел 76 памяти адресов начальных узлов ветвей сети, узел 77 памяти адресов конечных узлов ветвей сети, узел 78 памяти адресов выходящих ветвей узлов сети, узел 79 памяти адресов входящих ветвей узлов сети, узел 80 памяти адресов первой

13395 поиска ветвей, входящих в узлы сети, и поиска ветвей, выходящих из узлов сети, Блок 3 содержит и моделей 109 вет

5 вей (где п — количество ветвей в максимальном сечении сети) и узел

110 поиска моделей ветвей, Каждая модель 109 ветви состоит из формирователя 111 временных интервалов, 1О триггеров 112 и 1 3, элементов И 141 1 9, элементов ИЛИ 1 20-1 22п элементов

123 и 124 задержки.

Узел 109 поиска моцелей ветвей содержит шифратор !25 адреса и элементы

ИЛИ 126 и 127.

Устройство работает следующим образом.

В узлr 76-81 памяти блоков 2 и 4 формирования топологии в виде списков заносится информация о топологии моделируемой сети, Регистры 82-84 и узел

9.измерения длиннейшего пути предварительного обнулены, в регистр 85 блока 2 заносится код конечного узла 25 сети, в регистр 85 блока 4 заносится код начального узла сети, а в узел

6 памяти длительностей ветвей заносятся коды, длительностей ветвей моделируемой сети, При необходимости опреде- З0 ления резерва одной из ветвей сети, на вход 51 блока 1 управления поступает соответствующий признак, В регистр 17 номера заданной ветви заносится код номера ветви, полный резерв

35 которой необходимо определить, Так как триггер 21 установлен в нулевое состояние, то на входной полюс 60 блока 2 формирования топологии с нулевого выхода триггера 21 посту- 40 пает сигнал, разрешающий его работу, а с единичного выхода триггера 21 на входной полюс 65 блока 4 формирования топологии поступает сигнал, запрещающий работу блока 4 формирования топологии. Одновременно сигнал с единичного выхода. триггера 21 запрещает прохождение сигнала с выхода дешифратора

18 сравнения кодов через элемент И 24 блока 1 управления, С нулевого выхода

50 триггера 20 разрешающий сигнал поступает на вход элемента И 11, а с единичного выхода запрещающий сигнал поступает на вход элемента И 22, а также на вход элемента И 25, тем самым запрещая прохождение сигнала с выхода дешифратора 19 сравнения кодов, После начальной установки на полюс 71 блока 2 формирования топологии подается код номера ветви, выходящей из узла, принятого за начальный узел сети, а на полюс 73 блока 4 формирования топологии подается код номера ветви, входящей в узел, принятый за конечный узел сети. Начальный узел сети, таким образом, определяется по адресу номера ветви в узле 75 памяти блока 2 формирования топологии.

В некоторый момент времени сигнал

"Пуск", поступающий на полюс 72 блока 2 формирования топологии, проходит через элементы ИЛИ 98 и 99 и устанавливает триггер 87 в единичное состояние, Единичное состояние триггера 87 разрешает прохождение серии импульсов

ГИ 1 и ГИ 2 соответственно через элементы И 106 и 107. Кроме того, сигнал

"Пуск" поступает с полюса 72 блока

2 формирования топологии через элемент ИЛИ 100 на вход элемента 91 задержки. Так как ветвь выбрана как выходящая из начального узла сети, то код начального узла сети поступает через элемент ИЛИ 94 на адресный вход узла 80 памяти первой выходящей ветви. Через время задержки сигнал Пуск появляется на выходе элемента 91 задержки и поступает через элемент ИЛИ

93 на вход считывания узла 80 памяти.

Сигнал выборки по адресу начального узла позволяет сосчитать из узла 80 памяти код номера ветви, являющейся первой в списке ветвей, выходящих из начального узла сети, Код первой выходящей ветви с выхода узла 80 памяти поступает через элемент ИЛИ 95 на информационный вход регистра 82 выходящей ветви и записывается в него по первому импульсу ГИ 1, поступающему на управляющий вход регистра с выхода элемента И 106, Записанный код первой выходящей ветви с выхода регистра 82 поступает на адресный вход узла 78 памяти, а также через выходной полюс

36 блока 2 формирования топологии и элемент ИЛИ 31 на адресный вход узла

6 памяти длительностей ветвей, на информационный вход узла 7 памяти номеров моделируемый ветвей и на вход дешифратора 18 блока 1 управления, Затем импульс ГИ 2, сдвинутый относительно импульса ГИ 1, поступает с выхода элемента И 107 на вход считывания узла 78 памяти и по адресу первой ветви, выходящей из начального узла сети, осуществляет выборку номера второй ветви, выходящей из того же узла °

Одновременно импульс ГИ 2 поступает через выходной полюс 37 блока 2 формирования топологии и затем через элемент ИЛИ 32 — на вход считывания

5 узла Ь памяти длительности ветви, на вход элемента 14 задержки блока 1 управления и на входной полюс 38 поиска свободной модели ветви блока

3 моделей ветвей, По сигналу ГИ 2 и адресу номера первой выходящей из узла ветви, хранящемуся в регистре 81, осуществляется считывание кода дли% тельности этой ветви иэ узла 6 памяти длительностей ветвей, Одновременно сигнал поиска свободной модели ветви с полюса 38 поступает на входы элементов И )16(1) и )17(1) первой модели

)09(1) ветви блока 3 моделей ветвей, Так как все модели ветви свободны

20 то триггер 112(1) будет находиться в нулевом состоянии и сигнал с выхода элемента И ) 17 (1) через элемент 124 задержки поступает на единчиный вход триггера 112(1). Через время задержки, 25 достаточное для срабатывания всех элементов, этот сигнал устанавливает триггер 112(1) в единичное состояние, что соответствует загрузке длительности рассматриваемой ветви сети в пер30 вую модель 109(1) ветви блока 3 моделей ветвей, Одновременно сигнал с выхода элемента И 1)7(1) поступает на первый вход элемента И 118(1) и через элемент ИЛИ 120(1) — на.вход шифратора )25 адреса, На второй вход элемента И 118(1) через входной полюс 61 поступает код длительности ветви, который через элемент И 118(1) заносится в качестве исходной информации в формирователь 111(1) временного интер40 вала, С выхода шифратора 125 адреса полученный по сигналу с полюса (1,3) код адреса модели ветви поступает через выходной полюс 44 блока 3 моделей ветвей на адресный вход узла 7 памяти номеров моделируемых ветвей блока 1 управления, Через время, достаточное для организации описанных процессов, в блоке 3 моделей ветвей, на выходе элемента 14 задержки блока

1 управления формируется сигнал, поступающий на вход записи узла 7 памяти номеров моделируемых ветвей. Сигнал записи позволяет записать по адресу номера выбранной модели ветви (в данном случае первой) номер ветви, длительность которой внесена уже в формирователь

1)1(1) временного интервала данной мо8! 8 дели ветви. На этом заканчивается подготовка первой выходящей из узла ветви к процессу временного моделирования длительности. Описанный процесс подготовки моделей )09 ветвей к моделированию длительности кратко можно записать в виде выполнения ряда операций: считывание из блока 2 формирования топологии адреса ветви, затем считывание ее длительности, поиск свободной от вычислений модели ветви, ввод ее в формирователь временного интервала кода длительности ветви и запись в узел памяти моделируемых ветвей по адресу номера выбранной модели ветви номера первой ветви.

Далее считанный по адресу номера первой выходящей ветви из узла 80 памяти выходящих ветвей блока 2 формирования топологии номер следующей ветви в списке выходящих из узла ветвей поступает на информационный вход регистра 82 и с приходом второго импульса ГИ 1 записывается в указанный регистр, Записанный в регистр 82 код поступает вновь на адресный вход узла

78 памяти, а также через полюс 36 блока 2 формирования топологии и далее через элемент ИЛИ 31 на адресный вход узла 6 памяти длительности, на вход элемента 14 задержки блока 1 управления и на входной полюс 38 поиска свободной модели ветви блока 3 моделей ветвей, С приходом второго импульса ГИ 2 из узла 6 памяти длительностей считывается код длительное ти второй исходящей из узла ветви.

Этот код поступает через полюс 6) блока 3 моделей ветвей на входы элементов И 118(1), 118(2),...,118(n) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 38 блока 3 моделей ветвей на входы элементов И 116(1) и 1)7(1) поступает сигнал поиска свободной модели ветви.

Так как триггер 112(1) первой модели ветви находится в единичном состоянии, означающем занятость модели ветви, то сигнал с выхода элемента И

116() ) поступает на вход 38 (2) второй модели 109 (2) ветви и триггер 112 (2), который находится в нулевом состоянии. Тогда сигнал с выхода элемента

И 117(2) поступает на вход элемента

И 1 18(2), и в формирователь 11)(2) временных интервалов заносится исходная информация о длительности второй

13395 исходящей из узла ветви. Одновременно сигнал с выхода элемента И 117(?) через элемент 124(2) задержки устанавливает триггер 112(2) в единичное

5 состояние, по этому же сигналу на выходе шифратора 125 адреса формирует— ся номер второй модели ветви, который через выходной полюс 44 блока 3 моделей ветвей поступает на адресный 10 вход узла 7 памяти номеров моделируемых ветвей, и при формировании через некоторое время сигнала на выходе элемента 14 задержки в памяти по адресу номера модели ветви записывается 15 номер ветви, код длительности которой записан в формирователь 111(2) временного интервала, Так осуществляется подготовка ветвей, выходящих из начального узла, к процессу временного моделирования их длительностей до тех пор„ пока не будет считан номер последней ветви из списка ветвей, выходящих из начального узла, По адресу номера последней ветви из списка выходящих из узла ветвей в узле 80 памяти будет считан код х (метка окончания списка номеров ветвей, выходящих из одного узла), который записывается в регистр )О

82, В этом случае дешифратор 88 с.остояния х определяет информацию о конце списка путем сравнения кода, хранящегося в регистре 82, с заданной кодовой комбинацией х. Дешифратор 88 вырабатывает ня выходе сигнал, который поступает через элемент ИЛИ 101 на нулевой вход триггера 87, сбрасывает его в нулевое состояние. Кроме того, сигнал с выхода дешифраторя. 88 ФО через элемент IUD 96 поступает на выходной полюс 41 блока 2 формирования топологии, С полюса 41 сигнал поиска прерывания поступает через элемент

ИЛИ 27 на вход триггера 10 прерывания (5 блока 1 управления и устанавливает его в единичное состояние. Одновременно сигнал поиска прерывания с выхода элемента II)IH 27 поступает ня входной полюс 42 блока 3 моделей ветвей. Так как выполняется моделирование длительностей ветвей, выходящих из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер )О прерывания находится в единичном состоянии. Единич1 ное состояние триггера 10 разрешает прохождение импульсов ГЬ 2 с полк>са

70 через элемент И 11 на счетный вход

81 )О (суммирование) узла 9 измерения длиннейшего пути, я также через элеме>п

ИЛИ 26 и входной полюс 62 блока 3 моделей ветвей на входы элементов

И 119 () ), 19 (2)...,, ) ) 9(п) моделей ветвей )09(1), 109(2),...,109(n) .

1)мпульсы поступают с выходов элемеH тов И 119() ), 1)9(2),... 119(п) ня входы формирователей временных интервалов тех моделей ветвей, триггеры

112(l), 112(2),...,1! 2(п) которых находятся в единичном состоянии. Импульсы ГИ 2 поступают на вход узла

9 измерения длиннейшего пути блока 1 управления и на входы формирователей временного интервала моделей ветвей, занятых процессом временного моделирования, блока 3 моделей ветвей до тех пор, пока один (или несколько) из формирователей 111 временного интервала не сформирует сигнал об окончании процесса временного моделирования длительности ветви, Сигналы с выхода формирователей

111(1), 111(2),...,111(п) временного интервала поступают на единичные входы триггеров 113(1), 113(2),..., 113(п) и устанавливают их в единичное состояние. Одновременно сигнал с выхода формирователя )11 поступает через элемент ИЛИ 126 на вход (1,1) поиска прерывания первой модели

119()) ветви и далее на входы элемен:тов И 114()) и 155(! ) ° В случае, если триггер 113(1) находится в единичном состоянии (модель ветви закончила процесс временного моделирования длительности ветви), сигнал прерывания поступает с выхода элемента управления, Одновременно сигнал с выхода элемента И 115(1) через элемент

ИЛИ )22(1) поступает на единичный вход триггера 1) 2(1), устанавливая его в единичное состояние, что соответствует освобождению модели !09(1) ветви для последующих вычислений.. Кроме того, сигнал с выхода элемента

И 115(1) через элемент 123()) задержки и элемент ИЛИ 121(1) сбрасывает триггер 113(1) в нулевое состояние, а также через элемент ИЛИ 120(1) и полюс (1,3) сигнал с выхода элемента

И 11(1) поступает на вход шифратора

125 адреса. На вь>ходе шифратора формируется номер .данной модели ветви.

Код номера модели ветви с выхода шифратора 125 адреса через входной полюс

14 блока 1 управления поступает на ад11 13395 ресный вход узла 7 памяти моделируемых ветвей сети. По сигналу прерывания, поступающему с входного полюса

45 блока 1 управления, триггер 10 прерывания устанавливается в нулевое состояние и запрещает прохождение импульсов ГИ 2 через элемент И 11 на вход узла 9 измерения длиннейшего пути и на входной полюс 62 блока 3 моделей ветвей. Одновременно сигнал прерывания поступает на вход элемента 15 задержки и на вход считывания узла 7 памяти номеров моделей ветвей, из которого IIQ адресу номера модели вет- )5 ви считывается номер ветви сети, Последний номер ветви поступает на вход дешифратора 19 сравнения кодов и через элемент ИЛИ 13 — на адресный вход узла 8 памяти, После того, как будет выполнено считывание номера ветви из узла 7 памяти, на выходе элемента 15 задержки вырабатывается задержанный сигнал прерывания, который поступает на вход записи узла 8 25 памяти. По этому сигналу в узел 8 памяти записывается метка "1", характе— ризующая свершение процесса временного моделирования длительности данной ветви. После того, как будет записана 30 метка свершения, с выхода элемента

16 задержки задержанный сигнал прерывания поступает через полюс 56 в блок 2 формирования топологии, В этот же момент времени с выхода узла

7 памяти номера моделируемой ветви (полюс 52) в блок 2 формирования топологии поступает номер рассматриваемой ветви, Результатом процесса анализа пре- 10 рывания в блоке 1 управления является выдача номера рассматриваемой ветви (полюс 52) и сигнала начала анализа свершения ветви (полюс 56) в блок 2 формирования топологии, 45

Код номера рассматриваемой ветви с полюса 52 поступает на адресный вход узла 77 памяти конечного узла, а сигнал начала анализа ветви с полюса 56 поступает на единичный вход триггера 85, устанавливая его в единичное состояние, Единичное состояние триггера 86 разрешает прохождение импульсов ГИ 1 (полюс 66) и ГИ 2 (полюс 67) через элементы И 107 и 105.

Кроме того, сигнал начала анализа ветви поступает на вход элемента 92 задержки и на вход считывания узла

77 па ати. С приходом сигнала выборки

81

12 в узел 77 памяти по адресу номера ветви, вызвавшей прерывание„происхо— дит считывание ячейки памяти, в которой записан номер конечного узла рассматриваемой ветви, Код считанного конечного узла с выхода узла 77 памяти поступает на адресный вход узла

81 памятй первой входящей ветви и на информационный вход регистра 84 конечного узла. Через время задержки, достаточное для считывания информации из узла 77 памяти, сигнал начала анализа ветви поступает на управляющий вход регистра 84 конечного узла и на вход считывания узла 81 памяти, По задержанному сигналу начало анализа ветви в регистре 84 происходит запись номера конечного узла ветви, а в узле 81 памяти по адресу номера конечного узла происходит считывание номера ветви, первой в списке входящих ветвей, в рассматриваемый узел, Код номера первой входящей ветви с выхода узла 8! памяти поступает через элемент ИЛИ 95 на информационный вход регистра 83 входящей ветви и записывается в него по первому импульсу

ГИ 1, поступающему на управляющий вход регистра с выхода элемента И 104.

С выхода регистра 83 код номера входящей ветви поступает на адресный вход узла 79 памяти входящих ветвей, на вход дешифратора 89 и через полюс 39 и элемент ИЛИ 29 на адресный вход узла 8 памяти блока 1 управления. Пер— вый импульс ГИ 2 поступает с выхода элемента И 105 блока 2 формирования топологии через полюс 40 и элемент

ИЛИ 30 на вход считывания узла 8 памяти ветвей блока 1 управления. Метка свершения, считанная по адресу первой ветви, поступает через полюс

54 в блок 2 формирования топологии.

Если метка отсутствует, что означает несвершение процесса моделирования длительности ветви с данным номером, то нулевой сигнал метки с полюса 54 через элементы НЕ 108 и ИЛИ 98 сбрасывает триггер 86 в нулевое состояние °

Кроме того, сигнал с выхода элемента

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

)3

13395 узле не сформирована функция И свершения цля всех входящих в него ветвей, Тогда сигнал с полюса 41 блока 1 управления через элемент ИЛИ 27 посту5 пает на единичный вход триггера 10 прерывания и одновременно через полюс

42 блока 3 моделей ветвей, — на вход элемента ИЛИ 126 узл» 110 поиска моделей ветвей, С выхода элемента ИЛИ 126 )0 сигнал поступает на входы элементов

И 114(1) и 115(l) первой модели ветви. Если первая модель закончила процесс моделирования длительности ветви и еще не анализировалась, то триг- )5 гер 113(1) будет находиться в единичном состоянии, В этом случае сигнал с выхода элемента И 115()) анализируемой модели ветви поступает через элемент ИЛИ )27 на выходной полос 45, 2 а также через элемент ИЛИ 120 — на вход дешифратора 125 адреса, который формирует код номера модели ветви на выходном полюсе 44 блока 3 моделей ветвей. Кроме того, сигнал с выхода 25 элемента И 1)5(1) в своей модели ветви устанавливает триггеры 112(1) и

113(1) в нулевое состояние. Блок. управления, получив номер анализируемой модели ветви и сигнал прерывания, Зo повторяют все ранее описанные операции: считывает из узла 7 памяти номер сформированной ветви сети, в узел 8 памяти записывает метку свершения данной ветви и передает в блок 2 фор- мирования топологии сигнал начала анализа прохождения ветви и код номера ветви. Если же в блоке 3 моделей ветвей в первой модели 109(1) ветви триггер )12(1) находится в нулевом состоянии, то сигнал с полюса 42 через элемент 126 и элемент И 114(1) поступает на входы элементов И 114(2) и 115(2) второй модели 109(2) ветви.

Если триггер !13(2) второй модели

109(2) ветви находится в единичном состоянии, то на выходе элемента И

115(2) появляется сигнал поиска прерывания в,цанной ветви, По этому сигналу на выходе шифратора 125 адреса формируется код номера анализируемой модели ветви, а на выходе элемента

ИЛИ 127 формируется сигнал прерывания.

Затем блок 1 управления. повторяет все ранее описанные операции связанные с анализом прохождения ветви ° В случае, если триггер 113(2) находится в нулевом состоянии, то на выходе элемента И 114(2) второй модели 109(2) 81

l4 ветви формируется с i(1 t/ )Jl) п<и"I уl/ ший на вход элементов И 11 (3) и 1) 5(3) третьеи модели 109(3) ветви и т д.

Если же в блоке 3 моделей ветвей не содержится моделей 109 ветвей, имеющих триггер 113 в единичном состоянии, то процесс анализа свершения ветви заканчивается и начинается временное моделирование сети. В этом случае импульсы ГИ 2 (полюс 70) через элемент И ll продолжают поступать на счетный вход узла 9 измерения длиннейшего пути, а также через элемент

ИЛИ 26 и полюс 62 на входы элементов

И 119(1), 11.9(2)... l 9(п) блока

3 моделей ветвей, В случае, если сигнал метки свершения ветви с полюса 54 блока 1 управления имеет единичное значение (ветвь закончилась), то этот сигнал выдает разрешение на прохождение импульса ГИ 2 через элемент И 102 на вход считывания узла 79 памяти входящей ветви, На адресные входы уз/ ла 79 памяти в это время поступает

/ код номера первой входящей ветви в списке с выхода регистра 83. По адресу первой входящей ветви из узла 79 памяти будет считая код номера второй ветви в списке ветвей, входящих в рассматриваемый узел, который поступает через элемент ИЛИ 96 на информационный вход регистра 83 и записывается в него по второму импульсу ГИ с выхода элемента И 104, Далее по адресу второй ветви (полюс 39) и сигналу проверки свершения ветви (полюс

40) производится считывание узла 8 памяти метки свершения данной ветви, входящей в рассматриваемый узел, и если ветвь имеет метку свершения, то переходят к следующей ветви из списка входящих в узел ветвей.

Описанный процесс анализа списка ветвей, входящих в рассматриваемый узел, продолжается до тех пор, пока не будут опрошены все ветви, что спо1 собствует выполнению функции конъюнкции относительно входящих ветвей для рассматриваемого узла. В этом случае по адресу последнего номера ветви в списке из узла 79 памяти будет считана информация х, определяющая конец списка. Код х записывается в регистр

83 входящей ветви и далее поступает на вход дешифратора 89 состояния х, который путем сравнения кодов вырабатывает сигнал конца списка. Получен-.:

16

15 !

339581 ньп. сигнал проходит через элементы

ИЛИ 98 и 99 и устанавливает триггеры

86 и 87 соответственно в нулевое и единичное состояния. Сигнал с выхода

5 дешифратора 89 поступает также на вход элемента И 103, второй вход которого связан с выходом дешифратора

99 сравнения кодов. Дешифратор 90 сравнивает коды, хранящиеся в регист- 10 ре 85 конецкого узла сети и 84 конечного узла ветви. Как указывалось ра— нее, регистр 85 хранит код конечного узла сети, а регистр 84 — рассматри— ваемого узла сети, сформировавшего функцию конъюнкции свершения входящих в него ветвей в данный момент времени, Если значения этих кодов совпадают (сформирована логическая функция конъюнкции для конечного узла сети), 20 то дешифратор 90 сравнения кодов выдает разрешение на прохождение сигна— ла конца списка с выхода дешифратора

89 состояния х через элемент И 103 на выходной полюс 43 блока 2 формиро- 25 вания топологии, что соответствует концу моделирования заданной сети, В случае, если не сформирован конечный узел сети, то сигнал с выхода де-. шифратора 89 поступает через элемент

ИЛИ 93 на вход считывания узла 80 памяти первой выходящей ветви, на адресный вход которого в этот момент времени поступает код номера сформированного узла сети. Вновь начинается описанный процесс подготовки к временному моделированию длительностей тех ветвей, которые выходят из данного сформированного узла. Описанные процессы подготовки ветвей к времен- 40 ному моделированию их длительностей и анализа ветвей, закончивших процесс временного моделирования, будут чередоваться в указанном порядке до тех пор, пока не будет сформирован задан- 45 ный узел сети. B этом случае на вход ной полюс 43 блока 1 управления поступает сигнал индикации результата расчета. Сигнал индикации результата расчета с полюса 43 блока 1 управления поступает на вход элемента И 23 и через элемент ИЛИ 28 — на вход элемента И 12 блока 1 управления.

В данный момент времени в узле 9 измерения длиннейшего пути содержится код величины длиннейшего кути моделируемой сети, Если на входном полюсе

51 блока 1 управления отсутствует сигнал полного резерва, то режим вычисления закончен и содержимое узла

9 измерения длиннейшего пути через элемент И 12 выдается на выходной полюс 74 блока 1 управления ° Если же на полюсе 51 присутствует сигнал полного резерва, то сигнал с полюса 43 поступает на вход элемента И 23, на втором входе которого с полюса 51 присутствует разрешающий сигнал, Сигнал с выхода элемента И 23 поступает на единичный вход триггера 20, устанавливая его в единичное состояние, Единичный выход триггера 20 разрешает прохождение импульсов измерительной серии (ГИ 2) через элемент И 22 на счетный вход вычитания узла 9 измерения линейного пути.

Одновременно разрешающий сигнал с единичного выхода триггера 20 поступает на вход элемента И 25 и разрешает прохождение сигнала с выхода дешифратора 19 сравнения кодов. 3апрещающий потенциал с нулевого выхода триггера 20 поступает на элемент

И 11 и запрещает прохождение импульсов измерительной серии на счетный вход суммирования . узла 9 измерения длиннейшего пути. Сигнал с выхода элемента И 23 через элемент 34 задержки поступает на вход обнуления узла 8 памяти„ во все ячейки которого записываются нулевые метки свершения ветвей.

Одновременно сигнал с выхода элемента 34 задержки поступает на входной полюс 58 блока 2 формирования топологии, а также через элемент 35 задержки — на входной полюс 59 блока

2 формирования топологии. Элемент 35 задержки задерживает сигнал, поступающий на его вход, на время, достаточное для обнуления узла 8 памяти.

Сигнал с входного полюса 58 блока

2 формирования топологии через элемен" ты ИЛИ 98 и 101 устанавливает триггеры 86 и 87 в нулевое состояние, а в регистр 84 записывается код "0", в результате этого блок 2 моделирования топологии установлен в исходное состояние, Далее в устройстве начина-. ется повторное моделирование сети от начального узла сети к конечному.

Сигнал с входного полюса 59 блока

2 формирования топологии через элементы ИЛИ 100 и 99 поступает на единичный вход триггера 87, устанавливая его в единичное состояние. Единичное состояние триггера 87 разрешает про)7 133958 хождение серии импульсов I H l (полюс

66) и ГИ 2 (полюс 67) соответственно через элементы И 106 и 107, Кроме то„ о, сигнал с выхода элемента ИЛИ 100

5 поступает на вход элемента 91 задерж .и и на вход считывания узла 76 памяти начальных узлов. При поступлении сигнала считывания в узле 76 памяти происходит считывание ячейки памяти по адресу номера ветви, выходящей иэ начального узла сети, код которой присутствует на полюсе 71, Так как выбранная ветвь выходит из начального узла сети, то на выходе узла 76 памя- )5 ти появится код начального узла сети, который поступает через элемент ИЛИ

94 на адресный вход узла.80 памяти первой выходящей ветви, В это же время на вход считывания узла 80 памяти поступает через элемент ИЛИ 93 сигнал с выхода элемента 91 задержки, В результате этого из узла 80 памяти считывается код номера первой ветви из списка выходящих ветвей из началь- 25 ного узла сети, Код первой ветви, выходящей из начального узла, с выхода узла 80 памяти поступает через элемент ИЛИ 95 на информационный вход регистра 82 выходящей ветви. При этом ч0 производится подготовка к временному моделированию длительности первой. ветви, выходящей из начального узла сети, Затем определяются номера следующих ветвей из списка ветвей выходя35 щих из начального узла сети, с после-. дующей подготовкой к временному моделированию их длительностей. Далее моделирование сети в устройстве выполняется аналогично, моделирование длительностей ветвей сменяется формированием топологии заданной сети. Однако имеются следующие отличия: узел 9 и -и ер ения длиннейшего п ути работает в режиме вычитания; ттрн определении 45 номера свершившейся ветви по сигналу прерывания (полюс 45) в блоке 1 управления осуществляется сравнение кода номера ветви считанного из узла 7 памяти с кодом номера заданной ветви из регистра 17, Так по сигналу прерывания, поступающему из блока 3 моделей ветвей (полюс 45), в узле 7 памяти блока 1 управления по адресу номера модели ветви (полюс 44) произво— дится считывание номера сформированной ветви. Код этой ветви поступает на дешифратор 19 и сравнивается с. кодом номера заданной ветви, хранящем1

18 ся в регистре 17 номера заданной ветви.

Если код номера заданной ветви (регистр 17) не совпадает с кодом номера ветви, считанной из узла 7 памяти номеров моделируемых ветвей, то устройство продолжает работу без изменений, Если же код номера заданной ветви регистр 17) совпадает скодом иомера ветви, считанного иэ узла 7 памяти, то в устройстве сформирован временной интервал, равный величине раннего окончания заданной ветви, и в узле

9 изменения длиннейшего пути содержится код разности величины длиннейшего пути сети и величины раннего окончания заданной ветви, В этом случае на выходе дешифратора 19 сравнения кодов вырабатывается сигнал равенства. Сигнал с выхода дешифратора 19 проходит через элемент И 25, на втором входе которого присутствует разрешение с выхода триггера 20, и устанавливает триггер 21 обратного хода в единичное состояние.

Единичное состояние триггера 21 через полюс 65 в блоке 4 формирования топологии запрещает работу блока 2 формирования топологии, выдавая запрет на полюс 60. Кроме того, единичный выход триггера 21 разрешает про- . хождение сигнала с выхода. дешифратора

1 8 сравнения кодов через элемент И 24.

Сигнал равенства кодов с выхода элемента И 25 поступает в блок 4 формирования топологии (полюс 75) и устанавливает триггеры 86 и 87 в исходное состояние. Этот же сигнал с выхода элемента И 25 через элемент 33 задержки поступает на входной полюс

63 блока 3 моделей ветвей и входной полюс 63 блока 4 формирования топологии. Сигнал с полюса 63 блока 3 моделей ветвей через элементы ИЛИ 121(1), 121(2),.. °, 121(n) и 122(1), 122(2), . ° °, 1 22 (п) устанавливает триггеры

112(1) 112(2), °,,112(п) и 113(1), )!3(2)...,,113(п) в нулевое состояние.

В результате все модели ветвей устанавливаются в исходное состояние.

Сигнал с полюса 64 блока 4 формирования топологии поступает на вход триггера 87 и .устанавливает его в единичное состояние. Разрешающий сигнал с выхода триггера 87 разрешает прохождение импульсов ГИ 1 (полюс 68) l9 13395 и I ll 2 (полюс 69) соответственно че— рез элементы И 106 и 107, На входах элементов И 104-107 при этом присутст-. вует также разрешающий сигнал с полю5 са 65. Кроме этого, сигнал с выхода элемента И1И 100 поступает на вход элемента 91 задержки и на вход считывания узла 76 памяч .и конечных узлов.

На адресный вход узла 76 памяти с по- 10 люса 73 поступает номер ветви, входящей в конечный узел сети, поэтому по сигналу считывания из узла 76 памяти будет считан код конечного узла сети, Код конечного узла сети поступает че- 15 рез элемент ИЛИ 94 на адресный вход

80 памяти первой входящей ветви. В

1 это же время сигнал с выхода элемента 91 задержки, задержанный на время, достаточное для считывания информации с узла 76 памяти, через элемент KIH 93 поступает на вход считывания узла 80 памяти. iIo этому сигналу осуществляется считывание номе—

:ра первой ветви в списке ветвей, вхо- 25 дящих в конечный узел сети. Номер первой ветви с выхода узла 80 памяти поступает через элемент 95 на информационный вход регистра 82 входящей ветви и записывается в него по перво- З0 му импульсу ГИ 1, поступающему с выхода элемента И 106 на управляющий вход регистра. Записанный код первой входящей ветви с выхода регистра 82 поступает на адресный вход узла 78 памяти, на вход дешифратора 88, а так-. же через входной полюс 46 блока 1 управления и элемент ИЛИ 31 на адресный вход узла 6 памяти длительностей ветвей, на информационный вход узла 40

7 памяти и на вход дешифратора 18.

Если поступающий номер ветви отличается от номера ветви, записанного в регистре 17 номера заданной ветви, то импульс 1 И 2 поступает с выхода эле- 45 мента И 107 на вход считывания узла

78 памяти. По импульсу ГИ 2 и адресу номера первой ветви считывается .номер второй ветви, входящей в тот же конечный узел. Одновременно импульс

ГИ 2 с выхода элемента И 107 через входной полюс 47 блока 1 управления (элемент ИЛИ 32) поступает на вход считывания узла 6 памяти длительностей ветвей, вход элемента 14 задержки

55 и на входной полюс 38 поиска свободных моделей ветвей блока 3 моделей ветвей. Считанный код длительности, данной ветви с выхода узла 6 памяти

81

20 поступает через полюс 61 H I)J|OK 3 моделей ветвей. По сигналу, поступающему с полюса 39, в блоке 3 моделей ветвей определяется номер свободной модели ветви, в формирователь 111 временных интервалов которой загружается код длительности ветви. Код номера выбранной ветви с блока 3 моде— лей ветвей через полюс 44 поступает на адресный вход узла 7 памяти блока

1 управления. По сигналу с выхода элемента 14 задержки в узел 7 памяти записывается номер ветви по адресу номера модели ветви, поступающего с полюса 44 блока 3 моделей ветвей.

Считанный код номера второй ветви, входящей в конечный узел сети, с выхода узла 78 памяти через элемент

ИЛИ 9 5 на информационный вход регистра 82 входящих ветвей. По второму импульсу ГИ 1, поступающему с выхода элемента И 106, код номера второй ветви записывается в регистр 82. Записанный номер второй ветви с выхода регистра 82 поступает на адресный вход узла 78 памяти, на вход дешифратора

88 и через входной полюс 46 блока 1 управления (элемент ИЛИ 31) — на адресный вход узла 6 памяти, на информационный вход узла 7 памяти и на вход дешифратора 18 сравнения кодов.

Если номер рассматриваемой ветви отличается от номера ветви, хранящегося в регистре 17, то по второму импульсу

ГИ 2, поступающему с выхода элемента. .И 107, с узла 78 памяти считывается код номера третьей ветви. Одновремен|но импульс с выхода элемента И 107 через входной полюс 47 блока 1 управления (элемен ИЛИ 32) поступает на вход считывания узла 6 памяти и на вход элемента 14. задержки, а также через полюс 38 — в блок 3 моделей ветвей. Считанный код длительности рассматриваемой ветви с выхода узла 6 памяти поступает через полюс 61 в блок 3 моделей ветвей, По сигналу, поступающему с полюса 38, в блоке 3 моделей ветвей осуществляется поиск свободной модели ветви и загрузки ко;, да длительности рассматриваемой ветви в формирователь временных интервалов найденой модели ветви. Номер найденой модели ветви с блока 3 моделей ветвей через полюс 44 поступает на адресный вход узла 7 памяти блока управления. По сигналу, поступающему с выхода элемента 14 задержки, в

21 3395 узел 7 памяти записывается код номера ветви по адресу номера выбранной модели ветви. Так осуществляется подготовка ветвей, входящих в конечный

5 узел, к процессу временного моделирования длительностей до тех пор, пока не будет подготовлена к процессу моделирования длительности последняя ветвь из списка ветвей, входящих в ко-!0 нечный узел. По адерсу номера последней ветви из списка входящих ветвей из узла 78 памяти будет считан код х (метка окончания списка), который записывается по очередному импульсу

ГИ 1 в регистр 82. В этом случае в схеме сравнения кодов определяется информация о конце списка ° Дешифратор

88 формирует сигнал, который через элемент ИЛИ 101 устанавливает триггер 87 в нулевое состояние, этот же сигнал с выхода дешифратора 88 через элемент ИЛИ 56 и полюс 50 блока 4 формирования топологии поступает в блок 1 управления. Сигнал с входного 25 полюса 50 блока 1 управления через элемент ИЛИ 27 поступает на вход триггера 10 и устанавливает его в еди— ничное состояние, Одновременно сигнал с выхода элемента ИЛИ 27 поступает через полюс 42 поиска прерывания в блок 3 моделеи ветвей.

По сигналу, поступаюшему с полюса

42, в блоке 3 моделей ветвей производится поиск моделей ветвей, закон35 чивших процесс временного моделирования длительностей ветвей. Если в блоке 3 моделей ветвей нет моделей ветвей, закончивших процесс моделирования длительности ветвей, то разрешающие сигналы с выходов триггеров

10 и 20 разрешают прохождение импульсов ГИ 2 (полюс 70) через элемент

И 22 на вход вычитания узла 9 измерения длиннейшего пути и одновременно через элемент ИЛИ 26 (полюс 26) в блок 3 моделей ветвей.

Импульсы ГИ 2 с выхода элемента

И 22 поступают на вход узла 9 измерения длиннейшего пути и в блок 3 моде50 лей ветвей до тех пор, пока одни или несколько формирователей временных интервалов моделей ветвей не закончат процесс временного моделирования длительности ветви (ветвей). В этом

55 случае блок 3 моделей ветвей опреде-.. ляет номер ветви, формирователь 111 временных интервалов которой закончил процесс моделирования длительности.

81 22

Номер найденной модели ветви поступает через полюс 44 из блока 3 моделей ветвей на адресный вход узла 7 памяти блока 1 управления. Одновременно с блока 3 моделей ветвей через полюс

45 поступает сигнал прерывания на вход триггера 10 и устанавливает его в нулевое состояние, так как импульсы ГИ 2 через элемент И 22 не проходят. Сигнал прерывания с полюса 45 поступает на вход считывания узла 7 памяти и на вход элемента 15 задержки.

С узла 7 памяти по сигналу прерывания считывается номер ветви, процесс моделирования длительности которой за кончился. По адресу номера ветви, поступающему с выхода узла 7 памяти через элемент ИЛИ 13 в узел 8 памяти меток свершения ветви, и по сигналу с выхода элемента 15 задержки производится запись метки "1". Сигнал с выхода элемента 16 задержки поступает через полюс 57 в блок 4 формирования топологии, Сигнал начала анализа свершения ветви с полюса 57 блока 4 формирования топологии поступает на вход триггера 86 и устанавливает его в единичное состояние. Разрешающий сигнал с выхода триггера 86 разрешает прохож дение импульсов ГИ 1 (полюс 68) и

ГИ 2 (полюс 69) соответственно через элементы И 104 и 105. Одновременно сигнал с полюса 57 поступает на вход элемента 92 задержки и на вход считывания узла 77 памяти, на адресный

М вход которого с узла 7 памяти блока

1 управления (полюс 53) поступает но.— . мер ветви, вызвавшей прерывание процесса временного моделирования. По сигналу выборки из узла 77 памяти считывается код номера началЬного узла рассматриваемой ветви. Номер. начального узла с выхода узла 77 памя-. ти поступает на адресный вход узла

81 памяти и на информационный .вход регистра 84 начального узла. Задержан-. ный сигнал с выхода элемента 92 задержки поступает на вход считывания узла 81 памяти первой исходящей ветви и на управляющий вход регистра 84.

Код начального узла, считанного с узла 77 памяти, записывается в регистр

84, а с узла 81 памяти считывается код номера первой ветви из списка ветвей, выходящих из рассматриваемого узла. Считанный код номера ветви с выхода узла 81 памяти через элемент

23 ваемого узла, Описанный процесс анализа списка ветвей, выходящих из рассматриваемого узла, продолжается до тех пор, пока не будут опрошены все ветви списка, что соответствует выполнению функции конъюнкции относительно выходящих из узла ветвей, В этом случае по адресу последнего номера ветви в списке из узла 79 памяти будет считана информация х, определяющая конец списка, Код х записывается в регистр 83 выходящей ветви и далее поступает на вход дешифратора 89 состояния х, который путем сравнения кодов вырабатывает сигнал конец списка. Полученный сигнал с выхода дешифратора 89 через элементы ИЛИ 98 и 99 устанавливает триггеры 86 и 87 соответственно в нулевое и единичное состояния, Сигнал с выхода дешифратора 89 поступает так же через элемент ИЛИ 93 на вход считывания узла 80 памяти первой входящей ветви. В это же время, на адресный вход узла 80 памяти поступает код номера сформированного узла с выхода регистра 84. По сигналу, поступающему на вход считывания узла 80 памяти, определяется номер первой ветви из списка ветвей„ входящих в рассматриваемый узел.

133958

Ш!1! 97 поступает на информационный вход регистра 83 выходящей ветви. По первому импульсу ГИ 1, поступающему с выхода элемента 104, в регистр 83

5 записывается код первой ветви, считанной из узла 81 памяти, Код номера ветви, записанного в регистре 83, поступает на вход дешифратора 89, на адресный вход узла 79 памяти и через входной полюс 48 блока 1 управления (элементы ИЛИ 29 и 13) на адресный вход узла 8 памяти блока 1 управления

Далее первый импульс ГИ 2 с выхода элемента И 105 поступает через полюс

49 в блок 1 управления, Импульс ГИ 2 с полюса 49 поступает через элемент

ИЛИ 30 на вход считывания узла 8 памяти. Считанная метка свершения ветви с выхода узла 8 памяти поступает на входной полюс 55 блока 4 формирования топологии. Если метка свершения ветви отсутствует, то сигнал с полюса 55 через элементы НЕ 108 и ИЛИ 98 поступает на вход тригге- 25 ра 86 и устанавливает его в нулевое состояние. Одновременно сигнал с выхода элемента НЕ 108 через элемент

ИЛИ 98 поступает на входной полюс 50 блока 1 управления ° Сигнал с полюса

50 через элемент ИЛИ 27 поступает на вход установки в единичное состояние триггера 10 блока 1 управления, устанавливая его в единичное состояние. Одновременно сигнал с выхода эле35 мента ИЛИ 27 блока 1 управления по-. ступает через полюс 42 в блок 3 моделей ветвей. По сигналу поиска прерывания, поступаюшему с полюса 42 в блоке 3 моделей ветвей, производится поиск моделей ветвей, закончивших процесс моделирования.

Если же сигнал метки свершения ветви с полюса 55 блока 4 формирователя топологии имеет единичное состояние, т.е. процесс формирования длительности для ветви закончился, то он разрешает прохождение импульса ГИ 2 через элемент И 102 с выхода элемента

И 105 на вход считывания узла 79 памяти. В это же время с выхода регистра 83 код номера первой ветви из списка ветвей, выходящих из рассматриваемого узла, поступает на адресный вход узла 79 памяти. По адресу первой

55 выходящей ветви из узла 79 памяти будет считан код номера второй ветви в списке ветвей, выходящих из рассматриваемого узла. Этот код поступает! 24 через элемент 1%!!! 97 на информационный вход регистра 83и записывается в него с приходом второго импульса

ГИ 1 с выхода элемента !04 ° Далее по адресу второй ветви (полюс 48) с по— люса 49 производится считывание из узла 8 памяти метки свершения данной ветви, Если вновь имеется метка свершения, то переходят к следующей вет— ви из списка выходящих из рассматри-.

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

Устройство для определения длиннейшего пути в сетях, содержащее блок управления, первый блок формирования топологии, блок моделирования ветвей, генератор тактовых импульсов, первый выход которого подключен к первому тактовому входу первого блока формиро-ЗО вания топологии, второй выход генератора тактовых импульсов подключен к второму тактовому входу первого блока формирования топологии и .к тактовому Bxo,tjÓ блока УпРавления, выходы с 35 первого по пятый которого подключены соответственно к входам признака начала анализа прохождения ветви, признака начала прохождения ветви, номера анализируемой ветви первого блока 40 формирования топологии и к входам кодов длительности ветви и измеряемой серии блока моделирования ветвей, выходы номера модели ветви и выход прерывания блока моделирования ветвей подключены соответственно к первому и второму входам задания режима блока управления, первый информационный вход устройства подключен к входу кода номера ветвей, выходящих из началь5п ного узла моделируемой сети, первого блока формирования топологии, вхоц

-запуска устройства подключен к входу запуска первого блока формирования . топологии, причем блок управления со- 55 держит узел измерения длиннейшего пути, триггер прерывания, с первого по третий узлы памяти, с первого по третий элементы задержки, два элемен25 1339 дешифратор 18 сравнения кодов блока

1 управления по результату сравнения двух кодов формирует сигнал, который поступает через элементы И 24 и ИЛИ

28 на вход элемента И 12. В данный

5 момент времени в узле 9 измерения длиннейшего пути из величины длиннейшего пути сети будет дополнительно вычтена еще величина длиннейшего пути из конечного узла сети в конечный узел рассматриваемой ветви„ Код> хранящийся в узле 9, соответствует величине полного резерва ветви„ номер которой записан в регистре 17 номера заданной ветви, Сигнал, поступающий с выхода дешифратора 18, разрешает прохождение кода величины полного резерва с выхода узла 9 измерения длиннейшего пути через элемент И 12 на выходной полюс

74 блока 1 управления, Формула изобретения

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

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

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

) 33958 шестой, седьмой и восьмой выходы ко-торого подключены к входам поиска ,прерывания, сброса моделей ветвей и поиска свободной модели ветви блока

5 моделирования ветвей, выходы с девятого по четырнадцатый блока управления подключены соответственно к входам признаков конца определения длиннейшего пути, полного резерва и прямого прохода первого блока формирования топологии и к входам признака обратного прохода, сброса моделей ветвей, индикации результата расчета второго блока формирования топологии, пятнад- )5 цатый выход блока управления подключен к выходу результата устройства, входы с четвертого по четырнадцатый задания режима блока управления подключены сООтВетстВеннО к Выходам индикации результата расчета, поиска прерывания, номера анализируемой ветви, поиска свободной модели ветви, номера изготавливаемойк моделированию ветви первого блока формирования топологии и к выходам поиска прерывания, номера анализируемой ветви, номера подготавливаемой к моделированию ветви, проверки прохождения ветви, поиска свободной модели ветви второго блока формирования топологии, вход кода номера ветви, резерв которой надо определить, устройство подключено к информационному входу блока управления, причем блок управле35 ния дополнительно содержит триггер длиннейшего пути, регистр, -риггер обратного хода, первый и второй дешифраторы, четыре элемента И, шесть элементов ИЛИ и три элемента задерж- 4> ки, при этом третий вход задания режима блока управления подключен к первому входу третьего элемента И, четвертый вход задания режима блока управления подключен к втоРому входу 45 третьего элемента И и к первому входу третьего элемента ИЛИ, входы с пятого по четырнадцатый задания режима блока управления подключены соответственно к первому входу четвертого элемента ИЛИ, к первому входу пятого элемента ИЛИ, к первому входу шестого элемента ИЛИ, к первому входу седьмого элемента ИЛИ, к первому входу восьмого элемента ИЛИ, к .второму

55 входу четвертого элемента ИЛИ, к второму входу пятого элемента ИЛИ, к второму входу седьмого элемента ИЛИ, к второму входу восьмого элемента! 28

И1)И и к второму входу шестого элемента HJIH выход Второго блока памяти подключен к третьему выходу блока управления и к первому входу первого дешифратора, выход которого подключен к первому входу четвертого элемента

И, выход четвертого элемента ИЛИ подключен к входу установки в "1" триг29 которого подключен к второму входу второго элемента ИЛИ и к тактовому входу узла измерения:длиннейшего пути, тактовый вход блока управления подключен к третьему входу шестого

339581 3О элемента И, выход восьмого элемента

ИЛИ подключен к входу чтения первого узла памяти, выход пятого элемента

ИЛИ подключен к второму входу перво5 го элемента ИЛИ.

1339581

Составитель В,Смирнов

Техред M.Дидык Корректор М. Пожо

Редактор А.Ворович

Заказ 4224/40 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4,