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

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

.1

951

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

задержки подключен к первому входу второго триггера, второй вход которого соединен с выходом двоичного/ счетчика, выходы второго и четбертого элементов И подключены соответственно к разрядным входам двоичного счетчика, второй выход второго триггера соединен с первым входом шестого элемента И модели ветви, выход пятого элемента ИЛИ блока формирования топологии и выходы двоичных счетчиков всех моделей ветвей подключены к входам первого элемента ИЛИ узла поиска моделей ветвей, выход которо го соединен с вторьми входами пятого и шестого элементов И первой модели ветви блока моделей ветвей, выход шестого элемента И, у-й модели ветви, где ,..., (п-1), блока моделей ветвей подключен к входу поиска прерывания (j+1)-й модели ветви, вькоды пятых элементов И всех моделей ветвей соединены с входами второго элемента ИЛИ узла поиска моделей ветвей выходы элементов ИЛИ всех моделей ветвей подключены к входам шифратора адреса узла поиска моделей ветвей, выход первого элемента И j-й модели ветви соединен с вторыми входами первого и третьего элементов И (|+1)-й модели ветви блока моделей ветвей, выход узла памяти длительностей вет вейблока управления подключен к вто рому входу четвертого элемента И каждой модели ветви блока моделей ветвей, выход шифратора адреса узла поиска моделей ветвей блока моделей ветвей соединен с адресным входом узла памяти номеров моделируемых зетвей блока управления, выход которого подключен к первому входу элемента ИЛИ, выход которого соединен с адресным входог узла памяти меток свершения ветвей блока управления, выход которого подключен к входу элемента НЕ блока формирования топологии, выход четвертого элемента И блока формирования топологии соединен с вторыми входами первого и третьего элемейтов И первой модели ветви блока моделей ветвей, с входом считывания узла памяти длительностей ветвей блока управления и с входом первого элемента задержки блока управления, выход первого элемента задержки блока управления Подключён к входу записи узла памяти номеров моделируемых ветвей блока управления, выход второго элемента ИЛИ узла поиска моделей ветвей блока моделей ветвей соединен с

входом считьшания узла памяти номеро моделируемых ветвей, с. первым входом триггера прерьшания и входом второго элемента задержки блока управления, выход второго элемента задержки блока управления подключен к входу записи узла памяти меток свершения ветвей и к входу третьего элемента задержки блока управления, выход которого соединен с управляющим входом узла памяти адресов конечных узлов ветвей сети блока формирования топологии, выход регистра адреса вьпсодящей ветви блока формирования топологии подключен к адресному входу узла памяти длительностей ветвей и к информационному входу узла памяти номеров моделируе1У ых ветвей блока управления, выход регистра адреса входящей ветви 6j7OKa формирования топологии соединен с вторым входом элемента ИЛИ блока управления, первый вход элемента ИЛИ блока управления подключен к адресному входу узла памяти адресов конечных узлов ветвей сети блока формирования топологии, выход шестого элемента И блока формирования топологии подключен к входу считывания узла памяти меток свершения ветвей блока управления, выход пятого элемента ИЛИ блока формирования топологии соединен с вторым входом триггера прерывания блока управления, выход которого подключен к первому входу первого элемента И блока управления, выход которого соединен с входом счетчика, выход которого подключен к первому входу второго элемента И блока управления, второй вход которого соединен с выхо дом второго элемента И блока формирования топологии, второй выход генератора тактовых импульсов подключен к второму -входу первого элемента и блока управления, выход которого соединен с вторыми входами второго элемента И всех узлов моделей ветвей блока моделей ветвей. 1 . 1 Изобретение относится к цифровой вычислительной технике, в частности к устройствам для обработки информации специального назначения с точки зрения вычислительного устройства, и может быть использовано при постро ении специализированных вычислительных устройств для моделирования сетевых задач оперативного управления. Цель изобретения - повьшение коэф фициента полезного использования оборудования. На фиг. 1 показана блок-схема предлагаемого устройства; на фиг.2 схема одного из возможных вариантов выполнения блока формирования топологии; на фиг..З - схема одного из возможных вариантов выполнения блока моделей ветвей. Предлагаемое устройство (фиг. 1) состоит из блока 1 управления, блока 2 формирования топологии, блока 3 моделей ветвей, генератора 4 импульсов. Входы k выходы названы полюсами. Блок 1 управления содержит узел 5 памяти длительностей ветвей, узел 6 памяти номеров моделируемых вбтвей, узел 7 памяти меток свершения ветвей узел 8 измерения длиннейшего пути, триггер 9 пргрьюания, первый элемент И 10 и второй элемент И 11, элемент ИЛИ 12, линии 13, 14 и 15 задержки. Выход 16 номера подготавливаемой к моделированию ветви блока 2 формирования топологии соединен с адресным входом узла 5 памяти и с информа ционным входом узла 6 памяти. Выход 17 поиска свободной модели ветви бло ка 2 формирования топологии соединен с входом считьгоания узла 5 памяти и через линию задержки 13 с входом записи узла 6 памяти блока 1 управле ния и с входом 18 поиска свободной модели ветви блока 3 мдделей ветвей. Выход 19 номера анализируемой ветви блока 2 формирования топологии соеди нен через элемент ИЛИ 12 с адресным входом узла 7 памяти блока управления. Выход 20 проверки свершения вет ви блока 2 формирова;1ия топологии сети соединен с входом считывания узла 7 памяти блоки 1 управления. Выход 21 поиска прерьюания соединен с входом установки 1 триггера 9 прерьшания блока 1 управления и с входом 22 блока 3 моделей ветвей. Выход 23 индикации результата расче12та блока 2 формирования топологии соединен с входом второго элемента И 11 блока 1 управления. Выход 24 номера модели ветви блока 3 моделей ветвей соединен с адресным входом узла 6 памяти блока 1 управления. Выход 25 прерывания блока 3 моделей ветвей соединен с входом считывания узла 6 памяти, входом установки О триггера 9 прерывания и входом линии 14задержки блока 1 управления. Выход номера анализируемой ветви сети, узла 6 памяти блока 1 управления соединен с входом 26 блока 2 формирования топологии. Выход свершения ветви узла 7 памяти блока 1 управления соединен с входом 27 блока 2 формирования топологии. Выход начсша анализа свершения ветви сети линии 15задержки блока 1 управления соединен с входом 28 блока 2 формирования топологии. Выход кода длительности ветви узла 5 памяти блока 1 управления соединен с входом 29 блока 3 моделей ветвей. Выход измерительной серии импульсов первого элемента И 10 блока 1 управления соединен с входом 30 блока 3 моделей ветвей. Входные полюса 31 и 32 блока 2 формирования топологии предназначены для подключения сдвинутых относительно друг друга серий импульсов генератора 4 ГИ1, ГИ2. Вход 33 блока 1 управления подключен к соответствующему выходу генератора 4. Входными полюсами устройства являются входаые полюсы 34 и 35 блока 2 формирования топологии. Выходным полюсом устройства является выходной полюс 36 блока 1 управления, соединенный с выходом второго элемента И 11 блока 1 управления. В устройстве на фиг. 1 блок 1 управления предназначен для организации взаимодействия между блоком 2 формирования топологии и блоком 3 моделирования ветви устройства в процессе моделирования и определения величины длительности длиннейшего пути исследуемой сети. Блок 2 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети, и номеров ветвей, выходящих из исследуемого узла сети, а также дпя определения момента окончания процесса вычислений. Блок 3 моделей ветвей предназначен для организации процесса временного моделирования длительностей ветвей сети. Генератор 4 импульсов предназначен для формирования серий импульсов ГИ1 и ГИ2, сдвинутых .относительно друг друга., В блоке 1 управления :(фиг. 1) узел 5 памяти длительностей ветвей предназначен для хранения информации о величинах длительностей ветвей сети, а именно для хранения по адресу номера ветви кода длительности данной ветви. Узел 6 памяти номеров моделируемых ветвей предназначен для хранения информации о соответствии номера модели ветви из блока 3 моделей ветвей номеру ветви сети, модели руемой в текущий момент времени данной моделью ветви. Узел 7 памяти меток свершения ветвей сети блока управления предназначен для хранения информации о завершении процесса временного моделирования длительностей ветвей сети. Узел 8 измерения длительности длинейшего пути предназначен для фор мирования величины длительности длин нейшего пути сети и может быть выпол нен в виде счетчика со счетным входо и параллельной вьвдачей информации. Триггер 9 прерывания предназначен для организации временного разделени между процессом временного моделирования длительностей ветвей сети и процессом анализа топологии моделируемой сети. Первьй и второй элементы И 10 и 1 предназначены соответственно для организации временного разделения процесса решения и для выдачи полученно го результата пЬспе завершения про- цесса моделирования сети. Линии 13, 14 и 15 задержки предназначены для предотвращения гонок при работе устройства. Блок 2 формирования топологии (фиг. 2) содержит узел 37 памяти адресов начальных узлов ветвей сети, узел 38 памяти адресов конечных узлов ветвей сети, узел 39 памяти адре сов выходящих ветвей узлов сети, узел 40 памяти адресов входящих ветвей узлЬв сети, узел 41 памяти адресов первой выходящей ветви узлов сети, узел 42 памяти адресов первой входящей ветви узлов сети, регистр 43адреса выходящей ветви, регистр 44адреса входящей ветви, регистр 45 адреса конечного узла ветви, региста конечного узла сети, триггеры и 48, дешифраторы 49 и 50 дешифратор 51 сравнения кодов, линии 52 и 53 задержки, элементы ИЛИ 54-60, элементы И 61-66, элемент НЕ 67. Входами блока являются полюсы 34 и 35, соединенные соответственно с входом считьшания и адресным входом узла 37 памяти начального узла. Вход 26 HOMeija анализируемой ветви сети блока 2 формирования топологии соединен с адресным входом узла 38 памяти конечного узла. Вход 28 начала анализа свершения ветви соединен с входом считывания узла 38 памяти конечного узла. Вход 27 свершения ветви соединен через элемент НЕ 67 и элемент ИЛИ 59 с входом установки нуля триггера 47. Выход 21 снятия прерывания блока 2 формирования топологии соединен с выходом элемента ИЛИ 57. Выход 16 номера подготавливаемой к моделированию ветви соединен с выходом регистра 43 адреса выходящей ветви. Выход 19 номера айализируемой ветви блока 2.формирования топологии соединен с выходом регистра 44 адреса входящей ветви. Выход 17 поиска свободной модели ветви соединен с выходом элемента И 66. Выход 20 проверки свершения ветви соединен с выходом элемента И 64. Выход 23 разрешения вьщачи результатов соединен с выходом элемента И 62. Узлы 37-42 памяти предназначены для хранения информации о топологии моделируемой сети (узел 37 памяти - для хранения номера начального узла ветви по адресу номера данной ветви; узел 38 памяти - для хранения номера конечного узла ветви по адресу номера данной ветви; узел 41 памяти - для хранения по адресу номера узла номера ветви, первой из списка ветвей, выходящих из данного узла; узел 42 памяти - для хранения по адресу номера узла номера ветви, первой из списка ветвей, входящих в данный узел; узел 39 памяти - для хранения в виде списков номеров вет- , вей, выходящих из узлов сети, а узел 40 памяти - для хранения в виде списков номеров ветвей, входящих в узлы сети). Регистр 43 адреса выходящей ветви регистр 44 адреса входящей ветви , блоке 2 формирования топологии представляют собой регистры с параллельным приемом информации. Регистр 43 предназначен для проме жуточного хранения номера ветви при определении ветвей, выходящих из узла, а регистр 44 - для промежуточного хранения адресов (номеров) ветвей, входящих в узел. Регистры 45 и 46 выполнены аналогичным образом и предназначены для хранения адреса рассматриваемого узла сети и для постоянного хранения адреса конечного узла сети. Дещифратор 51 сравнения кодов предназначен для поразрядного сравнения кодов из регистров %5 и 46. Дешифраторы 49 и 50 состояния X предназначены для сравнения поступаю щих на них кодов с кодовой комбинацией состояния X, заданного постоянно в схеме. Блок 3 моделей ветвей (фиг. 3) со держит п моделей 68 ветвей (где г количество ветвей в максимальном се чении сети) и узел 69 поиска моделей ветвей. Цифрами в скобках обозначены порядковые номера совершенно одинаковых по своему конструктивному исполнению и функциональному назначе-. нию блоковi узлов, элементов и полюсов. Каждая модель 68 ветви (фиг. 3) состоит из формирователя 70 временны интервалов, триггеров 71 и 72, элементов И 73-78, элемента ИЛИ 79, элементов 80 и 81 задержки. Схема узла 69 поиска моделей ветвей, детализированная на фиг. 3, содержит шифратор 82 адреса и элементы ИЛИ 83 и 84. Входы 29(1), 29(2), о., 2 9 () кода дл тельности ветви соединены с входами элементов И 77(1),77(2),..., 77(п). Входы 30(1), 30(2),..., 30(П) измери. тельной серии импульсов соединены с входами элементов И 78( J) , 78(2) 78(п) узла 68 моделей ветвей. Вход 18(1 поиска свободной модели ветви соеди нен с входами элементов И 75(1) и 76(1) первой модели 68(1) ветви. Вы ход элемента И 75(1) первой модели 68(1) ветви соединен с входом 18(2) поиска свободной модели ветви второ модели 68(2) ветви, выход элемента И 75(2) второй модели 68(2) ветви соединен с входом 18(3) поиска сво-55 бодной модели веТви третьей модели 68(3) ветви и т.д. до п. Вход 22 поиска прерывания соединен с входом элемента ИЛИ 83 узла 69 поиска моделей ветвей блока 3 моделей ветвей. Выход элемента ИЛИ 83 узла 69 поиска моделей ветвей соединен с входом (1,1) поиска прерывания первой модели 68(1) ветви. Первая цифра в скобках обозначает более высокий в иерархии порядковый номер (в данном случае номер модели ветви), а вторая - более низкий в иерархии номер (з данном случае порядковьй номер входа или выхода этой модели). Входы (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) поиска прерьшания третьей модели 68(3) ветви и т.д. до й модели ветви. Выходы (1,2), (2,2) J ..., (|,2)переполнения формирователей 70(1),70(2),...,70(п временных интервалов моделей 68(1) ,68(2),..., 68(п)ветвей соединены с входами элемента ИЛИ 83 узла 69 поиска моделей ветвей. Выходы (1,4),(2,4),...,(п,4)сигналов прерывания с выходов элементов И 74(1), 74(2),...,74(h) моделей 68(1), 68(2), 68(п) ветвей соединены с входами элемента ИЛИ 84. Выходы (1,3), (2.,3),..., (г,3) кода моделей ветвей с выходов элементов ИЛИ 79(1), 79(2),...,79(п) моделей 68(1), 68(2),..., 68(п)ветвей соединены с входами элемента ИЛИ 84. Выходы (1,3), (2,3),..., (г.3) кода моделей ветвей с выходов элементов ИЛИ 79(1), 79(2),...,79(п) моделей 68(1), 68(2)68(п) ветвей соединены с входами шифратора 8:2 адреса узла 69 поиска моделей ветвей. Выход 25 прерывания блока 3 моделей ветвей соединен с выходом элемента ИЛИ 84 узла 69 поиска моделей ветвей. Выход 24 номера Модели ветви соединен с выходом шифратора 82 адреса узла 69 поиска модели ветви. Формирователи 70(1), 70(2),..., 70(п) временного интервала моделей 68(1), 68(2), 68(п) ветвей предназначены для временного моделирования длительностей ветвей сети и могут быть выполнены в.виде двоичного счетчика с параллельным вводом исходной информации. Шифратор 82 адреса узла 69 поиска моделей ветвей предназначен для формиро1вания адреса каждой модели ветви Устройство работает следующим образом. В узлы 37-42 памяти блока 2 форми рования топологии в виде списков заносится информация о топологии моделируемой сети. Регистры 43-45 предварительно обнуляются, а в регистр 46 конечного узла сети заносится код номера конечного узла сети. Триггеры 9, 47, 48, 71(1), 71(2),...,71(п) 72(п), 72(1), 72(2),..., 72(п) находятся первоначально в нулевом состоя нии, узел 7 памяти меток свершения блока управления обнуляется. После начального установа на полюс 36 блока 2 формирования топологии подается код номера ветви, выходящий из узла, принятого при данном решениц за начальный. Начальньй узел таким образом, определяется по адресу номера ветви в узле 37 памяти блока формирования топологии. В некоторый момент времени сигнал Пуск, поступающий на полюс 34, про ходит через элемент ИЛИ 60 и устанав ливает триггер 48 в единичное состоя ние . Единичное состояние триггера 48 разрешает прохождение серии импульсов ГИ1 (полюс 31) и ГИ2 (полюс 32) соответственно через элементы И 65 и 66. Кроме того, сигнал Пуск поступает на вход элемента 52 задержки и на вход считывания узла памяти начальных узлов. При пост пглении сигнала разрешения выборки в узле 37 памяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 35. Так как ветвь выбрана как выходящая из начального узла сети, то на выходе узла 37 памяти появляется код началь ного узла сети, который поступает через элемент ИЛИ 55 на адресный вход узла 41 памяти первой выходящей ветви. Через время задержки, достаточное для считьтания информации из узла 37 памяти, сигнал Пуск появляется на выходе элемента 52 задержки и поступает через элемент ИЛИ 54 на вход считьшания узла 41 памяти. Сигнал выборки по адресу начального узла позволяет сосчитать из узла 41 памяти код номера ветви. являющейся первой в списке ветвей, выходящих из начального узла сети. Код первой выходящей ветви с Выхода узла 41 памяти поступает через злемент ИЛИ 56 на информационный вход регистра 43 выходящей ветви и записывается в него по первому импульсу ГИ1, поступившему на управляющий вход регистра с выхода элемента И 65. Записанньш код первой выходящей ветви с выхода регистра 43 поступает на адресный вход узла 39 памяти, а также через выходной полюс 16 блока 2 формирования топологии - на адрес ный вход узла 5 памяти длительностей и информационный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления. Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на вход считывания узла 39 памяти и по адресу первой выходящей из начального узла ветви осуществляет выборку второго номера ветви, выходящей из того же узла. Одновременно импульс ГИ2 поступает на .вход считьгоания узла 5 памяти длительностей, элемента 13 задержки блока 1 управления и вход 18 поиска свободной модели ветви блока 3 моделей ветвей. По сигналу ГИ2 и адресу номера первой выходящей из узла ветви в регистре 43 осуществляется считывание кода длительности этой ветви из узла 5 памяти длительностей. Одновременно сигнал поиска свободной модели ветви с полюса 18 поступает на входы элементов 75(1) и 76(1) первой модели 68(1) ветви блока 3 моделей ветвей. Так как все модели ветвей свободны, то триггер 71(1) будет находиться в нулевом состоянии и сигнал с вьЬсода элемента 76(1) через элемент 81(1) задержки поступит на вход установки единичного состояния триггера 71(1), который через время задержки, достаточное для срабатывания всех элементов, установит его в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви первой модели ветви. Одновременно сигнал с выхода элемента И 76(1) поступает на первый вход элемента И 77(1) и через элемент ИЛИ 79(1) на вход шифратора адреса. На второй вход элемента И 77(1) поступает через вход 29 кода длительности код длительности ветви, KOTOpbtft через элемент И 77(1) заносится в качестве исходной информации в формирователь 70 временного интервала. С выхода шифратора 82 адреса полученный по сигнал с полюса (1,3) код адреса модели вет ви поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока управления. Через время, достаточное для организации описанных процессов в блоке 3 моделей ветвей, на выходе элемента 13 задержки блока 1 управления появляется сигнал, поступающий на вход записи узла 6 памяти номеров моделируемых ветвей. Сигнал записи позволяет записать по адресу номера выбранной модели ветви (в данном случае первой) номер ветви длительность которой внесена уже в формирователь 70(2) временного интервала данной модели ветви. На этом заканчивается подготовка первой выходящей из узла ветви к процессу временного моделирования длительности. Для этого, суммируя описанное, вьшолняется считывание из блока 2 формирования топологии адреса ветви, затем считывание ее длительности, поиск свободной от вычислений модели ветви, ввод в ее формирователь временного интервала кода длительности ветви и запись в узел номера моделируемых ветвей по адресу номера выбранной модели ветви номера первой ветви.

Далее считанный по адресу номера первой выходящей ветви из узла 39 памяти выходящих ветвей блока 2. формирования топологии номер следующей ветви в списке выходящих из узла ветвей поступает на информационньй вход регистра 43 и с приходом второго импульса ГИ} записьшается в указанный регистр. Записанный в регистр 43 код поступает вновь на адресный вход узла 37 памяти, а также через полюс 16 на адресный вход узла 5 памяти и информационный вход узла 6 памяти. С приходом второго импульса ГИ2 из узла 5 памяти длительностей считывается длительность второй исходящей из узла ветви н поступает через полюс 29 на входы элементов И 77(1), 77(2),...,77(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 18(1) на входы элементов 75(1) и 76(1) поступает сигнал поиска свободной модели ветви. Так как триггер 71(1) первой

модели ветви находится в единичном состоянии, означающем его занятость, то сигнал с выхода элемента75(1) поступает на вход 18(2) второй модели ветви, триггер 71(2) которой находится в нулевом состоянии. Тогда сигнал с выхода элемента И 76(1) поступает на вход элемента И 77(2) и в формирователь временных интервалов вводится исходная информация о коде длительности ветви.Одновременн сигнал с выхода элемента И 76(2) через элемент 80(2) задержки устанавливает триггер 71(2) в единичное состояние, по этому же сигналу ня выходе шифратора 82 адреса формируется номер второй модели ветви, который через .полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей, и при появлении через некоторое время сигнала на выходе элемента 13 задержки в памяти по .адресу номера модели ветви записывается номер ветви, код длительности которой введен в формирователь 70 временного интервала данной ветви.

Так осуществляется подготовка ветвей, выходящих из н ачального узла, к процессу временного моделирования их длительностей до тех пор, пока не будет сосчитана последняя ветвь из списка. По адресу ее номера в узле 39 памяти будет считан код X, который записывается в регистр 43. В этом случае, так как выход регистра 43-подключен к дешифратору 49 состояния X, в комбинационной схеме путем сравнения кодов будет определена информация о конце списка, записанная в регистре 43 блокд 2 формирования топологии. Дешифратор 49 вырабатывает на выходе сигнал, который поступает на нулевой вход триггера 48, сбрасьшаёт его в нулевое состояние, кроме того, сигнал с выхода дешифратора поступает на полюс 21. С полюса 21 сигнал (поиска прерывания) поступает на единичный вход триггера прерьшания и устанавливает его в единичное состояние, одновременно сигнал поиск прерывания поступает в блок 3 моделей ветвей. Так как выполняется моде.лирование длительностей ветвей, выходящих из начального узла сети,и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер 9 прерывания остается в единичном состоянии и на счетный вход узла 8 измереНИЯ длиннейшего тути и через полюс 30 во все формирователи 70 временног интервала моделей ветвей, триггеры 71 которых находятся в единичном состоянии, начнет поступать импульс серии ТИ1. Так продолжается до тех пор пока один Из формирователей 70 временного интервала не выдаст сигна об окончании процесса временного моделирования длительности ветви. Сигналы, с выхода формирователей 70(0,70(2),. . .,70(п) временного интервала поступают на единичные входа триггеров 72(1), 72(2),..., 72(п) и устанавливают триггеры в единичное состояние. Одновременно сигнал с выхода формирователя 70 поступает через элемент ИЛИ 83 на вход поиска прерьшания (1,1) первой модели ветви и в случае, если триггер 7.2(1) находится в единичном состоянии, сигнал прерывания с выхода элемента 74(1) поступает через элемент ИЛИ 84 через полюс 25 в блок управления .1, устанавливает триггер 71(1) в нулевое состояние, что означает освобождение модели ветви для последующих вычислений . Одновременно этот же сигнал через элемент 80 задержки сбрасывает триггер 72(1) в нулевое состояние и выдает с полюса (1,3) сигнал на вход шифратора 82 адреса, по которому фор мируется номер данной модели ветви, который через полюс 24 поступает в блок 1 управления. Номер модели нетви с полюса 24 поступает на адресньй вход узла 6 памяти номеров моделируемых ветвей. При получении с полюса 25 сигнала прерьтания, который поступает на вход считьшания узла 6 памяти номеров моделируемых ветве й, считьшается по адресу номера модели ветви номер ветви сети, который поступает через элемент ИЛИ 12 на адресный вход узла памяти меток свершения ветвей. Через время, достаточное для считывания номера ветви, на вход записи через элемент 14 задержки поступает сигнал прерывания, по адресу номера ветви в узел 7 памяти меток свершения ветвей записывается метка 1, характеризующая свершение процесса моделирования длительности данной ветви. Через время, достаточное для записи метки, с выхода элемента 15 задержки сигнал прерывания поступает через полюс 28 в блок 2 формирования топологии, Че15112 рез полюс 26 с выхода узла 6 памяти номера моделируемой ветви в блок формирования топологии поступает номер ветви. Код номера ветви с полюса 26 поступает на адресный вход узла 38 памяти конечного узла, а сигнал начала анализа ветви с полюса 28 поступает на вход триггера 47 и устанавливает его в единичное состояние. Единичное состояние триггера 47 разрешает прохождение импульсов ГИ1 (полюс 31) и ГИ2 (полюс 32) через элементы И 63 и 64. Кроме того, сигнал начала анализа ветви поступает на вход линии 53 задержки и на вход считывания узла 38 памяти. С приходом сигнала выборки в узле памяти конечного узла 38 по адресу номера ветви, вызвавшей прерывание, происходит считьшание ячейки памяти, в которой записан номер конечного узла рассматриваемой ветви. Код считанного номера узла с выхода узла 38 памяти поступает на адресные входы узла 42 памяти первой выходящей ветви и на информационные входы регистра 45 конечного узла. Через время задержки, достаточное для считывания информации из узла 38 памяти, сигнал начала анализа ветви поступает на управляющий вход регистра 45 конечного узла и на вход считывания узла 42 памяти. По задержанному сигналу начала анализа ветви в регистре 45 происходит запись номера конечного узла ветви, а в блоке 42 памяти по адресу номера конечного узла происходит считывание номера ветви, первой в списке входящих ветвей, в рассматриваемый узел. Код номера первой входящей ветви с выхода узла 42 памяти поступает через элемент ИЛИ 58 на информационный вхЪд регистра 44 входящей ветви и записывается в него по первому импульсу ГИ1,поступающему на управляющий вход регистра с выхода элемента И 63. С выхода регистра 44 код номера первой входящей ветви поступает через полюс 19 на адресный вход узла 7 памяти меток свершения ветвей блока 1 управления и на адресный вход узла 40 памяти входящих ветвей. Первый импульсу ГИ2 поступает с выхода элемента б4 на вход считывания узла 40 памяти блока формирования топологии и через полюс 20 на вход считьшания узла 7 памяти меток свершения ветвей блока 13.. 1 управления. Метка свершения, считанная по адресу первой ветви с вых да узла 7 памяти меток свершения ве вей, поступает через полюс 27 в бло формирования топологии. Если метка отсутствует, что означает несвершение процесса моделирования длительности ветви с данным номером, то ну вой сигнал метки с полюса 27 через элемент НЕ 67 сбрасывает триггер 47 в нулевое состояние. Кроме того,, сигнал с выхода элемента НЕ 67 пост пает через элемент ИЛИ 57 на полюс 21 поиска прерьшания. Наличие нулевого сигнала метки свершения ветви означает, что хотя бы одна из ветве списка, входящих в узел, не заверши ла процесс временного моделирования своей длительности и, следовательно в данном узле не сформирована функция и для всех входящих в него ветвей. Тогда сигнал с полюса 27 посту пает на единичный вход триггера 9 прерывания и одновременно через полюс 22 на вход элемента ИЛИ 83 узла 69 поиска моделей ветвей блока 3 мо делей ветвей. С выхода элемента ИЛИ 83 сигнал поступает на входы элементов И 73(1) и 74(1) первой мо дели ветви. Если модель ветви закон чила процесс моделирования длительности ветви, которая еще не анализи ровалась, то триггер 72 будет находиться в единичном со-стоянии. Тогда сигнал с выхода элемента 74 такой модели ветви вновь, поступит на вход шифратора 82 адреса для формирования номера данной модели ветви, сбросит в нулевое состояние триггеры 72 и 71, а также через элемент ИЛИ 83 вьщаст сигнал прерьшания. Блок 1 управления, получив номер мо дели ветви и сигнал прерывания, повторит все описанные операции, связанные с анализом свершения ветви. Если же в блоке 3 моделей ветвей не имется моделей, имеющих триггеры 72 в единичном состоянии, то про цесс анализа проводиться не будет и импульсы серии ГИ1 через элемент И 10 продолжат поступать в узел определения длиннейшего пути и в блок моделей ветвей. Если же сигнал метки свершения ветви с полюса 27 имеет единичное значение, т.е. процесс формирования длительности для ветви закончился, .то он выдает разрешение на прбхождр 1 ние импульса ГИ2 через элемент И 61 на вход считывания узла 40 памяти входящей ветви. На адресные входы узла 40 памяти в .это время поступает код номера первой входящей ветви в списке с выхода регистра 44. По адресу первой входящей ветви из узла 40 памяти будет считан .код номера второй ветви в списке, который поступает через элемент ИЛИ 58 на информационные входа. регистра 44 и записывается в него с приходом второго импульса ГИ1 с выхода элемента И 63. Далее осуществляется через полюс 19 опрос м.етки свержения данной ветви; входящей в рассматриваемый узел, и переход к следующей ветви из списка входящих в него ветвей. Описанный процесс анализа списка ветвей продолжается до тех пор, пока не будут опрошены все ветви, входят щие в рассматриваемый узел, что соответствует выполнению функции конъюнкции относительно входных ветвей для рассматриваемого узла. В этом случае по адресу последнего номера ветви в списке из узла 40 памяти будет считана информация X, определающая конец списка. Код X записывается в регист1 44 входящей ветви И далее поступает на вход дешифратора 50 состояний X, который путем сравнения кодов вырабатывает сигнал конца спискаi Полученньш сигнал проходит через элементы ИЛИ 59 и 60 и устанавливает триггеры 47 и 48 соответственно в нулевое и единичное состояния. Сигнал с выхода дешифратора 50 поступает также на вход элемента И 62, второй вход которого связан с выходом дешифратора 51 сравнения кодов. Дешифратор 51 сравнивает кода, хранящиеся в регистре 46 конечного узла сети и в регистре 45 конечного узла. Как указьгоалось ранее,регистр 46 хранит код конечного узла сети, а регистр 45 - код рассматриваемого узла сети, сформировавшего функцию конъюнкции в данный момент времени. Если значения этих кодов совпадают (сформирована логическая функция коньюнкции для конечного узла сети), то дешифратор 51 сравнения кодов вьщает разрешение на прохождение сигнала конца спис1 а с выхода дешифратора 50 состояния через элемент И 62 на выходной полюс 23 блока 2 формирования топологии, что соответстьует концу моделирования заданной сети.. Данный сигнал с полюса 23 поступает на вход элемента И 11 блока 1 управления и разрешает выдачу во внешние устройства величины длин- $ нейшего пути сети, накопленной к данному моменту в узле 8 формирования длиннейшего пути. В случае, если не сформирован конечный узел сети, то сигнал с выхода дешифратора 50 посту-О пает через элемент ИЛИ 54 на вход считьшания узла 41 памяти первой выходящей, ветви, на адресный вход которого в этот момент времени поступает код номера сформированного узла сети,15ч Вновь начинается описанный процесс подготовки к временному моделированию длительностей тех ветвей,- которые выходят из данного сформированного узла. Описанные процессы подготовки 20 ветвей к временному моделированию длительностей и анализа ветвей, закончивших процесс временного моделирования, будут чередоваться в указанном порядке и повторяться до тех пор, пока не будет сформирован заданный конечньй узел сети с вьщачей сформированной в узле 8 формирования длиннейшего пути блока 1 управления величины длиннейшего пути в сети.

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

г

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

Дн

3fi

.65

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЗАДАЧ О ДЛИННЕЙШЕМ ПУТИ В СЕТЯХ, содержащее генератор тактовых импульсов , блок формирования топологии и блок моделей ветвей, причем блок формирования топологии содержит узел памяти адресов первой выходящей ветви узлов сети, узел памяти адресов первой входящей ветви узлов сети, узел памяти адресов выходящих ветвей узлов сети, узел памяти адресов входящих ветвей узлов сети, регистр адреса выходящей ветви, регистр адреса входящей ветви, узль памяти адресов начальных и конечных узлов ветвей сети, регистры адреса конечного узла ветви и конечного узла сети, первый и второй триггеры, первый и второй дешифраторы, блок сравнения кодов, две линии задержки, семь элементов ИЛИ, шесть элементов И и элемент НЕ, вькоды регистров адреса выходящей и входящей ветвей соединены с адресными входами соответственно уэла памяти адресов выходящих ветвей узлов сети и узла памяти адресов входящих ветвей уэлов сети, адресный вход узла памяти адресов начальных узлов ветвей сети является входом задания адреса начальной ветви блока формирования топологии, управляющий вход узла памяти адресов начальных узлов ветвей сети является пусковьм входом блока формирования i:onoлогии и соединен с входом первой линии задержки и,первым входом первого элемента ИЛИ, адресный вход уэла памяти адресов конечных узлов ветвей сети является входок задания адреса конечного уэла ветви блока формирования топологии, управляющий вход уэла памяти адресов конечных уэлов ветвей сети является входом прерьшаСЛ ния работы блока формирования топологии и соединен с входом второй линии задержки и единичным входом первого триггера, пёрвьй вход первого элемента И соединен с входом элемента НЕ и является входом приема сигналов окончания работы моделей ветвей блока формирования топологии, информационный вход регистра адреса конечного уэла ветви соединен с выходом уэла памяти адресов конечных узлов ветвей сети и адресным входом узла памяти адресов первой входящей ветви уэлов сети, управляющий вход регистра адреса конечного уэла ветви соединен с выходом второй линии задержки и управляющим входом уэла памяти адресов первой входящей ветви уэлов сети, информационный вход регистра адреса конечного уэла сети является входом задания адреса конечного узла сети блока формирования топологии, выход регистра адреса конечного уэла