Устройство для определения характеристик сетей

 

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

СОЮЗ СОВЕТСКИХ соцИАлистичесних

РЕСГ1УЬЛИК

09) (11) (g1) 4 G 06 F 15/20

Г

Ф .i

<.

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР по делАм изоБРетений и ОткРытий (21) 3806351/24-24 (22) 25.10.84 (46) 07.01.87. Бюл. Ф 1 (71) Институт проблем моделирования в энергетике АН УССР (72) А.Г. Додонов, Л.И. Минченко, С.П. Пелехов и Н.М. Сасюк (53) 681.333(088.8) (56) Авторское свидетельство СССР

В 422002, кл. G 0 G 7/48, 1972.

Авторское свидетельство СССР

В 1024930, кл. 0 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК СЕТЕЙ (57) Изобретение относится к области вычислительной техники, в частности к устройствам обработки информации специального назначения с точки зрения,конструкции вычислительного устройства. Целью изобретения является повышение быстродействия при определении характеристик сетей. Поставлен-I ная цель достигается эа счет дополнительного введения операционного блока, содержащего блок памяти номеров свершившихся событий в узлах, вы- . читатель, регистры, элементы И, ИЛИ, НЕ и элементы задержки, регистр номера конечного узла сети, дешифратор нулевого состояния, блок сравнения кодов коммутатора, триггеры, блок памяти количеств входящих в уз1 лы ветвей, два блока расчета характеристик, содержащего два блока памяти ранних окончаний событий в узлах, сумматор, регистры и элементы И, ИЛИ, блок памяти кодов весов длительности ветвей. В блок моделирования тополо- Ж гни введены два коммутатора, регистр фр номера начального узла сети н элемент задержки. Быстродействие при расчете характеристик сетей увеличивается по крайней мере в 1,5 — 2 раза по срав- Я нению с известными устройствами за счет изменения процедур обработки 1 исходной информации. 3 ил. 00

12821

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

Цель изобретения — повышение бы-! .стродействия устройства при определе- 10 нии характеристик сетей.

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

f5 фиг. 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 расчета характеристик предназначен для определения, хранения и выдачи расчетных характеристик моделируемой сети. Генератор

51 2

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 состояния предназначен для дешифраций кода, (Коммутаторы 65 и 66 предназначены

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

Блок 3 расчета характеристик (фиг.

3), содержит блок 76 памяти ранних окончаний событий в узлах, блок 77 памяти кодов весов длительностей ветвей, сумматор 78, три регистра 79;81, схему 82 сравнения, коммутатор 83, группу элементов И 84, элемент И 85, элемент ИЛИ ЯГ>.

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

N-разрядного кода резултата. Все остальные триггеры, элементы И, ИЛИ, 30

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

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

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

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

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

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

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

Номера первых списков хранятся в блоке 60 памяти по адресам номеров узлов, которые являются начальными для ветвей данных списков. В блоке

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

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

1282151

После выполнения описанных предварительных установок и ввода перечисленной исходной информации устройство начинает работу по сигналу "Пуск", который поступает с входного полюса 5 5 устройства в блок 2 моделирования топологии. Сигнал "Пуск" через элемент

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

В результате по сйгналу 1 Пуск" на выход блока 60 памяти считывается номер первой ветви, выходящей из данного узла, который через коммутатор 66, управляемый единичным состоянием триггера 68, поступает на информационный вход регистра 63. Одновременно с выхода коммутатора код номера начального узла через полюс 23 поступает в блок 3 расчета характеристик и через коммутатор 83, управляемый единичным сигналом, поступающим через полюс 24 с триггера 68, поступает на адресный вход блока 76 памяти ранних окончаний событий в узлах, Сигнал "Пуск" с выхоца элемента ИЛИ 73 блока 2 моделирования топологии через полюс 26 и элемент ИЛИ

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

Код раннего свершения события узла поступает на информационный вход регистра 80, куда и записывается по сигналу "Пуск", задержанному элементом 75. задержки блока 2 моделирования топологии, и поступающему на вход разрешения записи регистра 80 блока расчета характеристик через полюс 21.

Триггер 67 управления блока 2 моделирования топологии, установленный в единичное состояние сигналом "Пуск", разрешает формирование на выходах элементов И 69-72,импульсов управления,: синхронных импульсам ГИ1-ГИ4 тактового генератора, поступающим на входы этик элементов соответственно через полюсы 6-9.

По импульсу ГИ1 с выхода элемента

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

По импульсу ГИ2 с выхода элемента И 70 в блоке 59 памяти номеров выходящих из узлов ветвей считывается по адресу номера первой ветви, код номера которой с выхода регистра

63 поступает на адресный вход блока

59 памяти, код номера следующей выходящей из данного (начального) узла

1 ветви. По этому же сигналу триггер

68 устанавливается в нулевое состояние. Считанный в блоке 59 памяти код номера следующей ветви поступает на второй вход коммутатора 66, управляемого теперь нулевым сигналом триггера 68, и с выхода его поступает на информационный вход регистра

63. Нулевой сигнал с выхода триггера 68 через полюс.24 разрешает поступление кода номера конечного узла первой выходящей ветви, код которой пока еще находится в регистре

63, через коммутатор 83 на адресный вход блока 76 памяти ранних окончаний событий в узлах блока 3 расчета карактеристик. Управляемый импульс с выхода элемента И 70 блока 2 моделирования топологии через полюс

27 и элемент ИЛИ 86 поступает на вход считывания блока 76 памяти блока 3 расчета характеристик. По номеру конечного узла ветви считыва7 12 ется величина раннего свершения этого узла.

Код считанной величины поступает на информационный вход регистра 79.

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

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

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

45. Если же код в регистре 34 не равен нулю, то на выходе дешифратора будет присутствовать нулевой сигнал.

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

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

78 поступает на один из входов схемы

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

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

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

Как уже рассматривалось, по тактовому сигналу ГИ2 в регистр 34 операционного блока 1 заносится уменьшенный на единицу код количества ветвей, входящих в конечный узел анализируемой ветви. Полученный код с выхода регистра 34 поступает на инфор5 мационный вход блока 32 памяти коли:честв входящих в узлы ветвей, куда и записывается по адресу номера конечного узла анализируемой ветви, который поступае г через полюс 16 с выхода блока 6 1 памяти конечных узлов ветвей блока 2 моделирования топологии. Сигнал записи формируется на выходе элемента И 71 блока 2 моде- 5 лирования топологии синхронно тактовому импульсу ГИЗ и через полюс 13 поступает на вход записи блока 32 памяти количеств входящих в узлы ветвей операционного блока 1. f0

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

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

Номера свершившихся узлов записываются в виде списков в блок 31 памяти номеров свершившихся событий в узлах. Этот процесс организуется следующим образом, Нулевой код в регист- 4> ре 34 преобразуется дешифратором 38. нулевого состояния в единичный сигнал на его выходе, который поступил на входы элементов .И 44 и 45, разрешает

1 формирование на их выходах управляющих сигналов. По управляющему сигналу с полюса 13 от блока 2 моделирования топологии на выходе элемента

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

1282151 10 топологии через коммутатор 40 операционного блока 1 поступает код номера конечного узла анализируемой вет-. ви. Управление коммутатором 40 в данном случае осуществляет единичный сигнал, поступающий с единичного входа триггера 67 блока 2 моделирования топологии через полюс 14. На информационный вход блока памяти поступает содержимое регистра 35 и на вход старшего (и+1)-го разряда входа— сигнал с инверсионного выхода тригге.ра 52. В исходном состоянии триггер

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

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

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

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

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

11 1282 в регистре 35. В старшем (n+1)-м разряде этого же информационного слова метка отсутствует, так как триггер

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

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

11 из блока ? моделирования топологии. Этот сигнал вырабатывается дешифратором 64, который определяет 30 очередной код в регистре 63 выходящих ветвей как код Х,, который является признаком окончания списка ветвей, выходящих из начального узла.

Сигнал с выхода дешифратора 64 устанавливает триггер 67 в нулевое состояние и прекращает работу блока 2 моделирования топологии по анализу выходящих из узла ветвей. На этом заканчивается этап анализа ветвей, 40 выходящих из начального узла сети.

После этого устройство переходит к анализу ветвей, выходящих из улов, свершившихся в процессе предыдущего этапа. Так как все множество свер- 45 шившихся узлов записано в виде списка в блоке 31 памяти номеров свершившихся узлов операционного блока 1, то необходимо провести анализ ветвей, выходящих из каждого узла этого спис-50 ка, и лишь после этого перейти к анализу ветвей, выходящих из вновь свершившихся узлов, которые также будут записаны в блоке 31 памяти опера/ ционного блока в виде нового списка. 55

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

151 12 метки обработки в исходном состоянии находится в нулевом состоянии и, следовательно, лишь на выходе элемента

И 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

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

Одновременно сигнал с выхода элемента 57 задержки сбрасывает триггер

42 в нулевое состояние и прекращает работу операционного блока 1, Дапее повторяются описанные операции этапа анализа выходящих из узла ветвей.

Никаких отличий, кроме отмеченных, от приведенного описания нет. Лишь по окончании этапа в связи с. тем, что триггер 43 метки обработки нахо" дился все это время в единичном состоянии, на выходе элемента И 46 по тактовому сигналу ГИ2 будет сформирован управляющий сиг ал, который поступит на вход считывания блока

31 памяти, на адресный вход которого через коммутатор 40, управляемый в данный момент нулевым сигналом с полюса 14 (так как триггер 67 блока

2 моделирования топологии по окончании этапа. анализа списка ветвей, выходящих из узла, сбрасывается в нуль), поступит код номера узла, хранящийся в регистре 36. lIo этому адресу иэ блока 31 памяти будет считан код следующего в анализируемом списке свершившегося узла.

Считанный код с выхода блока 31 памяти через коммутатор 41, управляемый в данный, момент единичным сигналом с триггера 43, поступает на информационный вход регистра 36 и записывается туда по тактовому сигналу

ГИЗ с выхода элемента И 47. В случае, если считанный код является номером свершившегося узла анализируемого списка, то на выходе старшего (и+1)ro разряда снова будет присутствовать нулевой сигнал метки, который запретит формирование сигнала на выходе элемента И 50, Если же в (n+

1)-м разряде будет единица, то это означает окончание обработки данного списка свершившихся узлов и на выходе элемента И 50 появится сигнал, который через элемент 56 задержки сбросит в нулевое состояние триггер

43 метки обработки. Тогда по тактовому сигналу ГИ4, сформированному на выходе элемента И 48, сигнал не

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

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

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

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

36 и 37, который через элемент HE

54 и элемент И 51 запретит подачу управляющего сигнала через полюс 19 и блок 2 моделирования топологии.

B результате он не будет включен в работу по анализу выходящих из этого узла ветвей (так как их нет) и в блок

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

45 раннего свершения данного узла, что соответствует по определению величине длиннейшего пути.

К этому моменту времени в блоке

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

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

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

20 количество несвершившихся ветвей,которое в виде кода постоянно формиру" ется и корректируется в блоке 32 памяти.

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

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

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

25 входом первого коммутатора операционного блока и с выходом блока памяти номеров конечных узлов ветвей блока моделирования топологии, выход четвертого элемента И блока моделирования топологии подключен к первому входу второго элемента И операционного блока, выход второго элемента И блока моделирования топологии соединен с входом считывания блока памяти количеств входящих в узлы 35 . ветвей и входом первого элемента задержки операционного блока, выход подключен к входу разрешения записи первого регистра операционного блока, выход которого соединен с вхо- 40 дом дешифратора нулевого состояния операционпого блока, .выход которого соединен с вторыми входами первого и второго элементов И операционного блока, выход первого элемента И операционного блока подключен к входу записи блока памяти номеров свершившихся событий в узлах операционного блока, выходы п младших разрядов которого соединены с соответствующими информационными входами второго коммутатора операционного блока, управляющий вход которого. подключен к единичному выходу второго триггера операционного блока и к первым входам третьего четвертого и пятого элементов И операционного блока, нуле-ой выход второго триггера операци51 18 онного блока соединен с первым входом шестого элемента И операционного блока, выход которого подключен к входу второго элемента задержки операционного блока, выход второго элемента задержки операционного блока соединен с нулевым входом первого триггера операционного. блока, выход дешифратора состояния блока моделирования топологии соединен с единичным входом первого триггера операционного блока, единичный выход которого соединен с вторыми входами третьего, четвертого-, пятого и шестого элементов И операционного блока, третьи входы третьего, четвертого и пятого элементов И операционного блока соединены соответственно с вторым, третьим и четвертым выходами генератора тактовых импульсов, третий вход шестого элемента И операционного блока подключен к третьему выходу генератора тактовых импульсов, выход второго элемента И операционного блока соединен с единичным входом третьего триггера операционного блока и с выходом разрешения записи второго регистра операционного блока, выход которого соединен с вторым информационным входом второго коммутатора операционного блока и с и младшими разрядами информационного входа блока памяти номеров свершивiыхся событий в узлах, вход (п+1)-ro разряда информационного входа которого соединен с нулевым выходом третьего триггера операционного блока, выход второго коммутатора операционного блока соединен с информационным входом третьего регистра операционного блока, выход которого подключен к второму информационному входу первого коммутатора операционного блошка и второму информационному входу первого коммутатора блока моделирования, топологии, управляющий вход первого коммутатора операционного блока соединен с единичным выходом первого триггера блока моделирования топологии, выход перво>о коммутатора операционного блока подключен к адресному входу блока памяти номеров свершившихся событий в узлах операционного блока, выход третьего элемента

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

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

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

51 20 первым входом сумматора блока расчета характеристик, выход которого !

:подключен к информационному входу блока памяти ранних окончаний событий в узлах блока расчета характеристик, выход которого соединен с информационными входами первого и второго регистров блока расчета характеристик выход блока памяти номеров конечных узлов ветвей соединен с первым информационным входом коммутатора блока расчета характеристик, второй информационный вход которого соединен с выходом первого коммутатора блока моделирования топологии и адресным входом блока памяти номеров первых выходящих иэ узлов ветвей блока моделирования топологии, единиЧный выход второго триггера блока моделирования топологии соединен с управляющим входом коммутатора блока расчета характеристик, выход которого подключен к адресному входу блока памяти ранних окончаний событий в узлах блока расчета характеристик, выход четвертого элемента

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

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

22 элементов И г руппы блока рас чета характеристик являются информа ционными выходами ус тройст ва.

Фиг. /

1282151

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

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

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

Заказ 7262/49 Тираж 670

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

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

Подписное

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