Вычислительное устройство для формирования маршрута сообщения

(Ю 01) 0611 2 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ А ЙПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМ,Ф СВ ЯБ.АЦ у;,"д(21) 3470757/18-24 ния быстродействия и сокращения обору- (22) 15,07.82 давания, оно содержит регистр ввода и (46) 23. 10.83 Бюл, Ю 39блок сравнения и двоичных чисвп, ин(72) В. С. Любинский и В. П. Синя- формационные входы которого соединевин . ны соответственно с выходами ком (53) 681 325.22(088.8) мутатора, тактовыйи управляющий (56) 1. Клейнрок Л. Вычислительные входы подключены соответственно к системы с очередями. Н., "Мир,1979, выходу генератора тактовых импульсов с. 470-473. и к входу установки исходного состо 2, Авторское свидетельство СССР яния устройства выходы блока сравпо заявке 1 г 3241464/18-24 , нения и двоичных чисел соединены сокл. 6 06 Г 15/20, 1980 (прототип). : ответственно с первыми входами элемен. трв И групп, вторые входы которых (54)(57) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО подключены к информационному выходу ДЛЯ ФОРИИРОВАНИЯ МАРШРУТА СООБЩЕ- регистра ввода, адресный выход кото- НИЯ содержащее генератор тактовых . рого соединен с адресным входом ком" "с УМ импульсов, группы элементов И, блок мутатора, выходы групп элементов И буферных регистров и коммутатор, соединены соответственно с входами группа информационных входов которо- . блока буферных регистров, выходы го является группой информационных которого являются выходами устройствходов устройства, о т л и ч а ю- ва, вход регистра ввода является щ е е с я тем, что, с целью повыве" информационным входом устройства. Е1 1049Изобретение относится к вычислительной технике и предназначено для применения в устройствах коммутации сообщений и пакетов в сетях электронных вычислительных машин (ЗВИ).Известно устройство для формиро вания кода маршрута в цифровой сети связи, включающее мини-ЗВИ Я .Недостатками устройства являются высокая стоимост,ь, сложность и 10 сравнительно низкая надежность.Наиболее бпизким к изобретению по технической сущности является устройство для формирования маршрута сообщения, содержащее генератор 15 тактовых импульсов, группу элементов И, блок буферных регистров, ком,мутатор, группа информационных входов которого соединена с входными шинами устройства, а его выходыс группой входных шин блока сравнения, первый вход которого соединен с выходом генератора тактовых импульсов, а его второй вход - с управляющей шиной устройства 1 2.25Недостатками известного устройства являются сравнительно высокие аппаратурные затраты на его реализацию и низкое быстродействие, обусловленное необходимостью формирования таблицы маршрутов. Таблица маршрутов имеет число строк на единицу меньше числа узлов в цифровой сети связи, Число групп элементов И и блоков сравнения должно быть равно числу узлов назначения в сети, формирование таблицы маршрутов в указанном устройстве осуществляется последовательно путем опроса, сравнения и записи в регистре величин задержек,40 поступающих от соседних узлов, Это требует значительных затрат времени.Цель изобретения - повышение быстродействия и сокращение оборудования,Поставленная цель достигается тем, 45 что вычислительное устройство, содержащее генератор тактовых импульсов, группы элементов И, блок буферных регистров и коммутатор, группа информационных входов которого является груп 50 пой информационных входов устройства, содержит регистр ввода и блок сравнения и двоичных чисел, информационные входы которого соединены соответственно с выходами коммутатора, такто вый и управляющий входы подключены соответственно к выходу генератора тактовых.импульсов и к входу установки ис 917 1ходного состояния устройства., выходыблока сравнения и двоичных чисел соединены соответственно с первыми входами элементов И групп, вторые входыкоторых подключены к информационномувыходу регистра ввода, адресный выходкоторого соединен с адресным входом коммутатора, выходы групп элементов Исоединены соответственно с входами блока буферных регистров, выходйкоторого являются выходами устройства,вход регистра ввода является информационным входом устройства.На фиг. 1 представлена блок-схемапредлагаемого устройства; на фиг. 2схема блока сравнения и двоичных чисел; на фиг.3 - схема коммутатора;нафиг. 4 - пример. процедуры выбора маршрута для пояснения работы устройства.Устройство содержит регистр 1 вво- да, блок 2 буферных регистров, группы элементов И 3, блок 4 сравненияи двоичных чисел, коммутатор 5, генератор 6 тактовых импульсов, информационный вход 7 устройства, вход 8установки исходного состояния устройства, выходы 9 устройства, группу информационных входов 10 устройства,входы-выходы 11-14 блоков устройства, регистры 154, 15215 ь, сдвигающий регистр 16, регистр 17 результата, элементы И 18,18218 п,элементы ИЛИ 194, 19 19 п , элемент 20 задержки, накапливающийсумматор 21, триггер 22 знака, элементы И 23, 244,242 24 п, группыэлементов И 254, 25, .25 п, 26,1, 26,,37 щ задержек, группы элементовИ 384 382,, 38 у, группы эле-.ментов ИЛИ 39,Устройство работает следующим образом,Сообщение по входу 7 поступает врегистр 1, Одновременно с этим навход 8 подается управляющий импульс,готовящий блок 4 к работе. Адресузла назначения принятого сообщения поступает в коммутатор 5, Вовходных регистрах коммутатора 5 хранятся вепичины задержек по всем возможнь 1 м маршрутам для сообщения спроизвольным адресом. Эти задержки пе917. 4Если второе двоичное число окажется больше или равно первому числу, тоединица из сдвигающего регистра 16 врегистр 17 результата не перезапишется еТактовый импульс после окончаниясравнения поступает также через элемент 30 задержки на шину сдвига сдвигающего регистра 16, обеспечивая сдвигединицы на один разряд, и через элемент ИЛИ 31 на вход сброса накапливающего сумматора 21, который устанавливается в нулевое состояние.Во втором и последующих тактах сравнения первым в. накапливающий сумматор21 записывается наименьшее число впрямом коде, выбранное в предыдущихтактах, Номер этого числа определяется положением единицы в регистре 17,Вторым числом в обратном коде в каждом такте сравнения записываются внакапливающий сумматор 21 очередныесравниваемые числа. После каждого такта сравнения единица в сдвигающем регистре 16 сдвигается на один разрядв сторону старших разрядов. Йерепицывается эта единица в соответствующийтриггер регистра 17 результата, еслив очередном такте сравнения второе число оказывается меньше первого.Приэтом все другие триггеры регистра17 результата устанавливаются в нулевое состояние сигналом, поступающим, через элементы ИЛИ 19 на нулевые входы этих триггеров,3 109риодически обновляются вутем опросасоседних узлов (входы 10). На,выходахкоммутатора 5 появляются величинызадержек по всем, возможным маршрутам следования для сообщения с за,двнным адресом. Эти задержки поступают на блок М. После сравнения задержек на одном иэ выходов блокапоявляется импульс, который, поступаяна одну из групп элементов И 3, разрешает прохождение сообщения из регистра 1 в буферный регистр, откудаоно передается на соседний узел.Следуя через выбранный соседний узелк узлу назначения; сообщение име- . 15ет минимальную задержку в пути.Блок сравнения работает следующимобразом,Исходное состояние устанавливает-.ся путем подачи на вход 8 установоч Оного. импульса, по которому в единичное состояние устанавливаются триггеры младших разрядов сдвигающего регистра 16, регистра 17 результата итриггер 3 ч управления. Счетчик 33 25и накапливающий сумматор 21 с тригге"ром 22 знака устанавливаются в нуле-вое состояние,Первый тактовый импульс через элемент И 35, открытый единичным потен- зоциалом с триггера управления, и эле-.мент И 21, который открыт единичнымпотенциалом с триггера младшего разряда регистра 17 результата, подаетсянд Входы группы элементов И 25 Пер З 5вое число в прямом коде из регистра15 записывается в накапливающий сумматор 2 Этот же импульс, задержан-ный элементом 20 задержки, подаетсяна элементы И 27, 27 д27 яЕди" 40ничным потенциалом с триггера младшего разряда сдвигающего регистра 16элемент И 27 открывается, сигнал сего выхода поступает на входы группыэлементов И 26 , и второе число из 45регистра 15 записывается в накапливающий сумматор 21 в обратном кодеЕсли второе двоичное число окажется меньше первого числа, то триггер 22 знака - в нулевом состоянии,поэтому тактовый импульс, задержанныйэлементами 20 и 29 на время выполнения суммирования, поступает черезэлементы И 23 и 284 на триггер регистра .17 результата, и единичноезначение из сдвигающего регистра 16перезаписывается в соответствующийтриггер регистра 17 результата.После подачи всех тактовых импульсов цикл сравнения чисел заканчивается. В результате один из триггеров регистра 17 результата находится в единичном состоянии,номер этого триггера соответствует номеру регистра, в котором записано минимальное число. После поступления последнего тактового импульса на выходе счет- цика 33 появляется импульс, который переводит триггер управления в нулевое состояние,. запрещая прохождение тактовых импульсов через элемент И 35, и через один из открытых элементов И 18 поступает на выход блока М.Коммутатор работает следующим ооразом. Двоичные числа задержек от соседних узлов для всех узлов назначения поступают на группы регистров 37,372 37 я по входам 1 О путем периодического опроса этих узлов (щ - число узлов назначения).10199 25 5При наличии на входе 11 адресаузла назначения на одном иэ выходовдешифратора 36 появляется высокийпотенциал, и информация о задержкахдля. данного узла назначения через 5группы элементов И 38 и группы эле ментов ИЛИ 39 передается на выход 9,В качестве примера, поясняющего.процедуру выбора маршрута передачи с минимальными задержками, рас Осмотрим процедуру выбора маршрутадля гипотетической цифровой сети,представленной на фиг,М.Для выбора маршрута с минимальной задержкой на узле-отправителе 15необходимо иметь информацию о задержках от соседних узлов, Для этогоформируется таблица задержек узлаПосле опроса всех соседних узлов таблица хранится в регистрах 37 коммутатора 5.Допустим, что нужно передать сообщение иэ узла 1 в узел Ч 1. Дляэтого на дешифратор 36 подаетсякод адреса узла Ч 1, и двоицныечисла задержек 0010, 0011, 0100поступают на блок ч. После сравнениячисел появляется импульс на выходе,соответствующем соседнему узлу П,исообщение передается в указанный узел,зОгде вновь определяется маршрут сминимальной задержкой , и т.д.В данном примере для передачисообщения иэ узла 1 в узел Ч 1 маршрут с минимальной задержкой проходит через узел П, хотя кратчайшиймаршрут - через узел 1 Ч,Предлагаемое устройство позволяетснизить аппаратурные затраты и повысить быстродействие при решении за- О 17дачи вычисления маршрута с минимальной задержкой в пути.В известном устройстве формировение маршрута кратчайшего пути в цифровой сети связи осуществляется на основе данных, хранимых в регистрах в виде таблицы маршрутов. Таблица маршрутов имеет (М) строк, где М- общее число узлов в цифровой сети связи. Число групп элементов И и блоков сравнения также равно цислу узлов назначения в сети.В.предлагаемом устройстве вместо группы блоков сравнения, содержащей (М) блоков, используется один блок сравнения и двоичных чисел, где и - число соседних узлов.Число буферных регистров и групп элементов И равно не (М), как в известном устройстве, а и. Так как в любой цифровой сети связи (М)и, то изобретение обеспечивает сокращение объема оборудования при решении такого же объема задач, как и в известном устройстве.Предлагаемое устройство по сравнению с. известным является более быстродействующим, так как в известном устройстве формирование таблицы маршрутов осуществляется последовательно путем опроса, сравнения и записи в регистре величин задержек, поступающих от соседних узлов, в в предлагаемом устройстве величины задержек хранятся в регистрах коммутатора и эти задержки одновременно поступают на блок сравнения, который обеспечивает выбор маршрута из всех возможных маршрутов для сообщения с заданным адресом.1049917 А.Повхюю е 5 ееееаее ееаа ееее ктная,П "Патент фили жгород, ул. Редактор О.ееееЗакаэ 8427/ВНИИ итель В.ВертлибА.Бабинец Корреюю е1706 Подпинного комитета СССРобретений и открытий35, Раушская наб., д. Составгир ТехредеееееееюТиражГосударствепо дФлам из