SU1282151A1 - Устройство дл определени характеристик сетей - Google Patents

Abstract

Изобрете ние относитс  к области вычислительной техники, в частности к устройствам обработки информации специального назначени  с точки зрени , конструкции вычислительного устройства . Целью изобретени   вл етс  повьшение быстродействи  при определении характеристик сетей. Поставленна  цель достигаетс  за счет дополнительного введени  операционного блока, содержащего блок пам ти номеров свершившихс  событий в узлах, вы- читатель, регистры, элементы И, ИЛИ, НЕ и элементы задержки, регистр номера конечного узла сети, дешифратор нулевого состо ни , блок сравнени  кодов коммутатора, триггеры, блок пам ти количеств вход щих в узлы ветвей, два блока расчета характеристик , содержащего два блока пам ти ранних окончаний событий в узлах, сумматор, регистры и элементы И, ИЛИ, блок пам ти кодов весов длительности j ветвей. В блок моделировани  топологии введены два коммутатора, регистр номера начального узла сети и элемент задержки. Быстродействие при расчете характеристик сетей увеличиваетс  по крайней мере в 1,5-2 раза по сравнению с известными устройствами за счет изменени  процедур обработки исходной информации. 3 ил. (Л с to 00 rsD СП

Description

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

Цель изобретени  - повьшение бы-

.стродеистви  устройства при определе

1нии характеристик сетей.

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

Устройство содержит операционный блок 1, блок 2 моделировани  топологии , блок 3 расчета характеристик, генератор 4 тактовых импульсов.

Входом устройства  вл етс  полюс 5 сигнала Пуск блока 2 моделировани  топологии. Первый, второй, третий и четвертьш выходные полюсы 6-9 генератора 4 тактовых импульсов соединены с соответствующими входами операционного блока 1 и блока 2 моделировани  топологий. Управл ющий выход операционного блока 1 соединен с входным полюсом 10 блока 2 моделировани  топологии. Соответствующие выходы блока 2 моделировани  топологии соединены с входными полюсами 11-16 операционного блока 1. Выходы операционного блока 1 соединены с входными полюсами 17-19 блока 2 моделировани  топологии и с полюсом 20 блока 3 расчета характеристик . Соответствующие выходы блока 2 моделировани  топологии соединены с входными полюсами 21-29 блока 3 расчета характеристик. Выход блока 3 расчета характеристик соединен с выходным полюсом 30 устройства,  вл ющимс  его информационным выходом.

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

4 тактовых импульсов предназначен дл  синхронизации работ всех блоков устройства. Первый, второй, третий и четвертый выходы генератора 4 тактовых импульсов, соединенные с его выходными полюсами 6-9, предназначены дл  подачи на соответствуюиц е входы блоков устройства сдвинутых относительно друг друга серий тактг- вых импульсов соответственно ГИ1, ГИ2, ГИЗ и ГИ4.

Операционный блок 1 (фиг.1) со- .держит блок 31 пам ти номеров свершившихс  событий в узлах, блок 32 пам ти количеств вход щих в узлы ветвей, вычитатель 33, три регистра 34-36, регистр 37 номера конечного узла сети, дешифратор 38 нулевого состо ни , блок 39 сравнени  кодов, два коммутатора 40,41, первый 42, второй 43 триггеры, восемь элементов И 44-51, третий триггер 52, элемент ИЛИ 53, элемент НЕ 54, четыре элемента 55-58 задержки.

Блок 2 моделировани  топологии (фиг.2) содержит блок 59 пам ти номеров выход щих из узлов ветвей, блок 60 пам ти номеров первых выход щих из узлов ветвей, блок 61 пам ти номеров конечных узлов ветвей, регистр 62 номера начального узла сети, регистр 63 номеров выход щих ветвей, дешифратор 64 состо ни , два коммутатора 65 и 66, два триггера 67 и 68, четыре элемента И 69-72, два элемента ИЛИ 73 и 74, элемент 75 задержки;

В блоке 2 моделировани  топологии блок 59 пам ти номеров выход щих из узлов ветвей предназначен дл  хранени  списков номеров ветвей, выход щих из узлов моделируемой сети. Блок

60пам ти номеров первых выход щих из узлов ветвей предназначен дл  хранени  номеров первых ветвей списков выход щих из узлов ветвей. Блок

61пам ти номеров конечных узлов ветвей предназначен дл  хранени  номеров конечных узлов всех ветвей моделируемой сети. Регистр 62 номера начального узла предназначен .дл  хранени  кода номера начального узла молекулируемой сети. Регистр 63 номеров выход щих ветвей предназначен дл  записи, хранени  и выдачи кодов номеров ветвей, выход щих из узлов сети. Дешифратор 64 состо ни  предназначен дл  дешифраций кода X . Коммутаторы 65 и 66 предназначены

31

дл  разделени  во времени двух потоков данных, поступающих к одному и тому же входу.

Блок 3 расчета характеристик (фиг 3), содержит блок 76 пам ти ранних окончаний событий в узлах, блок 77 пам ти кодов весов длительнрстей ветвей , сумматор 78, три регистра схему 82 сравнени , коммутатор 83, группу элементов И 84, элемент И 85, элемент ИЛИ 86,

В блоке 3 расчета характеристик блок 76 пам ти ранних окончаний событий в узлах предназначен дл  записи , хранени  и выдачи промежуточных и окончательных кодов величин ранних окончаний событий каждого узла сети. Блок 77 пам ти кодов весов длительностей ветвей предназначен дл  хранени  исходных данных о ве- личинах длительностей всех ветвей сети. Схема 82 сравнени  кодов предназначена дл  сравнени  двух кодов и формировани  сигнала на выходе при наличии на втором входе кода большего , чем на первом. Группа элементов И 84 предназначена дл  подачи на информационньш вьпсод устройства N-разр дного кода резултата. Все остальные триггеры, элементы И, ИЛИ, НЕ, элементы задержек в устройстве предназначены дл  организации правильной работы схемы и предотвращени   влений гонок.

Устройство предназначено дл  опре делени  величины длиннейшего пути и других характеристик сетей. К числу этих характеристик относ тс  величины ранних начал и ранних окончаний ветвей, ранних свершений узлов, свободных резервов всех ветвей сети.

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

Характеристики ветвей сети: ранне начало, раннее окончание и свободный резерв определ ютс  исход  из ра нних свершений их начальных и конечных узлов . Величина раннего начала ветвей совпадает с величиной раннего окончани  их начального узла, величины ранних окончаний ветвей определ ютс  как суммы их ранних начал и их длительностей , а свободные резервы

,-

25

12821

г. .5 1 , , О

и - е

30

40

55

51 .4 как разности между величинами ранних свершений их конечных узлов и ранних окончаний данных ветвей.

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

Устройство работает следукхцим образом .

Предварительно в блоки пам ти номеров первых ветвей, выход щих из начальных узлов 60, номеров ветвей, выход щих из начальных узлов 59, и номеров конечных узлов ветвей 61 блока 2 моделировани  топологии заноситс  исходна  информаци  о топо- .логии сети. В блок 59 пам ти информаци  заноситс  в виде списков ветвей , выход щих из узлов сети, т.е. по адресу предыдущей ветви списка выход щих из узла ветеей записыва- ,етс  номер последующей, а по адресу последней записываетс  кодовый набор X. Номера первых списков хран тс  в блоке 60 пам ти по адресам номеров узлов, которые  вл ютс  начальными дл  ветвей данных списков, В блоке 61 пам ти по адресам ветвей хран тс  номера их конечных узлов, Такой набор топологической информации достаточен дл  работы устройства по определению заданного набора характеристик , В регистре 62 хранитс  номер начального узла сети,

В блок 77 пам ти блока 3 расчета характеристик по адресам ветвей занос тс  коды их длительностей, а в блок 32 пам ти операционного блока 1 по адресам узлов предварительно заноситс  код количества ветвей, вход щих в данный узел. В регистр 37 операционного блока 1 заноситс  код номера конечного узла сети. Остальные все регистры и узлы пам ти устройства предварительно очищаютс , а триггеры обнул ютс .

.

5128

После выполнени  описанных предварительных установок и ввода перечисленной исходной информац11и устройство начинает работу по сигналу Пуск, который поступает с входного полюса 5 устройства в блок 2 моделировани  то пологий. Сигнал Пуск,через элемент ИЛИ 74 устанавливает в единичное состо ние триггер 67 управлени  и через элемент ИЛИ 73 устанавливает в единичное состо ние триггер 68 и поступает на вход считывани  блока 60 пам ти номеров первых выход щих из узлов ветвей, Так как триггер 42 операционного блока 1 находитс  в нулевом состо нии, то через полюс 10 на управл ющий вход коммутатора 65 .поступает нулевой сигнал, который разрешает поступление через коммутатор 66 на адресньй вход блока 60 па- м ти номера начального узла сети с выхода регистра 62 начального узла,

В результате по сигналу Пуск на выход блока 60 пам ти считываетс  номер первой ветви, вьгход щей из данного узла, который через коммутатор 66, управл емый единичным состо нием триггера 68, поступает на

информационный вход регистра 63. Од

новременно с выхода коммутатора код

номера начального узла через полюс 23 поступает в блок 3 расчета характеристик и через коммутатор 83, управл емый единичным сигналом, поступаю- пщм через полюс 24 с триггера 68, поступает на адресный вход блока 76 пам ти ранних окончаний событий в узлах. Сигнал выхода элемента ИЛИ 73 блока 2 моделировани  топологии через полюс 26 и элемент ИЛИ 86 поступает на вход считывани  этого же блока 76 пам ти. На выходе блока 76 пам ти счит1 шаетс  нулевой код, соответствующий величине раннего свершени  событи  начального узла сети. Код раннего свершени  событи  узла поступает на информационный вход регистра 80, куда и записываетс  по сигналу Пуск, задержанному элементом 75. задержки блока 2 моделировани  топологии, и поступающему на вход разрешени  записи регистра 80 блока расчета характеристик через полюс 21,

Триггер 67 управлени  блока 2 моделировани  топологии, установленный в единичное состо ние сигналом Пуск разрешает формирование на выходах зле ментов И 69-72,импульсов управлени .

15

25

8215

5 20

30

, 55 , е-

40

45

16

синхронных импульсам ГИ1-ГИ4 тактового генератора поступающим на входы этих элементов соответственно через полюсы 6-9.

По импульсу ГИ1 с выхода элемента И 69 код номера первой выход щей из начального узла ветви записываетс  в регистр 63, с выхода которого поступает на адресньй вход блока 61 пам ти номеров конечных узлов ветвей , в котором по этому же импульсу считываетс  номер конечного узла первой ветви, выход щей из начального узла. Код номера ветви с выхода регистра 63 через полюс 29 поступает на адресный вход блока 77 пам ти длительностей ветвей блока 3 расчета характеристик . Считанньш в блоке 61 пам ти код номера конечного узла рассматриваемой ветви через полюс 16 поступает в операционньй блок 1 на адресньй вход блока 32 пам ти количества вход щих в узлы ветвей и через полюс 22 поступает.на второй вход коммутатора 83 блока 3 расчета характеристик.

По импульсу ГИ2 с выхода элемента И 70 в блоке 59 пам ти номеров выход щих из узлов ветвей считываетс  по адресу номера первой ветви, код номера которой с выхода регистра 63 поступает на адресный вход блока 59 пам ти, код номера следующей выход щей из данного (начального) узла ветви. По этому же сигналу триггер 68 устанавливаетс  в нулевое состо ние . Считанньй в блоке 59 пам ти код номера следующей ветви поступает на второй вход коммутатора 66, управл емого теперь нулевым сигналом триггера 68, и с выхода его поступает на информационньй вход регистра 63. Нулевой сигнал с выхода тригге- .ра 68 через полюс.24 разрешает поступление кода номера конечного узла первой выход щей ветви, код которой пока еще находитс  в регистре 63, через коммутатор 83 на адресньй вход блока 76 пам ти ранних окончаний событий в узлах блока 3 расчета характеристик. Управл емьй импульс с выхода элемента И 70 блока 2 моделировани  топологии через полюс 27 и элемент ИЛИ 86 поступает на вход считьгеани  блока 76 пам ти блока 3 расчета характеристик. По номеру конечного узла ветви считываетс  величина раннего свершени  этого узла.

Код считанной величины поступает на информационный вход регистра 79. Одновремег1но по тому же сигналу с полюса 27 в блоке 77 пам ти кодов весов длительностей ветвей считываетс  код длительности рассматривав емой в регистре 63 ветви. Считанньй код длительности ветви поступает на информационный вход регистра 81 блока 3 расче Та характеристик. Одновременно импульс с элемента И 70 через ПОЛЮС 15 поступает на вход считывани  блока 32 пам ти количества вход щих в узлы ветвей операционного блока ,1, где считывает записанньй код, который поступает на первый вхо вычитател  33, на второй вход которого посто нно поступает код единицы Вычитатель 33 уменьшает на единицу записанную в блоке 32 пам ти величину количества вход щих в узел ветвей . Код полученной разности посту- разрешит запись нового кода, который

пает на информационньй вход регистра 34, куда и записываетс  по этому же управл ющему импульсу, которьй задерживаетс  на соответствующее врем  элементом 55 задержки и поступает с его выхода на вход разрешени  записи регистра 34. С выхода регистра 34 новьй код количества вход щих в узел ветвей поступает на информационный вход блока 32 пам ти коли30

с выхода сумматора 78 поступает на информационньй вход узла 76 пам ти, на следующем такте ГИ4 по управл ю- . щему сигналу, которьй поступит ,с элемента И 72 через полюс 25. Таким образом, в блоке 76 пам ти по адресу номера узла будет записана максимальна  величина раннего окончани  из i- рассмотренных вход щих в данньй узел ветвей. Когда будут рассмотрены все

честв вход щих в узлы ветвей, а так- 35 вход щие в узел ветви, записанна  же на вход дешифратора 38, где срав- по номеру данного узла величина авто- ниваетс  с кодом нул . Если получен- матически станет величиной раннего ный в регистре 34 код равен нулю,то свершени  этого узла. Если же код,

полученньй на выходе сумматора 78, не превьш1ает код, имеющийс  в регистре 79, то на выходе схемы 82 сравнени  будет нулевой сигнал, которьй

это означает, что все вход щие в узел

шетви рассмотрены и узел свершилс . Тогда на выходе дешифратора 38 по - витс  единичньй сигнал, которьй разрешит формирование управл ющих импульсов на выходах элементов И 44 и 45. Если же код в регистре 34 не равен нулю, то на выходе дешифратора будет присутствовать нулевой сигнал.

По тактовому импульсу ГИЗ с выхода элемента И 71 через полюс 28 выполнитс  запись имеющегос  кода раннего свершени  конечного узла рассматриваемой ветви в регистр 79 и кода длительности этой ветви в регистр 81 блока 3 расчета характеристик. Выход регистра 80, в котором к этому моменту хранитс  код раннего свершени  начального узла рассматриваемой вет- |ви, и вьрсод регистра 81 соединены с

40

50

не разрешит запись нового значени , и в блоке 76 пам ти по номеру узла сохранитс  прежнее значение, по- . прежнему большее из всех рассмотренных ранее.

Как уже рассматривалось, по тактовому сигналу ГИ2 в регистр 34 операционного блока 1 заноситс  умень- шенньй на единицу код количества ветвей , вход щих в конечньй узел анали- . зируемой ветви. Полученньй код с выхода регистра 34 поступает на инфор- мационньй вход блока 32 пам ти коли- :честв вход щих в узлы ветвей, куда и записываетс  по адресу номера конечного узла анализируемой ветви.

O

5

0

входами сумматора 78, на выходе которого в результате будет получен код величины раннего окончани  данной ветви, который может быть равен по величине коДу раннего свершени  конечного узла данной ветви, если он максимальный среди всех вход щих в данный узел ветвей. Дл  проверки это го полученный код с выхода сумматора 78 поступает на один из входов схемы 82 сравнени , на другой вход которой поступает код с выхода регистра 79, в котором записан код раннего свершени  данного узла, равньй максимальному -.из кодов ранних окончаний рас- смотренньгх ранее вход щих в этот узел ветвей либо равный нулю, если такие ветви еще не рассматривались.

Если код, полученньй на выходе сумматора 78, больше имеющегос  в регистре 79, то на выходе схемы 82 сравнени  по витс  единичный сигнал, ко- торьй, поступив на вход элемента И 85,

0

с выхода сумматора 78 поступает на информационньй вход узла 76 пам ти, на следующем такте ГИ4 по управл ю- . щему сигналу, которьй поступит ,с элемента И 72 через полюс 25. Таким образом, в блоке 76 пам ти по адресу номера узла будет записана максимальна  величина раннего окончани  из i- рассмотренных вход щих в данньй узел ветвей. Когда будут рассмотрены все

40

0

не разрешит запись нового значени , и в блоке 76 пам ти по номеру узла сохранитс  прежнее значение, по- . прежнему большее из всех рассмотренных ранее.

Как уже рассматривалось, по тактовому сигналу ГИ2 в регистр 34 операционного блока 1 заноситс  умень- шенньй на единицу код количества ветвей , вход щих в конечньй узел анали- . зируемой ветви. Полученньй код с выхода регистра 34 поступает на инфор- мационньй вход блока 32 пам ти коли- :честв вход щих в узлы ветвей, куда и записываетс  по адресу номера конечного узла анализируемой ветви.

fO

15

который поступаеп- через полюс 16 с выхода блока 61 пам ти конечных узлов ветвей блока 2 моделировани  топологии. Сигнал записи формируетс  на выходе элемента И 71 блока 2 моделировани  топологии синхронно тактовому импульсу ГИЗ и через полюс 13 поступает на вход записи блока 32 пам ти количеств вход щих в узлы ветвей операционного блока 1.

Если код, сформированньй в регистре 34, больше нул , то это означает , что не все ветви, вход щие в данньй узел, проанализированы и тогда по тактовому импульсу ГИ4 операционный блок 1 никаких действий не выполн ет, так как нулевой сирнал на выходе дешифратора 38 нулевого состо ни  блокирует формиробание управл ющ1сс сигналов на выходе элемента И 45. В этом случае по тактовому импульсу выполн ютс  лишь описанные операции в блоке 3 расчета характеристик.

Если полученный в регистре 34 код равен нулю, то это означает, что все ветви, вход щие в данньй узел, проанализированы , т.е. величины их длительностей учтены в блоке расчета характеристик и, следовательно, их конечньй узел свершилс . Свершение узла предполагает переход к анализу выход щих из начального (либо любого другого) узла ветвей, поэтому номер свершившегос  узла необходимо запомнить . Так как в процессе текущего анализа выход щих ветвей может свершитьс  некоторое множество узлов, то необходимо организовать определенньй пор док хранени  номеров таких узлов. 40

Номера свершившихс  узлов записываютс  в виде списков в блок 31 пам ти номеров свершившихс  событий в узлах. Этот процесс организуетс  слетопологии через коммутатор 40 операционного блока 1 поступает код номера конечного узла анализируемой ветви . Управление коммутатором 40 в данном случае осуществл ет единичньй сигнал, поступающий с единичного входа триггера 67 блока 2 моделировани  топологии чере.з полюс 14. На информа- ционньй вход блока пам ти поступает содержимое регистра 35 и на вход старшего (п+1)-го разр да входа - сигнал с инверсионного выхода тригге- -ра 52. В исходном состо нии триггер 52 находитс  в нулевом состо нии, а регистр 35 очищен. При по влении сигнала с дешифратора 38 о свершении первого узла сети по сигналу с элемен та И 44 в блок 31 пам ти по номеру свершившегос  узла записываетс  со20 держимое регистра 35 и единица в старший (п+1)-й разр д, котора   вл етс  меткой конца списка.

По управл ющему сигналу, синхронному ГИ4, поступающему с блока 2 моделировани  топологии, через полюс 12 на выход элемента И 45 операционного блока поступает сигнал, по которому на выходе элемента И 45 формируетс  также управл ющий сигнал.

30 Управл ющий сигнал с элемента И 45 поступает на вход разрешени  записи регистра 35, на информационньй вход которого поступает код номера свершившегос  узла. Этот код записываетс  в регистр 35, а триггер 52 тем же управл ющим сигналом устанавливаетс  в единичное состо ние. В результате к концу тактового сигнала ГИ4 в регистре 35 запоминаетс  номер первого свершившегос  узла, а в блоке 31 пам ти по адресу номера этого узла в (п+1)-м старшем разр де записываетс  метка конца списка. При свершении в процессе продолжающегос  анализа

25

35

дующим образом. Нулевой код в регист-45 выход щих ветвей следующего узла сеO

5

0

топологии через коммутатор 40 операционного блока 1 поступает код номера конечного узла анализируемой ветви . Управление коммутатором 40 в данном случае осуществл ет единичньй сигнал, поступающий с единичного входа триггера 67 блока 2 моделировани  топологии чере.з полюс 14. На информа- ционньй вход блока пам ти поступает содержимое регистра 35 и на вход старшего (п+1)-го разр да входа - сигнал с инверсионного выхода тригге- -ра 52. В исходном состо нии триггер 52 находитс  в нулевом состо нии, а регистр 35 очищен. При по влении сигнала с дешифратора 38 о свершении первого узла сети по сигналу с элемен- та И 44 в блок 31 пам ти по номеру свершившегос  узла записываетс  со0 держимое регистра 35 и единица в старший (п+1)-й разр д, котора   вл етс  меткой конца списка.

По управл ющему сигналу, синхронному ГИ4, поступающему с блока 2 моделировани  топологии, через полюс 12 на выход элемента И 45 операционного блока поступает сигнал, по которому на выходе элемента И 45 формируетс  также управл ющий сигнал.

30 Управл ющий сигнал с элемента И 45 поступает на вход разрешени  записи регистра 35, на информационньй вход которого поступает код номера свершившегос  узла. Этот код записываетс  в регистр 35, а триггер 52 тем же управл ющим сигналом устанавливаетс  в единичное состо ние. В результате к концу тактового сигнала ГИ4 в регистре 35 запоминаетс  номер первого свершившегос  узла, а в блоке 31 пам ти по адресу номера этого узла в (п+1)-м старшем разр де записываетс  метка конца списка. При свершении в процессе продолжающегос  анализа

5

5

ре 34 преобразуетс  дешифратором 38, нулевого состо ни  в единичньй сигнал на его выходе, которьй поступил на входы элементов И 44 и 45, разрешает

1 .,., , - .

формирование на их вьпхоДах. управл ющих сигналов.;По управл ющему сигналу с полюса 13 от блока 2 моделировани  топологии на выходе элемента И 44 формируетс  сигнал, которьй по ,ти номер этого узла через полюс 16 поступает на вход коммутатора 40, который по-прежнему управл етс  единичным сигналом с полюса 14, и через 50 коммутатор 40 - на адресньй вход блока 31 пам ти.

По управл ющему сигналу, синхрон- .ному ГИЗ, с элемента И 44 операционного блока в блок пам ти по адресу

ступает на вход записи блока 31 пам -55 ; номера нового свершившегос  узла за- ти номеров свершившихс  ветвей. На писываетс  номер предьщущего свер- адресньй вход этого блока пам ти с шившегос  в процессе данного анализа полюса 16 от блока 2 моделировани . выход щих ветвей узла, хран щегос 

,ти номер этого узла через полюс 16 поступает на вход коммутатора 40, который по-прежнему управл етс  единичным сигналом с полюса 14, и через 50 коммутатор 40 - на адресньй вход блока 31 пам ти.

По управл ющему сигналу, синхрон- .ному ГИЗ, с элемента И 44 операционного блока в блок пам ти по адресу

111

в регистре 35. В старшем (п+1)-м разр де этого же информационного слова метка отсутствует, так как триггер 52 находитс  уже в единичном состо - НИИ и на вход (п+1)-го разр да посту пает нулевой сигналi По тактовому сигналу ГИ4 на выходе элемента И 45 формируетс  управл ющий сигнал, по которому выполн етс  запись кода номера вновь свершившегос  узла в ре- гистр 35 и подтверждаетс  единичное состо ние триггера 52. В результате к окончанию тактового сигнала ГИ4 в регистре 35 хранитс  код номера последнего свершившегой  узла сети, а в блоке 31 пам ти по адресу номера последующего свершившегос  узла сети хранитс  код номера предыдущего свершившегос  узла. По адресу номера первого свершившегос  узла . записываетс  метка в (п+1)-м разр де . При получении сигнала с дешифратора 38 о свершении очередного узла описанные операции повтор ютс .

Анализ ветвей, выход щих из на- чального узла сети, оканчиваетс  по сигналу, поступаюшему через полюс 11 из блока 2 моделировани  топологии . Этот сигнал вырабатываетс  дешифратором 64, которьш определ ет очередной код в регистре 63 выход щих ветвей как код X,, который  вл етс  признаком окончани  списка ветвей , выход щих из, начального узла. Сигнал с выхода дешифратора 64 уста- навливает триггер 67 в нулевое состо ние и прекращает работу блока 2 моделировани  топологии по анализу выход щих из узла ветвей. На этом заканчиваетс  этап анализа ветвей, выход щих из начального узла сети. После этого устройство переходит к анализу ветвей, выход щих из улов, свершившихс  в процессе предыдущего этапа. Так как все множество свер- шившихс  узлов записано в виде списк в блоке 31 пам ти номеров свершившихс  узлов операционного блока 1, то необходимо провести анализ ветвей, выход щих из каждого узла этого спис ка, и лишь после этого перейти к анализу ветвей, выход щих из вновь свершившихс  узлов, которые также будут записаны в блоке 31 пам ти операционного блока в виде нового списка.

По сигналу с полюса 11 от блока 2 моделировани  топологии триггер 42 операционного блока 1 устанавливаетс  в единичное состо ние. Триггер 43

15112

метки обработки в исходном состо ни находитс  в нулевом состо нии и, слдовательно , лишь на выходе элемента И 49 по тактовому сигналу ГИЗ будет сформирован управл ющий сигнал, ко- торьм установит в нулевое состо ни триггер 52 метки и через элемент ИЛИ 53 поступит на вход разрешени  записи регистра 36. На информационный вход этого регистра через коммутатор 41, управл емый в данный момент нулевым сигналом триггера 43 метки обработки, поступит содержимое регистра 35, в котором в данный момент времени находитс  код номера узла, который  вл етс  начальным в списке свершившихс  узлов, хра н щихс  в блоке 31 пам ти. По тактовому сигналу ГИЗ код номера этого узла будет записан в регистр 36. Затем задержанный на определенное врем  этот же управл ющий сигнал, пройд через элемент 58 задержки, установит в единичное состо ние триггер 43 метки обработки. Тогда (уже по тактовом сигналу ГИ4) на выходе элемента И 48 будет сформирован управл ющий сигнал который через полюс 18 поступит,в л блок 2 моделировани  топологии и выполнит почти все функции, выполн емы сигналом Пуск.

Исключени  будут в следующем. Номер узла в блок 2 моделировани  топологии поступает с выхода регистра 36 операционного блока 1 через полюс 17. С полюса 17 код номера узла поступает на второй вход коммутатора 65, которьй управл етс  в данный момент единичным сигналом с полюса 10, куда он поступает с единичного выхода триггера 42 операционного блока. Следовательно, на выходе коммутатора 65 присутствует не содержимое регистра 62 номера начального узла сети, а код номера свершившегос  узла, записанный в регистре 36 операционного блока 1. Триггер 67 блока 2 моделировани  топологии устанавливаетс  в единичное состо ние сигналом с полюса 19, куда он приходит с выхода элемента И 51 операционного блока. Так на входы элемента И 51 приход т задержанный элементом 57 задержки управл ющий сигнал по ГИ 4 с элемента И 48 и инверсный сигнал с блока 39 сравнени  кодов, который вырабатывает сигнал в случае совпадени  кода свершившегос  узла в регистре 36

13

кода конечного узла сети в реистре 37, то на выходе элемента И 51 полюсе 19 сигнал по витс  несколько озже, чем на полюсе 18, и только том случае, если узел, анализ выод щих ветвей которого предстоит сделать, не  вл етс  конечным узлом сети.

Одновременно сигнал с выхода элеента 57 задержки сбрасывает триггер 42 в нулевое состо ние и прекращает работу операционного блока 1. Далее повтор ютс  описанные операции этапа анализа выход щих из узла ветвей. Никаких отличий, кроме отмеченных, от приведенного описани .-нет. Лишь по окончании этапа в св зи с тем, что триггер 43 метки обработки находилс  все это врем  в единичном состо нии , на выходе элемента И 46.по тактовому сигналу Г112 будет сформирован упрагзл ющий сигчал, которьй поступит на вход считывани  блока 31 пам ти, на адресный вход которого через коммутатор 40, управл емьй в данный момент нулевым сигналом с 14 (так как триггер 67 блока 2 моделировани  топологии по окончании этапа, анализа списка ветвей, выход щих из узла, сбрасываетс  в нуль), поступит код номера узла, хран щийс  в регистре 36. По этому адресу из блока 31 пам ти будет считан код следующего в анализируемом сниске свершившегос  узла.

Считанный код с выхода блока 31 пам ти через коммутатор 41, управл емый в данный юмент единичным сиг- напом с триггера 43, поступает на ин- формационньп вход регистра 36 и записываетс  туда по тактовому сигналу ГИЗ с выхода элемента И 47. В случае, если считанньй код  вл етс  номером свершившегос  узла анализируемого списка, то на выходе старшего (п+1)- го разр да снова будет присутствовать нулевой сигнал метки, который запретит формирование сигнала на выходе элемента И 50. Если же в (п+ 1)-м разр де будет единица, то это означает окончание обработки данного списка свершившихс  узлов и на выходе элемента И 50 по витс  сигнал, которьй через элемент 56 задержки сбросит в нулевое состо ние триггер 43 метки обработки. Тогда по тактовому сигналу ГИ4, сформированному на выходе элемента И 48, сигнал не

- - , , 8215114

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

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

W

f5

20

25

30

35

40

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

При анализе этого последнего списка конечньй узел сети будет занесен в регистр 36 и тогда на выходе блока 39 сравнени  кодов по витс  единичньй сигнал,  вл ющийс  результатом совпадени  кодов в регистрах 36 и 37, которьй через элемент НЕ 54 и элемент И 51 запретит подачу управл ющего сигнала через полюс 19 и блок 2 моделировани  топологии. В результате он не будет включен в работу по анализу выход щих из этого узла ветвей (так как их нет) и в блок 3 расчета характеристик с выхода блока 39 через полюс 20 поступит сигнал разрешени  выдачи кода величины длиннейшего пути в сети, которьй разре45

шит через группу элементов И 84 выдачу на выходной полюс устройства содержимого регистра 80, куда по сигналу- с полюса 21 будет считан код раннего свершени  данного узла, что соответствует по определению вели- v чине длиннейшего пути.

К этому моменту времени в блоке 31 пам ти будет сформирована информаци  о величинах ранних свершений событий всех узлов сети, т.е. коды величин длиннейших путей до каждого узла (от начального). В совокупности с исходной информацией о величинах де тельностей ветвей в ёлоке 77 пам ти это составит функционально полньй набор исходных данных дл  быстрого определени  любого, перечисленного набора рассчитьшае50

15 12

мых характеристик, а также их любой композиции. Использование новых блоков (операционного и расчета характеристик ) позвол ет в отличие от известных устройств существенно сокра- тить врем  расчета и отказатьс  от использовани  блока моделей вртвей.

При моделировании сети отсутствует процесс временного моделировани  длительностей ветвей, а при оценке свертени  узлов используетс  блок 32 па- м ти количества вход щих в узлы ветвей . Это приводит к тому, что процесс анализа свершени  узла существенно сокращаетс , так как нет необходимости после свершени  каждой вход щей в узел ветви перебирать весь список вход щих ветвей, провер   свершени  каждой. Достаточно проверить количество несвершившихс  ветвей,ко- торое в виде кода посто нно формируетс  и корректируетс  в блоке 32 пам ти.

Claims (1)

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

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

   5

   0

   5

   0

   5

   0

   5

   0

   5

   15116

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

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

   O

   0

   0

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

   0

   сов, выход второго элемента И опера0

   ционного блока соединен с единичным входом третьего триггера операционного блока и с выходом разрешени  записи второго регистра операционного блока, выход которого соединен с вторым информационным входом второго коммутатора операционного блока и с п младшими разр дами информационного входа блока пам ти номеров свершив- IШixc  событий в узлах, вход (п+1)-го

   5 разр да информационного входа которого соединен с нулевым выходом третьего триггера операционного блока, выход второго коммутатора операционного блока соединен с информационным входом третьего регистра операционного блока, выход которого подключен к второму информационному входу первого Kot iMyTaTopa операционного блока п второму информационному входу пер вого коммутатора блока моделировани  топологии, управл ющий вход первого коммутатора операционного блока соединен с единичным вь1ходом первого триггера блока моделировани  топологии , выход первого коммутатора операционного блока подключен к адресному входу блока пам ти номеров свершившихс  событий в узлах операционного блока, выход третьего элемента

   55 И операционного блока соединен с

   входом-считывани  блока пам ти номеров свершившихс  событий в узлах операционного блока, выход (п+1)-го

   0

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

   O

   0

   5

   первым входом сумматора блока расчета характеристик, выход которого ;подключен к информационному входу блока пам ти ранних окончаний событий в узлах блока расчета характеристик , выход которого соединен с информационными входами первого и второго регистров блока расчета характеристик , выход блока пам ти номеров конечных узлов ветвей соединен с первым информационным входом коммутатора блока расчета характеристик , второй информационный вход которого соединен с вькодом первого комму татора блока моделировани  топологии и адресным входом блока пам ти номеров первых выход щих из узлов ветвей блока моделировани  топологии , единичньй выход второго триггера блока моделировани  топологии соединен с управл ющим входом коммутатора блока расчета характеристик, выход которого подключен к адресному входу блока пам ти ранних окончаний событий в узлах блока расчета характеристик , выход четвертого элемента И блока моделировани  топологии соединен с первым входом элемента И блока расчета характеристик, выход которого подключен к входу записи блока пам ти ранних окончаний событий в уз- . ,лах блока расчета характеристик,вход считывани  которого соединен с выходом элемента ИЖ блока расчет;а 5 характеристик, второй вход которого соединен с выходом второго элемента И блока моделировани  топологии и с входом считывани  блока пам ти кодов весов длительности ветвей блока расчета характеристик, выход которого соединен с информационным входом третьего регистра блока расчета характеристик , выход которого соединен с вторым входом сумматора блока расчета характеристик, выход которого подключен к первому входу схемы сравнени  блока расчета характеристик, выход третьего элемента И блока моделировани  топологии соединен с входами разрешени  записи второго и третьего регистров блока расчета характеристик, выход второго регистра блока расчета характеристик соединен с вторым входом схемы срав- 5 нени  блока расчета характеристик, выход которой подключен к второму входу элемента И блока расчета харак- тегистик, выход регистра номеров вы0

   0

   5

   0

   21128215122

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

   фаг. /

   Редактор С. Пекарь

   Ф1/г.з

   Составитель С. Назаров

   Техред М.Ходанич Корректор Е . Сирохман