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

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

Иллюстрации

Показать все

Реферат

 

1. УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ В СЕТЯХ ЭЛЕКТРОННЫХ ВЕМИСЛИТЕЛЬНЙХ МАШИН, содержащее блок управления, первый регистр, первую группу элементов И, первую группу элементов ИЛИ, первую группу регистров, единичные входы которых подключены кпервой группе входов устройства, единичные входы разрядов регистров первой группы соединены с первой группой входов блока управления , единичные выходы разрядов первого регистра соединены с первыми входами элементов И первой группы, первый тактовый выход блока управления подключен к управляющему входу первого регистра, вход управления записью которого соединен с выходом разрешения блока управления , информационные входы первого регистра соединены с первой группой входов устройста, и с второй группой входов блока управления, отличающееся тем, что, с целью расширения области применения , в него введены первый элемент И, первая, вторая, третья, четвертая , пятая и шестая группы блоков элементов И, вторая группа элементов И, элемент ИЛИ, счетчик, блок памяти, дешифратор, группа блоков регистров, группа блокЪв элементов ИЛИ, группа сумматоров, вторая, третья и четвертая группы регист-: (ров, второй и третий регистры и блок выделения экстремального числа, причем нулевые выходы разряде первого регистра соединены с входами первого элемента И, выход которого подключен к первым входам блоков элементов И первой группы, к первому входу блока выделения экстремального числа, к входу сброса счетчика, к входу запуска блока управления, ну левые выходы р.азрядов j-ro регистра первой группы соединены с первыми входами j-ro элемента И первой груп ,пы, единичные выходы разрядов этого регистра соединены с первыми входами j-rro блока элементов И второй группы, выход j-ro блока элементов И второй группы подключен,, к входу J-ro элемента ИЛИ первой группы, «Л выход которого соединен с первым с входом J-ro элемента И второй груп|пы , выход которого подключен к ну-левому входу J-ro разряда первого регистра и к первому входу J-го эле;Мента И третьей группы, выход которого соединен с нулевым входом J-ro регистра первой группы, и J-й вход третьей группы входов уст :ройства подключен к входу i-ro блоел Ю ка регистров группы, выход которого :Соединен с первыми входами i-ro блока элементов и четвертой группы, о: выходы которых подключены к входам 1-го блока элементов ИЛИ второй группы, выход которого подключен к первому входу i-ro сумматора-группы, четвертая группа входов устройства соединена с входами регистров второй группы, выход i-ro регистра которой подключен к второму входу i-ro сумматора группы, выходы сумматоров группы соединены с группой входов блока выделения экстремального числа, первая группа выходов которого подключена к перзым входам блоков элементов И пятой группы, выходы которых соединены с входами

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

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

РЕСПУБЛИК

„„Su„„1075261 A

3QB G 06 F 9 00

ОГ1ИСАНИЕ ИЗОБРЕТЕНИЯ /"

Н ABTOPCXOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ.. (21 ) 3496502/18-24 (22) 01.10.82 (46) 23.02.84. Бюл. 9 7 (72) В.В. Мазаник, В.М. Неффа, С.Н. Львов и В.В. Потетенко (53) 681.325(088.8) (56) 1.Авторское свидетельство СССР

Р 433489, кл. G 06 F 9/00, 1974.

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

9 629538, кл. G 06 F 9/00, 1978 (прототип).

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

9 752326, кл. С 06 F 7/02, 1978. (54)(57) 1. УСТРОЙСТВО ДЛЯ РАСПРЕДЕ.

ЛЕНИЯ ЗАДАНИЙ В СЕТЯХ ЭЛЕКТРОННЫХ

ВЫЧИСЛИТЕЛЬНЫХ МАШИН, содержащее блок управления, первый регистр, первую группу элементов И, первую группу элементов ИЛИ, первую группу регистров, единичные входы которых подключены к первой группе входов устройства, единичные входы разрядов регистров первой группы соединены с первой группой входов блока управления, единичные выходы разрядов первого регистра соединены с первыми входами элементов И первой группы, первый тактовый выход блока управления подключен к управляющему входу первого регистра, вход управления записью которого соединен с выходом разрешения блока управления, информационные входы первого регистра соединены с первой группой входов устройста, и с второй группой входов блока управления, о тл и ч а ю ш е е с я тем, что, с целью расширения области применения, в него введены первый элемент

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

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

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

:J-ro регистра первой группы, и

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

:соединена с входами регистров второй группы, выход i-го регистра которой подключен к второму входу

i-ro сумматора группы, выходы сумматоров группы соединены с группой входов блока выделения экстремального числа, первая группа выходов которого подключена к первым входам блоков элементов И пятой группы, выходы которых соединены с входами

1075261!

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

И второй группы, с вторым входом

j-го блока элементов И третьей группы, с вторым входом J-ro элемента И первой группы, с вторыми входами

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

2. устройство по п.1, о т л ич а ю щ е е с я тем, что блок

Изобретение относится к вычислительной технике, в частности к уст- ройствам управления в сетях элект ронных вычислительных машин (ЭВМ).

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

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

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

Недостатком устройства является низкое быстродействие.

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

1075261 деления, к второму входу. блока правления поиском и распределением одсоединены выходы регистра готовости процессоров, а к третьему входу — шины необходимого числа про. цессоров. Первый выход блока управления подсоединен к входу, управляющему приемом кода в регистр сдвига, второй выход подсоединен к входу, управляющему сдвигом регистра сдвига, третий выход, блока управления подсоединен к шине отказа от распределения задания, выходы регистра сдвига подключены к входам элемента ИЛИ окончания распределения и к первым входам эле. ментов И каждой из (по числу процессоров ) групп, к вторым входам каждой группы элементов И подключены соответствующие выходы регистра готовности,. к третьим входам элементов И подключены шины номера задания,. к выходам каждой группы элементов И подключены входы соответствующих элементов ИЛИ, выходы которых йодсоединены к нулевым входам соответствующих триггеров регистра сдвига и регистра готовности, к входам процессоров подключены выходы соответствующих групп элементов И, а выходы процессоров подсоединены к единичным входам триггеров регистра готовности Г23.

Недостатком известного устройства является невозможность распределения заданий в сетях ЭВМ с учетом состояния процессоров и минимального суммарного времени задержки на передачу данных о ожидании в очереди на выходе узла обработки.

Целью изобретения является расширение области применения устройства.

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

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

15 выделения экстремального числа, к входу сброса счетчика, к входу запуска блока управления, нулевые выходы разрядов g-ro регистра первой группы соединены с первыми входами

j-ro H первой группы, единичные выходы разрядов этого регистра соединены с первыми входами J-ro блока элементов И второй группы, выход g-го блока элементов И второй группы подключен к входу 1-го элемен та ИЛИ первой группы, выход которого соединен с первым входом J-ro элемента И второй группы, выход кото рого подключен к нулевому входу g-го

30 разряда первого регистра и к первому входу j-го элемента И третьей группы, выход которого соединен с нулевым входом j-го регистра первой груп пы, J-й вход третьей группы входов

g5 устройства подключен к входу i-ro блока регистров группы, выход которого соединен с первыми входами

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

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

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

65 блока памяти соединен со счетным

1075261 входом счетчика," выход которого соединен с адресным входом блока памяти, выход которого подключен к входу дешифратора, -ый выход которого соединен с вторым входом j-ro блока элементов И второй группы, с- 5

° вторым входом J-ro блока элементов

И третьей группы, с вторым входом

g-го элемента И первой группы, с вторыми входами g-ro блока элементов

И пятой и шестой групп, с вторым Щ входом g-ro блока элементов И чет.вертой группы, выходы элементов

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

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

Блок управления содержит элемент запрета, первый и второй элементы 35

И, первый, второй и третий элементы ИЛИ, первый и второй триггеры, формирователь импульсов, элемент сравнения, генератор импульсов и элемент НЕ, причем вход останова 4О блока соединен с управляющим входом элемента запрета и с первым входом первого элемента ИЛИ, выход которого подключен к нулевому входу пер« ного триггера, нулевой выход которого соединен с первым входом первого элемента И:, выход которого подключен к второму тактовому выходу блока и информационному входу . элемента запрета, выход которого соединен с единичным входом первого триггера, единичный выход которого подключен к .первому входу второго элемента И, второй вход которого соединен с вторым входом первого элемента И, и с выходом генератора импульсов, первая группа входов элемента сравнения подключена к входам второго элемента ИЛИ, выход которого соединен с входом формирователя импульсов, выход которого 60 подключен к единичному входу второго триггера, единичный выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с третьими входа, 65 ми первого и второго элементов И, выход элемента сравнения подключен к выходу разрешения блока И и к входу элемента НЕ, выход которого соединен с сигнальным выходом блока и с первым входом третьего элемента

ИЛК, второй вход которого подключен к второму входу первого элемента

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

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

Устройство содержит блок 1 управления, группу регистров 2, элемент

И 3, регистр 4, группу элементов И 5 груйпу элементов ИЛИ 6, группы блоков элементов И 7 и 8, группу элементов И 9,- элемент ИЛИ 10, счетчик 11, блок 12 памяти, дешиф-, ратор 13, группу блоков регистров

14, третью группу блоков элементов

И 15, группу блоков элементов ИЛИ

16, группу сумматоров 17, группу регистров 18, блок 19 выделения .экстремального числа, группы блоков элементов И 20 и 21, регистры 22 и 23, блоки регистров 24 и 25, груп. пу блоков элементов И 26, элемент

27 запрета, элемент И 28, второй элемент ИЛЙ 29, триггер 30, элемент

ИЛИ 31, Формирователь 32 импульсов, элемент 33 сравнения, элемент MJIH

34, триггер 35, элемент И 36, генератор 37 импульсов, элемент HE 38.

На Фиг. 2 изображен, блок регистров 39, группа поразрядных узлов

40 анализа, третий, четвертый и пятый блоки элементов И 41-43, второй и третий блоки элементов ИЛЙ 44 н

45, блок триггеров 46, блок элементов И-НЕ 47, четвертый блок элементов ИЛИ 48, шестой блок элементов

И 49, первый и второй блок входов

50 и 51, выход 52, третий блок входов 53, группу блоков входов 54, четвертый и пятый блоки входов 55 и 56 и блок выходов 57 устройства, первый и второй блоки выходов 58 и 59, первый вход 60, группу блоков входов 61 и второй вход 62 блока

19 выделения экстремального числа.

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

В исходном состоянии в g-м регистре 2 готовности хранятся данные о готовности к работе процессоров -гь узла обработки, в i-м регистре

18 очереди хранится код времени

1075261 ожидан в очереди при передаче данных к i-му узлу обработки, а в

ig-м регистре 14 задержки хранится код минимального времени задержки при передаче данных из i-ro в )-й узел обработки. Триггеры 30, 35 и

46, счетчики 11 и регистры 4, 22

25 и 39 находятся в нулевом состоянии. Блок 12 содержит 1 ячеек, в каждой из которых записан код номе» ра узла, на котором возможна обра-. ботка задания. Коды номеров узлов .могут быть упорядочены, например, по удаленности от данного узла обработки.

Устройство обеспечивает формирование заголовка задания, включающего номер задания; исходные данные для его обработки, номер соседнего узла и код минимального времени задержки при передаче данных из данного узла в узел назначения для p-ro узла назначения.

В работе устройства можно выделить три этапа.

На первом этапе проводится.проверка воэможности выполнения задания в сети ЭВМ и прием задания на обслуживание, Go входам 50 код необходимого для выполнения задания числа процессоров (одному процессору соответст)вует один разряд кода числа) посту-. пает на входы элемента ИЛИ 31 и на первые входы элемента 33 сравнения.

Одновременно по входам 55 и 56 соответственно поступает код номера задания (записывается в регистр

22) и код исходных данных (в регистр 23 ). При этом на выходе элемента ИЛИ 31 появляется сигнал, который через формирователь 32 импульсов (фиг..За — выход формирователя ) устанавливает триггер 35 пуска .(фиг.З е — единичный выход триггера) в единичное состояние. На вторые входы элемента 33 сравнения поступает с регистров 2 код количества свободных процессоров. Если количество свободных процессоров меньше количества необходимых для выполнения задания, то на выходе элемента

HE 38 и выходе 52 появляется сигнал отказа от выполнения задания, который через элемент ИЛИ 34 сбрасывает триггер 35 пуска в нулевое состояние.

Если количество свободных процессоров в сети ЭВМ больше либо равно необходимому, то на выходе элемента

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

На втором этапе определяются . узлы назначения (где есть свободные процессоры), производится выделение процессоров на этих узлах, опреде65 мого )-ro регистра 2 готовности понналичии сивнала на -м выходе ление минимального времени задержки и номеров соседних узлов, маршрут передачи данных через которые обеспечивают такое время. Второй этап выполняется за несколько шагов.Каж5 дый шаг в общем случае включает три типа итераций. В начале каждого шага выполняется итерация первого типа, обеспечивающая поиск ближайшего к данному узлу i-го узла обра10 ботки, на котором есть хотя бы один свободный процессор.

Выполнение итерации начинается с появления на выходе элемента Й 28 сигнала, обеспечивающего обращение к блоку 12 по адресу, увеличенному на единицу. Иэ блока 12 считывается код номера g-го узла, и íà g-м выходе дешифратора 13 появляется сигнал, который разрешает работу g- ro элемента И 9. Если с нулевЫх выходов всех триггеров g-го регистра 2 готов ности поступают единичные сигналы, сообщающие о том, что в )-м узле все процессоры заняты, то на выходе

3-го элемента И 9 появляется единичный сигнал, который запрещает прохождение импульсов через элемент 27 запрета и через элемент ИЛИ 29 и подтверждает нулевое состояние триггера 30. При этом разрешается поступ

30 ление сигнала с генератора 37 импульсов через элемент И 28 на счетный вход счетчика 11 и запуск блока

12. Адрес обращения к блоку 12 увеличивается на единицу по сравнению с предыдущим циклом считывания, что ,обеспечивает выборку очередного номера узла .

Итерация первого типа (Фиг.З), 1 тип повторяется до тех riop, 4() пока не найдется узел, на котором есть хотя бы один свободный процессор. В этом случае на выходах всех элементов И 9 будут нулевые сигналы.

Нулевой сигнал с выхода. элемента

45 И 10 Разрешает прохождение сигнала с выхода элемента И 28 (фиг.Зк) через элемент запрета 27 .(фиг. 38),который устанавливает триггер 30 в единичное состояние (фиг. Зд). Нулевой сигнал с нулевого выхода триггераг30 запрещает прохождение импульсов с генератора 37 через элемент И 28 и. состояние счетчика 11 нв изменяется. На этом итерация первого типа заканчивается.

Итерация второго и третьего типов выполняется одновременно после итерации первого типа (фиг. Зи, к, П и ttl типы).

При выполнении итерации второго типа устройство распределяет части задания на свободные процессоры выбранного узла назначения. С этой .целью производится выдача содержи1075261

;дешифратора 13 на первые входы груп пы элементов И 5 (через группы элементов И. 7 и ИЛИ б). При этом на выходах некоторых элементов И 5 появляется разрешающий сигнал.Оче видно, что номера этих элементов 5 определяются совпадением одноименных единичных разрядов в g-м регистр ре 2 готовности и регистре 4. С выходов элементов и 5 сигналы поступают на сброс соответствующих тригге- - Ю ров регистра 4 g-го регистра 2 готовности через соответствующие элементы И 8. Если при этом в регистре 4 остались триггеры в единичном состоянии (о чем сообщает сигнал на 15 выходе элемента И 3 ), то с выхода элемента И 36 в регистр 4 подаются импульсы сдвига до тех пор, пока -й регистр 2 готовности не будет полностью обнулен. Если все триггеры g-го регистра 2 готовности сброшены в нулевое состояние, то на выходе g-ro элемента И 9 появляется сигнал, который через элементы ИЛИ 10 и 29 устанавливает триггер 30 в нулевое состояние, что запрещает прохождение импульсов. сдвига с генератора 37 импульсов через элемент И 36. На этом итерация второго типа заканчивается.

Если при этом не все разряды регистра 4 "сдвига обнулены, то устройство йовторяет итерацию первого гипа поиска свободных узлов сети

ЭВМ. При установке в нулевое состояние acez триггеров регистра 4 на очередном. шаге выполнения итерации второго типа на выходе элемента И 3 появляется сигнал (фиг. ЗЖ1.. Это означает, что задание обеспечено необходимым числом процессоров на 4О выбранных узлах обработки. На этом заканчивается выполнение второго этапа.

При выполнении итерации третьего типа устройство определяет соседний 45 узел от данного, Маршрут пере- дачи данных которого обеспечивает минимальное время задержки с уче- том ожидания в очереди на данном узле. Сигнал с g-ro выхода дешифратора 13 разрешает поступление кода времени задержки:(минимального времени задержки при передаче данных из i-го соседнего узла на -й узел назначений,j c ig-го регистра 14 через ig-ю группу члемен-. тов И 15, i-ю группу элементов ИЛИ

16 иа второй вход i-ro сумматора

17, на первый вход которого поступает код времени ожидания в очере ди при передаче исходных данных

60 из данного на i-й соседний узел. Суммарный код времени задержки с выхода 1-го сумматора 17 записывается в i-й регистр 39 блока 19: для выделения экстремального из б5

nm"ðàçðÿäíûõ двоичных чисел. Сигнал с единичного выхода триггера

30 по входу 60 разрешения блока 19 устанавливает группу триггеров 46 в единичное. состояние и разрешает поразрядный анализ сравниваемых чисел (записанных в регистрах 39 /.

Если в первом разряде чисел имеется и "0", и "1", то через элементы

И 41 и 42, узлов 40 анализа на группу элементов ИЛИ 48 и 44 поступают единичные сигналы. На выходе элемента И-НЕ 47 будет формироваться нулевой сигнал, которым закрывается элемент И 49. Через элементы И

43 узлов анализа и ИЛИ 45, относящиеся к тем регистрам, в первом разряде которых записан "0", единичный сигнал поступает на входы установки в нулевое состояние. соответствующих триггеров 46. Элементы И 41 и 42 соответствующих узлов анализа закрываются, и единичный сигнал будет только на выходе элемента

ИЛИ 48. На выходе элемента И-HE 47 формируется единичный сигнал, по которому открывается элемент Й 49.

Далее производится анализ следующего разряда оставшихся сравниваемых чисел. Если же в первом разряде сравни-, ваемых чисел содержатся только нулевые коды или только единичные, то на выходе соответствующего элемента И-HE 47 будет единичный сигнал, который открывает элемент И 49.

Следовательно, в этом случае сразу производится анализ второго или последующих разрядов, Чосле того, как все Разряды сравниваемых чисел будут проанализированы, на выходе соответствующего элемента И 49 формируется единичный уровень. Нри этом на выходе 58 содержится код минимальной: задержки с учетом ожидания в очереди на выходе данного узла при передаче данных через i-й соседний узел в д-й узел назначения, который записывается при наличии разрешающего сигнала на -м выходе дешифратора 13 через j-ю группу элементов

И 21 в -й регистр 25 минимальной задержки. На выходах 59 содержится код номера i-го соседнего узла, время задержки при передаче дан ных через который является минимальным. Этот код записывается при наличии разрешающего сигнала на J-м выходе дешифратора 13 через -ю группу элементов И 20 в -й регистр 24 номера соседнего узла.

На этом итерация третьего типа заканчивается.

На третьем этапе производится выдача сформированного заголовка задания на выходы 57 устройстза.

Сигнал с выхода элемента И 3 поступает на вход гоуппы элементов И 26

12

1075261

11 и разрешает выдачу заголовка зада- ния из регистров 22-25 на выходы

57 устройства. При этом сигнал с выхода элемента И 3 сбрасывает триггеры 30, 34 и 46 и устанавливает в нулевое состояние счетчик 11 и ре. гистры 22-25 и 39. На этом работа устройства заканчивается.

1075261

ВНИИПИ Заказ 499/42

Тираи 699 Подписное

ЮЮ МЮ

Филиал ППП "Патент", r.Óõ îðîä,óï.Ïðîåêòíàÿ,4