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

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

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

На фиг.1 представлена функциональная схема примера реализации устройства; на фиг. 2 - функциональная схема блока формирования топологии; на фиг. 3 - функциональная схема блока моделей ветвей; на фиг. 4 - обобщенная структурная схема устройства; на фиг 5 и 6 - блок-схемы алгоритма определения величины длиннейшего пути в графе.

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

Блок 1 управления в свою очередь содержит узел 5 памяти длительностей ветвей, узел 6 памяти номеров моделируемых ветвей, узел 7 памяти меток свершения ветвей, узел 8 памяти значения свершения узлов сети, узел 9 памяти меток незагруженных ветвей, узел 10 измерения длиннейшего пути, триггер 11 прерывания, элементы И 12 - 18, элементы ИЛИ 19 - 26,элементы НЕ 27 и 28, схему 29 сравнения кодов, счетчик 30 поиска незагруженных ветвей, вспомогательные элементы задержки 31 - 38.

Выход 39 номера подготавливаемой к моделированию ветви блока 2 формирования топологии соединен с адресным входом узла 5 памяти, информационным входом узла 6 памяти и входами элементов ИЛИ 19 и 24 блока 1 управления. Выход 40 поиска свободной модели ветви блока 2 формирования тополо(Л

с:

ел

Јь

00

со w

гии соединен с входом считывания узла 5 памяти, через вспомогательный элемент 31 задержки с входом записи узла 6 памяти, с входом элемента ИЛИ 20 и через вспомогательный элемент 32 задержки с входом элемента И 12 блока 1 управления. Выход 41 номера анализируемой ветви блока 2 формирования топологии соединен через .элемент ИЛИ 19 с адресным входом узла 7 памяти блока 1 управления. Выход 42 проверки свершения ветви блока 2 формирования топологии соединен через элемент ИЛИ 20 с входом считывания узла 7 памяти блока 1 управления, Вь ход 43 номера начального узла ветви блока 2 формирования топологии через элемент ИЛИ 21 соединен с адресным входом узла 8 памяти блока 1 управления. Выход 44 номера конечного узла ветви блока 2 формирования топологии соединен через элемент ИЛИ 21 с адресным входом узла 8 памяти блока 1 управления. Выход 45 поиска прерывания блока 2 формирования топологии соединен с входом установки в единичное состояние триггера I1 прерывания блока 1 управления и с входом 46 блока 3 моделей ветвей„ Выход 47 индикации результата расчета блока 2 формирования топологии соединен с входом элемента И 17 блока 1 управления.

Выход 48 номера модели ветви блока моделей ветвей 3 соединен с адресным входом узла 6 памяти блока 1 управления. Выход 49 прерывания блока моделей ветвей 3 соединен с входом считывания узла 6 памяти, через элемент ИЛИ 23 с входом установки в нулевое состояние триггера 11 прерывания и входом элемента 33. задержки блока 1 управления. Выход 50 наличия занятых моделей ветвей блока 3 моделей ветвей соединен с входом элемента И 15 и через элемент НЕ 28 с входом элемента И 8 блока I управления. Выход 51 наличия свободных моделей ветвей блока 3 моделей ветвей соединен с информационным входом узла 9 памяти блока 1 управления.

Выход номера свершенной ветви сети узла 6 памяти блока 1 управления соединен с входом 52 блока 2 формирования топологии, Выход начала анализа свершения ветви сети элемента 34 задержки блока 1 управления соединен с входом 53 блока 2 формирования топологии Выход свершения ветви узла

0

5

0

5

0

5

0

5

7 памяти блока 1 управления соединен с входом 54 2 формирования топологии Выход пуска элемента ИЛИ 25 блока 1 управления соединен с входом 55 блока 2 формирования топологии. Выход номера ветви, исходящей из узла сети, элемента ИЛИ 26 блока 1 управления соединен с входом 56 блока 2 формирования топологии.

Выход кода длительности ветви узла 5 памяти блока 1 управления соединен с входом 57 блока 3 моделей ветвей Выход поиска свободной модели ветви элемента И 12 блока 1 управления соединен с входом 58 блока 3 моделей ветвей0 Выход импульсов измерительной серии элемента И 15 блока 1 управления соединен с входом 59 блока 3 моделей ветвей.

Входные полюса 60 и 61 блока 2 формирования топологии предназначены для подключения сдвинутых друг относительно друга серии импульсов ГИ1 и ГИ2 генератора 4 импульсов.

Входными полюсами устройства являются входные полюса 62 и 63 блока управления 1. Выходным полюсом устройства является выходной полюс 64 бАока 1 управления, соединенный с выходом элемента И 17 блока 1 управления

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

В блоке 1 управления (фиг,1) узел 5 памяти длительностей ветвей предназначен для хранения информации о величинах длительностей ветвей-сети, а именно для хранения по адресу номера ветви кода длительности данной

ветви. Узел 6 памяти номеров моделируемых ветвей предназначен для хранения информации о соответствии номера модели ветви из блока 3 моделей ветвей номеру ветви сети, моделируемой в текущий момент времени данной моделью ветви. Узел 7 памяти меток свершения ветвей сети предназначен для хранения информации о завершении процесса временного моделирования длительностей ветвей сети. Узел 8 памяти значения свершения узлов сети служит для хранения информации о величине раннего свершения каждого узла сети. Узел 9 памяти меток незагруженных ветвей сети предназначен для хранения информации о том, что длительность данной ветви не моделировалась из-за отсутствия свободных моделей ветвей в блоке 3 моделей ветвей.Узел 10 измерения длиннейшего пути предназначен для формирования величины длиннейшего пути сети и может быть выполнен в виде счетчика с счетным входом, входом приема параллельного кода и с параллельной выдачей информации.

Триггер 11 прерывания предназначен для организации временного разделения между процессом моделирования длительностей ветвей сети и процессом анализа топологии моделируемой сети. Элемент И 12 предназначен для организации выдачи сигнала поиска свободной модели ветви в блок 3 моделей ветвей только.в случае нулевой метки свершения данной ветви. Элемент И 13 предназначен для формирования сигнала записи в узел 8 памяти только в том случае, если код узла 10 измерения длиннейшего пути будет больше кода узла 8 памяти значения свершения узлов. Элемент И 14 предназначен для организации выдачи сигнала с выхода триггера 1I прерывания только в момент действия сигнала ГИ2.Элемент И 15 предназначен для организации выдачи импульсов измерительной серии в устройство 10 измерения длиннейшего пути и в блок 3 моделей ветвей только при наличии занятых моделей ветвей в блоке 3 моделей ветвей. Элемент И 16 предназначен для формирования сигнала только в случае считывания единичной метки из узла 9 памяти меток незагруженных ветвей.Элемент И 17 предназначен для организации выдачи результата вычислений вели0

5

0

5

чины длиннейшего пути из узла вычисления длиннейшего пути только при наличии сигнала индикации расчета из блока 2 формирования топологии. Элемент И 18 предназначен для формирования сигнала считывания узла 9 памяти по сигналу ГИ2 генератора 4 импульсов в случае единичного выхода триггера 11 прерывания блока 1 управления и отсутствия сигнала о наличии занятых моделей ветвей из блока 3 моделей ветвей. Элементы ИЛИ 19-26 предназначены для формироврния соответствующих сигналов из двух направлений. Элемент НЕ 27 предназначен для получения нужного логического уровня сигнала свершения ветви из узла 7 памяти блока 1 управления. Элемент НЕ 28 предназначен для получения нужного логического уровня сигнала наличия занятых моделей ветвей из блока 3 моделей ветвей. Схема 29 сравнения кодов 29 предназначена для получения сигнала в случае, если код узла 10 измерения длиннейшего пути будет больше кода, считанного из узла 8 памяти блока 1 управления. Счетчик 30 поиска незагруженных ветвей предназначен для формирования кода, который поступает на адресный вход узла 9 памяти блока 1 управления при поиске незагруженных ветвей. Вспомогательные элементы 31 - 38 задержки предназначены для предотвращения гонок при работе устройства.

Блок 2 формирования топологии (фиг.2) содержит узел 65 памяти адресов начальных узлов ветвей сети, узел 66 памяти адресов конечных узлов ветвей сети, узел 67 памяти адресов выходящих ветвей узлов сети, узел 68 памяти адресов входящих ветвей узлов сети, узел 69 памяти адре- , сов первой выходящей ветви узлов сети, узел 70 памяти адресов первой входящей ветви узлов сети, регистр

71адреса выходящей ветви, регистр

72адреса входящей ветви, регистр 73 адреса конечного узла ветви, регистр 74 конечного узла сети, триггеры 75 и 76, дешифраторы 77 и 78, дешифратор 79 сравнения кодов, элементы 80 и 81 задержки, элементы ИЛИ 82 - 88, элементы И 89 - 94, элемент НЕ 95.

Входами блока 2 формирования топологии являются полюса 55 и 56,соединенные соответственно с входом считы-- вания и адресным входом узла 65 памя,0

5

0

0

5

715

ти начального узла. Вход 52 номера анализируемой ветви сети блока 2 формирования топологии соединен с адресным входом узла 66 памяти конечного узлас Вход 53 начала анализа свершения ветви соединен с входом считывания узла 66 памяти конечного узла Вход свершения ветви 54 соединен через элемент НЕ 95 и элемент ИЛИ 87 с входом установки нуля триггера 75,

Выход А5 поиска прерывания блока 2 формирования топологии соединен с выходом элемента ИЛИ 85„ Выход 43 номера начального узла ветви соединен с выходом узла 65 памяти адресов начальных узлов ветвей сети. Выход 39 номера подготавливаемой к моделированию ветви соединен с выходом регистра 71 адреса выходящей ветви. Выход 44 номера конечного узла ветви соединен с выходом узла 66 памяти адресов конечных узлов ветвей сети. Выход 41 номера анализируемой ветви соединен с выходом регистра 72 адреса входящей ветви. Выход 40 поиска свободной модели ветви соединен с выходом элемента И 94, Выход 42 проверки свершения ветви соединен с выходом элемента И 92„ Выход 47 разрешения выдачи результата соединен с выходом элемента И 90. Узел 65 памяти предназначен для хранения номера начального узла ветви по адресу номера данной ветви, Узел 66 памяти предназначен для хранения номера конечного узла ветви по адресу номера данной ветви,Узел 69 памяти предназначен для хранения по адресу номера узла номера ветви, первой из списка выходящей из данного узла ветвей.

Узел 70 памяти предназначен для хранения по адресу номера узла,номера ветви, первой из списка входящих в данный узел ветвей. Узел 67 памяти предназначен для хранения в виде списков номеров ветвей, выходящих из узлов сети. Узел 68 памяти предназначен для хранения в виде списков номеров ветвей, входящих в узлы сеткв

Регистр 71 блока 2 формирования топологии предназначен для промежуточного хранения номера ветви при определении ветвей, выходящих из узла, Регистр 72 предназначен для промежуточного хранения номеров ветвей,входящих в узел. Регистр 73 предназначен для хранения номера рассматриваемого узла сети Регистр 74 предназна

0

5

0

5

793

0

5

0

5

0

5

8

чен для хранения номера конечного узла сети0

Дешифратор 79 сравнения кодов блока 2 формирования топологии предназначен для поразрядного сравнения кодов из регистров 73 и 74. Дешифраторы 77 и 78 состояния X предназначены для сравнения поступающих на них кодов с кодовой комбинацией состояния X, заданного постоянно в схеме

Блок 3 моделей ветвей (фиг.З) содержит п моделей ветвей 96(1), 96(2),...,96(n), где п - любое число ъ , и узла 97 поиска моделей ветвей. Цифрами в скобках обозначены порядковые номера совершенно одинаковых по своему конструктивному исполнению и Функциональному назначению блоков, узлов,, элементов и полюсов.

Каждая модель ветви 96 (фиг.З) состоит из формирователя 98 временных интервалов, триггеров 99 и 100, элементов И 101 - 106, элемента ИЛИ 107, элементов задержки 108 и 109.

Схема узла 97 поиска моделей ветвей блока 3 моделей ветвей (фиг.З), содержит шифратор 110 адреса и элементы ИЛИ 111 - 114,

Входы 57(1), 57(2),...,57(п) кода длительности блока 3 моделей ветви соединены с входами элементов И 105(1), 105(2),...,105(п). Входы 59(1), 59(2),.. . ,59(п) измерительной серии импульсов соединены с входами

элементов И 106(1), 106(2)106(п).

Вход 58(1) поиска свободной модели ветви соединен с входами элемента И 104(1) первой модели ветви 96(1). Выход элемента 103(1) первой модели ветви 96(1) соединен с входом 58(2) блока поиска свободной модели ветви второй модели ветви 96(2), выход элемента 103(2) соединен с входом 58(3) блока третьей модели ветви 96(3) и т.д.

Вход 46 поиска прерывания соединен с входом элемента ИЛИ 111 узла 97 поиска моделей ветвей блока 3 моделей ветвей. Выход элемента ИЛИ 111 узла 97 поиска моделей ветвей соединен с входом 1,1 поиска прерывания первой модели ветви 96(1). Здесь и везде в дальнейшем первая цифра в скобках обозначает номер модели ветви, а вторая - порядковый номер входа или выхода этой модели.

Входы 1,1, 2,1,...,п,1 поиска прерывания моделей ветвей 96(1), 96(2),.„.,96(п) соединены с входами элементов И 101(1), 101(2),.„.,101(п

и 102(1), 102(2)102(п).Выход

элемента И 101(1) первой модели ветви 96(1) соединен с входом 2,1 поиска прерывания, второй модели ветви 96(2), выход элемента И 101(2) второй модели ветви 96(2) соединен с входом 3.1 поиска прерывания третьей модели ветви 96(3) и т.д. до п-й модели ветви. Выходы 1,2, 2,2,,,., . ,., переполнения формирователей временных интервалов 98(1),98(2 ),... ...,98(п) моделей ветвей 96(1), 96(2),...,96(п) соединены с входами элемента ИЛИ 111 узла поиска моделей ветвей 97. Выходы 1 „4,2,4, ...,п.4 сигналов прерывания с выходов элементов И 102(1),102(2),...,102(п) моделей ветвей 96(0,96(2), ...,96(n) соединены с входами элемента ИЛИ 112 узла поиска моделей ветвей 97. Выходы 1.3,2.3,...,п,3 кода моделей ветвей с выходов элементов ИЛИ 3 07(1), 107(2),...,107(п) моделей ветвей 96(1), 96(2),.,.,96(п) соединены с входами шифратора адреса 110 узла поиска моделей ветвей 97. Выходы 1.5, 2,5,,..,п,5 наличия занятых моделей ветвей с единичного выхода триггеров 99(0,99(2), ...,99(п) моделей ветвей 96(0,96(2), ...,9б(п) соединены с входами элемента ИЛИ ИЗ узла поиска моделей ветвей 97. Выходы 1.6, 2.6,...,п.6 наличия свободных моделей ветвей с нулевого выхода триггеров 99(1), 99(2),...,99(п) моделей ветвей 96(1),96(2),...,9б(п) соединены с входами элемента ИЛИ 114 узла поиска моделей ветвей 97. Выход 49 прерывания блока 3 моделей ветвей соединен с выходом элемента ИЛИ 112 узла поиска моделей ветвей 97, Выход 48 номера модели ветви блока 3 моделей ветвей соединен с выходом шифратора ПО адреса узла поиска модели ветви 97. Выход наличия занятых моделей ветвей 50 блока 3 моделей ветвей соединен с выходом элемента ИЛИ 113 узла поиска моделей ветвей 97. Выход 51 наличия свободных моделей ветвей блока 3 моделей ветвей соединен с выходом элемента ИЛИ 114 узла поиска моделей ветвей 97.

Фо-рмирователи 98(0,98(2),..., ...,98(п) временного интервала моде48793

10

)

10

15

20

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

Шифратор 110 адреса узла поиска моделей ветвей 97 предназначен для формирования адреса каждой модели ветви.

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

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

В узлы 65-70 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети. Регистры 71 - 73 блока 2 формирования топологии предварительно обнуляются, а в регистр 74 конечного узла сети заносится код номера конечного узла сети. Узел 7 памяти меток свершения и узел 9 меток незагруженных ветвей блока 1 управления обнуляются, Узел 10 измерения длиннейшего пути и счетчик 30 поиска незагруженных ветвей блока управления обнуляются. Триггер 11 блока 1 управления, триггеры 75 и блока 2 формирования топологии и триггеры 99(1),99(2),...,99(п), 100(1), 100(2),...,100(п) блока 3 моделей ветвей устанавливаются в нулевое состояние.

После начальной установки на полюс 63 блока 1 управления подается код номера ветви, выходящий из узла, принятого за начальный. Этот код поступает на вход элемента ИЛИ 26. В некоторый момент времени сигнал Пуск, поступающий на полюс 62 бло25

30

40

45

1

76

ка управления 1, проходит через элемент ИЛИ 25 на входной полюс 55 блока 2 топологии. Код номера ветви через элемент ИЛИ 26 блока 1 управления поступает на полюс 56 блока 2 топологии, проходит через элемент ИЛИ 88 и устанавливает триггер 76 в единичное состояние. Единичное состояние триггера 76 разрешает прохождение серии импульсов ГИ1, которые

1

поступают с полюса 60, и импульсов ГИ2, которые поступают с полюса 61, через элементы И 93 и 94 соответственно. Кроме того, сигнал Пуск поступает на вход элемента 80 задержки и на вход считывания узла 65 памяти начальных узлов. При поступлении сигнала считывания в узле 65 памяти происходит считывание информации из ячейки памяти по адресу номера ветви, поступающего из полюса 56.Так как указанная ветвь выбрана как выходящая из начального узла сети, то на выходе узла 65 памяти появится код начального узла сети, который через элемент ИЛИ 83 поступает на адресный вход узла 69 памяти первой выходящей ветви. Через время задержки,достаточ- ное для считывания информации из узла 65 памяти, сигнал Пуск появляется на выходе элемента 80 задержки и через элемент ИЛИ 82 поступает на вход считывания узла 69 памяти. Сигнал считывания позволяет считывать из узла 69 памяти по адресу начального узла сети код номера ветви, являющейся первой в списке ветвей, виходящих из начального узла сети. Этот код с выхода узла 69 памяти через элемент ИЛИ 84 поступает на информационный вход регистра 71 выходящей ветви и записывается в него по первому импульсу ГИ1, поступающему на управляющий вход регистра с выхода элемента 93 И.

Записанный код первой выходящей ветви с выхода регистра 71 поступает на адресный вход узла 67 памяти выходящих ветвей, а также через выходной полюс 39 блока 2 формирования топологии на адресный вход узла 5 памяти длительностей, информационный вход узла 6 памяти номеров моделируемых ветвей, через элемент ИЛИ 24 на адресный вход узла 9 памяти меток незагруженных ветвей и через элемент ИЛИ 19 на адресный вход узла 7 памяти меток свершения блока 1 управления.

Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, с выхода элемента И 94 блока 2 топологии поступает на вход считывания узла 67 памяти Осуществляется считывание номера второй ветви, выходящей из того же уз- лас Одновременно по импульсу ГИ2 сигнал поиска свободной модели ветви с выхода элемента И 94 через выходной

48793

12

10

15

20

25

30

35

40

45

50

55

полюс 40 блока 2 топологии поступает на вход считывания узла 5 памяти длительностей, на вход элемента 31 задержки через элемент ИЛИ 20, на вход считывания узла 7 памяти меток свершения и на вход элемента 32 задержки блока 1 управления.

По сигналу поиска свободной модели ветви и адресу номера первой выходящей из узла ветви осуществляется считывание кода длительности этой ветви из узла 5 памяти длительностей. Этот код через полюс 57 поступает в блок 3 моделей ветвей,Сигнал поиска свободной модели ветви, который через элемент ИЛИ 20 поступает на вход считывания узла 7 памяти блока 1 управления, осуществляет считывание метки свершения по адресу загружаемой ветви сети (в данном случае, по адресу первой ветви, исходящей из начального узла сети). Так как в начальный момент метка свершения ветви равна О, то сигнал низкого уровня через элемент НЕ 27 поступает на первый вход элемента И 12, На другой вход этого элемента через время задержки, достаточное для считывания информации из узла 7 памяти, с выхода элемента 32 задержки поступает сигнал поиска свободной модели ветви. На выходе элемента И 12 сформируется сигнал высокого уровня,который через выходной полюс 58 поступает в блок 3 моделей ветвей.Кроме того, сигнал поиска свободной модели ветви с выхода элемента И 12 блока 1 управления поступает на вход установки параллельного кода узла 10 измерения длиннейшего пути, на вход записи узла 9 памяти меток незагруженных ветвей и через элемент ИЛИ 22 на вход считывания узла 8 памяти значения свершения узлов 8.

Сигнал, который поступает на вход считывания узла 8 памяти,осуществляет считывание информации о текущем значении свершения узла (в данном случае нулевой информации) по адресу номера узла, первая исходящая ветвь которого загружается в блок моделей ветвей0 Номер этого узла поступает из блока 2 формирования топологии через полюс 43 и элемент 21 на адресный вход узла 8 памяти блока 1 управления Считанный из узла памяти 8 код поступает на входы установки параллельного кода узла 10

измерения длиннейшего пути и записывается в него по сигналу разрешения установки параллельного кода, который поступает с выхода элемента И 12

Сигнал, который поступает на вход записи узла 9 памяти, осуществляет запись информации о наличии свободных моделей ветвей, которая поступает с входного полюса 51 по адресу номера загружаемой ветви, которьй поступает с блока 2 формирования топологии через входной полюс 39 и элемент ИЛИ 24 на адресньй вход узла 9 памяти. Если для моделирования данной ветви есть свободные модели ветви, то на входном полюсе 51 присутствует сигнал низкого уровня с выхода элемента ИЛИ 114 блока 3 моделей ветвей ив узел 9 памяти блока 1 управления по адресу загружаемой ветви будет записана нулев.ая метка, т.е. данная ветвь загружается в блок 3 моделей ветвей. В противном случае в узел 9 памяти записывается единичная метка. Это означает, что для моделирования данной ветви нет свободных моделей и данная ветвь в блок моделей ветвей загружена не будет.

Сигнал поиска свободной модели ветви, которьй с выхода элемента И 12 через полюс 58 подается в блок 3 моделей ветвей, поступает на входы элементов И 103(1) и 104(1) первой модели ветви 96(1) блока 3 моделей ветвей о Так как в рассматриваемый момент (загружается первая ветвь, исходящая из начального узла сети) все модели ветвей свободные, то триггер 99(1) находится в нулевом состоянии и сигнал с выхода элемента И 104(1) через элемент 109(1) задержки поступает на вход установки единичного состояния триггера 99(1).

Триггер 99(1) устанавливается в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви первой модели ретви. Одновременно сигнал с выхода элемента И 104 поступает на первый вход элемента И 105(1) и через элемент ИЛИ 107(1) на вход шифратора адреса. На второй вход элемента И 105(1) через полюс 57 поступает код длительности ветви, считанный из узла 5 памяти длительности блока 1 управления. Этот код заносится в качестве исходной информации в фор0

5

0

мирователь 98(1) временного интервала первой модели ветви 96(1) блока 3 моделей ветвей. По сигналу, которьй поступает с выхода элемента И 104(1) через элемент ИЛИ 107(1) и полюс 1.3 на шифратор адреса 110, формируется код первой модели ветви. Этот код через полюс 48 поступает на адресный вход узла памяти номеров моделируемых ветвей 6 блока 1 управления. Через время, измеряющееся от момента поступления сигнала поиска свободной модели ветви до момента поступления кода свободной модели ветви, на выходе элемента 31 задержки блока 1 управления появится сигнал, поступающий на вход записи узла 6 памяти номеров моделируемых ветвей. Этот сигнал позволяет записать по адресу номера выбранной модели ветви (в данном случае, первой),номер ветви, длительность которой уже записана в формирователь временного

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

Далее считанньй по адресу номера первой выходящей из узла ветви, из узла памяти выходящих ветвей 6(7 блока 2 формирования топологии номер следующей ветви в списке выходящих из узла ветвей поступает через элемент ИЛИ 84 на информационный вход регистра 71 и записывается в него с приходом второго импульса ГИ1 .Написанный в регистр 71 код вновь поступает на адресный вход узла 67 памяти, а также через полюс 39 на адресный вход узла 5 памяти, на информационный вход узла 6 памяти и через элемент ИЛИ 19 на адресный вход узла 7

с памяти, и через элемент ИЛИ 24 на адресньй вход узла 9 памяти блока 1 управления. С приходом второго км- пульса ГИ2 из узла 5 памяти длительностей считывается длительность втоQ рой исходящей из узла ветви и поступает через полюс 57 на входы элементов И 105(1), 105(2),...,105(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно осуществляется считывание метки свершения из узла 7 памяти блока 1 управления по адресу номера второй исходящей из узла ветви. Если считана нулевая метка, то на выходе элемента И 12 сформирует0

5

0

5

ся сигнал высокого уровня, который поступает на вход узла 10 разрешения установки параллельного кода устройства измерения длиннейшего пути, на вход записи узла памяти меток незагруженных узлов 9 и через элемент ИЛИ 22 на вход считывания узла 8 памяти значения свершения узлов.Осуществляется считывание кода текущего значения свершения узла по адресу номера начального узла ветви из узла 8 памяти и запись этого кода в устройство I04измерения длиннейшего пути «, Кроме этого, производится запись метки в узел 9 памяти по адресу номера ветви.

Если для моделирования длительности этой ветви имеется свободная модель, то записывается нулевая метка, В противном случае, записывается единичная метка. Кроме того, сигнал с выхода элемента И 12 через полюс 58

10

15

20

Так осуществляется подготовка к м делированию ветвей, выходящих из начального узла сети. Это происходит до тех пор, пока из узла 67 памяти блока 2 топологии не будет считана последняя ветвь из списка исходящих из начального узла ветвей. После это го, по адресу ее номера из узла 67 памяти будет считан код X, которьй записывается в регистр 71. Выход регистра 71 подключен к дешифратору состояния X 77, поэтому при записи в регистр 71 кода X на выходе дешифратора 7 появится сигнал. Этот сигнал поступает на нулевой вход тригге ра 76, сбрасывая его в нулевое состояние. Кроме того, сигнал с выхода дешифратора 77 через элемент ИЛИ 85 и полюс 45 поступает на вход триггера 11 прерывания блока 1 управления, устанавливая его в единичное состояние. Одновременно сигнал поиска прерывания с полюса 45 блока 1 управлепоступает на входы элементов И 103(1)25 ния поступает через полюс 46 в блок

30

40

я 104(1) первой модели ветви 96(1) блока 3 моделей ветвей, Так как триггер 99(1) первой модели ветви находится в единичном состоянии (модель занята), то сигнал с выхода элемента И 103(1) поступает на вход 58(2), второй модели ветви. Триггер 99(2) второй модели ветви находится в нулевом состоянии, поэтому сигнал с выхоца элемента И 104(2) поступает на вход элемента И 105(2), на другой вход которого поступает код длительности ветви. Производится запись кода длительности ветви в формирователь 98(2) временного интервала второй модели ветви 96(2),, Одновременно сигнал с выхода элемента 104(2) через элемент 109(2) задержки устанавливает триггер 99(2) в единичное состояние. Кроме того, сигнал с выхода элемента И 104(2) через элемент ИЛИ 107(2) и полюс 2,3 поступает на вход шифратора 110 адреса. На выходе шифратора 110 адреса сформируется код номера второй модели ветви, которьй через полюс 48 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления По этому адресу в узле 6 памяти при поступлении сигнала с выхода элемента 31 задержки, записывается код номера подготавливаемой к моделированию ветви сети, который поступаем с полюса 39.

45

50

55

3 моделей ветвей.

Сигнал поиска прерывания с полюса 46 через элемент ИЛИ 111 узла 97 поиска моделей ветвей поступает на вход элементов И 10l(l) и 102(1) пер вой модели ветви Ј6(l) блока 3 моде лей ветвей. Так как триггер 100(I) прерывания первой модели ветви находится в нулевом состоянии, то на выходе элемента 101(2) сформируется сигнал поиска прерывания, который че рез полюс 2.1 поступает на входы эле ментов И 101(2) и 102(2) второй моде ли ветви 9б(2)и т.д. Так как в рассматриваемый период триггеры 100(1), 100(2),,,.,100(п) прерывания всех моделей ветвей 96(1), 96(2)....,96(п находятся в нулевом состоянии, то на выходе ни одного из элементов 102(1) 102(2),.„.,102(п) сигнал не сформиру ется, что даст отсутствие сигнала на выходе элемента 112 узла 97 поиска моделей ветвей. Поэтому триггер 11 блока 1 управления находится в единичном состоянии, и потенциал с его единичного выхода поступает на первы вход элемента И 14. На другой вход этого элемента с генератора 4 импуль сов через полюс 61 поступают импульсы серии ГИ1. На выходе элемента И сформируются сигналы высокого уровня которые поступают на первый вход эле мента И 15 На другой вход этого эле мента с блока моделей ветвей через

0

Так осуществляется подготовка к моделированию ветвей, выходящих из начального узла сети. Это происходит до тех пор, пока из узла 67 памяти блока 2 топологии не будет считана последняя ветвь из списка исходящих из начального узла ветвей. После этого, по адресу ее номера из узла 67 памяти будет считан код X, которьй записывается в регистр 71. Выход регистра 71 подключен к дешифратору состояния X 77, поэтому при записи в регистр 71 кода X на выходе дешифратора 7 появится сигнал. Этот сигнал поступает на нулевой вход триггера 76, сбрасывая его в нулевое состояние. Кроме того, сигнал с выхода дешифратора 77 через элемент ИЛИ 85 и полюс 45 поступает на вход триггера 11 прерывания блока 1 управления, устанавливая его в единичное состояние. Одновременно сигнал поиска прерывания с полюса 45 блока 1 управле5 ния поступает через полюс 46 в блок

0

0

5

0

5

3 моделей ветвей.

Сигнал поиска прерывания с полюса 46 через элемент ИЛИ 111 узла 97 поиска моделей ветвей поступает на вход элементов И 10l(l) и 102(1) первой модели ветви Ј6(l) блока 3 моделей ветвей. Так как триггер 100(I) прерывания первой модели ветви находится в нулевом состоянии, то на выходе элемента 101(2) сформируется сигнал поиска прерывания, который через полюс 2.1 поступает на входы элементов И 101(2) и 102(2) второй модели ветви 9б(2)и т.д. Так как в рассматриваемый период триггеры 100(1), 100(2),,,.,100(п) прерывания всех моделей ветвей 96(1), 96(2)....,96(п) находятся в нулевом состоянии, то на выходе ни одного из элементов 102(1), 102(2),.„.,102(п) сигнал не сформируется, что даст отсутствие сигнала на выходе элемента 112 узла 97 поиска моделей ветвей. Поэтому триггер 11 блока 1 управления находится в единичном состоянии, и потенциал с его единичного выхода поступает на первый вход элемента И 14. На другой вход этого элемента с генератора 4 импульсов через полюс 61 поступают импульсы серии ГИ1. На выходе элемента И 4 сформируются сигналы высокого уровня, которые поступают на первый вход элемента И 15 На другой вход этого элемента с блока моделей ветвей через

1715

полюс 50 поступает потенциал высокого уровня о наличии занятых моделей ветвей. На выходе элемента И 15 сформируются импульсы измерительной сери которые поступают на счетный вход узла 10 измерения длиннейшего пути и через полюс 59 в блок 3 моделей ветвей. В блоке 3 моделей ветвей импульсы измерительной серии с полюса 59 поступают на те формирователи 98 временного интервала, триггеры занятости 99 которых находятся в единичном состоянии. Так продолжается до тех пор, пока хотя бы один из формирователей 98 не выдаст сигнал об окончании процесса моделирования длительности ветви.

Сигналы с выхода формирователей временного интервала 98(1), 98(2),. ...,98(п) поступают на единичные входы тригг еров 1 00( 1 ), 100(2-),..., 100(п), устанавливая их в единич- Ґое состояние. Одновременно сигнал с выхода формирователей 98(1), 98(2),...,98(п) через элемент ИЛИ 11 узла 97 поиска моделей ветвей и полюс 1.1 поиска прерывания поступает на элементы И 101(1) и 102(1) первой модели ветви 96(1). Если триггер 100(l) прерывания первой модели ветви 96(1) находится в единичном состоянии (модель закончила формирование длительности ветви), сигнал прерывания с выхода элемента 102(1) через полюс 1.4 и элемент ИЛИ 112 узла 97 поиска моделей ветвей поступает на полюс 49 и с него в блок 1 управления. Кроме того, сигнал с выхода элемента И 102(1) устанавливает его в нулевое состояние. Это означает освобождение данной модели для последующих вычислений. Одновременно сигнал с выхода элемента 102(1) через элемент 107(1) и полюс 1.3 поступает на вход шифратора 110 адреса узла 97 поиска моделей ветвей.На выходе, шифратора ПО сформируется код первой модели ветви, которьй через полюс 48 поступает в блок 1 управления. Кроме того, сигнал с выхода элемента 102(1) первой модели ветви 96(1) через элемент 108(1) задержки поступает на нулевой вход триггера 100(1), устанавливая его в нулевое состояние.

Код номера модели ветви,сформированный шифратором 110 адреса узла 97 поиска моделей ветвей блока 3 мо

0

5

0

5

793

18

делей ветвей, с полюса 48 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления. Сигнал прерывания с полюса 49 поступает на вход считывания узла 6 памяти номеров моделируемых ветвей. Происходит считывание по адресу номера модели ветви кода номера ветви сети. Этот код через элемент ИЛИ 19 поступает на адресный вход узла 7 памяти меток свершения ветвей. Через время, достаточное для считывания номера ветви с узла 6 памяти, на вход записи узла 7 памяти через элемент 33 задержки поступает сигнал прерывания, и по адресу номера ветви в узел 7 памяти меток свершения ветвей записывается единичная метка, характеризующая завершение процесса моделирования длительности данной ветви. Через время, достаточное для записи метки свершения в узел 7 памяти, сигнал прерывания появится на выходе элемента 34 задержки. С выхода элемента 34 задержки сигнал начала анализа свершения ветви поступает на вход элемента 35 задержки и через полюс 53 в блок 2 формирования топологии. Через полюс 52 в блок 2 формирования топологии с узла 6 памяти поступает код номера ветви.

Код номера ветви с полюса 52 поступает на адресный вход узла 66 памяти конечных узлов блока 2 формирования топологии. Сигнал начала анализа ветви с полюса 53 поступает на единичный вход триггера 75, устанавливая его в единичное состояние,Единичное состояние триггера 75 разрешает прохождение импульсов ГИ1 с полюса 60 и импульсов ГИ2 с полюса 61 через элементы И 91 и 92 соответственно. Кроме того, сигнал начала С анализа ветви с полюса 53 поступает на вход элемента 81 задержки и на вход считывания узла 66 памяти.Происходит считывание ячейки памяти, в которой записан номер конечного узла ветви, вызвавшей прерывание.Код считанного номера узла с выхода узла 66 памяти поступает на выходной полюс 44.

С полюса 44 код номера конечного узла анализируемой ветви через элемент ИЛИ 21 блока 1 управления поступает на адресный вход узла памяти значения свершения узлов сети 8.Через время, достаточное для считыва0

5

0

0

5

ния кода номера конечного узла анализируемой ветви с узла памяти 66 блока формирования топологии 2, на выходе элемента задержки 35 блока управления 1, появится сигнал начала анализа свершения, который через элемент ИЛИ 22 поступает на вход считывания узла 8 памяти значения свершения узлов. Происходит считывание кода текущего значения свершения узла по адресу номера конечного узла анализируемой ветви. Так как в данном случае свершилась первая ветвь,входящая в узел, то с узла 8 памяти считы- вается нулевой код. Этот код поступает на первый вход схемы 29 сравнения кодов. На другой вход схемы сравнения поступает код из узла 10 измерения длиннейшего пути. Схема 29 сравнения кодов работает таким образом, что сигнал на ее выходе формируется в том случае, когда код, поступающий из узла 10 измерения длиннейшего пути, будет больше кода, поступающего

из узла памяти значения свершения узлов 8, Такая ситуация имеет место в рассматриваемом случае, поэтому сигнал с выхода схемы 29 сравнения поступает на первый вход элемента И I3„ На другой вход элемента И 13 поступает сигнал с выхода элемента 36 задержки, задержанный относительно сигнала считывания уэла 8 памяти на время, достаточное для сравнения кодов на схеме 29 сравненияt На выходе элемента И 13 формируется сигнал, который поступает на вход записи узла 8 памяти Происходит запись кода, который поступает с узла измерения длиннейшего пути на информационный вход узла 8 памяти по адресу номера конечного узла анализируемой ветви. Таким образом,осу

0

5

0

5

0

ра УЗ конечного узла и на вход считывания узла 70 памяти. По этому сигналу происходит запись кода номера первой в списке входящих в рассматриваемый узел ветвей из узла 70 памяти. Код номера первой входящей ветви с выхода узла 70 памяти через элёйент ИЛИ 86 поступает на информационный вход регистра входящей ветви 72 и записывается в него по первому импульсу ГИ1 , поступающему на управляющий вход регистра с выхода элемента И 91 , С выхода регистра 72 код номера первой входной ветви поступает на адресный вход узла 68 памяти входящих ветвей, и через полюс 41 и элемент ИЛИ 19 блока 1 управления на адресный вход узла 7 памяти меток свершения ветвей0 Первый импульс ГИ2 с выхода элемента И 92 блока 2 формирования топологии через полюс 42 и элемент ИЛИ 20 блока 1 управления поступает , на вход считывания узла 7 памяти меток свершения ветвей. Метка свершения, считанная по адресу первой ветви, с выхода узла 7 памяти меток свершения ветвей через полюс 54 поступает в блок 2 формирования топологии. Если метка отсутствует, что означает несвершенйя моделирования длительности ветви с данным номером,то нулевой сигнал метки с полюса 54 через элемент НЕ 95 и элемент ИЛИ 87 сбрасывает триггер 75 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 95 через элемент ИЛИ 85 поступает на полюс 45 поиска прерывания. Наличие нулевого сигнала метки свершения ветви означает,что в рассматриваемом узле не сформирована функция И для всех входящих в него ветвей. В этом случае сигнал с полюса 45 поступает на единичный вход

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

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

Кроме того, код считанного номера конечного уэла свершившейся ветви с выхода узла 66 памяти блока 2 формирования топологии поступает на адресный вход узла 70 памяти первой входящей ветйи и на информационный вход регистра 73 конечного узла г-Через время задержки, достаточное для считывания информации из узла 66 памяти, сигнал начала анализа свершения ветви с элемента 81 задержки поступает на управляющий вход регист50

55

ления и одновременно через полюс 46 поступает на вход элемента ИЛИ 11I узла 97 поиска моделей ветвей 97 блока 3 моделей ветвей0 С выхода элемента ИЛИ 111 узла 97 поиска моделей ветвей блока 3 моделей ветвей, С выхода элемента ИЛИ 111 сигнал поступает на входы элементов И 101(l) и 102(1) первой модели ветви, Если триггер прерывания 100(1) первой модели ветви находится в нулевом состоянии,то на выходе элемента 101(1) сформируется сигнал высокого уровня, который через полюс 21 поиска прерывания постриггера 1 1 прерывания блока 1 управ

ления и одновременно через полюс 46 поступает на вход элемента ИЛИ 11I узла 97 поиска моделей ветвей 97 блока 3 моделей ветвей0 С выхода элемента ИЛИ 111 узла 97 поиска моделей ветвей блока 3 моделей ветвей, С выхода элемента ИЛИ 111 сигнал поступает на входы элементов И 101(l) и 102(1) первой модели ветви, Если триггер прерывания 100(1) первой модели ветви находится в нулевом состоянии,то на выходе элемента 101(1) сформируется сигнал высокого уровня, который через полюс 21 поиска прерывания пос21

тупает на входы элементов И 101(2) и 102(2) второй модели ветви. Если триггер 100(2) прерывания второй модели ветви находится в нулевом состоянии (вторая модель ветви не закон- чипа моделирование длительности ветви), сигнал поиска прерывания с выхода элемента И 101(2) второй модели ветви через полюс 3.1 поступает на входы элементов И 101(3) и 102(3) третьей модели ветви и т.д. Описанный процесс происходит до тех пор, пока не обнаружится J-я модель, у которой триггер прерывания 100(j) находится в единичном состоянии (модель ветви закончила моделирование длительности ветви, которая еще не анализировалась). В этом случае, сигнал с выхода элемента 102(j) через элемент 107(j) j-й модели ветви вновь поступит на вход шифратора 110 адреса для формирования номера данной модели ветви. Кроме того, сигнал с выхода элемента И 102(j) через элемент ИЛИ 12 узла 97 поиска моделей ветвей выдает сигнал прерывания, а через элемент 108(j) задержки сбросит в нулевое состояние триггер 100(j) данной модели ветви. Блок 1 управления,получив номер модели ветви и сигнал прерывания, повторит все описанные операции, связанные с анализом свершения ветви. Если же в блоке 3 моделей ветвей не имеется моделей, у которых триггер 100 находится в единичном состоянии, то процесс анализа свершения ветви не проводится, триггер 11 блока управления находится в единичном состоянии и импульсы серии ГИ1 через элемент И 14 поступают на первый вход элемента И 15 блока 1 управления. На другой вход этого элемента через полюс 50 поступает сигнал наличия занятых моделей ветвей с выхода элемента ИЛИ 113 узла 97 поиска моделей ветвей блока 3 моделей ветвей. Если в блоке 3 моделей ветвей в рассматриваемый момент имеется хотя бы одна модель ветви, у которой триггер 99 занятости находится в единичном состоянии, то на выходе элемента ИЛИ 113 узла 97 поиска моделей ветвей присутствует потенциал высокого уровня. Этот потенциал дает разрешение на прохождение импульсов серии ГИ1 через элемент И 15 блока 1 управления в узел 10 измерения длиннейшего пути и через полюс 59 в блок 3 мо

1548793

22

0

5

0

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

Если в рассматриваемый момент в блоке 3 моделей ветвей нет ни одной занятой модели ветви (процесс моделирования находится в точке, когда смоделированы длительности всех загруженных ветвей, но конечный узел сети не сформирован), на выходе элемента ИЛИ 113 узла 97 поиска моделей ветвей присутствует потенциал низкого уровня о Этот потенциал через полюс 50 поступает на вход элемента И 15 блока 1 управления, запрещая прохождение импульсов серии ГИ1 на вход узла 10 измерения длиннейшего пути и в блок 3 моделей ветвей. Кроме того, сигнал с полюса 50 через элемент НЕ 28 поступает на первый вход элемента И 18 блока 1 управления. На второй вход это- 5 го элемента поступает разрешающий потенциал с выхода триггера 11, на третий - импульсы серии ГИ1 с полюса 61. На выходе элемента И 18 сформируется сигнал высокого уровня,который поступает на счетный вход счетчика 30 поиска незагруженных ветвей, на вход считывания узла 9 ггамяти меток незагруженных ветвей, на элемент 37 задержки. Сигнал, поступивший на счетный вход счетчика 30, увеличива0

5

ет его код на 1. Этот код через

0

элемент ИЛИ 24 поступает на адресный вход узла 9 памяти. На вход считывания узла памяти поступает сигнал с выхода элемента И 18. Происходит считывание ячейки памяти, адрес которой определяется кодом счетчика 30.Если по данному адресу считана нулевая метка, сигнал низкого уровня с выхоу да узла 9 памяти поступает на вход элемента И 16, запрещая прохождение сигнала с выхода элемента И 18. Это состояние сохраняется до поступления следующего импульса серии ГИ1. Сле- Q дующий импульс серии ГИ1 опять увеличит на 1 код счетчика 30 и произойдет считывание ячейки узла 9 памяти по новому адресу и т.д. Если по некоторому адресу из узла 9 памяти считана единичная метка, сигнал высокого уровня с выхода узла 9 памяти поступит на вход элемента И 16. На другой вход этого элемента поступает сигнал с элемента 37 задержки, задержанный

5

23

относительно сигнала на та И 18 на время, достаточней для считывания информации из узла 9 памяти. На выходе элемента И 16 сформируется сигнал пуска высокого уровня, который через элемент ИЛИ 25 и полюс 55 поступает в блок формирования то- рологии. Через полюс 56 и элемент ИЛИ 26 блока 1 управления со счетчи- ka 30 в блок 2 формирования тополо™ ии поступает код номера незагружен- (ной ветви. Получив сигнал пуска и |код номера незагруженной ветви, блок формирования топологии начинает загрузку ветвей, исходящих из узпа, где обнаружена незагруженная исходящая етвь„ Кроме этого, сигнал с выхода (элемента И 16 блока 1 управления поступает на элемент 38 задержки. Через Время, достаточное для срабатывания элементов ИЛИ 25 и 26 блока 2 управления топологии, на выходе элемента 38 задержки блока 1 управления сфор-- йируется сигнал, который поступает на вход сброса счетчика 30, устанавливая все разряды счетчика в нулевое состояние, и через элемент ИЛИ 23 на вход триггера 11, устанавливая его В нулевое состояние.

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

Сигнал пуска, который поступает На полюс 55 блока 2 топологии, прохо- рит через элемент ИЛИ 88 и устанавливает триггер 76 в единичное состоя ние„ Кроме этого, сигнал пуска поступает на вход элемента 80 задержки и на вход считывания узла 55 памяти начальных узлов. На адресный вход узла 65 памяти поступает код номера незагруженной ветви с входного полюса 56, Происходит считывание из узла 65 памяти кода номера начального узла ветвИо Этот код через элемент ИЛИ 83 поступает кя адресный вход узла 69 памяти и на выходной полюс 43, С полюса 43 код номера начального узла ветви через элемент ИЛИ 21 поступает на адресный вход узла 8 памяти блока управления. Осуществляется считывание величины свершения данного узла из узла 8 памяти и запись этой величины в узел 10 измерения длиннейшего пути,

По коду номера начального узла ветви, который с выхода элемента ИЛИ 83 поступает на адресный вход уз10

15

20

25

154879324

выходе элемен- ла 69 памяти блока 2 топологии, осуществляется считывание номера первой ветви, выходящей из рассматриваемого узла. Этот код с выхода узла 69 памяти через элемент ИЛИ 84 поступает на информационный вход регистра

71 и записывается в него по сигналу

-

ГИ1, поступающему с выхода элемента И 93. С выхода регистра 71 код номера первой ветви поступает на выходной полюс 39. На выходной полюс 40 по сигналу ГИ2 поступает сигнал поиска свободной модели ветви с выхода элемента И 94, С полюса 40 сигнал поиска свободной модели ветви через элемент ИЛИ 20 поступает на вход считывания узла 7 памяти блока 1 управления. На адресный вход узла 7 памяти поступает код номера первой ветви с входного полюса 39. Производится анализ свершения данной ветви„

Если при анализе свершения ветви из узла 7 памяти блока 1 управления считана единичная метка,, это означает, что длительность анализируемой ветви уже смоделирована,, сигнал высокого уровня свершения ветви с полюса 54 поступает на вход элемента И 89 блока 2 формирования топологии. Этот сигнал разрешает прохождение импульса серии ГИ2 через элемент И 89 на вход считывания узла 68 памяти входящей ветвио На адресные входы узла 68 памяти в это время поступает код номера первой входящей в данный узел ветви с выхода регистра 72, По адресу первой входящей ветви из узла 68 памяти будет считан код номера второй ветви, входящей в данный узел. Считанный код через элемент ИЛИ 86 поступает на информационные входы регистра 72 и записывается в него с приходом второго импульса ГИ1 с выхода элемента И 91. Далее код второй входящей ветви с выхода регистра 72 через полюс 41 поступает в блок 1 управления, где проверяется метка ее свершения. Если метка свершения второй входящей ветви также равна 1, осуществляется переход к анализу свершения следующей ветви из списка входящих в рассматриваемый узел. Процессы, происходящие при обнаружении несвершившейся ветви, были описаны. Если же все ветви, входящие в рассматриваемый узел, имеют единичные метки свершения, по адресу последнего номера ветви из узла 68 памяти будет

30

35

40

45

50

55

25

считана информация X, определяющий конец списка. Код X записывается в регистр входящей ветви 72 и далее поступает на вход дешифратора состояния X 78, который вырабатывает сигнал конца списка о Сформированный -сигнал с выхода дешифратора 78 состояния через элементы ИЛИ 87 и 88 поступает на входы триггеров 75 и 76, устанавливая их соответственно в нулевое и единичное состояние. Кроме этого, сигнал с выхода дешифратора 78 поступает на вход элемента И 90, второй вход которого связан с выходом дешифратора 79 сравнения кодов 79, Дешифратор 79 сравнивает коды конечного узла сети, которьй хранится в регистре 74, и рассматриваемого узла сети, сформировавшего функцию конъюнкции, который хранится в регистре 73, Если значения, этих кодов совпадают (сформирована логическая функция конъюнкции для конечного узла сети), то дешифратор 79 сравнения кодов сформирует сигнал высокого уровня, который разрешит прохождение сигнала конца списка с выхода дешифратора 78 через элемент И 90 на вБкодной полюс 47 блока 2 формирования топологии. Это соответствует концу моделирования заданной сети, С полюса 47 сигнал конца списка поступает на вход элемента И 17 блока 1 управления и разрешает выдачу на выходной полюс 64 величины длиннейшего пути сети с узла 10 измерения длиннейшего пути, R случае, если в рассматриваемый момент времени конечный узел сети не сформирован, сигнал с выхода дешифратора 78 блока 2 формирования топологии через элемент ИЛИ 82 поступает на вход считывания узла 69 памяти первой выходной ветви, на адресный вход которого в этот момент поступает код номера сформированного узла сети с регистра конечного узла 73, Начинается процесс подготовки к временному моделированию длительностей тех ветвей, который выходит из рассматриваемого сформированного узла.

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

10

4879326

ветвей в случае, если количество моделей ветвей меньше количества ветвей в максимальном сечении сети,повторяются до тех пор, пока не будет сформирован заданньй конечный узел сети0 В этом случае величина длиннейшего пути в сети, сформированная в узле 10 измерения длиннейшего пути блока I управления, выдается на полюс 64.

Обобщенная структурная схема устройства представлена на фиг.4 следующими цифровыми обозначениями. Блок 115 определения инциндентных дуг, блок 116 синхронизации, блок 117 моделирования сети, блок 118 памяти (времени свершения вершин), блок 119 определения инцидентных вершин,счетчик 120, первый и второй блоки 121 и 122 элементов ИЛИ, элемент 123 ИЛИ, блок 124 сравнения, вход 125 пуска устройства, вход 126 задания номера начальной вершины устройства,выход 127 признака конца списка блока 115, выход 128 номера дуги блока 115,выход 129 признака выдачи номера дуги блока 115, выход 130 признака наличия условий приостановления моделирования блока 117, выход 131 номера свершенной вершины блока 117,выход 132 признака свершения вершины блока 117, выход 133 номера отложенной дуги блока 117, выход 134 признака выдачи номера отложенной дуги блока 117, выход 135 номера инцидентной вершины блока 119, выход 136 признака выдачи номера инцидентной верши15

20

25

30

35

ны, вход 137 задания номера конечной вершины сети, выход 138 конечной работы устройства.

Работа устройства по обобщенной структурной схеме поясняется блок- схемой алгоритма поиска величины длиннейшего пути в сети, где цифры в колонках справа указывают номер позиции блока, выполняющего предусмотренное блоком алгоритма действие, или номера позиций выходов блоков устройства, сигналы которых служат условиями переходов. Блоки алгоритма, которые могут выполняться параллельно, на фиг.5 и 6 показаны без разделительной стрелки. Формула изобретения

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

27

блок моделирования сети, счетчик,

блок памяти, элемент ИЛИ, два блока элементов ИЛИ, блок сравнения и блок определения инцидентных вершин,приче В1ход пуска устройства подключен к ггервому входу элемента ИЛИ,выход которого подключен к входу пуска блока определения инцидентных дуг, выход признака выдачи номера дуги которого подключен к входу признака запуска Моделирования дуги блока моделирова- |ия сети, вход задания кокера началь вершины сети устройства подклю- ч|ен к первому входу первого блока Элементов ИЛИ, выход которого подклю ен к входу задания номера вершины 4лока определения инцидентных дуг,. ыход номера дуги которого подключе к входу задания номера запускаемой Дуги блока моделирования сети,выход Признака конца списка исходящих дуг флока определения инцидентных дуг подключен к входу пуска блока синхронизации, выход которого подключен к суммирующему входу счетчика,выход признака выдачи номера инцидентной даершины блока определения инцидентных вершин подключен к второму входу элемента ИЛИ, выход номера инци- йентной вершины подключен к второму информационному входу первого блока элементов ИЛИ,, вход задания номера конечной вершины устройства подключен к первому информационному входу блока сравнения, выход которого является выходом признака окончания работы устройства, отличаю

0

793

щ

28

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

5

0

0

5

Ц

6

и

d

L

«5/W« «4 WW

т

&

т

№

SL

5nl

&

21

d

Пг&1

10

«5/

П

-ц

Л

L

л

Ј4

L..

tfJ

tf

го

ON Г- CO

r in

f13

нет

нет

, Vavaait тно8е/1иройачие -L о/п/мженных ЗщцЪкц

У1 в работе ,да устройства

С

Окончить

поде/шробание )

fug S