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

Изобретение относится к вычислительной технике и предназначено для применения в устройствах коммутации сообщений и пакетов в сетях электронных вычислительных машин (ЭВМ). Известно устройство для форм11рования кода маршрута в цифровой сети связи, включающее мини-ЭВМ l. Недостатками устройства являются высокая стоимост.ь, сложность и сравнительно низкая надежность. Наиболее близким к изобретению по технической сущности является устройство для формирования маршрута сообщения, содержащее генератор тактовых импульсов, группу элементов И, блок буферных регистров, ком,мутатор, группа информационных входов которого соединена с входными шинами устройства, а его выходы с группой входных шин блока сравнения , первый вход которого соединен с выходом генератора тактовых импуль сов, а его второй вход - с управляюще шиной устройства 2 . Недостатками известного устройства являются сравнительно высокие аппара турные затраты на его реализацию и низкЬе быстродействие, обусловленноенеобходимостью формирования таблицы маршрутов. Таблица маршрутов имеет число стро на единицу меньше числа узлов в цифровой сети свйзи. Число групп элеменf TOB и и блоков сравнения должно быть равно числу узлов назначения в сети. Формирование таблицы маршрутов в указанном устройстве осу цествляется последовательно путем опроса, сравнения и записи в регистре величин задержек поступающих от соседних узлов. Это требует значительных затрат времени. Цель изобретения - повышение быстродействия и сокращение оборудования Поставленная цель достигается тем что вычислительное устройство, содержащее генератор тактовых импульсов, группы элементов И, блок буферных регистров и коммутатор, группа информационных входов которого является груп пои информационных входов устройства, содержит регистр ввода и блок сравнения п двоичных чисел, информационные входы которого соединены соответственно с выходами коммутатора, тактовый и управляющий входы подключены со ответственно к выходу генератора такт вых :импульсов и к входу установки исходного состояния устройства, выходы блока сравнения п двоичных чисел соединены соответственно с первыми входами элементов И групп, вторые входы которых подключены к информационному выходу регистра ввода, адресный выход которого соединен с адресным входом коммутатора, выходы групп элементов И соединены соответственно с входами блока буферных регистров, выходы которого являются выходами устройства, вход регистра ввода является информационным входом устройства. , На фиг. 1 представлена .блок-схема предлагаемого устройства; на фиг. 2 схема блока сравнения п чисел; на фиг.З схема коммутатора;на фиг. 4 - пример процедуры выбора маршibyfa для пояснения работы устройства. Устройство содержит регистр 1 ввода, блок 2 буферных регистров, группы элементов И 3, блок Ц сравнения п двоичных чисел, коммутатор 5, генератор 6 тактовых импульсов, информационный вход 7 устройства, вход 8 установки исходного состояния устройства, выходы 9 устр.ойства, группу информационных входов 10 устройства, входы-выходы 11-й блоков устройства, регистры 15, 152..--,15ц, сдвигающий регистр 16, регистр 17 результата, элементы И 18, 182,..., 18ц,элементы ИЛИ 19, 19 , элемент 20 задержки, накапливающий сумматор 21, триггер 22 знака, элеwjf i-ii-io I w(-j - 9 I j-ri I I cf опагча , «7JiC2 „енты И 23, 2),2,..., 24, группы элементов И 25-1, 25г,, ,25п. 26, 26 ..., 2бц-1, элементы И 27f, 27, 28, 282, менты 29 и 30 задержки,элемент ИЛИ 31, элемент 32 задержки,счетчик 33,триггер З управления,элемент И35 дешифратор 36, группы регистров 37,37, .;.,37т задержек, группы элементов И 38, 38,..., 38fyj ,. группы элементов ИЛИ 39. I Устройство работает следующим образом. Сообщение по входу 7 поступает в регистр 1. Одновременно с этим на вход 8 подается управляющий импульс, готовящий блок 4 к работв. Адрес узла назначения п0инятого сообщения поступает в коммутатор 5. Во входных регистрах коммутатора 5 хранятся величины задержек по всем возможнь м маршрутам для сообщения с произвольным адресом. Эти задержки пе3риодически обновляются путем опроса соседних узлов (входы 10). На выхода коммутатора 5 появляются величины задержек по всем, возможным маршрутам следования для сообщения с за,данным адресом. Эти задержки поступают на блок i. После сравнения задержек на одном из выходов блока появляется импульс, который, поступа на одну из групп элементов И 3, разрешает прохождение сообщения из реги стра 1 в буферный 1регистр, откуда оно передается на соседний узел.Следуя через выбранный соседний узел к узлу назначения; сообщение имеет минимальную задержку в пути. Блок сравнения работает следующим образом. Исходное состояние устанавливается путем подачи на вход 8 установочного импульса, по которому в еди ничное состояние устанавливаются три геры младших разрядов сдвигающего ре гистра 16, регистра 1 результата и триггер З управления. Счетчик 33 и накапливающий сумматор 21 с тригге ром 22 знака устанавливаются в нулевое состояние. Первый тактовый импульс через эле мент И 35, открытый единичным потенциалом с триггера управления, и элемент И , который открыт единичным потенциалом с триггера младшего разр да регистра 17 результата, подается на входы группы элементов . Пер вое число в прямом коде из регистра 15 записывается в накапливающий с-ум матор 21.чЭтот же импульс, задержанный элементом 20 задержки, подается на элементы И 27, 27г2,... ,27 -1-Единичным потенциалом с триггера младше го разряда сдвигающего регистра 16 элемент И 27 открывается, сигнал с его выхода поступает на входы группы элементов И 26i , и второе число из регистра 1 S-j записывается в накапливающий сумматор 21 в обратном коде) I . . Если второе двоичное число окажется меньше первого числа, то триггер 22 знака - в нулевом состоянии, поэтому тактовый импульс, задержанны элементами 20 и 29 на время выполне ния суммирования, поступает через элементы И 23 и 28| на триггер регистра 17 результата, и единичное значение из сдвигающего регистра 16 перезаписывается в соответствующий триггер регистра 17 результата. П Если второе двоичное число окажется больше или равно первому числу, то единица из сдвигающего регистра 16 регистр 17 результата не перезапишется. Тактовый импульс после окончания сравнения поступает также через элемент 30 задержки на шину сдвига сдвигающего регистра 16, обеспечнвая сдвиг единицы на один разряд и через элемент ИЛИ 31 на вход сброса накапливающего сумматора 21, который устанавливается в нулевое состряние. Во втором и последующих тактах сравнения первым в накапливающий сумматор 21 записывается наименьшее число в прямом коде, выбранное в предыдущих тактах. Номер этого числа определяется положейием единицы в регистре 17. Вторым числом в обратном коде в каждом такте сравнения записываются в накапливающий сумматор 21 очередные сравниваемые числа. После каждого такта сравнения единица в сдвигающем регистре 16 сдвигается на один разряд , в сторону старших разрядов. Переписывается эта единица в соответствующий триггер регистра 17 результата, если в очередном такте сравнения второе число оказывается меньше первого.При этом все другие триггеры регистра 17 результата устанавливаются в нулевое состряние сигналом, поступающим через элементы ИЛИ 19 на нулевые входы этих триггеров. После подачи всех тактовых импульсов цикл сравнения чисел зака нчивается. В результате один из триггеров регистра 17 результата находится в единичном состоянии,номер этого триггера соответствует номеру регистра, в котором записано минимальное число. После поступления последнего тактового импульса на выходе счетчика 33 появляется импульс, который переводит триггер управления в нулевое состояние,- запрещая прохождение тактовых импульсов через элемент И 35, и через один из открытых элементов И 18 поступает на выход блока . Коммутатор работает следующим ооразом. Двоичные числа задержек от соседних узлов для всех узлов назначения поступают на группы регистров 37 ,37/2.. 37т по входам 10 путем периодического опроса этих узлов (т - число узлов назначения).

, $10 99

При наличии на входе адреса узла кавначения на одном из выходов дешифратора 36 появляется высокий потенциал, и информация о задержках для данного узла назначения через 5 группы элементов И 38 и группы элементов ИЛИ 39 передается на выход ЭВ-качестве примера, поясняющего процедуру выбора маршрута передачи с минимальными задержками, рас- О смотрим процедуру выбора маршрута для гипотетической цифровой сети, предстабленной на фиг..

Для выбора маршрута с минимальной задержкой на узле-отправителе 15 необходимо иметь информацию о задержках от соседних узлов. Для этого формируется таблица задержек узла. После опроса всех соседних узлов таблица хранится в регистрах 37 комму- 20 татора 5.

Допустим, что нужно передать сообщение И8 узла 1 в узел VI. Для этого на дешифратор Зб подается код адреса узла VI, и двоичные 25 числа задержек 0010, ООП, 0100 поступают на блок t. После сравнения чисел появляется импульс на выходе, соответствующем соседнему узлу II,и сообщение передается в указанный где вновь, определяется маршрут с минимальной задержкой , и т.д.

В данном примере для передачи сообщения из узла 1 в узел VI маршрут с минимальной задержкой прохо- j дит через узел П, хотя кратчайший маршрут - через узел TV.

Предлагаемое устройство позволяет снизить аппаратурные затраты и повысить быстродействие при решении за- jto

17

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

В известном уртройстве формирование маршрута кратчайшего пути в цифровой сети связи осуществляется на основе данных, хранимых в регистрах в виде таблицы маршрутов. Таблица .маршрутов имеет (N-1) строк, где N общее число узлов в цифровой сети связи. Число групп элементов И и блоков сравнения также равно числу узлов назначения в сети.

В.предлагаемом устройстве вместо группы блоков сравнения, содержащей (N-1) блоков, используется один блок сравнения п двоичных чисел, где п - число соседних узлов.

Число буферных регистров и групп элементов И равно не (N-1), как в известном устройстве, а п. Так как в любой цифровой сети связи {N-l)n, то изобретение обеспечивает сокращение объема оборудования при решении такого же объема задач. Как и в известном устройстве.

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

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