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

 

Изобретение относится к области вычислительной техники, может быть использовано для определения длиннейшего пути в сети и позволяет определять максимальный разрез в сети с учетом временных характеристик ветвей сети. Для определения длиннейшего пути в заданной сети строится ее модель. Так как в известном устройстве использовано динамическое закрепление моделей ветвей за ветвями сети, то в начальный момент для ветвей, выходящих из начального узла сети, ставятся в соответствие свободные модели ветвей. С этой целью последовательно вводят информацию о длительности каждой ветви, выходящей из начального узла, в свободные модели ветвей. При этом в узле памяти номеров моделируемых ветвей запоминается соответствие номера ветви сети и используемой модели ветви, Если модель ветви занята, то осуществляется обращение к следующей свободной модели ветви. Так осуществляется запись информации о длительности ветвей , выходящих из начального узла, которые вместе образуют первый фронт сети. При этом под фронтом понимается множество ветвей, обрабатываемых одновременно в каждый момент времени. После занесения информации о длительности для всех ветвей, принадлежащих первому фронту, осуществляется временное моделирование сети. В этом v. случае подается сигнал Пуск в начальный узел сети (в подготовлен1Л1е модели ветвей), который, распространяясь по сети, задерживается в каждой модели на величину, пропорциональную времени выполнения моделируемой ветви. Временное моделирование каждой моделью ветви выполняется путем заполнения заданного временного интервала импульсами генератора, Когда будет сформирован временной интервал хотя бы одной моделью ветви, сигнал об окончании этого интервала осуществит прерывание временного моделирования и позволит перейти к моделированию топологии исследуемой сети. При этом модель ветви, закончив моделирование заданной длительности, обнуляется и становится свободной. Од нако в работе этого устройства возможен случай, когда все модели ветвей блока моделей ветвей включены в процесс временного моделирования и на момоделирование следующих ветвей по топологии сети свободных моделей ветвей не хватает. Это свидетельствует о том, что в сети имеется такой разрез, число ветвей которого превышает количество моделей ветвей в блоке моделей ветвей устройства. 3 ил. i iO9 to Од CD К

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

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

РЕСПУБЛИК (51)4 G 06 F 15/20

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ вал хотя бы одной моделью ветви, сигнал об окончании этого интервала осуществит прерывание временного моделиГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 1161951 (21) 4101766/24-24 (22) 03.06.86 (46) 15,02.88. Бюл. У- 6 (71) Институт проблем моделирования в энергетике AH УССР (72 ) А.А. Котляренко, В.П. Приймачук и А.M. Щетинин (53) 681.333(088.8) (56) Авторское свидетельство СССР

9 1161951, кл. С 06 Р 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ЗАДАЧ О ДЛИННЕЙПЕМ ПУТИ В СЕТЯХ (57) Изобретение относится к области вычислительной техники, может быть использовано для определения длиннейmего пути в сети и позволяет определять максимальный разрез в сети с учетом временных характеристик ветвей сети. Для определения длиннейшего пути в заданной сети строится ее модель. Так как в известном уст. ройстве использовано динамическое закрепление моделей ветвей за ветвями сети, то в начальный момент для ветвей, выходящих из начального узла сети, ставятся в соответствие свободные модели ветвей. С этой целью по-. следовательно вводят информацию о длительности каждой ветви, выходящей из начального узла, в свободные модели ветвей. При этом в узле памяти номеров моделируемых ветвей запоминается соответствие номера ветви сети и используемой модели ветви . Если модель ветви занята, то осуществляется обращение к следующей свободной модели ветви. Так осуществляется за„„Я0„„1374239 А 2 пись информации о длительности ветвей, выходящих из начального узла, которые вместе образуют первый фронт сети. При этом под фронтом понимается множество ветвей, обрабатываемых одновременно в каждый момент времени.

После занесения информации о длительности для всех ветвей, принадлежащих первому фронту, осуществляется временное моделирование сети ° В этом .. случае подается сигнал Пуск в начальный узел сети (в подготовленные модели ветвей), который, распространяясь по сети, задерживается в каждой модели на величину, пропорциональную времени выполнения моделируемой ветви. Временное моделирование каждой моделью ветви выполняется путем заполнения заданного временного интервала импульсами генератора. Когда будет сформирован временной интеррования и позволит перейти к моделированию топологии исследуемой сети.

При этом модель ветви, закончив моделирование заданной длительности, обнуляется и становится свободной. Од» нако в работе этого устройства возможен случай, когда все модели ветвей блока моделей ветвей включены в процесс временного моделирования и на момоделирование следующих ветвей по то" пологии сети свободных моделей ветвей не хватает. Это свидетельствует о том, что в сети имеется такой разрез, число ветвей которого превышает количество моделей ветвей в блоке моде-" лей ветвей устройства. 3 ил.

1 13742

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

Р 1161951.

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

На фиг.1 представлена функциональная система устройства: на фиг.2— функциональная схема варианта.выполнения блока формирования топологии сети: на фиг.3 — функциональная схема варианта выполнения блока моделей ветвей.

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

° Блок 1 управления содержит. узел

5 памяти длительностей ветвей, блок

6 памяти номеров моделируемых ветвей,25 узел 7 памяти меток свершения ветвей, узел 8 памяти меток моделируемых ветвей, узел 9 памяти ветвеч максимального разреза сети, реверсивный счетчик 10 количества моделируемых ветвей30 счетчика 11 адреса меток ветвей максимального разреза сети, узел 12 измерения длиннейшего пути, регистр

13 количества ветвей в максимальном разрезе сети, триггер 14 форьа рования меток ветвей мак имального разреза сети узла, триггер 15 прерывания, узел 16 элементов И, элементы И 1721, ИЛИ 22, узлы 23 и 24 элементов . тов ИЛИ, элемент ИЛИ 25, элементы 40

26-29 задержки, элемент HE 30, схему

31 сравнения кодов.

Выход 32 номера подготавливаемой к моделированию ветви блока 2 формирования топологии соединен с адресным входом блока 5 памяти, с информационным входом узла 6 памяти и через элемент ИЛИ 23 с адресным входом ,узла 8 памяти.- Выход, 33 поиска свободной модели ветви блока 2 форми 5О рования топологии соединен с входом признака чтения узла 5 памяти; через элемент 27 задержки с входом признака записи узла 6 памяти, через элемент ИЛИ 22 с входом признака записи

55 узла 8 памяти, с суммирующим входом счетчика 10 и с входом 34 поиска номера анализируемой ветви, через элемент ИЛИ 25 соединен с адресным вхо39 2 дом узла 7 памяти. Выход 36 проверки совершения ветви соединен с входом признака чтения узла 7 памяти. Выход

37 поиска прерывания блока формирования топологии соединен с входом установки в "1" триггера 15 прерыва- ния, с входом элемента И 18 и с входом 38 поиска прерывания блока 3 моделей ветвей. Выход 39 индикации расчета блока 2 формирования топологии соединен с входами элементов И 16 и 21.

Выход 40 номера модели ветви блока 3 соединен с адресным- входом блока

6 памяти. Выход 41 прерывания. блока

3 моделей ветвей соединен- с входом признака чтения узла 6 памяти, с входом установки в "0".-триггера 15 прерывания, .с входом элемента 28 задержки, с входом элемента НЕ 30, с вычитающим входом счетчика 10

Выход номера свершившейся ветви узла 6 памяти блока 1 управления соединен с входом 42 блока 2 формирования топологии. Выход. метки свершения ветви узла 7 памяти соединен с входом 43 блока 2 формирования топологии, Выход начала анализа свершения ветви элемента 29 задержки блока 1 управления соединен с входом 44 блока 2 формирования топологии. Выход кода длительности ветви узла 5 памяти блока. 1 управления соединен с входом 45 блока 3 моделей ветвей. Выход измерительной серии. элемента И 20 блока 1 управления соединен с входом

46 блока 3 моделей ветвей.

Входной полюс 47. блока 2 формирования топологии предназначен для приема импульсов серии ГИ1, поступающих с. генератора 4 импульсов. Вход" ной полюс 48 блока ? формирования топологии предназначен для приема импульсоз серии ГИ2, поступающих с генератора 4 импульсов. Входной полюс

49 блока 1 управления предназначен для приема импульсов серии ГИ1, поступающих с генератора 4 импульсов.

Входной полюс 50 блока 1 управления предназначен для приема импульсов серии ГИ2, поступающих с генератора

4 импульсов, Входными полюсами устройства являются полюса 51 и 52 блока

2 Формирования топологии и полюса

53 и 54 блока 1 управления. Выходными полюсами устройства являются полюс 55 блока 1 управления, соединен- ный с выходом элемента И 16,, полюс

1374239

56 блока 1 управления, соединенный с выходом узла 9 памяти, полюс 57 блока 1 управления, соединенный с выходом элемента И 21.

Блок 2 формирования топологии содержит блок 58 памяти номеров началь ных узлов ветвей сети., блок 59 памяти номеров конечных узлов ветвей сети, узел 60 памяти номеров выходящих ветвей узлов сети, узел 60 памяти номеров входящих ветвей узлов сети 61, узел 62 памяти номеров первой выходящей ветви узлов 62 сети, узел 63 памяти номеров первой входящей ветви узлов сети, регистр 64 номера входящей ветви, регистр 65 номера входящей ветви, регистр 66 номера конечного узла ветви,- регистр 67 номера . конечного узла сети, триггеры 68 и

69, дешифраторы 70 и 71, схему 72 сравнения кодов, элементы 73 и 74 задержки, элементы ИЛИ 75-81, элементы

И 82-87; элемент НЕ 88, Блок 3 моделей ветвей содержит И 25 моделей 89(1)-89(М). и узел 90 поиска . моделей ветвей (здесь и далее цифрами в скобках обозначены порядковые номера одинаковых по своему конструк . тивному исполнению и функциональному назначению блоков, узлов, элементов и полюсов) .

Каждая модель 89 ветви состоит из формирователя 91 временных интервалов, триггеров 92 и 93, элементов

И 94-99, элемента ИЛИ 100.и элемен35 тов 101 и 102 задержки, Узел 90 поиска моделей ветвей содержит шифратор 103-адреса и элементы ИЛИ 104 и 105.

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

В узлы 58-63 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моде 45 лируемой сети. Регистры 64-66 .предварительно обнуляются, а в регистр 67 заносится код номера конечного узла сети. Триггеры 14 и 15 -блока 1 управ-ления триггеры 68 и 69 блока 2 формиЭ

50 рования топологии и триггеры 92(1)92(И) и 93(1)-.93(М) блока 3 моделей ветвей устанавливаются в нулевое состояние. В блох 5 памяти длительнос тей ветвей по адресу каждой ветви сети записывается код ее длительности, а узлы 6-9 памяти, счетчик 10 количества моделируемых ветвей, счетчик 11 адреса меток ветвей максимяльнага разреза сети и узел 12 измерения длиннейшего пути предварительно обнуляются.

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

ИЛИ 81 и устанавливает триггер 69 в единичное состояние. Единичное состояние триггера 69. разрешает прохождение серии импульсов ГИ1 и ГИ2 через элементы И 86 и 87. Кроме этого, сигнал пуска с полюса 51 поступает на вход элемента 73 задержки и на вход признака чтения блока 58.памяти начальных узлов. При поступлении признака чтения в блоке 58 памяти про- . исходит считывание ячейки-памяти по адресу номера ветви, поступающего с полюса 52. Так как ветвь выбрана как выходящая из начального узла сети,. то на выходе узла 58 памяти появляется код начального узла сети, который через элемент ИЛИ 76 поступает на адресный вход узла 62 памяти первой выходящей ветви. Через время задержки, достаточное для считывания информации иэ узла 58 памяти, сигнал пуска появляется на выходе элемента 73 задержки и поступает через элемент ИЛИ 75 на вход узла 62 признака чтения памяти. По этому сигналу из узла 62 памяти, по адресу начального узла считывается код номера ветви, являющейся первой в списке ветвей, выходящих иэ начального узла сети. Код первой. выходящей ветви с выхода узла 62 памяти через элемент

ИЛИ 77 поступает на информационный вход регистра 64 выходящей ветви к записывается в него по первому импульсу ГИ1, поступающему на управляющий вход регистра с.выхода элемента И 86.

Записанный код первой выходящей ветви с выхода регистра 64 блока 2 формирования топологии поступает на адресный вход узла 60 памяти и через выходной полюс 32 — на адресный вход узла 5 памяти длительностей, информационный вход узла б памяти номеров моделируемых ветвей и через узел 23 элемента ИЛИ вЂ” на адресный вход узла

8 памяти меток моделируемых ветвей.

Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на

5 1374239 6 вход признака чтения узла 60 памяти и по адресу первой выходящей из начального узла ветви считывается код второй ветви, выходящей из того же узла.

Одновременно сигнал поиска свободной модели ветви с выхода элемента

И 87 через выходной полюс 33-поступает иа вход признака. чтения узла

S памяти длительностей, на элемент

27 задержки, через элемент ИЗИ 22 на вход признака записи узла 8 памяти меток моделируемых ветвей и на суммирующий вход счетчика 10 количества моделируемых ветвей, а также на вход

34 поиска свободной модели ветви блока 3 моделей ветвей..По этому сигналу и адресу номера первой выходящей из узла ветви,. поступающему с полюса 32, 20 осуществляется чтение кода длитель,ности этой ветви из узла 6 памяти длительности, запись метки моделируемой ветви в узел 8 памяти и увеличение на " 1" кода счетчика 10 количест-25 ва моделируемых ветвей. Одновременно. сигнал поиска .свободной модели ветви с полюса 34 поступает на входы элементов И 96(1) и 97(1) первой модели

89(1) ветви. Так как в рассматриваемый момент все модели ветвей свободные, то триггер 92(1) находится в нулевом состоянии, и сигнал с выхода элемента 97(1) через элемент 102(1) задержки поступает на вход установки единичного состояния триггера 92(1).

Триггер 92(1) устанавливается в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви, первой модели ветви. Кроме того, сигнал е выхода элемента И 97(1) поступает на первый вход элемента И 98(1) и через элемент ИЛИ 100(1) на вход шифратора

103 адреса узла 90 поиска моделей ветвей. На второй вход элемента

И 98(1) первой модели 89(1) ветви через полюс 45 поступает код длительности ветви, который заносится в качестве исходной информации в формирователь 91(1) временного интервала.

По сигналу, который с выхода элемента И 97(1) через элемент ИЛИ 100(1) и полюс (1,3) поступает на вход шифратора 103 адреса, формируется код номера модели ветви. Этот код через полюс 40 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления. На вход признака записи узла 6 памяти поступает сигнал с выхода элемента 27 задержки. Осуществляется запись по адресу номера выбранной модели ветви (в данном случае первый) номера ветви, длительность которой уже внесе.на в формирователь 91(1) временного интервала данной модели 89(1) ветви, блока 3 моделей ветвей.iHa этом заканчивается подготовка первой ветви, выходящей из начального узла сети, к процессу временного моделирования длительности. При подготовке к моделированию ветви осуществляется считывание номера данной ветви, считывание ее длительности, запись метки моделирования ветви по ер адресу, увеличение на "1" кода счетчика количест-, 1 ва моделируемых ветвей, поиск сво- бодной от вычислений модели ветви, запись кода длительности ветви в формирователь временного интервала найденной свободной модели ветви, формирование кода найденной свободной модели ветви и запись номера подготавливаемой ветви сети по адресу номера модели в узел памяти номеров моделируемых ветвей..

Далее считанный по адресу номера первой выходящей ветви из узла 60 памяти выходящих ветвеи блока 2 формирования топологии номер следующей ветви из списка выходящих из узла ветвей поступает на информационный вход регистра 64 и с приходом второго импульса ГИ1 записывается в указанный регистр 64. Записанный в регистр 64 код вновь поступает на адресный вход узла 60 памяти и через полюс 32 на адресный вход узла 5 памяти, на информационный вход узла 6 памяти. С приходом второго импульса

ГИ2 на входном полюсе 33 блока 1 управления появляется сигнал поиска свободнои модели по которому осуществляется чтение длительности ветви из узла 5 памяти, запись метки моделирования ветви в узел 8 памяти и увеличение на " 1" кода счетчика 10;

Код длительчости ветви с выхода узла .

5 памяти через полюс 45, поступает на входы элементов И 98(1)-98(M) всех моделей ветвей блока 3. Кроме того, сигнал поиска свободной модели ветви с полюса 33 через полюс 34(1) посту" пает на входы элементов И 96(1) и

98(1) первой модели 89(1) ветвей.

Так как триггер 92(1) находится в

1374239 8 единичном состоянии, означающем занятость первой модели ветви, то сигнал с выхода элемента 96(1) через полюс 34(2) поступает на входы элементов И 96(2) и 97(2) второй модели

89(2) ветви. Так как триггер 92(2) .находится в нулевом состоянии, то сигнал с выхода элемента И 97(2) поступает на вход элемента И 98(2),и в формирователь 91(2) временных интервалов вводится информация о.коде длительности ветви. Одновременно сигнал с выхода элемента И 97(2) через эле мент 102(2) задержки устанавливает триггер 92(2) в единичное состояние.

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

И 97(2) через элемент ИЛИ 100(2) и полюс (2,3) поступает на вход шифратора 103 адреса узла 90 поиска моделей20 ветвей. По этому сигналу формируется код номера второй модели ветви, который через полюс 40 поступает на адресный вход узла блока 6 памяти номеров моделируемых ветвей. На вход признака 25 записи узла 6 памяти поступает сигнал с выхода элемента 27 задержки. происходит запись кода номера второй ветви, выходящей иэ начального узла сети, по адресу номера найденной свободной мо- 30 дели ветви.

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

35 ветвь из списка выходящих из начального узла ветвей. После этого по адресу, который определяется номером последней выходящей ветви, иэ узла 60 40 памяти блока 2 формирования топологии будет считан код К, который записывается в регистр 64. Выход регистра 64 подключен к дешифратору 70 К-состояния, поэтому в результате сравнения кодов на выходе дешифратора 70 формируется сигнал, означающий конец списка выходящих из узла ветвей. Сигнал с выхода дешифратора 70 поступает на вход установки в "0" триггера 69.

Кроме этого, сигнал с выхода дешифратора 70 через элемент ИЛИ -78 поступает на выходной полюс 87.

С полюса 37 сигнал поиска прерывания поступает на вход установки в "1" триггера 15 прерывания, устанавливая его в единичное состояние, и на вход элемента И 18. Кроме того, сигнал поиска прерывания с полюса 37 через полюс 38 поступает в блок 3 моделей ветвей. С полюса 38 сигнал поиска прерывания через элемент ИЛИ 104 узла 90 поиска моделей ветвей и полюс (1, 1) первой модели 89(1) модели поступает на вход элементов И 94(1) и 95(1).

Так как в рассматриваемый момент под . готовлены к моделированию все ветви, выходящие из начального узла сети, и моделей ветвей, закончивших процесс моделирования, нет, то триггеры 93 всех моделей ветвей находятся в нулевом состоянии. Поэтому на.выходе элементов И 95 всех моделей ветвей присутствует потенциал низкого уровня, что дает потенциал низкого уровня на выходе элемента ИПИ 105 узла 90 поиска моделей ветвей. Этот потенциал через полюс 41 поступает в блок 1 управления.

В блоке 1 управления потенциал низкого уровня с полюса 4.1 поступает на вход установки в "0 триггера

15. Кроме этого, сигнал с полюса 41 через элемент НЕ 30 поступает на вход элемента И 18. На другой вход этого элемента поступает сигнал с выхода схемы 31 сравнения кодов.

Так как в рассматриваемый момент код счетчика 10 количества моделируемых

1 ветвей (количество ветвей, выходящих из начального узла сети). больше кода регистра 13 количества ветвей в максимальном разрезе сети (нулевой код) то на выходе схемы 31 сравнения кодов.формируется сигнал высокîro уровня. Этот сигнал формирует на выходе элемента И 18 сигнал высокого уровня, который, поступая на вход . триггера 14, устанавливает его в единичное состояние и, поступая на вход признака записи регистра 13, записывает в него код из счетчика 10, Потенциал низкого уровня с инверсного выхода триггера 14 поступает на вход элемента И 20, запрещая прохождение импульсов серии ГИ2 на вход узла из- мерения длиннейшего пути. Потенциал высокого уровня с прямого выхода триггера 14 поступает на вход элемента И 19, на другой вход которого поступают импульсы серии ГИ1 с полюса

49. С приходом первого после установки в единичное состояние триггера 14 импульса ГИ1 на выходе элемента И 19 формируется сигнал, который поступает на суммирующий вход счетчика 11 адреса меток ветвей максимального

9 137423 сечения сети, увеличивая на "1" его код. С выхода счетчика 11 код через элементы ИЛИ 24 подается на адресный вход узла блока 9 памяти меток ветвей максимального сечения сети, а

5 через блоки 23 и 24 элементов ИЛИ— на адресный вход блока 8. памяти меток моделируемых ветвей., На вход признака чтения узла блока 8 памяти посту" 1р пает сигнал с выхода элемента И 17, на входы которого подаются сигналы

- с прямого выхода триггера 14 и сигнал

ГИ2 с полюса 50. Происходит чтение ячейки памяти узла 8 памяти.по адре5 су, который определяется кодом счетчика 11. Сигнал с выхода узла 8 памяти поступает на информационный вход. узла 9 памяти. На вход признака записи узла 9 памяти поступает сигнал с элемента 26 задержки, задержанный на время, достаточное для считывания информации из узла 8 памяти. Происходит перезапись информации с узла 8 памяти в узел 9 памяти. С приходом на вход элемента И 19 второго импульса серии ГИ1. на выходе элемента

19(20) формируется сигнал, который увеличивает на " 1" код счетчика 11, выхода которого код опять поступа 30 ет на адресные входы узлов 8 и 9 памяти. Происходят перезапись информации с узла 8,памяти в узел 9 памяти о новому адресу. Описанный процесс формирования адресов-и перезапись информации с узла 8 памяти в узел 9

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

При этом в узле 9 памяти формируются метки по тем адресам, которые соот ветствуют номерам ветвей, выходящим из начального узла сети.

Сигнал переполнения, выработанный счетчиком 11 .блока 1 управления, поступает на вход установки в "0" триггера 14. Потенциал низкого уровня с прямого выхода триггера 14 поступает на вход элемента И 19, запрещая прохождение импульсов серии ГИ1 на вход счетчика 11 и на вход элемента И 17, запрещая прохождение импульсов серии

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

1О

И 20, на другой вход которого поступает потенциал высокого уровня с выхода триггера 15. Импульсы серии ГИ2, поступающие с полюса 50 на третий вход элемента И 20, проходят на вход узла 12 измерения длиннейшего пути и на входной полюс 46 блока 3 моделей ветвей. С входного полюса 46 импульсы серии ГИ2 поступают на вход элементов И 99 всех моделей 89 ветвей. У тех моделей ветвей, триггеры 92 которых находятся в единичном состоянии

Э на второй вход элементов 99. поступает разрешающий потенциал с единичного выхода триггера 92, и импульсы серии

ГИ2 с выхода элементов И 99 поступают на суммируюший вход формирователей

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

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

91(1)-91(N) поступают на входы установки в " 1" триггеров 93(1)-93(М) и устанавливают их в единичное состояние. Одновременно сигналы с выходов формирователей 91(1)-91(М) через полюса (1,2), (2,2}-(М,2) поступают на входы элемента ИЛИ 104 узла 90 поиска моделей ветвей. С выхода элемента ИЛИ 104 сигнал прерывания через полюс (1,1) поступает на входы элементов И 94(1) и 95(1) первой модели 89(1) ветви.

Если триггер 93(1) первой модели

89(1) находится в единичном состоянии, сигнал прерывания. с выхода элемента 95(1) через полюс (1,4) и элемент ИЛИ 105 поступает на входной полюс 41 блока 1 управления. Кроме того, сигнал с выхода элемента 95(1) поступает на вход установки в "0" триггера 92, через элемент ИЛИ 100(1) и полюс (1,3) — на вход шифратора

103 адреса узла 90 поиска моделей ветвей, а через элемент 101(1) задержки †. на вход установки в "0" триггера 93(1). По сигналу, который поступил на вход шифратора 103 адреса, формируется код номера данной модели ветви. Этот код с выхода шйфратора 103 адреса через полюс 40 поступает в блок 1 управления.

Б блоке 1 управления код номера модели ветви с полюса 40 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей. На вход

13742 признака трения узла памяти поступает сигнал прерывания с входного полюса

41. Происходит чтение из узла памяти по адресу номера модели ветви, номера ветви сети. Этот код через элемент

ИЛИ 25 поступает на адресный вход уз-, .ла 7 памяти меток свершения ветвей., а через элемент 23 ИЛИ вЂ” на адресный вход узла 8 памяти меток моделируемых10 ветвей. Через время, достаточное для считывания номера. ветви из узла 6 памяти, на выходе элемента 28 задержки формируется сигнал прерывания, который поступает на вход признака записи15 узла 7 памяти и через элемент ИЛИ 22на вход признака записи узла 8 памяти.

Записывается единичная метка в узел 7 памяти по адресу номера свершившейся ветви, характеризующая завершение процесса моделирования длительности данной ветви. В узел 8 памяти записывается нулевая метка по адресу номера ветви, а из счетчика 10 вычитается единица, характеризующая исключение, данной ветви из списка ветвей, входящих в следующий разрез сети. Через время, достаточное для. записи метки свершения в узел 7 памяти, на выходе элемента 29.задержки появляется сигнал, который через полюс 44 поступает в блок 2 формирования топологии.

Через полюс 42 в блок 2 формирования топологии, с выхода узла 6 памяти поступает код номера свершившейся ветви сети.

В блоке 2 формирования топологии код номера свершившейся. ветви с полюса 42 поступает на адресный вход узла 59 памяти номеров конечных узлов ветвей сети. На вход признака чтения узла 59 памяти поступает сигнал начала анализа с входного полюса 44.

Кроме этого, сигнал с полюса 44 поступает на вход установки в "1" триггера и на вход элемента 74 задержки.

Единичное состояние триггера 68 разрешает прохождение импульсов серии

ГИ1 и серии ГИ2 через элементы И 84 и 85 соответственно. Цо сигналу начала анализа, который поступил на вход признака чтения узла 59 памяти, происходит чтение ячейки памяти, в которой записан номер конечного узла свершившейся ветви. Код считанного номера узла с выхода узла 59 памяти поступает на адресный вход узла 63 памяти первой входящей ветви и на информационньй вход регистра 66 ко39 12 нечного узла. По этому сигналу происходит запись кода номера конечного узла ветви в регистр 66 и считывания первой ветви, входящей в этот узел, из узла 63 памяти. Код номера первой входящей ветви с выхода узла 63 памяти через элемент ИЛИ 79 поступает на информационный вход регистра 65 входящей ветви и записывается в него по первому импульсу серии ГИ1, поступающему на вход признака записи регистра с выхода элемента И 84. С выхода регистра 65 код номера первой входящей ветви через полюс 35 поступает на адресный вход узла 7 памяти свершения ветвей на адресный вход узла 61 памяти номеров входящих ветвей;

По первому импульсу ГИ2, поступающему с выхода элемента 85 через полюс

36 на вход признака чтения узла па" мяти меток свершения, происходит чтение метки свершения по адресу первой входящей ветви. Сигнал считанной метки с выхода узла 7 памяти через полюс 43 поступает в блок 2 формирования топологии. Если метка отсутствует, что означает несвершение процесса моделирования ветви с данным номером, то нулевой сигнал метки с полюса 43 через элементы НЕ 88 и

ИЛИ 80 устанавливает триггер 68 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 88 поступает через элемент ИЛИ 78 на выход 37 поиска прерывания. Наличие нулевого сигнала метки свершения ветви означает, что хотя бы одна из ветвей; входящих в рассматриваемый узел, не свершилась, а следовательно, в дан . ном узле не сформировалась функция

И для всех входящих в него ветвей.

В этом случае сигнал с входа 37 пос-. тупает на вход установки в "1" триггера 15 прерывания и на вход элемента И 18 блока 1 управления. Кроме, того, сигнал поиска прерывания с выхода 37 через вход 38 поступает на вход элемента ИЛИ 104 узла поиска моделей ветвей. С выхода элемента

ИЛИ 104 сигнал поступает на входы элементов И 94(1) и 95(1) первой модели ветви. Если в блоке 3 моделей ветвей имеется еще модель ветви, которая окончила процесс моделирования длительности, то триггер 93 такой модели ветви находится в единичном состоянии. В этом случае сигнал с ,выхода элемента 95 этой модели ветви

1374239

I3 через элемент ИЛИ 100 вновь поступает на вход шифратора 103 адреса -для формирования кода номера данной модели ветви устанавливает в нулевое р

5 состояние триггеры 92 .и 93 и через элемент ИЛИ 105 выдает сигнал прерывания в блок 1 управления ° Блок 1 управления, получив номер модели ветви и сигнал прерывания, повторяет 1п все описанные операции, связанные с анализом свешения ветви. Если же в блоке 3 моделей ветвей не имеется .

4 моделей,, у которых триггер 93 находится в единичном состоянии, то про- 15 цесс анализа не проводится .и импульсы измерительной серии поступают через элемент И 20 блока 1- управления в узел 12 определения длиннейшего пути и в блок 3 моделей ветвей..

Если же сигнал метки свершения ветви с входа 43 блока 2 формирования топологии имеет единичное значение, т.е. процесс формирования длительности данной Ветви закончился То этот 25 сигнал дает разрешение на прохождение импульсов серии ГИ2 на вход признака чтения узла 61 памяти входящих ветвей. На адресный вход узла 61 памяти в это время поступает код номе- 30 ра первой входящей ветви с выхода ре: гистра 65. По адре у первой входящей ветви из узла 61 памяти считывается код номера второй, входящей в рассматриваемый -;-зел ветви. Считанный 35 код через элемент ЩЯ 79 поступает на информационный вход регистра 65 и записывается в него с приходом второ, го импульса ГИ1 с выхода элемента И 84. Далее осуществляется опро" мет-40 ки свершения считанной ветви и переход к следующей ветви из списка входящих в рассматриваемый узел ветвей..

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

: конца списка. Полученный сигнал про14 ходит через элементы-ИЛИ 80 и 81 и устанавливает триггеры 68 и 69 соответственно в нулевое и единичное состояние. Кроме того, сигнал с выхода дешифратора 7 1 поступает на вход элемента И 63, второй вход которого связан с выходом схемы 72 сравнения кодов, которая сравнивает коды, хранящиеся в регистре 67 конечного узла сети и в регистре 66 конечного узла ветви. Регистр 67 хранит код конечного узла сети, а регистр 66 — код рассматриваемого узла сети, сформировавшего функцию конъюнкции в данный момент времени. Если значения этих кодов совпадают (сформирована логическая функция конъюнкции для конечного узла сети), то схема 72 сравнения кодов вьдает разрешение на прохождение сигнал конца списка с выхода дешифратора 71 через элемент

И 83 на выход 39 блока 2 формирования топологии, что соответствует концу моделирования заданной сети; С выхода 39 блока 2 управления сигнал разрешения индикации расчета поступает на вход элемента И 21 и разрешает вьдачу на внешнее устройство величины длиннейшего пути сети, накопленной к данному моменту в узле

12 формирования длиннейшего пути.

Кроме того, сигнал с выхода 39 поступает на вход элемента И 16 разреmao вьдачу на внешнее устроиство величины количества ветвей в максимальном разрезе сети, сформированной к данному моменту в регистре 13; Для получения информации о номерах ветвей, которые принадлежат максимальному разрезу сети, необходимр подать . сигнал на вход 53 блока 1 управления, который поступает на вход признака чтения считывания узла памяти меток ветвей максимального сечения сети. На вход 54 поочередно подаются коды из всего диапазона номеров ветвей исследуемой сети. Эти коды поступают на адресный вход блока 9 памяти. Считанная из узла 9 памяти единичная метка соответствует ветви, которая принадлежит максимальному разрезу

В случае, если конечный узел сети не сформирован, сигнал с выхода дешифратора 71 блока 2 формирования топологии через элемент ИЛИ 75 поступает на вход признака чтения блока

62 памяти первой выходящей ветви.

13742

На адресный вход узла 62 памяти в этот момент поступает код номера сформированного узла сети. Происходит чтение кода номера первой ветви, выходящей из сформированного узла сети.

Этот код через элемент ИЛИ 77 посту,пает на информационный вход. регистра

64 и записывается в него по первому импульсу ГИ1, поступающему на вход признака записи регистра с выхода элемента 86 И. Записанный код номера первой выходящей ветви с выхода регистра 64 поступает на адресный вход узла ЬО памяти номеров выходящих вет-15 вей и через выход 32 — в блок 1 управления. Далее импульс ГИ2 с выхода элемента И 87 блока 2 формирования топологии поступает на вход признака чтения считывания блока 60 памяти. 20

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

Кроме того, импульс ГИ2 с выхода элемента И 87 через выход 33 поступает в блок 1 управления ° . По этому сигналу и адресу номера первой выходящей из узла ветви осуществляется считывание кода длительности этой ветви из узла 5 памяти,. запись метки моделируемой ветви в узел Ы памяти и увеличе- 30 ние на "1" кода счетчика 10. Одновременно сигнал поиска свободной модели ветви с выхода 33 через вход 34 поступает в блок 3 моделей ветвей. По этому сигналу осуществляется поиск свободной модели ветви, формирование ее кода и запись длительности ветви.

Код свободной модели ветви через вы1 ход 40 поступает в блок 1 управления.

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

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

50 из сформированного узла, на выходе дешифратора 70 формируется сигнал . поиска прерывания, который через элемент ИЛИ 78 и выход 37 поступает в блок 1 управления, где поступает на вход установки в "1 триггера 15 прерывания и на вход элемента И 18.

Кроме того, сигнал поиска прерывания

39 l6 с выхода 37 поступает в блок 3 моделей ветвей. По этому сигналу осуществляется поиск очередной модели ветви, окончившей процесс моделирования.

Если такая модель обнаружится, то сигнал прерывания с выхода элемента

ИЛИ 105 узла 90 поиска моделей ветвей через вход 41 поступает в блок 1 управления, устанавливая триггер 15; прерывания в нулевое состояние. Производится обработка очередного прерывания описанным образом. Это происходит до тех пор, пока не обработаются прерывания от всех моделей ветвей, окончивших к настоящему моменту процесс моделирования. После этого сигнал поиска прерывания с выхода дешифратора 70 через выходной полюс 37 поступает в блок 1 управления и устанавливает триггер 15 прерывания. в единичное состояние и через выход

38 поступает в блок 3 моделей ветвей.

Так как в рассматриваемый момент в блоке 3 моделей ветвей нет необработанных Моделей ветвей, которые окончили моделирование, то сигнал низкого уровня с выхода элемента ИЛИ 105 узла 90 поиска моделей ветвей через вход 41 поступает на вход установки в "0" триггера 15 и, кроме того, через элемент НЕ 30 — на вход элемента И 18. На другой вход триггера 15 поступает сигнал поиска прерывания с входа 37. На третий вход элемента поступает сигнал с выхода схемы 31 сравнения. В том случае, если код счетчика 10 (количество ветвей в рассматриваемом разрезе сети) больше кода регистра 13 (количество ветвей в максимальном предыдущем разрезе сети), сигнал с выхода схемы 31 сравнения, имеет высокий уровень, что разрешает установку триггера 14 в единичное состояние. Единичное состояние триггера 14 обуславливает перезапись меток моделируемых ветвей из узла блока Ы памяти в узел блока

9 памяти и кода счетчика 10 в регистр

13. Так осуществляется анализ величины разреза сети перед каждым отрезком моделирования длительности ветвей и формирование нового разреза сети в случае, если новый разрез больше максимального предыдущего paspesa

Описанные процессы подготовки ветвей к временному моделированию.длительностей, анализ величины и формирование разреза сети, временное моде17

1374239 лирование длительностей ветвей и ана-, 1 лиз ветвей, закончивших процесс временного моделирования, чередуются в указанном порядке и повторяются до тех нор, пока не будет сформирован заданный конечный узел сети и выдана информация о величине длиннейшего пути из узла блока 12 измерения длиннейшего пути и величине количества ветвей в максимальном разрезе сети из регистра 13.В случае, если при подготовке какой-либо ветви к процессу временного моделирования не обнаружится свободная модель ветви, процесс моделирования сети останавливается. При этом на выходном полюсе 106 блока 3 моделей ветвей, который соединен с выходом элемента 94(М).последней мо- 2О дели ветви 89(М), формируется сигнал

ВысОкОГО урОВНЯ, сиГнализирующий Об отсутствии свободных моделей ветвей.

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

Устройство для моделирования задач о длиннейшем пути в сетях по авт.св. Ф 1161951, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения максимального разреза сети с учетом вре-менных характеристик ветвей, блок управления дополнительно содержит четвертый и пятый узлы памяти, счетчик„реверсивный c t HE, регистр, схему сравнения, второй триггер, с третьего по пятый элементы И, узел элементов И, четвертый элемент задержки, второй элемент ИЛИ, два узла элементов ИЛИ и элемент НЕ, причем вход признака чтения узла .памяти длительности ветвей подключен к перBGNJJ входу второго элемента ИЛИ и суммирующему входу реверсивного счетчика, выход которого подключен к пер45 вому информационному входу схемы сравненчя и информационному входу регистра, вьиод которого подключен к первому входу узла элементов И и второму информационному входу схемы сравнения, выход признака больше ко- 50 торой подключен к первому входу третьего элемента И, выход которого подключен к входу признака записи, tt tt регистра и входу ус тановки в 1 второго триггера, прямой выход кото- 55 р ого и одключ ен к первому входу четвер ого элемента И и первому входу пятого элемента И, выход которого подключен к суммирующему входу счетчика, выход признака переполнения которого подключен к входу установки

tl tt в, О триггера, инверсный выход ко"

4 торого подключен к третьему входу .

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

1374239

° а ФюО м» I&a мю» e6Ab

Составитель А. Мишин

ТехредЛ.Сердюкова Корректор Б. Гирняк

Редактор К. Копча

Заказ б04/46 Тираж 704 Подписное

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

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

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

1374239