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

113

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

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

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

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

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

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

6памяти номеров моделируемых ветвей, узел 7 памяти меток свершения ветвей, узел 8 памяти меток моделируемых ветвей, узел 9 памяти ветвей максимального разреза сети, реверсивный счетчик 10 количества моделируемых ветвей счетчика 11 адреса меток ветвей максимального разреза сети, узел 12 измерения длинкейгаего путиа регистр 13 количества ветвей в максимальном разрезе сети, триггер 14 формирова ния меток ветве.й максимального разреза сети узла5 триггер 15 прерьшания5, узел 16 элементов И, элементы И 17- 2.1j ЙПИ 22, узлы 23 и 24 элементов тов ИЛИ, элемент ИЛИ 25, элементы 26-29 .задержки, элемент НЕ 30,, схему 31 сравнения кодов,

Выход 32 номера подготавливаемой к моделированию ветви блока 2 формирования топологии соединен с адрес- ным входом блока 3 памяти, с информационным входом узла 6 памяти и через элемент ИЖ 23 с адресным входом

,узла 8 памяти. Выход 33 поиска свободной модели, ветви блока 2 форми- . рования топологии соединен с входом признака чтения узла.5 памятиj через элемент 27 задержки с входом признака записи узла 6 памяти, через элемент ИЛИ 22 с входом признака записи узла 8 памятиJ с суммирующим входом счетчика 10 и с входом 34 поиска номера анализируемой ветйи, через элемент ИЛИ 25 соединен с адресным вхо9 2 дом узла 7. памяти. Выход 36-проверки совершения ветви-соединен с входом признака чтения узла 7-памяти. Выход 37 поиска прерывания блока формирования топологии соединен с входом установки в 1 триггера 15 прерьгаа- ния, с входом элемента И 18 и с входом 38 поиска прерьгаания блока 3 моделей ветвей. Выход 39 индикации расчета блока 2 формирования топологии соединен с входами .элементов И 16 и 21 .

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

3моделей ветвей соединен, с входом признака чтения узла 6 памяти, с входом установки в О.-триггера 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, поступающих с генера1: ора 4 импульсов. Входной полюс 48 блока 2 формирования топологии предназначен для приема импульсов, серии ТТИ2 поступающих с. генератора 4 импульсов. Входной погаос 49 блока 1 управления предназначен для приема импульсов серии ГИ, пос- тупаюшдх с генератора 4 импульсов. Входной полюс 50 блока 1 управлений предназначен для приема импульсов серии ГИ2, поступающих с генератора

4импульсов, Входными полюсами устройства ЯБЛ.ЯЮТСЯ полюса-51 и 52 блока 2 формирования топологии и полюса

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

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

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

69, дешифраторы 70 и 71, схему 72

30

сравнения кодов, элементы 73 и 74 задержки, элементы ИЛИ 75-81, элементы И, 82-87 j элемент НЕ 88, .

Блок 3 моделей ветвей содержит М 25 моделей 89(1)-89(М). и узел 90 поиска моделей ветвей (здесь и далее цифрами

в скобках обозначены порядковые но- мера одинаковых по своему конструк . тивному исполнений и функщюнальному назначению блоков, узлов, элементов и полюсов). ; ; Каждая модель 89 ветви состоит из формирователя 91 временных интервалов, триггеров 92 и 93, элементов И 94-99, элемента ИЛИ 100.и элементов 101 и 102 задержки.

Узел 90 поиска моделей ветвей содержит шифратор 103 адреса и элементы ИЛИ 104 и 105.

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

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

40

45

ления, триггеры 68 и 69 блока 2 формирования топологии и триггеры 92(1)- 92(М) и 93(1)-93(М) блока 3 моделей ветвей устанавливаются в нулевое состояние. Б блок 5 памяти длительное тей ветвей по адресу каждой ветви сети записывается код ее длительности, а узлы 6-9 памяти, счетчик 10 количества моделируемых ветвей, счетчик 11 адреса меток ветвей мак-|Q15 20

30

25

74239 .4

симального разреза сети и узел 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 памяти длительностей, информационный вход узла 6 памяти номеров моделируемых ветвей и через узел 23 элемента ИЛИ - на адресный вход узла 8 памяти меток моделируемых ветвей. Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на

35

40

45

50

55

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

Одновременно сигнал поиска свободной модели ветви с выхода элемента И 87 через выходной полюс 33-поступает на вход признака чтения узла 5 памяти длительностей, на элемент 27 задержки, через элемент ИЛИ 22 на вход признака записи узла 8 памяти меток моделируемых ветвей и на суммирующий вход счетчика 10 количества моделируемых ветвей,, а также на вход 34 поиска свободной модели ветви блока 3 моделей ветвей. По этому сигналу и адресу номера первой выходящей из

узла вет.ви,. поступающему с полюса 32, 2о ва моделируемых ветвей, поиск сво-бодной от вычислений модели ветви, запись кода длительности ветви в формирователь временного интервала найденной свободной модели ветви,

ние на 1 кода счетчика 10 количест-25 формирование кода найденной свободосуществляется чтение кода длитель- ,нести .этой ветви из узла 6 памяти длительности, запись метки моделируемой ветви в узел 8 памяти и увеличепризнака записи узла 6 памяти поступает сигнал с выхода элемента 27 задержки. Осуществляется запись по адресу номера выбранной модели ветви (в данном случае первый) номера ветви, длительность которой уже внесе- iна в формирователь 91(1) временного интервала данной модели 89(1) ветви,

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

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

ва моделируемых ветвей. Одновременно сигнал поиска .свободной модели ветви с полюса 34 поступает на входы эле- ментов И 96(1) и 97(1) первой модели 89(1) 1ветви. Так как в рассматриваемый момент все модели ветвей свободные, то триггер 92(1) находится в нулевом состоянии и сигнал с выхода элемента 97(1) череэ элемент 102(1) задержки поступает на вход установки единичного состояния триггера 92(1). Триггер 92(1) устанавливается в единичное состояние, что означает занятость процессом моделирозання длительности некоторой ветви, первой мо дели ветви. Кроме того, сигнал с выхода элемента И 97(I) поступает на первый вход элемента И 98(1) и через элемент ИЛИ 100(1) на вход шифратора 103 адреса узла 90 поиска моделей ветвей. На второй вход элемента И 98(1 первой модели 89(1) ветви через полюс 45 постз пает код длитель™ ности ветви, которьй заносится в качестве исходной информации в формирователь 91(1) временного интервала. По сигналу, которьш с выхода элемента И 97(1) через элемент IdllH 100(1) и полюс (1,3) поступает на вход шифратора 103 адреса, формируется код номера модели вед-ви. Этот код через полюс 40 поступает на адресный вход узла 6 памяти номеров моделируемых. ветвей блока 1 управления. На вход

0

ной модели ветви и запись номера подготавливаемой ветви сети по адресу номера модели в узел памяти номеров моделируемых ветвей.

Далее считанный по адресу номера первой выходящей ветви из узла 60 памяти выходящих ветвей блока 2 формирования топологии номер следующей ветви из-списка выходящих из узла ветвей поступает ка информационный вход регистра 64 и с приходом второго импульса ГИ1 записывается в указанный регистр 64. Записанный в регистр 64 код вновь поступает на ад- ресньн вход узла 60 памяти и через полюс 32 на адресньй вход узла 5 па- ьетти, на информационный вход узла 6 памяти, С приходом второго импульса га2 на входном полюсе 33 блока 1 управления появляется сигнал поиска свободной модели, по которому осуществляется чтение длительности ветви из узла 5 памяти, запись метки моделирования ветви в узел 8 памяти и . увеличение на 1 кода счетчика 10. Код длительности ветви с выхода узла . 5 памяти через полюс 45, поступает на входы элементов И 98C1)-98(M) всех моделей ветвей блока 3. Кроме того, сигнал поиска свободной модели ветви 5 с полюса 33 через полюс 34(1) поступает на входы элементов И 96(1) и 98(1) первой модели 89(1) ветвей. Так как триггер 92(1) находится в

0

единичном состоянии, означающем занятость первой модели ветви, то сигнал с выхода элемента 96(1) через полюс 34(2) поступает на входы элементов И 96(2) и 97(2) второй модели 89(2) ветви. Так как триггер 92(2) .находится в нулевом состоянии, то сигнал с выхода элемента И 97(2) поступает на вход элемента И 98(2)и в Q формирователь 91(2) временных интервалов вводится информация о. коде длительности ветви. Одновременно сигнал с выхода элемента И 97(2) через эле мент 102(2) задержки устанавливает триггер 92(2) в единичное состояние Кроме того, сигнал с выхода элемента И 97(2) через элемент ИЛИ 100(2) и полюс (2,3) поступает на вход пшфраполюс 38 поступает в блок 3 моделе ветвей. С полюса 38 сигнал поиска рывания через элемент ИЛИ 104 узла поиска моделей ветвер и полюс (1,1 первой модели 89(1) модели поступа на вход элементов И 94(1) и 95(1). Так как в рассматриваемьп момент п готовлены к моделированию все ветв выходящие из начального узла сети, и моделей ветвей, закончивших проц моделирования, нет, то триггеры 93 всех моделей ветвей находятся в ну вом состоянии. Поэтому на,выходе э ментов И 95 всех моделей ветвей пр сутствует потенциал низкого уровня что дает потенциал низкого уровня на выходе элемента ИПИ 1П5 узла 90 по ка моделей ветвей. Этот потенциал

15

l-opa 103 адреса узла 90 поиска моделеЙ20 через полюс 41 поступает в блок 1

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

управления,

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

моделируемых ветвей. На вход признака 25 Кроме этого, сигнал с полюса 41

через элемент НЕ 30 поступает на вход элемента И 18. На другой вход этого элемента поступает сигнал с выхода cxej-ibi 31 сравнения кодов.

записи узла 6 памяти поступает сигнал с выхода элемента 27 задержки. Нроис- ходит запись кода номера второй ветви, выходящей из начального узла сети, по адресу номера най,п,енной свободной мо- 30 как в рассматриваемый момент код дели ветви. счетчика 10 количества моделируемых

Так осуществляется подготовка вет- ветвей (количество ветвей, выходящих вей, выходящих из начального узла/, к из начального узла сети) больше кода

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

С полюса 37 сигнал поиска прерывания поступает на вход установки в 1 триггера 15 прерывания, устанавливая его в единичное состояние, и на вход элемента И 18. Кроме того, сигнал ,поиска прерьшания с полюса 37 через

Q4 :39-8

полюс 38 поступает в блок 3 моделей ветвей. С полюса 38 сигнал поиска прерывания через элемент ИЛИ 104 узла 90 поиска моделей ветвер и полюс (1,1) первой модели 89(1) модели поступает на вход элементов И 94(1) и 95(1). Так как в рассматриваемьп момент подт-, готовлены к моделированию все ветви, выходящие из начального узла сети, и моделей ветвей, закончивших процесс моделирования, нет, то триггеры 93 всех моделей ветвей находятся в нулевом состоянии. Поэтому на,выходе элементов И 95 всех моделей ветвей присутствует потенциал низкого уровня, что дает потенциал низкого уровня на выходе элемента ИПИ 1П5 узла 90 поиска моделей ветвей. Этот потенциал

15

управления,

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

через элемент НЕ 30 поступает на вход элемента И 18. На другой вход этого элемента поступает сигнал с выхода cxej-ibi 31 сравнения кодов.

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

5

5

д

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

0

.сечения сети, увеличивая на 1 его код. С выхода счетчика 11 код через элементы ИЛИ 24 подается на адресный вход узла блока 9 памяти меток ветвей максимального сечения сети, а через блоки 23 и 24 элементов ИЛИ - на адресный вход блока 8 памяти мето моделируемых ветвей.. На вход признака чтения узла блока 8 памяти поступает сигнал с выхода элемента И 17, на входы которого подаются сигналы с прямого выхода триггера 14 и сигна ГИ2 с полюса 50, Происходит чтение ячейки памяти узла 8 памяти-по адресу, который определяется кодом счетчика 11, Сигнал с выхода узла 8 памяти поступает на информационный вход- зла 9 памяти. На вход признака з апи си узла 9 памяти поступает сигнал с элемента 26 задержки, задержанный на вре;мя, достаточное для считывания информации из узла 8 памяти. Происходит перезапись информации с узла 8 памяти в узел 9 памяти; С приходом на вход элемента И 19 второго импульса серии ГИ1- на выходе элемента 19(20) формируется сигнал, который увеличивает на 1 код счетчика 11, с выхода которого код опять поступает на адресные входы узлов 8- и 9 па- мятио Происходят перезапись информа- .ции с узла 8,памяти в узел 9 памяти по HOBotry адресу. Описанный процесс формирования адресов-и перезапись информации с узла 8 памяти в узел 9 памяти происходит до тех пор, пока счетчик 11 не выработает сигнал переполнения, что означает конец перебора всех адресов, соответствующих номерам всех возможных ветвей сети, При этом а узле 9 памяти формируются метки по тем адресам, которые соответствуют номерам ветвей j вьпсодящим из начального узла сети.

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

0

5

0

5

0

5

0

5

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

Сигналы с выхода формирователей 91(1)-91(М) поступают на входы установки в 1 триггеров 93(1)-93(М) и устанавливают их в единичное состоя- ние. Одновременно сигналы с выходов формирователей 91(1)-91(М) через полюса (1,2), (2,2)-(М,2) поступают на входы элемента ИЛИ 104 узла 90 поиска моделей ветвей.С выхода элемента ИЛИ 1,04 сигнал прерывания через полюс (1,1) поступает на входы элементов И 94(1) и 95(1) первой модели 89(1) ветви. Если триггер 93(1) первой модели 89(1) находится в единичном состоянии, сигнал прерывания с выхода элемента 95(1) через полюс (1,4) и элемент ИЛИ 105 поступает на входной полюс 41 блока 1 управления. Кроме того, сигнал с выхода элемента 95(1) поступает на вход установки в О триггера 92, через элемент ИЛИ 100(1) и полюс (1,3) - на вход шифратора 103 адреса узла 90 поиска моделей ветвей, а через элемент 101(1) задержки -т на вход установки в триггера 93(1). По сигналу, который поступил на вход шифратора 103 адреса, формируется код номера данной модели ветви. Этот код с выхода шифратора 103 адреса через полюс 40 поступает в блок 1 управления.

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

признака трения узла памяти поступает сигнал прерывания с входного полюса 41. Происходит чтение из узла памяти по адресу номера модели ветви, номера ветви сети. Этот код через элемент ИЛИ 25 поступает на адресный вход уз-,

.ла 7 памяти меток свершения ветвей, а через злемент 23 ИЛИ - на адресный вход узла 8 памяти меток моделируемых g ветвей. Через время, достаточное для считывания номера.ветви из узла 6 памяти, на выходе элемента 28 задержки формируется сигнал прерьгеания, который поступает на вход признака записи узла 7 памяти и через элемент ИЛИ 22- на вход признака записи узла 8 памяти. Записьшается единичная метка в узел 7 памяти по адресу номера свершившейся ветви, характеризующая завершение 20 процесса моделирования длительности данной ветви. В узел 8 памяти записывается нулевая метка по адресу номера ветви, а из счетчика 10 вычитается единица, характеризующая исключение 25

данной ветви из списка ветвей,входящих в следующий разрез сети. Через время, достаточное для записи метки свершения в узел 7 памяти, на выходе элемента 29.задержки появляется сиг- ,Q нал, который через полюс 44 поступает в блок 2 формирования топологии. Через полюс 42 в блок 2 формирования топологии, с выхода узла 6 памяти поступает код номера свершившейся

JC

ветви сети.

В блоке 2 формирования топологии код номера свершившейся, ветви с полюса 42 поступает на адресный вход узла 59 памяти номеров конечных узлов ветвей сети. На вход признака чтения узла 59 памяти поступает сигнал начала анализа с входного полюса 44. Кроме этого, сигнал с полюса 44 поступает на вход установки в 1 триггера и на вход элемента 74 задержки. Единичное состояние триггера 68 разрешает прохождение импульсов серии ГИ1 и серии ГИ2 через элементы И 84 и 85 соответственно. Цо сигналу начала анализа, который поступил на вход признака чтения узла 59 памяти, происходит чтение ячейки памяти, в которой записан номер конечного узла свершившейся ветви. Код считанного номера узла с выхода узла 59 памяти 55 поступает на адресньй вход узла 63 памяти первой входящей ветви и на информационный вход регистра 66 ко40

45

g

0 5

Q

C

5

0

5

нечного узла.- По этому сигналу происходит запись кода номера конечного узла ветви в регистр 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 этой модели ветви

мерез элемент ИЛИ 100 вновь поступает на вход шифратора 103 адреса для формирования кода номера данной модели ветви, устанавливает в нулевое состояние триггеры 92 .и 93 и через элемент ИЛИ 105 вьщает сигнал прерывания в блок 1 управления. Блок 1 управления, получив номер модели ветви и сигнал прерывания, повторяет все описанные операции, связанные с анализом свешения ветви. Если же в блоке 3 моделей ветвей не имеется моделей,- у которых триггер 93 находится в единичном состоянии, то про- -с вавшего функцию конъюнкции в данный

момент времени. Если значения этих кодов совпадают (сформирована логическая функция конък ккции для конечного узла сети), то схема 72 сравнения кодов вьщает разрешение на прохождение сигнал конца списка с выхода дешифратора 71 через элемент И 83 на выход 39 блока 2 формировацесс анализа не проводится -и импульсы измерительной серии поступают через элемент И 20 блока 1 управления в узел 12 определения длиннейшего пути и в блок 3 моделей ветвей. 20

Если же сигнал метки свершения ветви с входа 43 блока 2 формирования топологии имеет единичное значение, т.е. процесс формирования длительности данной ветви закончился, то этот 25 сигнал дает разрешение на прохождение импульсов серии ГИ2 на вход признака чтения узла 61 памяти входящих ветпей. На адресный вход узла 61 памяти в это время поступает-код номе- д РЗ первой входящей ветви с выхода реПйстра 65, По адресу первой входящей ветви и:-; узла 61 Г1а1 {яти считывается

КОД Номера второй входящей в-рассматриваемый узел ветви., Считанный код через элемент ЩЩ 79 поступает на инфорнационньй вход регистра 65 и записывается в него с приходом второго импульса 1111 с выхода элемента

35

ния топологии, что соответствует концу моделирования заданной сети-. С выхода 39 блока 2 управления сигнал разрешения индикации расчета поступает на вход элемента И 21 и разрешает выдачу на внешнее устройство величины длиннейшего пути сети, накопленной к данному моменту в узле 12 формирования длиннейшего пути.. Кроме того, сигнал с выхода 39 поступает на вход элемента И 16 разрешая вьщачу на внешнее устройство величины количества ветвей в максимальном разрезе сети, сформированной к данному моменту Б регистре 13-. Для получения информации о номерах ветИ 84. Далее осуществляется опрос вей, которые принадлежат максимальному разрезу сети, необходимр подать J сигнал на вход 53 блока 1 управления, который поступает на вход признака чтения считьшания узла памяти

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

ки свершения считанной ветви и переход к следующей ветви из списка входящих в рассматриваемый узел ветвей.. Описанный процесс анализа входящих

жается до тех пор, пока не будут опрошены все ветви, входящие в рассматриваемый узел. Это соответствует выпопнению функции конъюнкции относисети. На вход 54 поочередно подаются коды из всего диапазона номеров ветвей исследуемой сети. Эти коды поступают на адресный вход блока 9 пательно входящих ветвей рассматривав- мяти. Считанная из узла 9 памяти едит,

мого узла. В этом случае по адресу номера последней ветви в списке из узла 61 памяти считывается код К, определяющий конец списка.. Код К записывается в регистр 65 входяш.ей ветви и с него поступает на вход дешифратора 71 состояния К, которьй путем сравнения кодов вырабатывает сигнал : конца списка. Полученный сигнал про55

ничная метка соответствует ветви, которая принадлежит максимальному разрезу сети.

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

ходит через элементы ИЛИ 80 и 81 и устанавливает триггеры 68 и 69 соответственно в нулевое и единичное состояние. Кроме того, сигнал с вькода дешифратора 71 поступает на вход элемента И 63, второй вход которого связан с выходом схемы 72 сравнения кодов, которая сравнивает коды, хранящиеся в регистре 67 конечного узла сети ив регистре 66 конечного узла ветви. Регистр 67 хранит код конечного узла сети, а регистр 66 - код рассматриваемого узла сети, сформиро

ния топологии, что соответствует концу моделирования заданной сети-. С выхода 39 блока 2 управления сигнал разрешения индикации расчета поступает на вход элемента И 21 и разрешает выдачу на внешнее устройство величины длиннейшего пути сети, накопленной к данному моменту в узле 12 формирования длиннейшего пути.. Кроме того, сигнал с выхода 39 поступает на вход элемента И 16 разрешая вьщачу на внешнее устройство величины количества ветвей в максимальном разрезе сети, сформированной к данному моменту Б регистре 13-. Для получения информации о номерах ветметок ветвей максимального сечения

сети. На вход 54 поочередно подаются коды из всего диапазона номеров ветвей исследуемой сети. Эти коды поступают на адресный вход блока 9 па

ничная метка соответствует ветви, которая принадлежит максимальному разрезу сети.

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

На адресный вход узла 62 памяти в этот момент поступает код номера сформированного узла сети.. Происходи чтение кода .номера первой ветви, выходящей из сформированного узла сети Этот код через элемент ИЛИ 77 .посту- .пает на информационный вход регистра 64 и записывается в него по первому импульсу ГИ1,. поступающему на вход признака записи регистра с выхода элемента 86 И, Записанный код номера первой выходящей ветви с выхода регистра 64 поступает на адресный вход узла 60 памяти номеров выходящих вет вей и через выход 32- в блок 1 управления. Далее импульс ГИ2. с выхода элемента И 87 блока 2 формирования топологии поступает на вход признака 1тения считывания блока 60 памяти. Происходит считьгоание второй ветви, вькодящей из сформированного узла.. Кроме того, импульс ГИ2 с выхода элемента И 87 через выход 33 поступает в блок 1 управления.. По этому сигна- лу и адресу номера первой выходящей из узла ветви осуществляется считывание кода длительности этой ветви из узла 5 памяти,, запись метки моделируемой ветви в узел 8 памяти и увеличе ние на 1 кода счетчика 10. Одновременно сигнал поиска свободной модели ветви с выхода 33 через вход 34 поступает в блок 3 моделей ветвей. По этому сигналу осуществляется поиск свободной модели ветви, формирование ее кода и запись длительности ветви. Код свободной модели ветви через выход 40 поступает в блок 1 управления Осуществляется запись номера подго- тавливаемой ветви в узел 6 памяти, по адресу номера выбранной свободной модели ветви. На этом заканчивается подготовка к временному моделировани первой ветви, выходящей из сформиро- ванного узла сети. Аналогичным образом осуществляется подготовка остальных ветвей, выходящих из данного узла.

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

5 Q Q ,

5

5

0

с выхода 37 поступает в блок 3 моделей ветвей. По этому сигналу осуществляется поиск очередной модели ветви, окончившей процесс моделирования. Если такая модель обнаружится, то сигнал прерывания с выхода элемента ИЛИ 105 узла 90 поиска моделей ветвей через вход 41 поступает в блок 1 управления, устанавливая триггер 15 ; прерьтания в нулевое состояние. Про, изводится обработка очередного прерывания описанным образом. Это происходит до тех пор, пока не обработаются прерьшания от всех моделей ветвей, окончивщих к настоящему моменту процесс моделирования. После этого сигнал поиска прерьгоания с выхода дешифратора 70 через выходной полюс 37 поступает в блок 1 управления и устанавливает триггер 15 прерывания- в единичное состояние и через выход 38 поступает в блок 3 моделей ветвей. Так как в рассматриваемый момент в блоке 3 моделей ветвей нет необработанных Моделей ветвей, которые окончили моделирование, то сигнал низкого уровня с выхода элемента ИЛИ 105 узла 90 поиска моделей ветвей через вход 41 поступает на вход установки в О триггера 15 и, кроме того, через элемент НЕ 30 - на вход элемента И 18. На другой вход триггера 15 поступает сигнал поиска прерывания с входа 37. На третий вход элемента поступает сигнал с выхода схемы 31 сравнения. В том случае, если код счетчика 10 (количество ветвей в рассматриваемом разрезе сети) больще кода регистра 13 (количество ветвей в максимальном предыдущем разрезе сети), сигнал с выхода схемы 31- сравнения, имеет высокий уровень, что разрешает установку триггера 14 в единичное состояние. Единичное состояние триггера 14 обуславливает перезапись меток моделируемых ветвей из узла блока 8 памяти в узел блока 9 памяти и кода счетчика 10 в регистр 13. Так осуществляется анализ величины разреза сети перед каждым отрезком моделирования длительности ветвей и формирование-нового разреза сети в случае, если новый разрез больше максимального предьщущего разреза..

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

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

В случае, если при подготовке акой-либо ветви к процессу- временного моделирования не обнаружится j

свободная модель ветви процесс модеирования сети останавливается. При этом па выходном полюсе 106 блока 3 моделей ветвей, который соединен с выходом элемента 94(М) последней мо- 20 дели ветви 89(М), формируется сигнал высокого уровня, сигнализирующий об отсутствии свободных моделей ветвей. ормула изобретения

Устройство для моделирования за- 2 ач о длиннейшем пути в сетях по авт.св. №1161951, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения максимального разреза сети с учетом временньк характеристик ветвей, блок управления дополнительно содержит четвертый и пятый узлы памяти, счетчик, реверсиБНьШ. счетчик, регистр, схему сравнения, второй триггер, с третьего по пятый элементы И, узел элементов И, четвертьй элемент задержки, второй элемент ИЛИ, два узла элементов ИЛИ и элемент НЕ, причем вход признака чтения узла памяти длительности ветвей подключен к первому входу второго элемента ИЛИ и

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

30

35

40

45

50

j

0

5

0

5

0

5

0

подключен к суммирующему входу счетчика, вькод признака переполнения которого подключен к входу установки в ,0 триггера, инверсный выход которого подключен к третьему входу г первого элемента И, первый тактовый вход блока управления подключен к второму входу пятого элемента И, вход прерывания блока управления подключен к вычитающему входу реверсивного счетчика, входу элемента НЕ и входу первого элемента задержки, выход которого подключен к второму входу второго элемента ИЛИ,, выход которого подключен к входу признака записи четвертого узла памяти, вход.установки в 1 триггера прерывания подключен к второму входу третьего элемента И , выход элемента НЕ подключен к третьему входу третьего элемента И и информационному входу четвертого узла памяти, второй вход первого элемента И подключен к второму входу четвертого элемента И, вьпсод которо-. го подключен к входу признака чтения четвертого узла памяти и входу четвертого элемента задержки, выход которого подключен к входу признака записи пятого узла памяти, информационный выход узла памяти номеров моделируемых ветвей подключен к первому входу первого узла элементов ИЛИ, адресный, вход узла памяти длительности ветвей подключен к второму входу первого узла элементов ИЛИ, выход которого подключен к адресному входу четвертого узла памяти,-выход которого подключен к информационному вхо ду пятого узла памяти, вход опроса блока управления подключен к входу признака чтения пятого узла памяти информационный выход которого является выходом признака принадлежности ветви к максимальному разрезу сети, информационный выход счетчика подключен к первому входу второго уз- ла элементов ИЛИ, вход блока управления для задания кода номера опрашиваемой ветви подключен к второму входу второго узла элементов ИЛИ, выход которого подключен к третьему входз первого узла элементов ИЛИ и адресному входу пятого узла памяти, второй вход второго элемента И подключен к второму входу узла элементов. И, выход которого является ВЫХОДОМ блока управления индикации количества ветвей в максимальном разрезесети.

Редактор Е, Копча

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

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

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

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

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

Производственно

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

IT

ifhie.g