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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам для решения задач организационного управления и теории графов. Целью изобретения является расширение функциональных возможностей устройства за счет вычисления полного резерва времени для ветви. Устройство содержит блок 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 и -и ер ения длиннейшего п ути работает в режиме вычитания; ттрн о