Устройство для моделирования задач о длиннейшем пути в сетях

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

4(st) С 06 F 15/20

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3608523/24-24 (22) 22.06.83 (46) 15 . 06. 85. Бюл. У 22 (72) А.Г.Додонов, А.А.Котляренко, С.П.Пелехов, В.П.Приймачук и В.M.Шишмарев (71) Институт проблем моделирования в энергетике АН УССР (53) 681,333(088.8) (56) Авторское свидетельство СССР

Р 422002, кл. С 06 G 7/48, 1972.

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

В 1024930, кл.. G 06 С 15/20, 1982. (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЗАДАЧ О ДЛИННЕЙШЕИ ПУТИ В СЕТЯХ, содержащее генератор тактовых импуль сов, блок формирования топологии и блок моделей ветвей, причем блок формирования топологии содержит узел памяти адресов первой выходящей ветви узлов сети, узел памяти адресов первой входящей ветви узлов сети, узел памяти адресов выходящих ветвей узлов сети, узел памяти адресов входящих ветвей узлов сети, регистр адреса выходящей ветви, регистр адреса входящей ветви, узлы памяти адресов начальных и конечных узлов ветвей сети, регистры адреса конечного узла ветви и конечного узла сети, первый и второй триггеры, первый и второй дешифраторы, блок сравнения кодов, две линии задержки, семь элементов ИЛИ, шесть элементов И и элемент НЕ, выходы регистров адреса выходящей и входящей ветвей соединены с адресными входами соответственно узла памяти адресов выходящих ветвей узлов сети и узла памяти адресов

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

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

И соединен с входом первого дешифратора, выход которого подключен к нулевому входу второго триггера и первому входу пятого элемента ИЛИ, второй вход которого соединен с выходом элемента НЕ и первым входом шестого элемента ИЛИ, выход пятого элемента

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

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

1951

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

И, второй элемент И, элемент ИЛИ, элементы задержки, блок моделей ветвей содержит П моделей ветвей, где

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

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

1161951 задержки подключен к первому входу второго триггера, второй вход которого соединен с выходом двоичного счетчика, выходы второго и четвертого элементов И подключены соответственно к разрядным входам двоичного счетчика, второй выход второго триггера соединен с первым входом шестого элемента И модели ветви, выход пятого элемента ИЛИ блока формирования топологии и выходы двоичных счет. чиков всех моделей ветвей подключены к входам первого элемента ИЛИ узла поиска моделей ветвей, выход которого соединен с вторыми входами пятого и шестого элементов И первой модели ветви блока моделей ветвей, выход шестого элемента И. j-й модели ветви, где j=1,..., (n-1), блока моделей ветвей подключен к входу поиска прерывания (1+1)-й модели ветви, выходы пятых элементов И всех моделей ветвей соединены с входами второго элемента ИЛИ узла поиска моделей ветвей, выходы элементов ИЛИ всех моделей ветвей подключены к входам шифратора адреса узла поиска моделей ветвей, выход первого элемента И -й модели ветви соединен с вторыми входами первого и третьего элементов И (1+1)-й модели ветви блока моделей ветвей, выход узла памяти длительностей ветвей блока управления подключен к вто" рому входу четвертого элемента И каждой модели ветви блока модеЛей ветвей, выход шифратора адреса узла поиска моделей ветвей блока моделей ветвей .соединен с адресным входом узла памяти номеров моделируемых вет- . вей блока управления, выход которого подключен к первому входу элемента

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

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

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

1 116195

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

Цель изобретения — повышение коэф-1О фициента полезного использования оборудования.

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

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

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

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

Блок 1 управления содержит узел 5 памяти длительностей ветвей, узел 6 памяти номеров моделируемых ветвей, узел 7 памяти меток свершения ветвей, узел 8 измерения длиннейшего пути, триггер 9 прерывания, первый элемент

И 10 и второй элемент И 11, элемент

ИЛИ 12, линии 13, 14 и 15 задержки.

Выход 16 номера подготавливаемой к моделированию ветви блока 2 форми35 рования топологйи соединен с адресным входом узла 5 памяти и с информационным входом узла 6 памяти. Выход

17 поиска свободной модели ветви блока 2 формирования топологии соединен 4 с входом считывания узла 5 памяти и через линию задержки 13 с входом записи узла 6 памяти блока 1 управления и с входом 18 поиска свободной модели ветви блока 3 моделей ветвей.

Выход 19 номера анализируемой ветви блока 2 формирования топологии соеди. нен через элемент ИЛИ 12 с адресным входом узла 7 памяти блока управления. Выход 20 проверки свершения вет- О ви блока 2 формирования топологии сети соединен с входом считывания узла 7 памяти блока 1 управления..

Выход 2.1 поиска прерывания соединен с входом установки "1" триггера 9 прерывания блока 1 управления и с входом 22 блока 3 моделей ветвей.

Выход 23 индикации результата расчета блока 2 формирования топологии соединен с входом второго элемента

И 11 блока 1 управления. Выход 24 номера модели ветви блока 3 моделей ветвей соединен с адресным входом узла 6 памяти блока 1 управления.

Выход 25 прерывания блока 3 моделей ветвей соединен с входом считывания узла 6 памяти, входом установки "0" триггера 9 прерывания и входом линии

14 задержки блока 1 управления °

Выход номера анализируемой ветви сети. узла 6 памяти блока 1 управления соединен с входом 26 блока 2 фор.

I мирования топологии. Выход свершения ветви узла 7 памяти блока 1 управления соединен с входом 27 блока 2 формирования топологии. Выход начала анализа свершения ветви сети линии

15 задержки блока 1 управления соединен с входом 28 блока 2 формирования топологии. Выход кода длительности ветви узла памяти блока 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 моделей ветвей предназначен для органиэации процесса вре51

3 . 11619 менного моделирования длительностей ветвей сети. Генератор 4 импульсов / предназначен для формирования. серий 1 импульсов ГИ1 и ГИ2, сдвинутых .относительно друг друга. 5

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

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

Триггер 9 прерывания предназначен 36 для организации временного разделения между процессом временного моделирования длительностей ветвей сети и процессом анализа топологии модели- руемой сети. 3$

Первый и второй элементы И 1О и 11 предназначены соответственно для организации временного разделения процесса решения и для выдачи полученно- го результата после завершения про-,Е цесса моделирования сети. Линии 13

14 и 15 зацержки предназначены для предотвращения "гонок" при работе устройства.

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

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

44 адреса входящей ветви, регистр 45 адреса конечного узла ветви, регистр, /

46 конечного узла сети, триггеры é7 и 48, дешифраторы 49 и 50, дешифратор 51 сравнения кодов, линии 52 и

53 задержки, элементы ИЛИ 54-60, элементы И 61-66, элемент НЕ 67.

Входами блока являются полюсы 34 и 35, соединенные соответственно с входом считывания и адресным входом узла 37 памяти начального узла. Вход

26 номера анализируемой ветви сети блока 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 памяти — для хранения по адресу номера узла номера ветви, первой as списка ветвей, выходящих из данного узла; узел 42 памяти - для хранения по адресу номера узла номера ветви, первой из списка ветвей, входящих в данный узел; узел 39 памяти - для хранения в виде списков номеров ветвей, выходящих as узлов сети, а узел 40 памяти - для хранения в виде списков номеров ветвей, входящих в узлы сети).

Регистр 43 адреса выходящей ветви и регистр 44 адреса входящей ветви в блоке 2 формирования топологии г

1161951 представляют собой регистры с параллельным приемом информации.

Регистр 43 предназначен для промежуточного хранения номера ветви при определении ветвей, выходящих из 5 узла, а регистр 44 — для промежуточного хранения адресов (номеров) ветвей, входящих в узел. Регистры 45 и 46 выполнены аналогичным образом и предназначены для хранения адреса 1О рассматриваемого узла сети и для постоянного хранения адреса конечного узла сети.

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

Дешифраторы 49 и 50 состояния Х предназначены для сравнения поступающих на них кодов с кодовой комбина« цией состояния Х, заданного постоян- 20 но в схеме.

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

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

Входы.29(1),29(2),..., 29(л) кода дли -4р тельности ветви соединены с входами элементов И 77(1),77(2),..., 77(п).

Входы 30(1), 30(2),..., 30(Л) измерительной серии импульсов соединены с входами элементов И 78(1), 78(2),..., 45

78(л) узла 68 моделей ветвей. Вход 18(1) поиска свободной моцели ветви соединен с входами элементов И 75(1) и

76(1) первой модели 68(1) ветви. Выход элемента И 75(1) первой модели SO

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(n) ветвей соединены с входами элементов И 73(1), 73(2),..., 73(п) и 74(1), 74(2),...,74(n). Выход элемента И 73(1) первой модели 68(1) ветви соединен с входом (2,1) поиска прерывания второй модели 68(2) ветви, выход элемента И 73(2) второй модели

68(2) ветви соединен с входом (3,1) поиска прерывания третьей модели 68(3) ветви и т.д. до п-й модели ветви. Выходы (1,2), (2,2), ...,(n 2)переполнения формирователей 70 (1), 70 (2),..., 70 (n ) временных интервалов моделей 68(1),68(2), ..., 68(п)ветвей соединены с входами элемент ИЛИ 83 узла 69 поиска моделей ветвей.

Выходы (1,4), (2,4),..., (n, 4) сигналов прерывания с выходов элементов И

74(1), 74(2),...,74(n) моделей 68(1), 68(2), 68(n) ветвей соединены с входами элемента ИЛИ 84 ° Выходы .(1,3), (2,3),...,(n,3) кода моделей ветвей с выходов элементов ИЛИ 79(1), 79(2),.,79(n) модеЛей 68(1), 68(2),..., 68(п)ветвей соединены с входами элемента ИЛИ 84,Выходы (1,3), (2,3),...,(n.3) кода моделей ветвей с выходов элементов HJIH 79(1), 79(2),...,79(n) моделей 68(1}, 68(2),...,68(n) ветвей:соединены с входами шифратора 82 адреса узла 69 поиска моделей ветвей. Выход 25 прерывания блока 3 моделей ветвей соединен с выходом элемента ИЛИ 84 узла

69 поиска моделей ветвей. Выход 24 номера модели ветви соединен с выходом шифратора 82 адреса узла 69 поиска модели ветви.

Формирователи 70(1), 70(2)...,, 70(n) временного интервала моделей

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

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

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

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

46 конечного узла сети заносится код номера конечного узла сети. Триггеры 9, 47, 48, 71(1), 71(2),...,71(й),!5

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

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

В некоторый момент времени сигнал

"Пуск", поступающий на полюс 34, проходит через элемент ИЛИ 60 и устанав-10 ливает триггер 48 в единичное состояние. Единичное состояние триггера

48 разрешает прохождение серии импульсов ГИ1 (полюс 31) и ГИ2 (полюс

32) соответственно через элементы

И 65 и 66. Кроме того, сигнал "Пуск" поступает на вход элемента 52 задержки и на вход считывания узла $7 памяти начальных узлов. При поступлении сигнала разрешения выборки в 40 узле 37 памяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 35. Так как.ветвь выбрана как выходящая as начального узла сети, то на выходе узла 37 памяти появляется код начального узла сети, который поступает через элемент ИЛИ 55 на адресный вход узла 41 памяти первой выходящей ветви. Через время задержки, достаточное для считывания информации из узла 37 памяти, сигнал "Пуск" появляется на выходе элемента 52 задержки и поступает через элемент

ИЛИ 54 на вход считывания узла 41 памяти. Сигнал выборки по адресу начального узла позволяет сосчитать из узла 41 памяти код номера ветви, 1 8 являющейся первой в списке ветвей, выходящих из начального узла сети.

Код первой выходящей ветви с выхода узла 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 кода длительности код длительности ветви, который через эле9 1161 мент И 77(1) заносится в качестве исходной информации в формирователь 70 временного интервала. С выхода шифратора 82 адреса полученный по сигналу с полюса (1,3) код адреса модели вет- ви поступает на адресный вход узла

6 памяти номеров моделируемых ветвей блока управления. Через время, достаточное для организации описанных процессов в блоке 3 моделей ветвей, на выходе элемента 13 задержки блока 1 управления появляется сигнал, поступающий на вход записи узла 6 памяти номеров моделируемых ветвей.

Сигнал записи позволяет записать по адресу номера выбранной модели ветви (в данном случае первой) номер ветви, длительность которой внесена уже в формирователь 70(2) временного интервала данной модели ветви. На этом 20 заканчивается подготовка первой выхо. дящей из узла ветви к процессу временного моделирования длительности.

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

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

43 код поступает вновь на адресный вход узла 37 памяти, а также через полюс 16 яа адресный вход узла 5 памяти и информационный вход узла 6 памяти. С приходом второго импульса

ГИ2 из узла 5 памяти длительностей считывается длительность второй ис- .у ходящей из узла ветви и поступает череэ полюс 29 на входы элементов

И 77(1), 77(2), ° .,77(n) всех моделей ветвей блока 3 моДелей ветвей.

Одновременно через полюс 18(1) на у входы элементов 75(1) и 76(1) поступает сигнал поиска свободной модели ветви. Так как триггер 7 1(1) первой

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

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

39 памяти будет считан код Х, который записывается в регистр 43. В этом случае, так как выход регистра

43-подключен к дешифратору 49 состояния Х, в комбинационной схеме путем сравнения кодов будет определена информация о конце списка, записанная в регистре 43 блока 2 формирования топологии. Дешифратор 49 вырабатывает на выходе сигнал, который поступает на нулевой. вход триггера 48, сбрасывает его в нулевое состояние, кроме того, сигнал с выхода дешифратора поступает на полюс 21. С полюса 2 1 сигнал (поиска прерывания) поступает на единичный вход триггера прерывания и устанавливает его в единичное состояние, одновременно сигнал поиска прерывания поступает в блок 3 моделей ветвей. Так как выполняется моделирование длительностей ветвей, выходящих из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер 9 прерывания остается в единичном состоянии и на счетный вход узла 8 измере11619 ния длиннейшего тути и через полюс

30 во все формирователи 70 временного интервала моделей ветвей, триггеры

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

Сигналы с выхода формирователей

70(1),70(2),...,70(п) временного интервала поступают на единичные входы триггеров 72(1), 72(2),..., 72(n) и устанавливают триггеры в единичное состояние. Одновременно сигнал с выхода формирователя 70 поступает через элемент ИЛИ 83 на вход поиска прерывания (1,1) первой модели ветви и в случае, если триггер 72(1) нахо- 20 дится в единичном состоянии, сигнал прерывания с выхода элемента 74(1) поступает через элемент ИЛИ 84 через полюс 25 в блок управления .1, устанавливает триггер 71(1) в нулевое состояние, что означает освобождение модели ветви для последующих вычислений. Одновременно этот же сигнал через элемент 80 задержки сбрасывает триггер 72(1) в нулевое состояние и 30 выдает с полюса (1,3) сигнал на вход шифратора 82 адреса, по которому фор. мируется номер данной модели ветви, который через полюс 24 поступает в блок 1 управления. Номер модели вет- З5 ви с полюса 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей. При получении с полюса 25 сигнала прерывания, который поступает на вход считывания узла 6 памяти номеров моделируемых ветвей, считывается по адресу номера модели ветви номер ветви сети, который поступает через элемент ИЛИ 12 на адресный вход узла памяти меток свершения ветвей. Через время, достаточное для считывания номера ветви, на вход записи через элемент 14 задержки поступает сигнал прерывания, по адресу номера ветви в узел 7 памяти у меток свершения ветвей записывается метка "1", характеризующая сверше ние процесса моделирования длительности данной ветви. Через время, достаточное для записи метки, с вы- у хода элемента 15 задержки сигнал прерывания поступает через полюс 28 в блок 2 формирования топологии. Че51 г рез полюс 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 поступает с выхода элемента 64 на вход считывания узла 40 памяти блока формирования топологии и через полюс 20 на вход считывания узла 7 памяти меток свершения ветвей блока

1161951

14.

13.

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

21 поиска прерывания. Наличие нулевого сигнала метки свершения ветви l5 означает, что хотя бы одна из ветвей списка, входящих в узел, не завершила процесс временного моделирования своей длительности и, следовательйо, в данном узле не сформирована функ- 2р ция и для всех входящих в него ветвей. Тогда сигнал с полюса 27 поступает на единичный вход триггера 9 прерывания и одновременно через полюс 22 на вход элемента ИЛИ 83 узла 25

69 поиска моделей ветвей блока 3 моделей ветвей, С выхода элемента

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

ИЛИ 83 выдаст сигнал прерывания.

Блок 1 управления, получив номер мо" дели ветви и сигнал прерывания, повторит все описанные операции, связанные с анализом свершения ветви.

Если же в блоке 3 моделей ветвей не имется моделей, имеющих триггеры 72 в единичном состоянии, то процесс анализа проводиться не будет и импульсы серии ГИ1 через элемент у»

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

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

40 памяти будет считан .код номера второй ветви в списке, который поступает через элемент ИЛИ 58 на информационные входы регистра 44 и записывается в него с приходом второго импульса ГИ1 с выхода элемента И 63.

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

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

50 состояний Х, который путем сравнения кодов вырабатывает сигнал конца списка. Полученный сигнал проходит через элементы ИЛИ 59 и 60 и устанавливает триггеры 47 и 48 соответственно в нулевое и единичное состояния. Сигнал с выхода дешифратора

50 поступает также на вход элемента И 62, второй вход которого связан с выходом дешифратора 51 сравнения кодов. Дешифратор 51 сравнивает коды, хранящиеся в регистре 46 конечного узла сети и в регистре 45 конечного узла. Как указывалось ранее,регистр 46 хранит код конечного узла сети, а регистр 45 — код рассматриваемого узла сети, сформировавшего функцию коньюнкции в данный момент времени, Если значения этих кодов совпадают (сформирована логическая функция коньюнкции для конечного узла сети), то дешифратор 51 сравнения кодов выдает разрешение на прохождение сигнала конца списка с выхода дешифратора 50 состояния через элемент И 62 на выходной полюс 23 блока

2 формирования топологии, что соот16

1161951

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

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

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

1161951.ты|я о

i 161951

Составитель И.Дубинина

Редактор М.Петрова Техред М.Кузьма Корректор И.Эрдейи

Заказ 3970/51 Тираж 710 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4