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

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

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

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

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

Входы и выходы названы полюсами.

Блок 1 управления содержит узел 5 памяти длительностей ветвей, узел 6 памяти номеров моделируемых ветвей, узел 7 памяти меток свершения ветвей, узел 8 измерения длиннейшего пути, триггер 9 прерывания, первый 10 и второй II элементы И, элементы ШШ 12, элементы 13-15 задержки.

На фиг. 1 показаны выход 16 номера подготавливаемой к моделированию ветви, выход 17 поиска свободной модели ветви, вход 18 поиска свободной модели ветви, вькод 19 номера анализируемой ветви, выход 20 проверки свершения ветви, выход 21 поиска прерывания, вход 22 поиска прерывания, вы-, ход 23 индикации результатов расчета, выход 24 номера модели ветви, выход 25 прерывания, вход:: 26-28 блока формирования топологии, входы 29 и 30 блоел

с со

кэ ел

14)

ка моделей ветвей, входы 31 и 32 блока формирования топологии, вход 33 блока управления.

Входными полюсами устройства яв- ляются вход 34 начального пуска и вход 35 номера ветви. Выходным полюсом является выход 36 величины длиннейшего пути.

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

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

щей ветви, регистр 44 номера входящей ветви, регистр 45 номера конечного узла ветви, регистр 46 номера конечного узла сети, триггеры 47 и 48, дешифраторы 49 и 50, дешифратор 5I сравнения кодов, элементы 52 и 53 задержки, элементы ИЛИ 54-60, элементы И 61-66, элемент НЕ 67.

Узлы 37-42 памяти предназначены для хранения информации о топологии моделируемой сети (узел 37 памяти - для хранения номера начального узла ветви по адресу номера данной ветви, узел 38 памяти - для хранения номера конечного узла ветви по адресу номера данной ветви, узел 39 памяти - для хранения в виде списков номеров ветвей, выходящих из узлов сети, узел 40 памяти - дЛя хранения в виде списков номеров ветвей, входящих в узлы сети, узел 41 памяти для хранения по адресу номера узла номера ветви, первой из списка ветвей, выходящих из данного узла, а узел 42 памяти - для хранения по адресу номера узла номера ветви, первой из списка ветвей, входящих в данньй узел).

Регистр 43 предназначен для проме

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

тельно другого.

В блоке 1 управления (фиг. l) узел 5 памяти длительностей ветвей предназначен для хранения информации о величинах длительностей ветвей сети, а именно для хранения по адресу номера ветви кода длительности данной ветви. Узел 6 памяти номеров моделируемых ветвей предназначен для хранения информации о соответствии номера модели ветви из блока 3 моделей.ветвей номеру ветви сети, моделируемой в:текущий момент времени данной моделью ветви. Узел 7 памяти меток

определении ветвей, выходящих из узла, а регистр 44 - для промежуточного хранения номера ветвей, входящих в узел. Регистры 45 и 46 предназначены

35 для хранения номера конечного узла ветви и для постоянного хранения номера конечного узл-а сети, соответственно.

Дешифратор 51 сравнения кодов пред40 назначен для пораз.рядного сравнения кодов из регистров 45 и 46.

Дешифраторы 49 и 50 состояний предназначены для сравнения поступающих на них кодов с кодовой комбинацией сосвершения ветвей предназначен для X,заданного постоянно в схеме. нения информации о завершении процес- / Блок 3 моделей ветвей (фиг. 3} со-.

са временного моделирования длительностей ветвей сети.

Блок 2 формирования топологии (фиг. 2) содержит узел 37 памяти номеров начальных узлов ветвей сети, узел 38 памяти номеров конечных узлов ветвей сети, узел 39 памяти номеров выходящих ветвей узлов сети, узел 40 памяти номеров входящих ветвей узлов сети, узел 41 памяти номеров первой выходящей ветви узлов сети, узел 42 памяти номеров первой входящей ветви узлов сети, регистр 43 номера выходяопределении ветвей, выходящих из узла, а регистр 44 - для промежуточного хранения номера ветвей, входящих в узел. Регистры 45 и 46 предназначены

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

Дешифратор 51 сравнения кодов предназначен для пораз.рядного сравнения кодов из регистров 45 и 46.

Дешифраторы 49 и 50 состояний предназначены для сравнения поступающих на них кодов с кодовой комбинацией со0

5

держит М моделей ветвей 68. (где Ы - количество ветвей в максимальном сечении сети) и узел 69 поиска моделей ветвей. Цифрами в скобках обозначены порядковые номера совершенно одинаковых по своему конструктивному исполнению и функциональному назначению блоков, узлов, элементов и полюсов. Каясдая .модель ветви 68 (фиг. 3) состоит из формирователя 70 временных интервалов, триггеров 71 и 72, элементов И 73-78, элемента .ИЛИ 79, элементов 80 и 81 задержки.

10

68(2),...,68(М) соединены с входами шифратора 82 адреса узла 69 поиска моделей ветвей. Выход 25 прерывания блока 3 моделей ветвей соединен с вы ходом элемента ШШ 84 узла 69 поиска моделей ветвей. Выход 24 номера модели ветви соединен с выходом шифратора 82 адреса узла 69 поиска моделей ветвей.

Формирователи временного интервала 70(1), 70(2),...,70(М) моделей ветвей 68(J), 68(2),..., 68(ы) предназначены для временного моделироваветвей предназначен для формирования адреса каждой модели ветви.

В блок 1 управления (фиг. 1) доСхема узла 69 поиска моделей ветвей (фиг. 3) содержит шифратор 82 адреса и элементы ИЛИ 83 и 84.

Входы 29(1), 29(2),...,29(М) кода длительности ветви соединены с входа- ми элементов И 77(1), 77(2),...,77(м) Входы 30(1)., 30(2),.. .,30(М) измерительной серии импульсов соединены с входами элементов И 78(1), 78(2),..., 78(М) узла моделей ветвей 68. Вход 18(1) поиска свободной модели ветви соединен с входами элементов И 75(1) и 76( I ) первой модели ветви 68(.1 ). Вы- Выход элемента И 75(1) первой модели 15 ния длительностей ветвей сети.-Шифра- ветви 68(1) соединен с входом 18(2) тор 82 адреса узла 69 поиска моделей поиска свободной модели ветви второй модели ветви 68(2), выход элемента И 75(2) второй модели ветви 68(2) соединен с входом 18(3) свободной моде- 20 полнительно введены узел 85 памяти ли ветви третьей модели ветви 68(3) времени начала моделирования ветвей, и так далее до М. Вход 22 поиска пре- узел 86 определения разности двух ко- рывания.соединен с .ходом элемента дов, блок 87 сравнения, третий эле- ИЛИ 83 узла 69 поиска моделей ветвей мент И 88, второй и третий элементы блока 3 моделей ветвей. Выход элемен- 25 ИЛИ 89-90, четвертый элемент 91 за- та ШШ 83 узла поиска моделей ветвей соединен с входом (1,1) поиска прерывания первой модели ветви 68(l). Первая цифра в скобках обозначает более высокой в иерархии порядковый номер (в данном случае номер модели ветви), а вторая более низкий в иерархии номер (в данном случае порядковый номер входа или выхода этой- модели).

Входы (1,1), (2,1),...,(М,1) поиска прерьшания моделей, ветвей 68(1), 68(2),...,68(М) соединены с входами элементов И 73(1),73(2),...,73(М) и .74(1),74(2),...,74(М). Выход элемента И 73(1) первой модели ветви 68(1) соединен с входом (2,1) поиска прерывания второй модели ветви 68(2), выход элемента И 73(2) второй модели ветви 68(2) соединен с входом (3,1).

поиска прерывания третьей модели вет- .с моделируемых ветвей и узел 8 памяти ви 68(3) и т;д. до М-й модели ветви. времени начала мод.елирования ветви Выходы (1,2),(2,2),...,(М,2) перепол- блока I управления обнуляются, нения формирователей временных интервалов 70(М) моделей ветвей 68(1), 68(2),...,68(М) соединены с входами элемента ИЛИ 83 узла поиска моделей ветвей 69. Выходы (1,4), (2,4j,..., (М,4) сигналов прерывания с выходов элементов И 74(1), 74(2),..., 74fM) моделей ветвей 68(1), 68(2),...,68(М) соединены с входами элемента ИЛИ 84. Выходы (1,-3),(2,3), ...,(М,3) кода моделей ветвей с выходов элементов ШШ 79(1) 79(2),..,,79(М} моделей ветвей 68(1),

30

35

40

держки, выходные полюса 92 и 93 сигналов неверной обработки длительности ветви и неверно обработанной ветви соответственно.

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

В узлы 37-42 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети, а в узел 5 памяти длительности ветвей записываются длительности ветвей. Регистры 43-45 предварительно обнуляются, а в-регистр 46 конечного узла сети заносится код номера конечного узла сети. Триггеры 9,

47,- 48; 71(1), 71(2)71 (М); ,72( 1),

72(2),...,72(М) находятся первоначально в нулевом состоянии, узе л 7 памяти меток свершения, узел 6 памяти номеров

Пойле начального установа на полюс 35 блока 2 формирования топологии гп подается код номера ветви, выходящей из узла, принятого при данном решении за начальный. Начальный узел, таким образом, определяется по адресу номера ветви в узле 37 памяти блока 2 формирования .топологии.

В некоторый момент времени сигнал Пуск, поступающий на полюс 34, проходит через элемент ИЛИ 60 и устанавливает триггер 43 в единичное состоя55

68(2),...,68(М) соединены с входами шифратора 82 адреса узла 69 поиска моделей ветвей. Выход 25 прерывания блока 3 моделей ветвей соединен с вы ходом элемента ШШ 84 узла 69 поиска моделей ветвей. Выход 24 номера модели ветви соединен с выходом шифратора 82 адреса узла 69 поиска моделей ветвей.

Формирователи временного интервала 70(1), 70(2),...,70(М) моделей ветвей 68(J), 68(2),..., 68(ы) предназначены для временного моделирования длительностей ветвей сети.-Шифра- тор 82 адреса узла 69 поиска моделей полнительно введены узел 85 памяти времени начала моделирования ветвей, узел 86 определения разности двух ко- дов, блок 87 сравнения, третий эле- мент И 88, второй и третий элементы ИЛИ 89-90, четвертый элемент 91 за-

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

В блок 1 управления (фиг. 1) дония длительностей ветвей сети.-Шифра- тор 82 адреса узла 69 поиска моделей полнительно введены узел 85 памяти времени начала моделирования ветвей, узел 86 определения разности двух ко- дов, блок 87 сравнения, третий эле- мент И 88, второй и третий элементы ИЛИ 89-90, четвертый элемент 91 за-

15 ния длительностей ветвей сети.-Шифра- тор 82 адреса узла 69 поиска моделей 20 полнительно введены узел 85 памяти времени начала моделирования ветвей, узел 86 определения разности двух ко- дов, блок 87 сравнения, третий эле- мент И 88, второй и третий элементы 25 ИЛИ 89-90, четвертый элемент 91 за-

30

5

0

держки, выходные полюса 92 и 93 сигналов неверной обработки длительности ветви и неверно обработанной ветви соответственно.

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

В узлы 37-42 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети, а в узел 5 памяти длительности ветвей записываются длительности ветвей. Регистры 43-45 предварительно обнуляются, а в-регистр 46 конечного узла сети заносится код номера конечного узла сети. Триггеры 9,

47,- 48; 71(1), 71(2)71 (М); ,72( 1),

72(2),...,72(М) находятся первоначально в нулевом состоянии, узе л 7 памяти меток свершения, узел 6 памяти номеров

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

Пойле начального установа на полюс 35 блока 2 формирования топологии гп подается код номера ветви, выходящей из узла, принятого при данном решении за начальный. Начальный узел, таким образом, определяется по адресу номера ветви в узле 37 памяти блока 2 формирования .топологии.

В некоторый момент времени сигнал Пуск, поступающий на полюс 34, проходит через элемент ИЛИ 60 и устанавливает триггер 43 в единичное состоя5

ние. Единичное состояние триггера 48 разрешает прохождение серии импульсов ГИ1 (полюс 31) и ГИ2 (полюс 32) соответственно через элементы И 65 и 66. Кроме этого, сигнал Пуск поступает на вход элемента 52 задержки и на вход считывания узла 37 памяти начальных узлов. При поступлении сигнала разрешения выборки в узле 37 па- JQ ветвей. По этому сигналу ГИ2 и адремяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 35. Так как ветвь выбрана, как выходящая из начального узла сети, то на выходе узла 37 памяти.по- 55 является код начального узла сети, который через элемент ИЛИ 55 поступает , на адресный вход узла 41 памяти первой выходящей ветви. Через время задержки, достаточное для считывания 20 информации из узла 37 памяти, сигнал Пуск появляется на выходе элемента 52 задержки и поступает через элемент ИЛИ 54 на вход считывания узла 41 памяти. Сигнал выборки по адре- 25 ходится в нулевом состоянии и сигнал

су начального узла позволяет сосчитать из узла 41 памяти код номера ветви, являющейся первой в списке ветвей, выходящих из начального узла сети. Код первой выходящей ветви с выхода узла 4 памяти поступает через элемент ИЛИ 56 на информационный вход регистра 43 номера выходящей ветви и записывается в него, по первому импульсуТИ, поступившему на управляю- ,с моделью ветви. Одновременно сигнал с

выхода элемента И 7б(1) поступает на первый вход элемента И 77(1 ) и через элемент ИЛИ 74(l) на вход дешифратора 82 адреса. На второй вход элемента И 77(1) через полюс 29 поступает код длительности ветви, который через элемент И 77(1) заносится в качестве исходной информации в формирователь 70(l) временного интервала.

щии вход регистра с выхода элемента И 65.

Записанный код первой выходящей ветви с выхода регистра 43 поступает на адресный вход узла 39 памяти, через выходной полюс 16 блока 2 формирования топологии - на вход элемента ИЛИ 89, а также на информационньш вход узла 6 памяти номеров моделируемых ветвей блока 1 управления. С выхода элемента ИЛИ 89 код первой выходящей ветви поступает на адресный вход узла 5 памяти длительностей ветви, а также на адресный вход узла 85 памяти времени начала моделирования ветвей блока 1 управления.

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

узла. Одновременно импульс ГИ2 через элемент ИЛИ 40 поступает на вход считывания узла 5 памяти длительностей ветвей, на вход записи узла 85 памяти времени начала моделирования ветвей, на вход элемента 13 задержки блока 1 управления и вход 18 поиска свободной модели ветви блока 3 моделей

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

. Одновременно сигнал поиска свободной модели ветви с полюса 18 поступает на входы элементов И 75(1) и 76(1) первой модели ветви 68(l) и блока 3 моделей ветвей. Так как все модели ветвей свободны, то триггер 72(1 ) нас выхода элемента И 76(1) через элемент 81(1) задержки, поступает на вход установки единичного состояния триггера 72(i),который через время задержки, достаточное для срабатывания всех элементов, устанавливает его в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви первой

0

5

0

5

выхода элемента И 7б(1) поступает на первый вход элемента И 77(1 ) и через элемент ИЛИ 74(l) на вход дешифратора 82 адреса. На второй вход элемента И 77(1) через полюс 29 поступает код длительности ветви, который через элемент И 77(1) заносится в качестве исходной информации в формирователь 70(l) временного интервала.

С выхода шифратора 82 адреса полученный по сигналу с полюса (1,3) код адреса модели ветви через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления. Через время, достаточное для организации описанных процессов в блоке 3 моделей в.етвей, на выходе элемента 13 задержки блока 1 управления появля.ется сигнал, поступающий на вход записи узла 6 памяти номеров моделируемых ветвей. Сигнал записи позволяет записать по адресу номера выбранной модели ветви (в данном случае первой) номер ветви, длительность которой внесена уже в формирователь 70 временного интервала данной модели ветви. На этом заканчивается подготовка первой выходящей из узла ветви к процессу временного моделирования длительности.

Таким образом, подготовка одной ветви к временному моделированию включает считывание из блока 2 формирова- Q ходе шифратора 82 адреса формируется ния топологии номера ветви, затем считьшание ее длительности, поиск свободной от вычислений модели ветви, ввод в ее формирователь временного интервала кода длительности ветви, за- )5 пись в узел номеров моделируемых ветвей по адресу номера выбранной модели ветви номера первой ветви, а также запоминание времени начала моделирования ветви, т.е. раннего начала ветви. 20

Далее считанный по адресу номера первой выходящей ветви из узла 39 памяти выходящих ветвей блока 2 формирономер второй модели ветви, который через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления, и при появлении через некоторое время сигнала на выходе элемента 13 задержки в узел 6 памяти по адресу номера модели ветви записывается номер ветви, код длительности которой введен в формирователь 70 временного интервала данной модели ветви.

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

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

вания топологии номер следующей в.етви

в списке выходящих из узла ветвей по- 25 их длительностей до тех пор, пока

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

ра 4 и с приходом второго импульса По адресу ее номера в узле 39 памяти

ГИ1 записьшается в указанный регистр.

Записанный в регистр 43 код поступает

блока 2 формирования топологии считывается код X, который записывается

вновь на адресный вход узла 39 памяти,30 в регистр 43. Так как выход региста также через полюс 16 и элемент ИЛИ 89 блока 1 управления на адресный вход узла 5 памяти длительностей ветвей и информационный вход узла 6 памяти номеров моделируемых ветвей. С Приходом второго импульса ГИ2 из узла 5 памяти длительностей ветвей считывается длительность второй исходящей из узла ветви и для нее в узел 85 памяти времени начала моделирования ветвей записьтается содержимое узла 8 измерения длиннейшего пути.

Далее считанный код длительности второй исходящей ветви поступает через полюс 29 на входы элементов И 77(1), 77(2),...,77(Ы) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 18(1) на входы элементов 75(1) и 76(1) первой модели ветви 68 поступает сигнал поиска свободной модели ветви. Так как триггер 72(1) первой модели ветви находится в единичном состоянии, означающим ее занятость, то сигнал с выхода элемента 75(1) поступает на вход 18(2) второй, модели ветви, триггер 72(2) которой находится в нулевом состоянии. Тогда сигнал с выхода элемента И 76(2) второй модели ветви 68(2)

35

40

45

50

55

ра 43 подключен к дешифратору 49 состояния X, в комбинационной схеме путем сравнения кодов определяется информация о конце списка. Дешифратор 49 вырабатывает на выходе сигнал, который, поступает на нулевой вход триггера 48, сбрасывая его в нулевое состояние. Кроме этого, сигнал с выхода дешифратора поступает на полюс 21. С последнего сигнал (поиска прерывания) поступает на единичный вход триггера прерывания 9 и устанавливает его в единичное состояние. Одновременно сигнал поиска прерывания поступает в блок моделей ветвей. Так как выполняется моделирование длительностей ветвей, выходящих из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер прерывания 9 остается в единичном состоянии. На счетный вход узла 8 измерения длиннейшего пути и через полюс 30 во все формирователи 70 временного интервала моделей ветвей, триггеры 72 которых находятся в единичном состоянии j начинают поступать импульсы серии ГИ1 . Так про- должается до тех пор, пока хотя бы один из формирователей 70 временного

поступает на вход элемента И 77(2) и в формирователь временных интервалов 70(2) вводится исходная информация о коде длительности ветви. Одновремен- но сигнал с выхода элемента И 76(2) через, элемент 81(2) задержки устанавливает триггер 72(2) в единичное состояние, по этому же сигналу на выходе шифратора 82 адреса формируется

номер второй модели ветви, который через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления, и при появлении через некоторое время сигнала на выходе элемента 13 задержки в узел 6 памяти по адресу номера модели ветви записывается номер ветви, код длительности которой введен в формирователь 70 временного интервала данной модели ветви.

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

блока 2 формирования топологии считывается код X, который записывается

5

0

5

0

5

ра 43 подключен к дешифратору 49 состояния X, в комбинационной схеме путем сравнения кодов определяется информация о конце списка. Дешифратор 49 вырабатывает на выходе сигнал, который, поступает на нулевой вход триггера 48, сбрасывая его в нулевое состояние. Кроме этого, сигнал с выхода дешифратора поступает на полюс 21. С последнего сигнал (поиска прерывания) поступает на единичный вход триггера прерывания 9 и устанавливает его в единичное состояние. Одновременно сигнал поиска прерывания поступает в блок моделей ветвей. Так как выполняется моделирование длительностей ветвей, выходящих из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер прерывания 9 остается в единичном состоянии. На счетный вход узла 8 измерения длиннейшего пути и через полюс 30 во все формирователи 70 временного интервала моделей ветвей, триггеры 72 которых находятся в единичном состоянии j начинают поступать импульсы серии ГИ1 . Так про- должается до тех пор, пока хотя бы один из формирователей 70 временного

интервала не выдает сигнал об окончании процесса временного моделирования длительности ветви.

Сигналы с выхода формирователей 70(1), 70(2),...,70(М) временного интервала поступают на единичные входы триггеров 71(1), 71(2),...,71(М) и устанавливают триггеры в единичное состояние. Одновременно сигнал с выхода формирователей 70 поступает через элемент ИЛИ 83 на вход поиска прерывания (I,1) первой модели ветви и в случае, если триггер 7l(l) находится в единичном состоянии, сигнал прерываВИЯ с выхода элемента 74(1) поступает через элемент ИЛИ 84 и полюс 25 в блок 1 управления, устанавливает триггер 72(1) в нулевое состояние, что означает освобождение модели ветви для последующих вычислений. Одновременно этот сигнал через элемент 80 задержки сбрасывает триггер 7l(l) в нулевое состояние и выдает с полюса (1,3) сигнал

на вход шифратора 82 адреса, по кото- 25 хода узла 86 определения разности

рому формируется номер данной модели ветви. Номер модели ветви с выхода шифратора 82 адреса через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления.

При получении с полюса 25 сигнала прерьтания, который поступает на вход считывания узла 6 памяти номеров моделируемых ветвей, считывается по адресу номера модели ветви номер ветви сети. Этот номер поступает через элемент ИЛИ 12 на адресный вход узла 7 памяти меток свершения ветвей, а также через элемент ИЛИ 89 на адресный вход узла 5 памяти длительноетей ветвей. Через время, достаточное для счи- втывания номера ветви, на вход записи узла 7 памяти меток свершения ветвей через элемент 14 задержки поступает сигнал прерывания, и по адресу номера ветви в узел 7 памяти меток свершения ветвей записывается метка , характеризующая-, свершение проГ

цесса моделирования длительности данной ветви. Одновременно сигнал прерывания с выхода элемента 14 задержки поступает на вход считывания узла 85 памяти времени начала моделирования ветви. Считьшаемая из узла 85 памяти по адресу кода ветви информация о начале моделирования ветви поступает на первый вход узла 86 определения разности двух кодов (схема вычитания).

на второй вход которого подается код (конца моделирования ветви) текущего времени моделирования сети с выхода узла 8 измерения длиннейшего пути.

Через время, достаточное для записи метки в узел 7 памяти меток свершения ветвей, с выхода элемента 15 задержки сигнал прерывания поступает на разрешающий вход узла 86 определения разности двух кодов, через полюс 28 в блок 2 формирования топологии, через элемент ИЛИ 90 на вход- считывания узла 5 памяти длительности ветвей, а также через элемент 91 задержки, на разрешающий вход блока 87 сравнения. Из узла 5 памяти длительностей ветвей считывается код длительности обрабатываемой ветви, а на выходе узла 86 определения разности двух кодов появляется разность времен начала и конца моделирования рассматриваемой ветви. На информационные входы блока 87 сравнения поступают коды с вы0

5

0

5

0

5

двух кодов и узла 5 памяти длительностей ветвей.

Таким образом, на выходе узла 86 определения разности двух кодов появляется код разности между кодами, определяющими время начала и время конца моделирования ветви, равный длительности ветви при правильном моделировании длительности. При различии кодов (неправильное моделирование ветви), поступающих на блок 87 сравнения, на его выходе появляется сигнал сбоя, поступающий на выходной полюс 92 неверной отработки длительности ветви, и на вход элемента И 88. На второй вход элемента И 88 поступает адрес кода ветви. Выход элемента И 88 соединен с выходным полю - сом 93 номера неверно отработанной ветви.

Далее в работе устройства код номера ветви, считанной ранее с выхода узла 6 памяти номера моделируемой ветви, через полюс 26 поступает на адресный вход узла 38 памяти конечного узла блока 2 формирования топологии, а сигнал начала анализа ветви с полюса 28 поступает на вход триггера 47 и устанавливает его в единичное состояние. Единичное состояние триггера 47 разрешает прохождение импульсов ГИ1 (полюс 31) и ГИ2. (полюс 32) j через элементы И 63 и 64. Кроме того, сигнал начала анализа ветви поступает

,5

10

15

- 1509925

на вход элемента 53 задержки и на - вход считывания узла 38 памяти. С приходом сигнала считывания в узле 38 памяти конечного узла по адресу номера ветви, вызвавшей прерывание, проис ходит считывание ячейки памяти, в которой записан номер конечного узла рассматриваемой ветви. Код считанного номер а узла с выхода узла 38 памяти поступает на адресные входы узла памяти первой выходящей ветви и на информационные входы регистра 45 конечного узла.

Через время задержки, достаточное для считывания информации из узла 38 памяти, сигнал начала анализа ветви поступает на управляющий вход регистра 45 конечного узла и на вход считывания узла 42 памяти. По задержанному сигналу начала анализа ветви в регистре 45 происходит запись номера конечного узла ветви, а в узле 42 памяти по адресу номера конечного узла происходит считывание номера ветви, первой в списке входящих в рассматриваемый узел ветвей. Код номера первой входящей ветви с выхода узла 42 памяуи поступает через элемент ИЛИ 58 на информационный вход регистра 44 входящей ветви и записывается в него по первому импульсу ГИ1, поступающему а управляющий вход регистра с выхода элемента И 63. С выхода регистра 44 од номера первой входящей ветвн по40

45

ступает через полюс 19 и элемент ИЛИ 12 а адресный вход узла 7 памяти меток свершения ветвей блока 1 управления на адресный вход узла 40 памяти ноеров входящих ветвей блока 2 формирования топологии. Первый импульс ГИ2 оступает с выхода элемента И 64 на ход элемента И 61 блока 2 формироваия топологии и через полюс 20 на ход считывания узла 7 памяти меток свершения блока 1 управления.

Метка свершения, считанная по адесу первой ветви с выхода узла 7 .паяти меток свершения ветвей, поступат через полюс 27 в блок 2 формироваия топологии. Если метка отсутствут, что означает несвершение процесса оделирования длительности ветви с анным номером, то нулевой сигнал метки с полюса 27 через элемент НЕ 67 и элемент ИЛИ 59 сбрасывает триггер 47 в нулевое состояние. Кроме того, сигал с выхода элемента НЕ 67 поступает ерез элемент ИЛИ 57 на полюс 21 пом

в т с м 25 с д л я эл в м по св ви им

20

30

50

55

в ли пу бл па го

ви че те вы пу ка сч ве мя ра вы дя ся то на и вт

5

10

15

9925

14

иска прерывания. Наличие нулевого сигнала метки Свершения ветви означает, что хотя бы в одной из ветвей списка, входящих в узел, не завершился процесс временного моделирования своей длительности и, следовательно, в данном узле не сформирована функция U для всех входящих в него ветвей Г Тог- да сигнал поиска прерывания-с полю-, са 21 поступает на единичный вход триггера прерывания 9 и одновременно через полюс 22 на вход элемента ИЛИ 83 узла поиска моделей ветвей 59 блока 3 моделей ветвей. С выхода элемента ИЛИ 83 сигнал поступает на входы элементов И 73(0 и 74(1) первой модели ветви.

Если модель ветви закончила процесс моделирования длительности ветви ,которая еще не анализировалась, то триггер 7 находится в единичном состоянии. Тогда сигнал с выхода элемента 74 такой модели ветви вновь по- . 25 ступает на вход шифратора 82 адреса для формирования номера данной модели ветви, сбрасывает в нулевое состояние триггеры 71 и 72, а также через элемент ИЛИ 83 выдает сигнал прерывания. Блок 1 управления, получив номер модели ветви и сигнал прерывания, повторяет все описанные операции, связанные с анализом свершения ветви. Если в блоке 3 моделей ветвей не имеется моделей, имеющих триггеры 71

20

30

в единичном состоянии, то процесс анализа прерывания не проводится и импульсы серии ГИ1 через элемент И 10 блока 1 управления продолжают поступать в узел 8 определения длиннейшего пути и в блок 3 моделей ветвей.

Если сигнал метки свершения ветви с полюса 27 имеет единичное значение, т.е. процесс формирования длительности для ветви закончился, то он выдает разрешение на прохождение импульса ГИ2 через элемент И 61 блока 2 формирования топологии на вход считывания узла 40 памяти входящей ветви. На адресные входы узла 40 памяти в это время поступает код номера первой входящей ветви в списке с выхода регистра 44.По адресу первой вхоящей ветви из узла 40 памя-ти считывает- ся код номера второй ветви в списке,который поступает через элемент ИЛИ 58 на информационные входы регистра 4 и записывается в него с приходом второго.импульса ГИ с выхода элемента И 63. Далее через полюс 19 осуществляется опрос метки свершения ветви, входящей в рассматриваемый узел, и переход к следующей ветви из списка входящих в него ветвей.

Описанньй процесс анализа входящих ветвей продолжается до тех пор, пока не опрошены все ветви, входящие в рассматриваемый узел, что соответствует выполнению функции конъюнкции относительно входных ветвей для рассматриваемого узла, В этом случае по 1 адресу последнего номера ветви в спис- Iке из узла 40 памяти считывается ин- формация X, определяющая конец списка. Код X записывается в регистр входящей ветви 44 и далее поступает на вход дешифратора 50 состояния, ко- торый путем сравнения кодов вырабатывает сигнал конца списка. Полученный сигнал проходит через элементы ИЛИ 59 и 60 и устанавливает триггеры 47 и 48 соответственно в нулевое и единич- нее состояния. Сигнал с выхода дешифратора 50 поступает также на вход элемента И 62, второй вход которого связан с выходом дешифратора 51 сравнения кодов. Последний сравнивает ко- ды, хранящиеся в регистре конечного узла сети 46 и регистре 45 конечного узла.

Регистр 46 хранит код конечного узла сети, а регистр 45 - код рассматриваемого узла сети, сформировавщего функцию конъюнкции в данный момент времени. Если значения этих кодов совпадают (сформирована логическая функций конъюнкции для конечного узла сети), то дешифратор 51 сравнения кодов выдает разрешение на прохождение сигнала конца списка с выхода дешифратора состояния 50 через элемент И 6

на вьпсодной полюс.23 блока 2 формиро- .с УЗЛа определения разности двух кодов

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

вания топологии, что соответствует концу моделирования заданной сети. Данный сигнал с полюса 23 поступает На вход элемента И 11 блока 1 управления и разрешает вьщачу во внешние устройства величины длиннейшего пути сети, накопленной к данному моменту в узле 8 измерения .длиннейшего пути. Если не сформирован конечный узел сети, то сигнал с выхода дешифратора 50 поступает через элемент ИЛИ 54 на вход считывания узла 41 памяти первой выходящей ветви, на адресный вход которого в этот момент времени поступа

5 0

д

5

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

Описанные процессы подготовки ветвей к временному моделированию - длительностей с запоминанием кодов времени начала моделирования и анализа ветви, закончивших процесс временного моделирования, с контролем правильности моделирования каждой ветви j чередуются в указанном порядке и повторяются до тех пор, пока не сформирован заданный конечный узел, сети с выдачей сформированной в узле 8 измерения длиннейшего пути блока I управления величины длиннейшего пути в сети. В процессе всего временного моделирования сети при неправильной работе устройства на выходных полюсах 92 и 93 фиксирзпотся все сбойные ситуации, связанные с неправильным формированием длительностей ветвей сети.

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

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

0

5

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

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

Редактор М. Бланар

Фиг.З

Составитель В. Чернышов

Техред Л.Олийнык Корректор Т. Палий

Заказ 5815/48

Тираж 668

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101

2f

Подписное