Устройство для определения длиннейшего пути в сетях Советский патент 1987 года по МПК G06F15/173 

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

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

На фиг,1 приведена блок-схема устройства; на фиг,2 схема блока формирования топологии; на фиг.З - схема блока моделей ветвей.

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

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

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

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

40 4 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети и номеров ветвей, выходящих из исследуемого узла сети при моделировании сети в

33-35 задержки, выход 36 номера подготавливаемой к моделированию ветви блока 2, выход 37 поиска свободной модели ветви блока 2, вход 38 поиска свободной модели ветви.блока 3, выход 39 номера анализируемой ветви блока 2, выход 40 проверки прохождения ветви блока 2, выход 41 поиска прерывания блока 2, вход 42 поиска прерывания блока 3, выход 43 индикации результата расчета блока 2, выход 44 номера 45 обратном направлении (от конечного уз- модели ветви блока 3, выход 45 преры- ла к начальному). Генератор 5 импульвания блока 3, выход 46 номера подготавливаемой к моделированию ветви блока 4, выход 47 поиска свободной модели ветви блока 4, выход 48 номера анализируемой ветви блока 4, выход , 49 проверки прохождения ветви блока 4, выход 50 поиска прерывания блока .4, вход 51 режима вычисления резерва времени для заданной ветви.

Входы 52 и 53 номера анализируемой ветви сети блоков 2 и 4, входы 54 и 55 признака прохождения ветви блоков 2 и 4ji входы 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 формирования топологии или блоком 4 формирования топологии с блоком 3 моделей ветвей устройства в. процессе моделирования и определения длиннейшего пути в исследуемой сети или вычисления полного резерва времени выбранной ветви в исследуемой сети, Блок 2 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети и номеров ветвей, выходящих из исследуемого узла сети, а также для определения момента окончания моделирования сети

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

4 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети и номеров ветвей, выходящих из исследуемого узла сети при моделировании сети в

обратном направлении (от конечного уз- ла к начальному). Генератор 5 импульQ

5

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

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

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

Узел 9 измерения длиннейшего пути блока 1 управления предназначен для формирования величины длительности длиннейшего пути сети и для формирования величины полного резерва заданной ветви сети,

Регистр 17 блока 1 управления предназначен для хранения кода номера заданной ветви полного резерва, который необходимо определить,. Дешифратор 18 сравнения кодов блока 1 управления предназначен для сравнения кода номера заданной ветви сети, хранящегося в регистре 17 номера заданной ветви, с кодом номера подготавливаемой к моделированию ветви, по- ступающего с входного полюса 36 блока 1 управления. Дешифратор 19 сравнения кодов блока 1 управления предназначен для сравнения кода номера заданной ветви сети, хранящегося в регистре 17 номера заданной ветви, с кодом номера анализируемой ветви, поступающего с выхода узла 7 памяти блока 1 управления,

Триггер 10 прерывания предназначен для организаций временного разделения между процессом временного моделирования длительностей ветвей сети и процессом анализа топологии моделируемой сети. Триггер 20 длинней- шего пути -ИЗ режима суммирования в режим вычитания путем разрешения прохождения импульсов ГИ.2, поступающих с полюса 70 блока 1 управления, Три1- гер 21 обратного хода предназначен для организации временного разделения работы блока 2 формирования топологии (при моделировании сети от начального узла к конечному) и работы блока 4 формирования топологии (при обратном моделировании сети от конечного узла к начальному).

Блок 2 содержит узел 76 памяти адресов начальных узлов ветвей сети, узел 77 памяти адресов конечных узлов ветвей сети, узел 78 памяти адресов рыходящих ветвей узлов сети, узел 79 памяти адресов входящих ветвей узлов сети, узел 80 памяти адресов первой

5

0 5 О

о 5 0

g

5

выходящей ветви узлов сети, узел 81 памя 1 и адресов первой входящей ветви узлов сети, регистр 82 адреса выхоДя- щей ветви, регистр 83 адреса входящей ветви, регистр 84 адеса конечного узла ветви, регистр 85 конечного узла сети, триггеры 86 и 87, дешифраторы 88 и 89, дешифратор 90 сравнения кодов, элементы 91 и 92 задержки, элементы ИЛИ 93-101, элементь: И 102-107 и элементы НЕ 108.

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

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

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

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

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

Триггеры 86 и 87 предназначены для разнесения во времени процесса

поиска ветвей входящих в узлы сети, и поиска ветвей, выходящих из узлов сети.

Блок 3 содержит п моделей 109 вет- вей (где п - количество ветвей в максимальном сечении сети) и узел 110 поиска моделей ветвей. Каждая модель 109 ветви состоит из формирователя 111 временных интервалов, триггеров 112 и 113, элементов И 114- 119, элементов ИЛИ 120-122п элементов 123 и 124 задержки.

Узел 109 поиска моделей ветвей содержи т шифратор 125 адреса и элементы g ливает триггер 87 в единичное состоя- ИЛИ 126 и 127,ние. Единичное состояние триггера 87

разрешает прохождение серии импульсов ГИ 1 и ГИ 2 соответственно через элеУстройство работает следующим образом,

В узлы 76-8 памяти блоков 2 и 4

формирования топологии в виде списков 2Q Пуск поступает с полюса 72 блока заносится информация о топологии моде- 2 формирован ш топологии через эле- лируемой сети. Регистры 82-84 и узел 9-измерения длиннейшего пути предварительного обнулены, в регистр 85 блока 2 заносится код конечного узла сети, в регистр 85 блока 4 заносится код начального узла сети, а в узел 6 памяти длительностей ветвей заносятся коды,длительностей ветвей моделируемой сети. При необходимости опреде-дд держки и поступает через элемент ИЛИ ления резерва одной из ветвей сети, 93 на вход считывания узла 80 памяти.

менты И 106 и 107. Кроме того, сигнал

мент ИЛИ 100 на вход элемента 91 задержки. Так как ветвь выбрана-как выходящая из начального узла сети, то 25 код начального узла сети поступает через элемент ШШ 94 на адресный вход узла 80 памяти первой выходящей ветви. Через время задержки сигнал Пуск появляется на выходе элемента 91 зана вход 51 блока 1 управления поступает соответствующий признак. В регистр 17 номера заданной ветви заносится код номера ветви, полный резерв которой необходимо определить.

Так как триггер 21 установлен в нулевое состояние, то на входной полюс 60 блока 2 формирования топологии с нулевого выхода триггера 2 поступает сигнал, разрешающий его работу, а с единичного выхода триггера 21 на входной полюс 65 блока 4 формирования топологии поступает сигнал, запрещающий работу блока 4 формирования топо- лог ии. Одновременно сигнал с единичного выхода триггера 21 запрещает прохождение сигнала с выхода дешифратора 18 сравнения кодов через элемент И 24 блока 1 управления, С нулевого выхода триггера 20 разрешающий сигнал поступает на вход элемента И 11, а с единичного выхода запрещающий сигнал поступает на вход элемента И 22, а также на вход элемента И 25, тем самым запрещая прохождение сигнала с выхода дешифратора 19 сравнения кодов

После начальной установки на полюс 71 блока 2 формирования тополо

гии подается код номера ветви, выходящей из узла, принятого за начальный узел сети, а на полюс 73 блока 4 формирования топологии подается код номера ветви, входящей в узел, принятый за конечный узел сети. Начальный узел сети, таким образом, определяется по адресу номера ветви в узле 75 памяти блока 2 формирования топологии. В некоторый момент времени сигнал Пуск, поступающий на полюс 72 блока 2 формирования топологии, проходит через элементы ИЛИ 98 и 99 и устанавменты И 106 и 107. Кроме того, сигнал

Пуск поступает с полюса 72 блока 2 формирован ш топологии через эле- держки и поступает через элемент ИЛИ 93 на вход считывания узла 80 памяти.

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

0

5

0

5

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

Затем импульс ГИ 2, сдвинутый относительно импульса ГИ 1, поступает с выхода элемента И 107 на вход счи- тьгоания узла 78 памяти и по адресу первой ветви, выходящей из начального узла сети, осуществляет выборку номера второй ветви, выходящей из того же узла.

Одновременно импульс ГИ 2 поступает через выходной полюс 37 блока 2 формирования топологии и затем через элемент ИЛИ 32 - на вход считьшания узла b памяти длительности ветви, на вход элемента 14 задержки блока 1 управления и на входной полюс 38 поиска свободной модели ветви блока 3 моделей ветвей. По сигналу ГИ 2 и адресу номера первой выходящей из узла ветви, хранящемуся в регистре 81, осуществляется считьшание кода длительности этой ветви из узла 6 памяти длительностей ветвей. Одновременно сигнал поиска свободной модели ветви с полюса 38 поступает на входы элементов И 116(0 и 117(1) первой модели 109(1) ветви блока 3 моделей ветвей. Так как все модели ветви свободньг, то триггер 112(1) будет находиться в нулевом состоянии и сигнал с выхода элемента И 117(1) через элемент 124 задержки поступает на единчиный вход

10

15

20

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

Далее считанный по адресу номера первой выходящей ветви из узла 80 памяти выходящих ветвей блока 2 формирования топологии номер следующей ветви в списке выходящих из узла ветвей поступает на информационный вход ретриггера 112(1). Через время задержки, 25 82 и с приходом второго импульса ГИ 1 записывается в указанный регистр, Записанный в регистр 82 код поступает вновь на адресный вход узла 78 памяти, а также через полюс 36 блока 2 формирования топологии и далее через элемент ИЛИ 31 на адресный вход узла 6 памяти длительности, на вход элемента 14 задержки блока 1 управления и на входной полюс 38 поиска свободной модели ветви блока 3 моделей ветвей, С приходом второго г1мпульса ГИ 2 из узла 6 памяти дли. тельностей считывается код длительное ти второй исходящей из узла ветви. Этот код поступает через полюс 6J блока 3 моделей ветвей на входы элементов И 1 1 8(1 ), 118(2),..,,118(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 38 блока 3 моделей ветвей на входы эле- ментов И 116(1) и 117(1) поступает сигнал поиска свободной модели ветви. Так как триггер 112(1) первой модели ветви находится в единичном состоянии, означающем занятость модели вет

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

35

са ГИ 1 записывается в указанный регистр, Записанный в регистр 82 код п ступает вновь на адресный вход узла 78 памяти, а также через полюс 36 блока 2 формирования топологии и далее через элемент ИЛИ 31 на адресный вход узла 6 памяти длительности, на вход элемента 14 задержки блока 1 управления и на входной полюс 38 пои ка свободной модели ветви блока 3 моделей ветвей, С приходом второго г1мпульса ГИ 2 из узла 6 памяти длительностей считывается код длительно ти второй исходящей из узла ветви. Этот код поступает через полюс 6J блока 3 моделей ветвей на входы элементов И 1 1 8(1 ), 118(2),..,,118(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 3 блока 3 моделей ветвей на входы эле- ментов И 116(1) и 117(1) поступает сигнал поиска свободной модели ветви Так как триггер 112(1) первой модели ветви находится в единичном состоянии, означающем занятость модели вет

40

50

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

ра выбранной модели ветви (в данном слу- И 117(2) поступает на вход элемента чае первой) номер ветви, длительность И 118(2), и в формирователь 111(2) которой внесена уже в формирователь 1Г1(1) временного интервала данной мовременных интервалов заносится исход ная информация о длительности второй

5

0

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

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

5

са ГИ 1 записывается в указанный регистр, Записанный в регистр 82 код поступает вновь на адресный вход узла 78 памяти, а также через полюс 36 блока 2 формирования топологии и далее через элемент ИЛИ 31 на адресный вход узла 6 памяти длительности, на вход элемента 14 задержки блока 1 управления и на входной полюс 38 поиска свободной модели ветви блока 3 моделей ветвей, С приходом второго г1мпульса ГИ 2 из узла 6 памяти дли. тельностей считывается код длительное ти второй исходящей из узла ветви. Этот код поступает через полюс 6J блока 3 моделей ветвей на входы элементов И 1 1 8(1 ), 118(2),..,,118(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 38 блока 3 моделей ветвей на входы эле- ментов И 116(1) и 117(1) поступает сигнал поиска свободной модели ветви. Так как триггер 112(1) первой модели ветви находится в единичном состоянии, означающем занятость модели вет

0

0

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

И 117(2) поступает на вход элемента И 118(2), и в формирователь 111(2)

временных интервалов заносится исходная информация о длительности второй

исходящей из узла ветви. Одновременно сигнал с выхода элемента И 117(2) через элемент 124(2) задержки устанавливает триггер 112(2) в единичное состояние, по этому, же сигналу на вы ходе шифратора 125 адреса формируется номер второй модели ветви, который через выходной полюс 44 блока 3 моделей ветвей поступает на адресный вход узла 7 памяти номеров моделируемых ветвей, и при формировании через некоторое время сигнала на выходе элемента 14 задержки в памяти по адресу номера модели ветви записывается is 9 измерения длиннейшего пути блока 1

номер ветви, код длительности которой записан в формирователь 11I(2) временного интервала.

Так осуществляется подготовка ветвей, выходящих из начального узла, к процессу временного моделирования их длительностей до тех пор, пока не будет считан номер последней ветви из списка ветвей, выходяш,их из начального узла, По адресу номера последней ветви из списка выходящих из узла ветвей в узле 80 памяти будет считан код X (метка окончания списка номеров ветвей, выходящих из одного

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

полюс 42 блока 3 моделей ветвей. Так о ки и элемент ИЛИ 121(1) сбрасывает

как вьпюлняется моделирование длительностей ветвей, вь ходяш.их из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер 10 прерывания на- гходится в единичном состоянии, Единич- ное состояние тригтера 10 разрешает прохойгдение импульсов ГИ 2 с полюса 70 через элемент.И 11 на счетный вход

(суммирование) узлг 9 измерения длиннейшего пути, а также через элемент ИЛИ 26 и входной полюс 62 блока 3 моделей ветвей на входы элементов И 119(1), 1 19(2), . .. , П9(п) моделей ветвей 109(1), 109(2),...,109(п). Гмпульсы поступают с выходов элементов И 119(1), 119(2),... 119(п) на входы формирователей временных интервалов тех моделей ветвей, триггеры 112(1), 1 12(2), . . .,П2(п) которых находятся в единичном состоянии. Импульсы ГИ 2 поступают на вход узла

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

Сигналы с выхода формирователей 111(1), 1I1 (2), ..,,(п) временного интервала поступают на единичные входы триггеров 113(1), 113(2),..., 113(п) и устанавливают их в единичное

хода формирователя 111 поступает через элемент ИЛИ 126 на вход (1,1) поиска прерывания первой.модели 119(1) ветви и далее на входы элементов И 114(1) и 155(1). В случае, если триггер 113(1) находится в единичном состоянии (модель ветви закончила процесс временного моделирования длительности ветви), сигнал прерывания поступает с выхода элемента управления. Одновременно сигнал с выхода элемента И 115(1) через элемент ИЛИ 122(1) поступает на единичный вход триггера 112(1), устанавливая его в единичное состояние, что соответствует освобождению модели 109(1) ветви для последующих вычислений, Кро- ме того, сигнал с выхода элемента И 115(1) через элемент 123(1) задержтриггер П3(1) в нулевое состояние, а также через элемент ШШ 120(1) и полюс (1,3) сигнал с выхода элемента И 11(1) поступает на вход шифратора 125 адреса. На выходе шифратора формируется номер .данной модели ветви, Код номера модели ветви с выхода шифратора 125 адреса через входной полюс 14 блока 1 управления поступает на адресный вход узла 7 памяти моделируемых ветвей сети. По сигналу прерывания, поступающему с входного полюса 45 блока 1 управления, триггер 10 прерывания устанавливается в нулевое состояние и запрещает прохождение импульсов ГИ 2 через элемент И 11 на вход узла 9 измерения длиннейшего пути и на входной полюс 62 блока 3 моделей ветвей. Одновременно сигнал прерывания поступает на вход элемента 15 задержки и на вход считьшания узла 7 памяти номеров моделей ветвей, из которого по адресу номера модели ветви считывается номер ветви сети. Последний номер ветви поступает на вход дешифратора 19 сравнения кодов и через элемент ИЛИ 13 - на адресный вход узла 8 памяти. После того, как будет выполнено сч итьшание номера ветви из узла 7 памяти, на выходе элемента 15 задержки вырабатывается задержанный сигнал прерывания, который поступает на вход записи узла 8 памяти. По Ьтому сигналу в узел 8 памяти записывается метка 1, характеризующая свершение процесса временного моделирования длительности, данной ветви. После того, как будет записана метка свершения, с выхода элемента 16 задержки задержанный сигнал пре- рьшания поступает через полюс 56 в блок 2 формирования топологии. В этот же момент времени с выхода узла 7 памяти номера моделируемой ветви (полюс 52) в блок 2 формирования топологии поступает номер рассматриваемой ветви.

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

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

9581 в узел 77 памяти по адресу номера ветви, вг,звавшей прерывание, происходит считывание ячейки памяти, в которой записан номер конечного узла рассматриваемой ветви. Код считанного конечного узла с выхода узла 77 памяти поступает на адресный вход узла 81 памяти первой входящей ветви и на информационный вход регистра 84 конеч- ного узла. Через время задержки, достаточное для считывания информации из узла 77 памяти, сигнал начала анализа ветви поступает на управляющий

5 вход регистра 84 конечного узла и на вход считывания узла 81 памяти. По задержанному сигналу начало анализа ветви в регистре 84 происходит запись номера конечного узла ветви, а

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

5 выхода узла 81 памяти поступает через элемент ИЛИ 95 на информационный вход регистра 83 входящей ветви и записывается в него по первому импульсу ГИ I, поступающему на управляющий

0 вход регистра с выхода элемента И 104. С выхода регистра 83 код номера входящей ветви поступает на адресный вход узла 79 памяти входящих ветвей, на вход дешифратора 89 и через полюс 39

J- и элемент ИЛИ 29 на адресный вход узла 8 памяти блока 1 управления. Первый импульс ГИ 2 поступает с выхода элемента И 105 блока 2 формирования топологии через полюс 40 и элемент

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

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

-g сигнала метки свершения ветви означает, что хотя бы одна из ветвей списка, входящих в узел, не завершила процесс временного моделирования своей длительности и, следовательно, в данном

г. иггыл,

узле не сформирована функция И свсфще- ния для всех входящих в него ветвей. Тогда сигнал с полюса 41 блока управления через элемент ИЛИ 27 поступает на единичный вход триггера 10 прерывания и одновременно через полюс 42 блока 3 моделей ветвей, - на вход элемента ИЛИ 126 узла 110 поиска моделей, ветвей. С выхода элемента ИЛИ 126 сигнал поступает на входы элементов И 14(1) и 115(1) первой модели вет- вИо Если первая модель закончила процесс моделирования длительности ветви и еще не анализировалась, то триг- g ИЛИ 26 и полюс 62 на входы элементов гер 113(1) будет находиться в единич- И 119(1), 119(2),..,, 119(п) блока

5

10

ветви формируется

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

. ном состоянии, в этом случае сигнал с выхода элемента И 115(1) анализируемой модели ветви поступает через элемент ИЛИ 127 На выходной полюс а также через элемент ИЛИ 120 - на вход дешифратора 125 адреса, который формирует код номера модели ветви на выходном полюсе 44 блока 3 моделей ветвей. Кроме того, сигнал с выхода элемента И П5(1) в своей модели ветви устанавливает триггеры П2(1) и 113(1) в нулевое состояние. Блок- 1 управления, получив помер анализируемой модели ветви-и сигнал прерывания, повторяют все ранее описанные операции: считывает из узла 7 памяти номер сформированной ветви сети, в узел 8 памяти записывает метку свершения данной ветви и передает в блок 2 формирования топологии сигнал начала анализа прохождения ветви и код номера ветви. Если же в блоке 3 моделей ветвей fe первой модели 109(1) ветви триггер 112(1) находится в нулевом состоянии, то сигнал с полюса 42 через элемент 126 и элемент И 114(1) поступает на входы элементов И 114(2) и 115(2) второй модели 109(2) ветви. Если триггер 113(2) второй модели 105(2) ветви находится в единичном состоянии, то на выходе элемента И 115(2) появляется сигнал поиска прерывания в данной ветви. По этому сигналу на выходе шифратора 125 адреса формируется код номера анализируемой модели ветви, а на выходе элемента ИЛИ 127 формируется сигнал прерывания Затем блок 1 управления повторяет все ранее описанные операции, связанные с анализом прохождения ветви, В случае, если триггер 113(2) находится в нулевом состоянии, то на выходе элемента И 114(2) второй модели 109(2)

9581

14

г. иггыл,

g ИЛИ 26 и полюс 62 на входы элементов И 119(1), 119(2),..,, 119(п) блока

5

0

ветви формируется

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

5

0 О

3 моделей ветвей,

В случае, если сигнал метки свершения ветви с полюса 54 блока 1 управления имеет единичное значение (ветвь закончилась), то этот сигнал выдает разрешение на прохождение импульса ГИ 2 через элемент И 102 на вход считывания узла 79 памяти 5 входящей ветви. На адресные входы узла 79 памяти в это время поступает . код номера первой входящей ветви в списке с выхода регистра 83. По адресу первой входящей ветви из узла 79 памяти будет считан код номера второй ветви в списке ветвей, входящих в рассматриваемый узел, который поступает через элемент ШТИ 96 на информационный вход регистра 83 и записывается в него по второму импульсу ГИ 1 с выхода элемента И 104, Далее по адресу второй ветви (полюс 39) и сигналу проверки свершения ветви (полюс 40) производится считывание узла 8 памяти метки свершения ветви, входящей в рассматриваемый узел, и если ветвь имеет метку свершения, то переходят к следующей ветви из списка входящих в узел ветвей.

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

0

5

0

5

иыГ: сигнал проходит через элементы Ш1И 98 и 99 и устанавливает триггеры 86 и 87 сортветстненно в нулевое и единичное состояния. Сигнал с выхода дешифратора 89 поступает также на вход элемента И 103, второй вход которого связан с выходом дешифратора 99 сравнения кодов. Дешифратор 90 сравнивает коды, хранящиеся в регистре 85 конечного узла сети и 84 конечного узла ветви. Как указывалось ранее, регистр 85 хранит код конечного узла сети, а регистр 84 - рассматриваемого узла сети, сформировавшего 15 прохождение импульсов измерительной

функцию конъюнкции свершения входящих в него ветвей в данный момент в ремени. Если значения этих кодов совпадают (сформирована логическая функция конъюнкции для конечного узла сети), 20 то дешифратор 90 сравнения кодов выдает разрешение на прохождение сигнала конца списка с выхода дешифратора 89 состояния X через элемент И 103

на выходной полюс 43 блока 2 формиро- 25 да триггера 20 поступает на элемент

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

В данный момент времени в узле 9

измерения длиннейшего пути содержится 2 формирования топологии через эле- код величины длиннейшего пути модели- менты РШИ 100 и 99 поступает на единичный вход триггера,87, устанавливая его в единичное состояние. Единичное

руемой сети. Если на входном полюсе 51 блока управления отсутствует сигнал полного резерва, то режим высостояние триггера 87 разрешает про . 339581 6

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

серии (ГИ 2) через элемент И 22 - на счетный вход вычитания узла 9 измерения линейного пути.

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

5

0

5

0

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

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

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

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

состояние триггера 87 разрешает про17

хождение серии импульсов ГИ 1 (полюс 66) и ГИ 2 (полюс 67) соответственно -зереэ элементы И 106 и 107. Кроме то- , 0, сигнал с выхода элемента ИШ 100 поступает на вход элемента 91 задержки и на вход считывания узла 76 памяти начальных узлов. При поступлении сигнала считывания в узле 76 памяти гтроисходит считывание ячейки памяти по адресу номера ветви, выходящей из начального узла сети, код которой присутствует на полюсе 71, Так как выбранная ветвь выходит из начального

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

ти появится код начального узла сети, который поступает через элемент ИЛИ 94 на адресный вход узла.80 памяти первой выходящей ветви, В это же время на вход считывания узла 80 памяти поступает через элемент ИЛИ 93 сигнал с .выхода элемента 91 задержки, В результате этого из узла 80 памяти считывается код номера первой ветви из списка выходящих ветвей из началь- него узла сети. Код первой ветви, выходящей из начального узла, с выхода узла 80 памяти поступает через элемент ИЛИ 95 на информационный вход

Единичное состояние триггера 21 через полюс 65 в блоке 4 формирова

регистра 82 выходящей ветви. При этом ЗО топологии запрещает работу блока 2

производится подготовка к временному моделированию длительности первой ветви, выходящей из начального узла сети. Затем определяются номера следующих ветвей из списка ветвей выходя щих из начального узла сети, с последующей подготовкой к временному моделированию их длительностей. Далее моделирование . сети в устройстве выполняется аналогично, моделирование дхш- тельностей ветвей сменяется формированием топологии заданной сети. Однако имеются следующие отличия; узел 9 измерения длиннейщего пути работает в режиме вычитания; при определении номера сверщившейся ветви по сигналу прерывания (полюс 45) в блоке управления осуи1ествляется сравнение кода номера ветви считанного из узла 7 памяти с кодом номера заданной ветви из регистра 17, Так по сигналу прерывания, постлгпающему из блока 3 моделей ветвей (полюс 45), в узле 7 памяти блока 1 управления по адресу номера модели ветви (полюс 44) производится считывание номера сформированной ветви. Код этой ветви поступает на дешифратор 19 и сравнивается с кодом номера заданной ветви, хранящем-

9581

Q18

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

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

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

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

Единичное состояние триггера 21 через полюс 65 в блоке 4 формирования

топологии запрещает работу блока 2

т„ Qg

5

формирования топологии, выдавая запрет на полюс 60. Кроме того, единичный выход триггера 21 разрешает про-, хождение сигнала с выхода- дешифратора 18 сравнения кодов через элемент И 24.

Сигнал равенства кодов с выхода элемента И 25 поступает в блок 4 формирования топологии (полюс 75) и устанавливает триггеры 86 и 87 в исходное состояние. Этот же сигнал с выхода элемента И 25 через элемент 33 задержки поступает на входной полюс 63 блока 3 моделей ветвей и входной полюс 63 блока 4 формирования топологии. Сигнал с полюса 63 блока 3 моделей ветвей через элементы ИЛИ 121(1), 121 (2),..., 121 (п) и 122(1), 122(2), ..,,122(п) устанавливает триггеры 112(1), 112(2),,..,Г12(п) и 113(1), 113(2),,..,П3(п) в нулевое состояние. В результате все модели ветвей устанавливаются в исходное состояние.

Сигнал с полюса 64 блока 4 форми- рования топологии поступает на вход триггера 87 и .устанавливает его в единичное состояние. Разрешающий сигнал с выхода триггера 87 разрешает прохождение импульсов ГИ 1 (полюс 68)

и ГИ 2 (nojiKJC 69) соответстненно через элементы Н 106 и 107. На входах элементов И 104-107 при этом присутст вует также разрешающий сигнал с полюса 65. Кроме этого, сигнал с выхода элемента ИЛИ 100 поступает н а вход элемента 91 задержки и на вход считывания узла 76 памяти конечных узлов. На адресный вход узла 76 памяти с полюса 73 поступает номер ветви, входящей в конечный узел сети, поэтому по сигналу считывания из узла 76 памяти будет считан код конечного узла сети.

Код конечного узла сети поступает че- 15 номера модели ветви, поступающего с

20

полюса 44 блока 3 моделей ветвей.

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

рез элемент РШИ 94 на адресный вход

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

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

35

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

ветвей, на информационный вход узла

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

поступает через rtojiioc 61 в блок 3 г-;о делей ветвей. По сигналу, поступаниле- му с полюса 39, в блоке 3 моделей ветве11 определяется номер свободной модели ветви, в формирователь 111 временных интервалов которой загружа- :ется код длительности ветви. Код номера выбранной ветви с блока 3 моделей ветвей через полюс 44 поступает на адресный вход узла 7 памяти блока 1 управления. По сигналу с выхода элемента 14 задержки в узел 7 памяти записывается номер ветви по адресу

полюса 44 блока 3 моделей ветвей.

Считанный код номера второй ветви, входящей в конечный узел сети, с выхода узл.а 78 памяти через элемент ИЛИ 95 на информационный вход регистра 82 входящих ветвей. По второму импульсу ГИ 1, поступающему с выхода элемента И 106, код номера второй ветви записывается в регистр 82. Записанный номер второй ветви с выхода ре- гистра 82 поступает на адресный вход узла 78 памяти, на вход дешифратора 88 и через входной полюс 46 блока 1 управления (элемент ИЛИ 31) - ма ад- ресный вход узла 6 памяти, на инфор- мационный вход узла 7 памяти и на 5 ный номер второй ветви с выхода ре- гистра 82 поступает на адресный вход узла 78 памяти, на вход дешифратора 88 и через входной полюс 46 блока 1 управления (элемент ИЛИ 31) - ма ад- о ресный вход узла 6 памяти, на инфор- мационный вход узла 7 памяти и на

5

0

5

0

5

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

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

ветвь из списка ветвей, входящих в KO-|Q сы ГИ 2 через элемент И 22 не прохонечный узел. По адерсу номера последней ветви из списка входящих ветвей из узла 78 памяти будет считан код х (метка окончания списка), который записывается по очередному импульсу ГИ 1 в регистр 82. В этом случае в схеме сравнения кодов определяется информация о конце списка. Дешифратор 88 формирует сигнал, который через элемент ИЛИ 101 устанавливает триггер 87 в нулевое состояние, этот же сигнал с выхода дешифратора 88 через элемент ИЛИ 56 и полюс 50 блока 4 формирования Топологии поступает в блок 1 управления. Сигнал с входного полюса 50 блока 1 управления через элемент ИЛИ 27 поступает на вход триггера 10 и устанавливает его в единичное состояние. Одновременно сигнал с выхода элемента ИЛИ 27 посту- . пает через полюс 42 поиска прерывания в блок 3 моделей ветвей.

По сигналу, поступающему с полюса 42, в блоке 3 моделей ветвей производится поиск моделей ветвей, закончивших процесс временного моделирования длительностей ветвей. Если в блоке 3 моделей ветвей нет моделей ветвей, закончивших процесс моделирования длительности ветвей, то разрешающие сигналы с выходов триггеров 10 и 20 разрешают прохождение импульсов ГИ 2 (полюс 70) через элемент К 22 на вход вычитания узла 9 измерения длиннейшего пути и одновременно через элемент ИЛИ 26 (полюс 26) в блок 3 моделей ветвей.

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

15

20

25

30

35

40

45

50

55

дят. Сигнал прерывания с полюса 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 памяти считывается код номера первой ветви из списка вет вей, выходящих из рассматриваемого узла. Сч11танный код номера ветви с выхода узла 81 памяти через элемент

Номер на11денной модели ветви поступает через nojmic 44 из блока 3 моделей ветвей на адресный вход узла 7 памяти блока 1 управления. Одновременно с блока 3 моделей ветвей через полюс 45 поступает сигнал прерывания на вход триггера 10 и устанавливает его в нулевое состояние, так как импуль5

0

5

0

5

0

5

0

5

дят. Сигнал прерывания с полюса 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 памяти считывается код номера первой ветви из списка ветвей, выходящих из рассматриваемого узла. Сч11танный код номера ветви с выхода узла 81 памяти через элемент

23

97 поступает на информационный вход регистра 83 выходящей ветви. По первому импульсу ГИ 1, поступающему с выхода элемента 104, в рех истр 83 записывается код первой ветви, считанной из узла 81 памяти. Код номера ветви, записанного в регистре 83, поступает на вход дешифратора 89, на адресный вход узла 79 памяти и через входной полюс 48 блока 1 управления (элементы ИЛИ 29 и 13) на адресный вход узла 8 памяти блока 1 управлени Далее первый импульс ГИ 2 с выхода элемента И 105 поступает через полюс 49 в блок 1 управления. Импульс ГИ 2 с полюса 49 поступает через элемент ИЛИ 30 на вход считывания узла 8 памяти. Считанная метка свершения ветви с выхода узла 8 памяти поступает на входной полюс 55 блока 4 формирования топологии. Если метка свершения ветви отсутствует, то сигнал с полюса 55 через элементы НЕ 108

3

и ИЛИ 98 поступает на вход тригге- 25 вход дешифратора 89 состояния х, ко30

ЗЕ

40

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

Если же сигнал метки свершения ветви с полюса 55 блока 4 формирователя топологии имеет единичное состояние, т.е. процесс формирования длительности для ветви закончился, то он разрешает прохождение импульса ГИ 2 через элемент И 102 с выхода элемента И 105 на вход считывания узла 79 памяти. В это же время с выхода регистра 83 код номера первой ветви из списка ветвей, выходящих из ра:ссматривае- мого узла, поступает на адресный вход узла 79 памяти. По адресу первой выходящей ветви из узла 79 памяти будет считан код номера второй ветви в списке ветвей, выходящих из рассмат- сиваемого узла. Этот код поступает

50

55

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

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

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

958124

через элемент ИЛИ 97 на информационный вход регистра 83 и записывается в него с приходом второго импульса ГИ 1 с выхода элемента 104. Далее по адресу второй ветви (полюс 48) с полюса 49 производится считывание из узла 8 памяти метки свершения данной ветви. Если вновь имеется метка свер10 шения, то переходят к следующей ветви из списка выходящих из рассматри- , ваемого узла.

Описанный процесс анализа списка ветвей, выходящих из рассматриваемого

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

20 последнего номера ветви в списке из узла 79 памяти будет считана информация X, определяющая конец списка. Код X записывается в регистр 83 выходящей ветви и далее поступает на

0

Е

0

0

5

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

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

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

25

дешифратор 18 сравнения кодов блока 1 управления по результату сравнения двух кодов формирует сигнал, который поступает через элементы И 24 и ИЛИ 28 на вход элемента И 12. В данный момент времени в узле 9 измерения длиннейшего пути из величины длиннейшего пути сети будет дополнительно вычтена еще величина длиннейшего пути из конечного узла сети в конечный узел рассматриваемой ветви,, Код, хранящийся в узле 9, соответствует величине полного резерва ветви,, номер которой записан в регистре 17 номера заданной ветви.

Сигнал, поступающий с выхода дешифратора 18, разрешает прохождение кода величины полного резерва с выхода узла 9 измерения длиннейптего пути через элемент И 12 на выходной по.пюс 74 блока 1 управления, Ф ормула изобретения

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

тактовому входу первого блока формиро-30 ду узла измерения длиннейшего пути и

вания топологии, второй выход генера35

40

45

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

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

958126

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

15 второго элемента задержки подключен к входу записи второго узла памяти, адресный вход которого подключен к первому входу задания режима блока управления, второй вход задания режи20 ма которого подключен к входу установки в О триггера прерывания, к входу чтения второго узла памяти и к входу третьего элемента задержки, выход которого подключен к входу записи перво25 го узла памяти и к входу первого элемента задержки, выход триггера прерывания подключен к второму входу первого элемента И, выход которого подключен к первому информационному вхо2713

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

Q-15 о 25 зо о .

35

0

5

128

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

29

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

1339581

30

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

« XS

ffS

f

П

т

т

jJz

К5

(u; |г(шмжш

(22;OJf j; (п,;1И|ад

((

(2.1)

-0f/,/;

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

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

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

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