Устройство для распределения заданий в сетях электронных вычислительных машин Советский патент 1984 года по МПК G06F9/00 

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

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

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

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

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 сумматора группы, выходы сумматоров группы соединены с группой входов блока выделения экстремального числа, первая группа выходов которого подключена к перзым входам блоков элементов И пятой группы, выходы которых соединены с входами

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

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

Недостатком устройства является

низкое быстродействие.

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

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

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

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

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

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

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

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

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

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

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

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

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

группу элементов ИЛИ б, группы блоков элементов И 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 сравнения, элемент ИЛИ 34, триггер 35, элемент И 36, генератор 37 импульсов, элемент НЕ 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 выделения экстремального числа.

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

В исходном состоянии в J-M регистре 2 готовности хранятся данные о готовности к работе процессоров J-ro узла обработки, в i-м регистре 18 очереди хранится код времени

ожиданпя в очередипри передаче данных к i-му узлу обработки, а в iJ-M регистре 14 задержки хранится код минимального времени задержки при передаче данных из i-ro в J-й узел обработки. Триггеры 30, 35 и 46, счетчики 11 и регистры 4, 22 25 и 39 находятся в нулевом состояНИИ. Блок 12 содержит 1 ячеек, в каждой из которых записан код номера узла, на котором возможна обра ботка задания. Коды номеров узлов .могут быть упорядочены, например, по удаленности от данного узла обработки.

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

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

Напервом этапе проводится провека возможности выполнения задания в сети ЭВМ и прием задания на обслуживание. По входам 50 код необходимог для выполнения задания числа процессоров (одному процессору соответст|вует один разряд кода числа) поступает на входаз элемента ИЛИ 31 и на первые входы элемента 33 сравнения. Одновременно по входам 55 и 56 соответственно поступает код номера задания {записывается в регист 22 и код исходных данных (в регистр 23 ). При этом на выходе элемента ИЛИ 31 появляется сигнал, который через формирователь 32 импульсов (фиг.. 3 а - выход формирователя ) устанавливает триггер 35 пуска (фиг.Зе - единичный выход триггера в единичное состояние. На вторые входы элемента 33 сравнения поступает с регистров 2 код количества свободных процессоров. Если количество свободных процессоров меньше количества необходимых для выполнения задания, то на выходе элемента НЕ 38 и выходе 52 появляется сигнал отказа от выполнения задания, который через элемент ИЛИ 34 сбрасывает триггер 35 пуска в нулевое состояние.

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

На втором этапе определяются . узлы назначения (где есть свободные процессорыJ, производится вьщеление процессоров на этих узлах, опреде;ление минимального времени задержки и номеров соседних узлов, маршрут передачи данных через которые обеспе|Чивают такое время. Второй этап выполняется за несколько шагов.Каждый шаг в общем случае включает три типа итераций. В начале каждого шага выполняется итерация первого .типа, обеспечивающая поиск ближайшего к данному узлу j-ro узла обработки, на котором есть хотя бы один свободный процессор.

Выполнение итерации начинается с появления на выходе элемента И 28 сигнала, обеспечиваклцего обращение к блоку 12 по адресу, увеличенному на единицу. Из блока 12 считываетс код номера j-ro узла, и на J-м выходе дешифратора 13 появляется сигнал который разрешает работу j-ro элемента И 9. Если с нулевых-выходов всех триггеров j-ro регистра 2 гото ;Ности поступают единичные сигналы, сообщающие о том, что в j-M узле все процессоры заняты, то на выходе j-ro элемента И 9 появляется единичный сигнал, который запрещает прохождение импульсов через элемент 27 запрета и через элемент ИЛИ 29 и подтверждает нулевое состояние триггера 30. При этс разрешается посту ление сигнала с генератора 37 импульсов через элемент И 28 на счетный ёход счетчика 11 и запуск блока 12. Адрес обращения к блоку 12 увеличивается на единицу по сравнению с предыдущим циклом считывания, что (Обеспечивает выборку очередного номера узла,

; Итерация первого типа (Фиг.З). 1 тип -повторяется до тех liop, пока не найдется узел, на котором есть хотя бы один свободный процессор. В этом случае на выходах всех элементов И 9 будут нулевые сигналы Нулевой сигнал с выходаэлемента И 10 разрешает прохождение сигнала с выхода элемента И 28 (фиг.3мJчерез элемент запрета 27 (фиг. 36,который устанавливает триггер 30 в еди-. ничное достояние (фиг. 3d). Нулевой сигнал с нулевого выхода триггера: 30 запрещает прохождение импульсов с генератора 37 через элемент И 28 и. состояние счетчика 11 не изменяется. На этом итерация первого типа заканчивается.

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

При выполнении итерации второго типа устройство распределяет части з цания на свободные процессоры выбранного узла назначения. С этой целью производится выдача содержимого j-ro регистра 2 готовности ПРИ.наличии сигнала на J-M.выходе .дешифратора 13 на первые входы гру пы элементов И 5 {через группы элементов И. 7 и ИЛИ 6. При этом н выходах некоторых элементов И 5 появляется разрешакнций сигнал,Очевидно, что номера этих элементов определяются соврадением одноименннх единичных разрядов в J-M регис ре 2 готовности и регистре 4.С вы ходов элементов И 5 сигналы поступ ют на сброс соответствующих тригге ров регистра 4 j-ro регистра 2 готовности через соответствующие эле менты И 8 Если при этом в регистре 4 остались триггеры в единичном состоянии (о чем сообщает сигнал н вьп4оде элемента ИЗ, то с выхода элемента И 36 в регистр 4 подаются импульсы сдвига до тех пор, пока j-й регистр 2 готовности не будет полностью обнулен. Если все триггеры j-ro регистра 2 готовности сброшены в нулевое состояние, то на выходе j-го элемента И 9 появляется сигнал, который через элементы ИЛИ 10 и 29 устанавливает триггер 30 в нулевое состояние, что запрещает прохождение импульсо сдвига.с генератора 37 импульсов .через элемент И 36. На этом итерация второго типа заканчивается. Ecj при этом не все разряды р гистра 4 сдвига обнулены, то устро ство повторяет итерацию первого : типа поиска свободных узлов сети ЭВМ. При установке в нулевое состо ние всех триггеров регистра 4 на очередном шаге выполнения итерации второго типа на выходе элемента И появляется сигнал (фиг. ЗДх). Это означает, что задание обеспечено необходил&ом числом процессоров на выбранных узлах обработки. На этом заканчивается выполнение второго этапа. При выполнении итерации третьег типа устройство определяет соседни узел (от данного, йаршрут передачи данных которого обеспечивает минимальное время задержки с учетом ожидания в очереди на данном ;узле. Сигнал с j-ro выхода дешифратора 13 разрешает поступление кода времени задержки (минимального времени задержки при передаче данных из i-ro соседнего узла на j-й узел назначений с ij-ro регистра 14 через ij-ю группу элемен тов И 15, i-ю группу элементов ИЛИ 16 на второй вход 1-го сумматора 17, на первый вход которого поступает код времени ожидания в очере дй при передаче исходных данных из данного на i-й соседний узел. {.Суммарный код времени задержки с выхода i-ro сумматора 17 записываатся в i-й регистр 39 блок 19 для в аделения экстремального из nm-разрядных двоичных чисел. Сигнал с единичного выхода триггера 30 по входу 60 разрешения блока 19 устанавливает группу триггеров 46 в единичное состояние и разрешает поразрядный анализ сравниваемых чисел (записанных в регистрах 39/, Если в первом разряде чисел имеется и О, и 1, то через элементы И 41 и 42, узлов 40 анализа на группу элементов ИЛИ 48 и 44 поступают единичные сигналы. На выходе элемента И-НЕ 47 будет формироваться нулевой сигнал, которым закрывается элемент И 49. Через элементы И 43 узлов анализа и ИЛИ 45, относящие ся к тем регистрам, в первом разряде которых записан О, единичный сигнал поступает на входы установки в нулевое состояние соответствующих триггеров 46. Элементы И 41 и 42 соответствующих узлов анализа закрываются, и единичный сигнал будет только на выходе элемента ИЛИ 48. На выходе элемента И-НЕ 47 формируется единичный сигнал, по которому открывается элемент И 49. Далее производится анализ следующего ра зряда оставшихся сравниваемых чисел. Если же S первом разряде сравниBaej ix чисел содержатся только нулевые коды или только единичные то на выходе соответствующего элемента И-НЕ 47 будет единичный сигнал, который открывает элемент И 49. Следовательно, в этом случае сразу производится анализ второго или последующих разрядов. 1осле того, как все разряды сравниваеьялх чисел бУдут проанализированы, на выходе соответствующего элемента И 49 формируется единичный уровень. При этом на выходе 58 содержится код минимальной: задержки с учетом ожидания в очереди на выходе данного узла при передаче данных через i-й соседний узел в j-й узел назначения, который записывается при наличии разрешающего сигнала на j-M выходе дешифратора 13 через j-ю группу элементов И 21 в регистр 25 минимальной задержки. На выходах 59 содержится код номера i-ro соседнего узла, время задержки при передаче данных через который является минимальным. Этот код записывается при наличии разрешакадего сигнала на j-M выходе дешифратора 13 через j-ю группу элементов И 20 в j-й регистр 24 Hoivsepa соседнего узла. На этом итерация третьего типа заканчивается. На третьем этапе производится . выдача сформированного заголовка задания на выходы 57 устройства. Сигнал с выхода элемента И 3 поступает на вход гоуппы элементов И 26

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

OmJtT n

Фи&1