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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

1511 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСКОМЪ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (61 ) 1161951 (21) 4314240/24-24 (22) 08 ° 10.87 (46) 23.09.89. Бюл. Р 35 (71) Институт проблем моделирования в энергетике АН УССР (72) В.A. Валетчик, А.Г. Додонов, В.П. Приймачук и А.M. Щетинин (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 1161951, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ 3АДАЧ О ДЛИННЕЙШЕМ ПУТИ В СЕТЯХ (57) Изобретение относится к вычисли-

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

1ф 1161951

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

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

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

Входы и выходы названы полюсами., SU„„1509925 A 2

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

Блок 1 управления содержит узел 5 памяти длительностей ветвей, узел 6 памяти номеров моделируемых ветвей, узел 7 памяти меток свершения ветвей, узел 8 измерения длиннейшего пути, триггер 9 прерывания, первый 10 и второй 11 элементы И, элементы ИЛИ 12, элементы 13-15 задержки. ЬР

На фиг. 1 показаны выход 16 номера Д подготавливаемой к моделированию ветви, выход 17 поиска свободной модели ветви, вход 18 поиска свободной модели ветви, выход 19 номера анализируемой ветви, выход 20 проверки свершения ветви, выход 21 поиска прерыва- Д ния, вход 22 поиска прерывания, выход 23 индикации результатов расчета, выход 24 номера модели ветви, выход 25 прерывания, вход:: 26-28 блока формирования топологии, входы 29 и 30 бло5 4

/ Блок 3 моделей ветвей (фиг. 3) со-. держит М моделей ветвей 68. (где И " количество ветвей в максимальном се,чении сети) и узел 69 поиска моделей ветвей, Цифрами в скобках обозначены порядковые номера совершенно одинаковых по своему конструктивному исполнению и функциональному назначению блоков, узлов, элементов и полюсов.

Каждая модель ветви 68 (фиг. 3) состоит из формирователя 70 временных интервалов, триггеров 71 и 72, элементов И ?3-78, элемента .ИЛИ 79, элементов 80 и 81 задержки.

3 150992 ка моделей ветвей, входы 31 и 32 блока формирования топологии, вход 33 блока управления.

Входными полюсами устройства яв5 ляются вход 34 начального пуска и вход 35 номера ветви. Выходным полюсом является выход 36 величины длиннейшего пути.

Блок 1 управления (фиг. 1) пред- назначен для организации взаимодействия между блоком 2 формирования топологии и блоком 3 моделей ветвей в процессе моделирования с целью определения величины длиннейшего пути ис- 15 следуемой сети, а также для контроля правильности функционирования каждой модели ветви.

Блок 2 формирования топологии предназначен для определения номеров вет- 20 вей, входящих в исследуемый узел сети, и номеров ветвей, выходящих из исследуемого узла сети, а также для определения момента окончания процесса вычислений. Блок 3 моделей ветвей предназначен для организации процесса временного моделирования длительностей ветвей сети, генератор 4 импульсов — для формирования серий импуль-. сов ГИ1 и ГИ2, сдвинутых один относи- 30 тельно другого.

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

Блок 2 формирования топологии (фиг. 2) содержит узел 37 памяти но- меров начальных узлов ветвей сети, узел 38 памяти номеров конечных узлов ветвей сети, узел 39 памяти номеров выходящих ветвей узлов сети, узел 40 памяти номеров входящих ветвей узлов сети, узел 41 памяти номеров первой выходящей ветви узлов сети, узел 42 памяти номеров первой входящей ветви узлов сети, регистр 43 номера выходя-. v щей ветви, регистр 44 номера входящей ветви, регистр 45 номера конечного узла ветви, регистр 46 номера конечного узла сети, триггеры 47 и 48, дешифраторы 49 и 50, дешифратор 51 сравнения кодов, элементы 52 и 53 задержки, элементы ИЛИ 54-60, элементы И 61 66, элемент НЕ 67, Узлы 37-42 памяти предназначены для хранения информации о топологии моделируемой сети (узел 37 памяти— для хранения номера началЬного узла ветви по адресу номера данной ветви, узел 38 памяти - для хранения номера конечного узла ветви по адресу номера данной ветви, узел 39 памяти— для хранения в виде списков номеров ветвей, выходящих из узлов сети, узел 40 памяти — для хранения в виде списков номеров ветвей, входящих в узлы сети, узел 41 памяти для хранения по адресу номера узла номера ветви, первой из списка ветвей, выходящих из данного узла, а узел 42 памяти — для хранения по адресу номера узла номера ветви, первой из списка ветвей, входящих в данный узел).

Регистр 43 предназначен для промежуточного хранения номера ветви при определении ветвей, выходящих из узла, а регистр 44 — для промежуточного хранения номера ветвеи, входящих в узел. Регистры 45 и 46 предназначены для хранения номера конечного узла ветви и для постоянногб хранения номера конечного узла сети, соответственно.

Дешифратор 51 сравнения кодов предназначен для поразрядного сравнения кодов из регистров 45 и 46.

Дешифраторы 49 и 50 состояния предназначены для сравнения поступающих на них кодов с кодовой комбинацией состояния Х,заданного постоянно в схеме, 5 !5099

Схема узла 69 поиска моделей ветвей (фиг. 3) содержит шифратор 82 адреса и элементы ИЛИ 83 и 84.

Входы 29(1), 29(2),...,29(H) кода длительности ветви соединены с входами элементов И 77(1), 77(2),...,77(М).

Входы 30(1), 30(2),...,30(М) измерительной серии импульсов соединены с входами элементов И 78(1), 78(2),..., 78(М) узла моделей ветвей 68. Вход

18(l) поиска свободной модели ветви соединен с входами элементов И 75(1) и 76{1) первой модели ветви 68(1). ВыВыход элемента И 75(1) первой модели ветви 68(1) соединен с входом 18(2) поиска свободной модели ветви второй модели ветви 68(2), выход элемента

И 75(2) второй модели ветви 68(2) соединен с входом )8(3) свободной моде- 20 ли ветви третьей модели ветви 68(3) и так далее до М. Вход 22 поиска прерывания.соединен с;ходом элемента

ИЛИ 83 узла 69 поиска моделей ветвей блока 3 моделей ветвей. Выход элемен- 25 та ИЛИ 83 узла поиска моделей ветвей соединен с входом (l,l) поиска прерывания первой модели ветви 68(1). Первая цифра в скобках обозначает более высокой в иерархии порядковый номер (в данном случае номер модели ветви), а вторая более низкий в иерархии номер (в данном случае порядковый номер входа или выхода этой-модели).

Входы (1,1), (2,1),...,(М,1) поиска прерывания моделей, ветвей 68(1), 35

68(2),...,68(М) соединены с входами элементов И 73(1),73(2), .,73(М) и .74(1),74(2),...,74(М). Выход элемента И 73(1) первой модели ветви 68(1) 40 соединен с входом (2,1) поиска прерывания второй модели ветви 68(2), выход элемента И 73(2) второй модели ветви 68(2) соединен с входом (3,1). поиска прерывания третьей модели вет- 45 ви 68(З) и т.д. до М-й модели ветви.

Выходы (1,2),{2,2),...,(М,2) переполнения формирователей временных интервалов 70(М) моделей ветвей 68(1), 68(2),...,68(М) соединены с входами элемента ИЛИ 83 узла поиска моделей ветвей 69. Выходы (1,4),{2,4),...,(М,4) сигналов прерывания с выходов элементов И 74(1), 74(2),..., 74(М) моделей ветвей 68(1), 68(2),...,68{М) соединены с входами элемента ИЛИ 84. Выходы (1;3),(2,3),...,(М,З) кода моделей ветвей с выходов элементов ИЛИ 79(1), 79(2),...,79(М моделей ветвей 68(1), 25 6

68(2),...,68(М) соединены с входами шифратора 82 адреса узла 69 поиска моделей ветвей. Выход 25 прерывания блока 3 моделей ветвей соединен с выходом элемента РЛИ 84 узла 69 поиска моделей ветвей. Выход 24 номера модели ветви соединен с выходом шифратора 82 адреса узла 69 поиска моделей ветвей.

Формирователи временного интервала 70(1), 70(2),...,70(М) моделей ветвей 68(1), 68(2),..., 68(N) предназначены для временного моделирования длительностей ветвей сети. Шифратор 82 адреса узла 69 поиска моделей ветвей предназначен для формирования адреса каждой модели ветви.

В блок 1 управления (фиг. 1) дополнительно введены узел 85 памяти времени начала моделирования ветвей, узел 86 определения разности двух кодов, блок 87 сравнения, третий элемент И 88, второй и третий элементы

ИЛИ 89-90, четвертый элемент 91 задержки, выходные полюса 92 и 93 сигналов неверной обработки длительности ветви и неверно обработанной ветви соответственно.

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

В узлы 37-42 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети, а в узел 5 памяти длительности ветвей записываются длительности ветвей. Регистры 43-45 предварительно обнуляются, а в регистр 46 конечного узла сети заносится код номера конечного узла сети. Триггеры 9, 47, 48; 71{l), 71(2),...,71(М);,72(1), 72(2),...,72(М) находятся первоначально в нулевом состоянии, узел 7 памяти меток свершения, узел 6 памяти номеров моделируемых ветвей и узел 8 памяти времени начала моделирования ветви блока 1 управления обнуляются.

После начального установа на полюс 35 блока 2 формирования топологии подается код номера ветви, выходящей из узла, принятого при данном решении за начальный. Начальный узел, таким образом, определяется по адресу номера ветви в узле 37 памяти блока 2 формирования .топологии.

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

"Пуск", поступающий на полюс 34, проходит через элемент ИЛИ 60 и устанав- ливает триггер 48 в единичное состояl 509925 ние. Единичное состояние триггера 48 разрешает прохождение серии импульсов ГИ1 (полюс 31) и ГИ2 (полюс 32) соответственно через элементы И 65 и 66. Кроме этого, сигнал "Пуск" поступает на вход элемента 52 задержки и на вход считывания узла 37 памяти начальных узлов. При поступлении сигнала разрешения выборки в узле 37 па- 10 мяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 35. Так как ветвь выбрана, как выходящая из начального узла сети, то на выходе узла 37 памяти.по- 15 является код начального узла сети, ко" торый через элемент ИЛИ 55 поступает на адресный вход узла 41 памяти первой выходящей ветви. Через время задержки, достаточное для считывания 20 информации из узла 37 памяти, сигнал

"Пуск" появляется на выходе элемента 52 задержки и поступает через элемент ИЛИ 54 на вход считывания узла 41 памяти. Сигнал выборки по адре- 25 су начального узла позволяет сосчитать из узла 41 памяти код номера ветви, являющейся первой в списке ветвей, выходящих из начального узла сети, Код первой выходящей ветви с выхода 30 узла 41 памяти поступает через элемент ИЛИ 56 на информационный вход регистра 43 номера выходящей ветви и записывается в него. по первому импульсу ГИl поступившему на управляю щий вход регистра с выхода элемента И 65 °

Записанный код первой выходящей ветви с выхода регистра 43 поступает на адресный вход узла 39 памяти, че- 40 рез выходной полюс 16 блока 2 формирования топологии — на вход элемента KIH 89, а также на информационный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления, С вы- 45 хода элемента ИЛИ 89 код первой выходящей ветви поступает на адресный вход узла 5 памяти длительностей ветви, а также на адресный вход узла 85 . памяти времени начала моделирования ветвей блока 1 управления.

Затем импульс ГИ2, сдвинутый отно" сительно импульса ГИ1, поступает на вход считывания узла 39 памяти номеров входящих ветвей узлов сети блока 2 формирования топологии и по- адресу первой выходящей из начального узла ветви осуществляет выборку второго номера ветви, выходящей .из того же узла, Одновременно импульс ГИ2 через элемент ИЛИ 40 поступает на вход считывания узла 5 памяти длительностей ветвей, на вход записи узла 85 памяти времени начала моделирования ветвей, на вход элемента 13 задержки бло-. ка 1 управления и вход 18 поиска свободной модели ветви блока 3 моделей ветвей. По этому сигналу ГИ2 и адресу номера первой выходящей из узла ветви осуществляется считывание кода длительности этой ветви из узла 5 памяти длительностей ветвей, а также запись в узел 85 памяти времени начала моделирования ветвей кода, хранящегося в узле 8 измерения длиннейшего пути.

Одновременно сигнал поиска свободной модели ветви с полюса 18 поступает на входы элементов И 75(1) и 76(1) первой модели ветви 68(1) и блока 3 моделей ветвей. Так как все модели ветвей свободны, то триггер 72(1) находится в нулевом состоянии и сигнал с выхода элемента И 76(1) через элемент 81(l) задержки, поступает на вход установки единичного состояния триггера 72(1),который через время задержки, достаточное для срабатывания всех элементов, устанавливает его в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви первой моделью ветви. Одновременно сигнал с выхода элемента И 76(1) поступает на первый вход элемента И 77(1) и через элемент ИЛИ 74(1) на вход дешифратора 82 адреса. На второй вход элемента И 77(1) через полюс 29 поступает код длительности ветви, который через элемент И 77(1) заносится в качестве исходной информации в формирователь

70(1) временного интервала.

С выхода шифратора 82 адреса полученный по сигналу с полюса (1 3) код адреса модели ветви через полюс 24 поступает на адресный вход узла 6 памяти .номеров моделируемых ветвей блока 1 управления, Через время, достаточное для организации описанных процессов в блоке 3 моделей ветвей, на выходе элемента 13 задержки блока 1 управления появляется сигнал, поступающий на вход записи узла 6 памяти номеров моделируемых ветвей. Сигнал записи позволяет записать по адресу номера выбранной модели ветви (в данном случае первой) номер ветви, дли15099 тельность которой внесена уже в формирователь 70 временного интервала данной модели ветви. На этом заканчивается подготовка первой выходящей из

5 узла ветви к процессу временного моделирования длительности.

Таким образом, подготовка одной ветви к временному моделированию включает считывание из блока 2 формирова- !ð ния топологии номера ветви, затем считывание ее длительности, поиск свободной от вычислений модели ветви, ввод в ее формирователь временного интервала кода длительности ветви, запись в узел номеров моделируемых ветвей по адресу номера выбранной модели ветви номера первой ветви, а также запоминание времени начала моделирования ветви, т.е. раннего начала ветви. 20

Далее считанный по ацресу номера первой выходящей ветви из узла 39 памяти выходящих ветвей блока 2 формирования топологии номер следующей ветви в списке выходящих из узла ветвей по- 25 ступает на информационный .вход регистра 4 и с приходом второго импульса

ГИ1 записывается в указанный регистр.

Записанный в регистр 43 код поступает вновь на адресный вход узла 39 памяти, 30 а также через полюс 16 и элемент

ИЛИ 89 блока 1 управления на адресный вход узла 5 памяти длительностей ветвей и информационный вход узла 6 памяти номеров моделируемых ветвей . С

35 приходом второго импульса ГИ2 из узла 5 памяти длительностей ветвей считывается длительность второй исходящей из узла ветви и для нее в узел 85 памяти времени начала моделирования ветвей записывается содержимое узла 8 измерения длиннейшего пути.

Далее считанный код длительности второй исходящей ветви поступает через полюс 29 на входы элементов И

77(1), 77(2),...,77(И) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 18(1) на входы элементов 75(1) и 76(1) первой модели ветви 68 поступает сигнал поиска свободной модели ветви. Так как триггер 72(1) первой модели ветви находится в единичном состоянии, означаю щим ее занятость, то сигнал с выхода элемента 75(1) поступает на вход 18(2) второй модели ветви, триггер 72(2)

55 которой находится в нулевом состоянии. Тогда сигнал с выхода элемента И 76(2) второй модели ветви 68(2) 25

1О поступает на вход элемента И 77(2) и в формирователь временных интервалов

70(2) вводится исходная информация о коде длительности ветви. Одновремен-, но сигнал с выхода элемента И 76(2) через элемент 81(2) задержки устанавливает триггер 72(2) в единичное состояние, по этому же сигналу на выходе шифратора 82 адреса формируется номер второй модели ветви, который через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления, и при появлении через некоторое время сигнала на выходе элемента 13 задержки в узел 6 памяти по адресу номера модели ветви записывается номер ветви, код длительности которой введен в формирователь 70 временного интервала данной модели ветви.

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

По адресу ее номера в узле 39 памяти блока 2 формирования топологии считывается код Х, который записывается в регистр 43. Так как выход регистра 43 подключен к дешифратору 49 состояния Х, в комбинационной схеме путем сравиения кодов определяется информация о конце списка. Дешифратор 49 вырабатывает на выходе сигнал, который поступает на нулевой вход триггера 48, сбрасывая его в нулевое состояние. Кроме этого, сигнал с выхода дешифратора поступает на полюс 21. С последнего сигнал (поиска прерывания) поступает на единичный вход триггера прерывания 9 и устанавливает его в единичное состояние. Одновременно сигнал поиска прерывания поступает в блок моделей ветвей. Так как выполняется моделирование длительностей ветвей, выходящих из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер прерывания 9 остается в единичном состоянии. На счетный вход узла S измерения длиннейшего пути и через полюс 30 во все формирователи 70 временного интервала моделей ветвей, триггеры 72 которых находятся в единичном состоянии начинают поступать импульсы серии ГИ1. Так про-. должается до тех пор, пока хотя бы один из формирователей 70 временного

150992 интервала не вьщает сигнал об окончании процесса временного моделирования длительности ветви.

Сигналы с выхода формирователей

70(1), 70(2),...,70(N) временного интервала поступают на единичные входы триггеров 71(1), 71(2),...,71(H) и устанавливают триггеры в единичное состояние. Одновременно сигнал с выхода 10 формирователей 70 поступает через элемент ИЛИ 83 на вход поиска преры-. вания (1,1) первой модели ветви и в случае, если триггер 71(1) находится в единичном состоянии, сигнал прерыва-15 ния с выхода элемента 74(1) поступает через элемент ИЛИ 84 и полюс 25 в блок 1 управления, устанавливает триггер 72(1) в нулевое состояние, что означает освобождение модели ветви для 20 последующих вычислений, Одновременно этот сигнал через элемент 80 задержки сбрасывает триггер 71(1) в нулевое состояние и вьщает с полюса (1,3) сигнал на вход шифратора 82 адреса, по кото- 25 рому формируется номер данной модели ветви, Номер модели ветви с выхода шифратора 82 адреса через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления.

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

35 сети. Этот номер поступает через элемент ИЛИ 12 на адресный вход узла ? памяти меток свершения ветвей, а также через элемент ИЛИ 89 на адресный вход узла 5 памяти длительностей ветвей. Через время, достаточное для счи-! отывания номера ветви, на вход записи узла 7 памяти меток свершения ветвей через элемент 14 задержки поступа-45 ет сигнал прерывания, и по адресу номера ветви в узел 7 памяти меток свершения ветвей записывается метка

t! и

1, характеризующая. свершение процесса моделирования длительности дан-- gp ной ветви. Одновременно сигнал прерывания с выхода элемента 14 задержки поступает на вход считывания узла 85 памяти времени начала моделирования ветви. Считываемая из узла 85 памяти по адресу кода ветви информация о начале моделирования ветви поступает на . первый вход узла 86 определения разности двух кодов (схема вычитания), 5

12 на второй вход которого подается код (конца моделирования ветви) текущего времени моделирования сети с выхода узла 8 измерения длиннейшего пути. Через время, достаточное для записи метки в узел 7 памяти меток свершения ветвей, с выхода элемента 15 задержки сигнал прерывания поступает на разрешающий вход узла 86 определения разности двух кодов, через полюс 28 в блок 2 формирования топологии, через элемент ИЛИ 90 на вход. считывания узла 5 памяти длительности ветвей, а также через элемент 91 задержки, на разрешающий вход блока 87 сравнения.

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

Таким образом, на выходе узла 86 определения разности двух кодов появляется код разности между кодами, определяющими время начала и время конца моделирования ветви, равный длительности ветви при правильном моделировании длительности. При различии кодов (неправильное моделирование ветви), поступающих на блок 87 сравнения, на его выходе появляется сигнал сбоя, поступающий на выходной полюс 92 неверной отработки длительности ветви и на вход элемента И 88. На второй вход элемента И 88 поступает адрес кода ветви. Выход элемента И 88 соединен с выходным полю— сом 93 номера неверно отработанной ветви, Далее в работе устройства код номера ветви, считанной ранее с выхода узла 6 памяти номера моделируемой ветви, через полюс 26 поступает на адресный вход узла 38 памяти конечно" го узла блока 2 формирования топологии, а сигнал начала анализа ветви с полюса 28 поступает на вход триггера 47 и устанавливает его в единичное состояние. Единичное состояние триггера 47 разрешает прохождение импуль" сов ГИ1 (полюс 31) и ГИ2.(полюс 32) через элементы И 63 и 64. Кроме того, сигнал начала анализа ветви поступает иска прерывания. Наличие нулевого сигнала метки Свершения ветви означает, что хотя бы в одной из ветвей списка, входящих в узел, не завершился процесс временного моделирования своей

«5 длительности и, следовательно, в данном узле йе сформирована функция U для всех входящих в него ветвей. Тог- . да сигнал поиска прерывания с полю-. са 21 поступает на единичный вход триггера прерывания 9 и одновременно через полюс 22 на вход элемента ИЛИ 83 узла поиска моделей ветвей 59 блока 3 моделей ветвей. С выхода элемента

ИЛИ 83 сигнал поступает на входы элементов И 73(1) и 74(1) первой модели ветви.

Если модель ветви закончила про2р цесс моделирования длительности ветви,которая еще не анализировалась, то триггер 71 находится в единичном состоянии. Тогда сигнал с выхода элемента 74 такой модели ветви вновь по25 ступает на вход шифратора 82 адреса для формирования номера данной модели ветви, сбрасывает в нулевое состояние триггеры 71 и 72, а также через элемент ИЛИ 83 выдает сигнал прерывания, Блок 1 управления, получив номер модели ветви и сигнал прерывания, повторяет все описанные операции, связанные с анализом свершения ветви. Если в блоке 3 моделей ветвей не имеется моделей, имеющих триггеры 71 в единичном состоянии, то процесс анализа прерывания не проводится и импульсы серии ГИ! через элемент И 10 блока 1 управления продолжают посту40 пать в узел 8 определения длиннейшего пути и в блок 3 моделей ветвей.

Если сигнал метки свершения ветви с полюса 27 имеет единичное значение, т.е. процесс формирования дли45 тельности для ветви закончился, то он выдает разрешение на прохождение импульса ГИ2 через элемент И 61 блока 2 формирования топологии на вход считывания узла 40 памяти входящей ветви. На адресные входы узла 40 памяти в это время поступает код номера первой входящей ветви в списке с выхода регистра 44.По адресу первой вхо. дящей ветви из узла 4С памяти считывает- ся код номера второй ветви в списке,ко7 торый поступает через элемент ИЛИ 58

55 на информационные входы регистра .44 и записывается в него с приходом второго .импульса ГИ1 с выхода эле13

150 на вход элемента 53 задержки и на вход считывания узла 38 памяти. С при ходом сигнала считывания в узле 38 памяти конечного узла по адресу номера ветви, вызвавшей прерывание, проис ходит считывание ячейки памяти, в которой записан номер конечного узла: рассматриваемой ветви. Код считанного номера узла с выхода узла 38 памяти поступает на адресные входы узла памяти первой выходящей ветви и на информационные входы регистра 45 конечного узла °

Через время задержки, достаточное для считывания информации из узла 38 памяти, сигнал начала анализа ветви поступает на управляющий вход регистра 45 конечного узла и на вход считывания узла 42 памяти. По задержанному сигналу начала анализа ветви в регистре 45 происходит запись номера конечного узла ветви, а в узле 42 памяти по адресу номера конечного узла происходит считывание номера ветви, первой в списке входящих в рассмаФриваемый узел ветвей. Код номера первой входящей ветви с выхода узла 42 памяти поступает через элемент ИЛИ 58 на информационный вход регистра 44 входящей ветви и записывается в него по первому импульсу ГИ1, поступающему на управляющий вход регистра с выхода элемента И 63. С выхода регистра 44 код номера первой входящей ветви поступает через полюс 19 и элемент ИЛИ )2 на адресный вход узла 7 памяти меток свершения ветвей блока 1 управления и на адресный вход узла 40 памяти номеров входящих ветвей блока 2 формирования топологии. Первый импульс ГИ2 поступает с выхода элемента И 64 на вход элемента И 61 блока 2 формирования топологии и через полюс 20 на вход считывания узла 7 памяти меток свершения блока 1 управления.

Метка свершения, считанная по адресу первой ветви с выхода узла 7 .памяти меток свершения ветвей, поступает через полюс 27 в блок 2 формирования топологии. Если метка отсутствует, что означает несвершение процесса моделирования длительности ветви с данным номероМ, то нулевой сигнал мет ки с полюса 27 через элемент НЕ 67 и элемент ИЛИ 59 сбрасывает триггер 4 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 67 поступает через элемент ИЛИ 57 на полюс 21 по9925 14

15 150992 мента И 63. Далее через полюс 19 осуществляется опрос метки свершения данной ветви, входящей в рассматри" ваемый узел, и переход к следующей ветви из списка входящих в него ветвей.

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

|адресу последнего номера ветви в спис- 15

I ке из узла 40 памяти считывается ин- формация Х, определяющая конец списка. Код Х записывается в регистр входящей ветви 44 и далее поступает на вход дешифратора 50 состояния, ко- 20 торый путем сравнения кодов вырабатывает сигнал конца списка. Полученный сигнал проходит через элементы ИЛИ 59 и 60 и устанавливает триггеры 47 и

48 соответственно в нулевое и единич- 25 ное состояния. Сигнал с выхода дешифратора 50 поступает также на вход элемента И 62, второй вход которого связан с выходом дешифратора 51 сравнения кодов. Последний сравнивает ко- 3{} ды, хранящиеся в регистре конечного узла сети 46 и регистре 45 конечного узла.

Регистр 46 хранит код конечного узла сети, а регистр 45 — код рассматриваемого узла сети, сформировавшего функцию конъюнкции в данный момент времени. Если значения этих кодов совпадают (сформирована логическая функция конъюнкции для конечного узла 40 сети), то дешифратор 51 сравнения кодов выдает разрешение на прохождение сигнала конца списка с выхода дешифратора состояния 50 через элемент И 62 на выходной полюс 23 блока 2 формиро- 45 вания топологии, что соответствует концу моделирования заданной сети.

Данный сигнал с полюса 23 поступает на вход элемента И 11 блока 1 управления и разрешает выдачу во внешние устройства величины длиннейшего пути сети, накопленной к данному моменту в узле 8 измерения, длиннейшего пути.

Если не сформирован конечный узел сети, то сигнал с выхода дешифратора 50 поступает через элемент ИЛИ 54 на вход считывания узла 41 памяти первой выходящей ветви, на адресный вход которого в этот момент времени поступа5

16 ет код номера сформированного узла сети. Вновь начинается описанный процесс подготовки к временному моделированию длительностей тех ветвей, которые выходят из данного сформированного узла, Описанные процессы подготовки ветвей к временному моделированию длительностей с запоминанием кодов времени начала моделирования и анализа ветви, закончивших процесс временного моделирования, с контролем правильности моделирования каждой ветви1чередуются в указанном порядке и повторяются до тех пор, пока не сформирован заданный конечный узел ". сети с выдачей сформированной в узле 8 измерения длиннейшего пути блока 1 управления величины длиннейшего пути в сети. В процессе всего временного моделирования сети при неправильной работе устройства на выходных полюсах 92 и 93 фиксируются все сбойные ситуации, связанные с неправильным формированием длительностей ветвей сети.

Формула и з обретения

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

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

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

7 1509925 18 ной ветви блока управления и устрой- соединен с вторым информационным вхоства в целом, выход узла измерения дом узла определения разности двух длиннейшего пути соединен с первым ин- кодов, выход которого соединен с пер« формационным входом узла определения вым информационным входом блока срав5 разности двух кодов и информационным нения, второй информационный вход ковходом узла памяти времени начала мо- торого соединен с выходом уэла памяти делирования ветвей, вход записи кото- длительности ветвей, управляющий вход рого соединен с входом первого эле-. блока сравнения соединен с выходом мента задержки и вторым входом тре- 0 четвертого элемента задержки, первый тьего элемента ИЛИ, выход второго эле- и второй входы третьего элемента ИЛИ мента задержки соединен с входом счи- соединены соответственно с входами нотывания узла памяти времени начала мера подготавливаемой ветви и поиска моделирования ветвей, выход которого . свободной модели ветви, 1509925

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

Редактор M. Бланар Техред Л.Олийнык Корректор Т, Палий

Заказ 5815/48 .Тираж б68 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101