Вычислительное устройство для формирования маршрута сообщения Советский патент 1983 года по МПК G06F15/173 

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

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

1. ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБЩЕНИЯ, содержащее блок управления, генератор тактовых импульсов, счетчик, группу элементов И, группу блоков сравнения, первый коммутатор, группу регистров адресов, выходы которых являются выходами устройства, информационныйВХОД каждого;регистра адресов подклю(ен к выходу соответствующего элемента И группы, информационные входы элементов . И группы подключены к группе входов блока управления и к группе выходов счетчика, тактовый вход которого соединен с выходом генератора тактовых импульсов, первый и второй выходы блока управления подключены к управляющим входам генератора тактовых импульсов и счетчика соответственно, третий выход блока управления подключен к управляющему входу первого коммутатора, первая группа информационных входов которого является первой группой входов устройства, вторая группа информационных входов первого коммутатора соединена с группой выходов счетчика, каждый выход группы выходов первого коммутатора подключен к первому входу соответствующего блока сравнения группы, второй и третий входы каждого блока сравнения группы подключены соответственно к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока сравнения группы подключены к управляющим входам соответствующих элементов И и регистров адресов, отличающееся тем, что, с целью повышения точности, в него введен . второй коммутатор, управляющий вход которого соединен с шестым выходом блока управления, выход второго коммутатора соединен с четвертыми входами блоков сравнения группы, первая . группа информационных входов второго коммутатора является второй груп(Л пой входов устройства, вторая группа информационных входов соединена с группой выходов счетчика, управляющий вход блока управления является управляющим входом устройства. 2. Устройство по п. 1, отли00 чающееся тем, что блок упч IND равления содержит элементы И, ИЛИ, НЕ, формирователь прямоугольных има пульсов, триггер, элементы задержки и дешифратор, группа входов которосо го является группой входов блока управления, выходы дешифратора, начиная с первого, подключены соответст-. венно к входам первого элемента ИЛИ, первый выход дешифратора соединен с первым входам первого элемента И и с входом элемента НЕ, выход которого соединен с первым входом второго элемента И, выход которого подключен к первому входу второго элемента ИЛИ, второй вход которого является

Изобретение относится к вычислительной технике и может использоват ся для сбора и обработки данных, в частности, в устройствах коммутации сообщений и пакетов в сетях электро ных оымислительных машин (ЭВМ). Известно устройство, содержащее генератор тактовых импульсов, счетчики, два регистра кода адреса, эле менты И и ИЛИ, регистр числа узлов сети, блок сравнения, регистр кода отказавшегося узл, элемент НЕ, регистр порядка перечисления узла сети, два циклических регистра сдвига 1 , Недостатком этого устройства является низкая эффективность, кото рая обуславливается формированием маршрута с минимальным числом межуз ловых связей между узлом отправлени и узлом назначения, что не исключает больших временных задержек в про межуточных узлах сети. Наиболее близким к изобретению по технической сущности является ус ройство, содержащее блок управления генератор тактовых импульсов, счетчик, группу элементов И, группу бло ков сравнения, первый коммутатор, группу регистров адресов соседних узлов, выходы которых являются выходом устройства, информационный вход каждого регистра группы подклю чен к выходу соответствующего элемента И группы, информационные входы всех элементов И группы объединены и подключены к группе входов блока управления, выходам счетчика, тактовый вход которого соединен с выходом генератора тактовых импульсо первый и второй выходы блока управления подключены к управляющим входа генератора тактовых импульсов и счетчика соответственно, третий выход блока управления подключен к управляющему входу первого коммутатора, первая группа информационных входов которого является первой группой входов устройства, вторая группа информационных входов первого коммутатора соединена с выходами счетчика, каждый выход группы входов первого коммутатора подключен к первому входу соответствующего блока сравнения группы, второй и третий входы каждого блокаосравнения группы объединены и. подключены к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока сравнения группы подключены к управляющим входам соответствующих элементов И и регистров адресов соседних узлов f2 . Недостатком известного устройства является его низкая точность, которая обуславливается тем, что при выборе маршрута не учитывается время, необходимое на передачу сообщения из узла отправления на соседний узел, а также время ожидания в очереди . Целью изобретения является повышение точности. Поставленная цель достигается тем, что в вычислительное устройство для формирования маршрута сообщения, содержащее блок управления, генератор тактовых импульсов, счетчик, группу элементов И, группу блоков сравнения, первый коммутатор, группу регистров адресов, выходы которых являются выходами устройства, информационный вход каждого регистра адресов подключен к выходу соответству1ющего элемента И группы, информацион ные входы элементов И группы подклочены к группе входов блока управления и к группе выходов счетчика, так товый вход которого соединен с выходом генератора тактовых импульсов, первый и второй выходы блока упрдвления подключены к управляющим входам генератора тактовых импульсов и счетчика соответственно, третий выход блока управления подключен к управляющему входу первого коммутатора, первая группа информацион ных входов которого является первой группой входов устройства, вторая группа |;1Нформационных входов первого коммутатора соединена с группой выходов счетчика, каждый выход груп пы выходов первого коммутатора подключен к первому входу соответствую щего блока сравнения группы, второй и третий входы каждого лока сравнения группы подключены соответ ственно к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока сравнения группы подключены к управляющим вхо дам соответствующих элементов И и регистров адресов, введен второй коммутатор управляющий вход которого соединен с шестым выходом блока управления, выход второго коммутатора соединен с четвертыми входами блоков сравнения группы, первая г|эуппа информационных входов второго коммутатора является второй груп пой входов устройства, вторая группа информационных входов соединена с группой выходов счетчика, управляющий вход блока управления является управляющим входом устройства. Кроме того, в вычислительном уст ройстве блок управления содержит эл мент И, ИЛИ, НЕ формирователь прямоугольных импульсов, триггер, элементы задержки и дешифратор, группа входов которого является группой входов блока управления, выходы дешифратора, начиная с первого, подключены соответственно к входам пер вого элемента ИЛИ, первый выход дешифратора соединен с первым входо первого элемента И и с входом элемента НЕ, выход которого соединен с первым входом второго элемента И, выход которого подключен к первому входу второго элемента ИЛИ, второй вход которого является управляющим входом блока, а выход подключен к 4 первому входу триггера, выхйд три1- гера является первым выходом блока, выход первого элемента И является вторым выходом блока, выход первого элемента ИЛИ через формирователь прямоугольных импульсов подключен к входу первого из четырех последовательно, соединенных элементов задержки, к второму входу триггера и к пятому выходу блока, выходы второго и третьего элементов задержки являются соответственно третьим и четBepTbfM выходами блока, выход первого элемента задержки является шестым выходом блока, выход четвертого элемента задержки соединен с вторыми входами пеового и второго элементов И.. На фиг. 1 представлена схема устройства;, на фиг. 2 - схема блока сравнения; на фиг. 3 схема блока управления; на фиг. k - схема первого коммутатора; на фиг, 5 схема второго коммутатора; на фиг. 6 - пример, поясняющий процедуру выбора маршрута передачи. Устройство содержит группу регистров 1 адресов, группу элементов И 2, группу блоков 3 сравнения, генера . тор Ц тактовых импульсов, счетчик 5 блок 6 управления, коммутаторы 7 и 8, шины 9-22 связи, группу элементов И 23, элемент 2 задержки, регистр 25 минимальных задержек, схему 26 сравнения, накапливающий сумматор 27, дешифратор 28, элемент И 29, элемент ИЛИ 30, элемент НЕ 31, элемент И 32, элемент ИЛИ 33 триггер 3, формирователь 35 прямоугольных импульсовi элементы 36-39 задержки, дешифратор JO, группу элементов ИЛИ k 1, группу элементов. И , группу буферных регистров 3, групг па элементов ИЛИ , дешифратор Б, группу элементов И 4б, входные -регистры Й7. Устройство работает следующим образом. Исходное состояние регистров группы 1 и счетчика 5 нулевое. Запуск устройства осуществляется поданей на (входную) шину 22 импульса после приема по шинам 10 информации о задержках от соседних узлов в буферные регистры коммутатора 7. На выходной шине 13 блока 6 управления появляется высокий потенциал, при этом запускается генератор t тактовых импульсов. Тактовые импульсы с генера-. тора поступают на счетчик 5. При совпадении кода на счетчике с кодом адреса соседнего узла генератор k тактовых импульсов отключается и в блоке 6 управления вырабатывается последовательность управляющих импульсов. Первый импульс появляется на шине И и устанавливает выходные регистры накапливающих сумматоров G ков 3 сравнения в нулевое состояние По второму импульсу (шина 15) в дан ные накапливающие сумматоры через коммутатор 8 поступает код задержки равный времени передачи сообщения на данный соседний узел и времени ожидания а .очереди. Длительность ожидания в очереди определяется временем передачи сообщений, стоящих в выходной очереди узла к данно му соседнему узлу. Эта задержка периодически обновляется и хранится во входных регистрах коммутатора 8. Третий импульс управления появляется на шине 17 и разрешает занесение информации о задержках от соседнего узла .для каждого из узлов назначения в накапливающие сумматоры группы блоков 3 сравнения, По четвертому импульсу (шина 1б) происходит сравнение принятых суммарных задержек с задержками, находящимися в регистрах минимальных задержек блоков сравнения, В тех блоках сравнения, где задержка мень ше, осуществляется ее перезапись в регистр минимальных задержек и выра батываются импульсы сброса (шины 20 устанавливающие соответствующие регистры группы 1 в нулевое состояние, и импульсы записи (шины 19) поступающие на элементы И группы 2 и разрешающие запись кода адреса соседнего узла со счетчика 5 в соот ветствующие регистры группы 1, После этого на шине 13 в блоке 6 управления появляется высокий потенциал и запускается генератор тактовых импульсов. При совпадении кода адреса следу ющего соседнего узла с кодом на сче чике 5 .вновь отключается генератор k, в блоке 6 управления вырабатываются импульсы управления, в блоках 3 сравнения происходит сравнени задержек и в соответствующие регист ры 1 записывается код адреса очеред ного соседнего узла, суммарная задержка прохождения сообщения через 696 который для данного узла назначения меньше. Таким образом, в регистрах 1 формируется таблица маршрутов, ,Цикл формирования продолжается до тех пор, пока на выходах счетчика не будет код адреса последнего соседнего узла После этого счетчик 5 обнуляется. Блок 6 управления работает следующим образом. На вход дешифратора 28 поступает двоичное число с выходов счетчика 5. Используются только те выходы дешифратору, которые соответствуют номерам соседних узлов для данного узла сети. Остальные выходы дешифратора 28 с выходами элемента ИЛИ 30 не соединяются. При наличии на входе дешифратора двоичного числа, соответствующего адресу соседнего узла, на одном из выходов появляется разрешающий потенциал, который через элемент ИЛИ 30 поступает на формирователь 35 прямоугольных импульсов. На выходе формирователя 35 появляется импульс, который поступает на вход триггера 3 и переводит его в нулевое состояние, запрещая прохождение тактовых импульсов на счетчик 5. Этот же импульс поступает на выходную шину 14 и через элементы Зб-38 задержки - на шины 15-17. С выхода Элемента 39 задержки импульс поступает на элемент И 32 и, если код адреса соседнего узла не является адресом последнего соседнего узла (низкий потенциал на последнем выходе дешифратора 28), переводит триггер З в единичное состояние, на шине13 вновь формируется высокий потенциал, разрешающий прохождение тактовых импульсов на счетчик 5. Если код адреса является адресом последнего соседнего узла, то высокий потенциал с последнего выхода дешифратора разрешает прохождение импульса управления через элемент И 29 на сброс счетчика 5 и запрещает установку триггера З в единичное состояние. Следующий циКл работы устройства начинается после приема новой ин формации о задержках от соседних узлов по шинам 10 в буферные регистры коммутатора 7, При этом триггер 3 переводится в единичное состояние импульсом, поступающим на его единичный вход через элемент ИЛИ 33 по шине 22, .. Блок сравнения работает следующим .образом. Исходное состо яние регистра 25 перед началом работЪ устройства - ед ничное. Импульсом, поступающим из блока управления по шине , устанавливаются в нулевое состояние реги стры накапливающего сумматора 27. Ин формация о задержках поступает на накапливающий сумматор 27 по шинам 18 и 21. Посяе сложения задержек по импульсу, поступающему по шине 1б, происходит сравнение числа А в выход ном регистре накапливающего сумматора 27 с числом в регистре 25. Так ка для данного такта А 4В (число В все единицы),то на выходе схемы 26 сравнения появляется импульс, который обнуляет регистр 25 и, пройдя через элемент 2 задержки, разрешает перезапись содержимого выходного регистра накапливающего сумматора в регистр 25. В последующие такты работы устрой ства происходит сравнение числа В в регистре 25 с числом А - суммарной задержкой от следующего соседнего уз .ла. Перезапись содержимого выходного регистра накапливающегося суммат ора 27 в регистр минимальных задержек 25 происходит только при выполнении условия А4 В. Коммутатор 7 работает следующим образом. При поступлении на входы дешифратора 0 кода адреса соседнего узла, на соответствующем выходе дешифратора появляется высокий потенциал, который поступает на группы элементов И 42 данного.соседнего узла. По сигналу управления на шине 17 коды задержек из груКпы регистров ЦЗ через группы элементов И 2 и элементов йхи4 41 поступают на шины 2. Коммутатор 8 работает аналогичным образом При наличии на входе дешифратора кода адреса соседнего узла и управляющего сигнала на шине 15 код задержки, равный времени передачи сообщения и времени . ожидайия в очереди, из соответствующего регистра 47 через группу элементов И 46 и группу элементов ИЛИ 4 поступает на выходную шину 18 коммутатора . В качестве примера, поясняющего процедуру выбора маршрута передачи С минимальными задержками, рассмотрим процедуру выбора маршрута для гипотетической цифровой сети (фиг.6). Для выбора маршрута с минимальной задержкой на узле отправителя необходимо иметь суммарную задержку которая складывается из задержки ожидания в очереди и задержки от соседних узлов, которые определяют загруженность узла по данному направлению. На узле отправителя составляется таблица задержек узла после опроса всех соседних узлов и суммирования задержек. ( сосед, узла хозла назнач. flo этой таблице юьЙираЪтся тако маршрут, для которого задержка минимальна, и составляется таблица маршрутов узла Алгоритм формирования таблицы маршрутов в предлагаемом устройстве поясняет следующая .

6

Регистры0001 0010 1010 0100 0010 1111 1111 1111 1111 1111 010 010 010 010 010 при совпадении кода адреса сосед него узла с кодом на счетчике 5 задержки от данногососеднего узла для всех узлов назначения поступают из коммутаторов 7 и 8 в накапливающий сумматор 27 блока 3 сравнения. Суммарная задержка сравнива-. ется с содержимым регистром 25, которые в исходном состоянии находятся в единичном состоянии. Так ка числа на выходах сумматора 27 меньше или равны числам в регистрах 25 (максимальная задержка) , то в реги.стры 1 заносится код адреса данного соседнего узла, а в регистры 25 переписывается суммарная задержка с выхода сумматора. Цикл по1100 27 nil 25 010 1 вторяется для всех соседних узлрв. После опроса и анализа задержек от последнего соседнего узла в регистрах 1 будет сформирована таблица маршрутов. Допустим, нужно передать сообщение из узла № 1 в узел № 6. Сообщение будет передано через узел № 2, хотя кратчайший маршрут проходит через узел № 4. Устройство позволяет вычислять код маршрута движения сообщения -в цифровой сети связи с минимальной задержкой в пути с большей точностью за счет учета времени ожидания в очереди в узле отправления и времени передачи на соседний узел.

Фиг. IS

Фиг.3 1/7

i J

(р:-Ш

{.

4/

I у

il

i

--о

46

$-

44

46

4v

о обо .5

47

47

-o

47

Фяг.б