Устройство для определения характеристик сетей Советский патент 1987 года по МПК G06F15/173 

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

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

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

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 выходящих ветвей следующего узла сере 34 преобразуется дешифратором 38, нулевого состояния в единичньй сигнал на его выходе, которьй поступил на входы элементов И 44 и 45, разрешает

1 .,., , - .

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

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

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

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

,ти номер этого узла через полюс 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 памяти.

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

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

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/г.з

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

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

Заказ 7262/49

Тираж 670Подписное

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

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

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

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