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

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

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

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ, содержащее блок.управления, регистр готовности процессоров, три элемента ИЛИ,регистр сдвига, группу блоков элементов И, две группы элементов ИЛИ, регистры номеров заданий, схемы сравнения, первую труппу элементов И, триггер управления, причем первая группа входов каждой схемы сравнения подсоединена ко входам номера непосредственно предшествующего задания устройства, а вторая группа входов - к соответствующим вы-/ ходам регистра номера задания, выходы каждой схемы сравнения подсоединены к первым входам соответствующих элементов И первой группы, кЬ вторым входам которых подсоединены соответствукщие выходы регистра готовности процессоров, выход каждого элемента И первой группы подключен к первому входу соответствующего элемента ИЛИ второй группы, ко второму входу которого подключен выход триггера управления, выходы элементов ИЖ второй группы подсоединены к первой группе входов счзответствующего блока элементов И группы, выход второго элемента ИЛИ подключен к нулевому входу триггера управления, вход кода числа процессоров устройства подключен ко входам второго элемента ИЛИ, информационным входам регистра сдвига и к первой группе входов блока управления, к управляющему входу которого подключен выход первого элемента ИЛИ, входы первого элемента ИЛИ подключены к выходам регистра сдвига, выход синхронизации блока управления подключен к управляющему входу регистра сдвига, а выход сдвига блока управления подключен ко вхо§ ду сдвига регистра сдвига, J -и выход которого ( j 1,. ..,П где п (/) максимальное количество процессоров в типе)подключен ко вторым входам элеме гов И группы, к третьим входам которых подключены выходы соответствукидих разрядов регистра готовности, а к четвертым входам вход номера задания устройства, выход третьего элемента ИЛИ подключен к единичному входу триггера управления, к выходам каждого блока элементов И группы подключены входы соответствующих элементов ИЛИ первой группы и входы регистров номера задания, вых:оды каждого элемента ИЛИ первой группы подключены к соответствующим нулевым входам регистра готовности процессо.ров, выходы номеров заданий устройства подключены к выходам соответствующих блоков элементов И группы, к единичным входам регистра готовности подключены входы состояния процессоров устройства, вьпсоды регистра готовности подключены ко вто-

Изобретение относится к .вычислительной технике и может найти применение в вычислительных системах для J acпpeдeлeния нагрузки между процессорами.

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

упрау ляющим входам группы элементов ll,

Недостатком данного устройства является большое время выполнения связанных заданий

Наиболее близким к изобретению является устройство для распределения заданий процессорам, содержащее блок управления, регистр готовности профессоров, элемент ИЛИ окончания распределения, регистр сдвига. группы .элементов И, первую и вторую группы элементов ИЛИ, процессоры, тины кода числа процессоров, шины номера задания, шину отказа, регистры номера задания, элементы И, триггер управления, элемент ИЛИ сбро са триггера, элемент ИЛИ объединения циклического переноса из старшего в младший разряд регистра сдвига, шины номера непосредственного предшествующего задания, узлы сравнения, к первым входам которых подсоединена группа шин кода номера непосредственно предшествующего задания, а ко вторым входам - выходы соответствующего регистра задания, выходы, каждого узла сравнения подсоединены к первым входам соответствующих элементов И, ко вторым входам которых подсоединены единичные выходы соответствующих триггеров регистра готов ности, выход каждого элемента И подключен к первому входу соответствующего элемента ИЛИ второй группы, ко второму входу которого подсоедине единичный выход триггера, выход каж дого элемента ИЛИ второй группы соединен с четвертым входом соответству ющей группы элементов И, единичный вход триггера соединен с выходом старшего разряда регистра сдвига и первым входом элемента ИЛИ объединения циклического переноса, а нулевой вход - с выходом элемента ИЛИ сброса триггера,-второй вход элемента ИЛИ объединения циклического переноса соединен с первой шиной код числа процессоров, а выход - с входом первого разряда регистра сдвига, шины кода числа процессоров подсоединены ко входам элемента ИЛИ сброса триггера, к третьему входу блока управления и ко входам регистра сдви га (кроме первого разряда), к первом входу блока управления подключен выход элемента ИЛИ окончания распре деления, а ко второму входу - выходы регистра готовности, первый выход блока управления подсоединен ко вхо ДУ, управляющему приемом кода из шин в регистр сдвига, а второй выг ход - ко входу, управляющему сдвиго в регистре, выходы регистра сдвига подсоединены ко входам элемента ИЛИ окончания распределения и к первым входам соответствующих групп элементов И, ко вторым входам которых .подключены соответствующие -разряды , регистра готовности, а к третьим входам.подключены шины номера задания, к выходам каждой группы элементов И подключены входы соответствующих элементов ИЛИ первой группы и регистров номера задания, выходы каждого элемента ИЛИ первой группы подключены к нулевым входам соответствующих триггеров регистра сдвига и регистра готовности, ко входам процессоров подключены выходы соответствующих групп элементов И, выходы процессоров подсоединены к единичным входам триггеров регистра готовности 2j . Работа известного устройства заключается в следующем. На первом этапе по шинам кода числа процессоров в блок управления поступает код числа необходимых для выполнения заданий процессоров. Блок управления сравнива.ет потребное число процессоров с количеством свободных процессоров, данные о готовности которых хранятся в регистре готовности процессоров. Элемент ИЛИ сброса триггера выдает сигнал, устанавливающий триггер в нулевое состояние. Блок управления вьздает по первому выходу сигнал записи кода числа необ5содимых для вьшолнения задания процессоров в регистр сдвига . Одновременно с этим по шинам номера задания на группы элементов И поступает код номера задания, а по шинам номера непосредственно предшест вующего задания подается код номера задания, непосредственно предшествующего данному. На регистрах номеров заданий хранятся коды номеров заданий, назначенных на соответствующие процессоры при предшествующих циклах работы устройства. После записи кода в регистр сдвига на выходах определенных rpyrin элейентов И появятся сигналы кода номера задания. Номер группы элементов И определяется совпадением единичных разрядов в регистре готовности и сигналов, вырабатываемых узлами сравнения, а также при совпадении одноименных единичных разрядов в регистрах готовности процессоров и сдвига. С выхода каждой группы элементов И код номера задания вьщается в соответствующий процессор и регистр номера задания, а через элемент ИЛИ первой группы обнуляет соответствующие разряды регистров готов ности процессоров и сдвига. Если при зтов в регистре сдвига остались единичные разряды, о чем свидетель ствует сигнал на выходе элемента ИЛ окончания распределения, то блок управления выдает в регистр сдвига импульсы сдвига. Если для выполнения задания потр буется количество процессоров, не превышающее число процессоров, заве шивших реализацию непосредственно предшествующего задания, то после определенного количества сдвигов ко в регистре сдвига все его разряды будут обнулены. При этом сигнал с первого входа блока управления снимается. Это означает, что задание распределено между теми процессора ми, которые завершили реализацию непосредственно предшествующего задания . Если необходимое число процессор превышает количество процессоров, завершивших реализацию непосредственно предшествующих заданий, тб пр сдвиге кода в регистре сдвига не все разряды будут обнулены. В этом случае выполняется второй этап распределения задания на любой свобод ный процессор, Особенности его выполнения состоят в следующем. Единичный сигнал с выхода старшего разряда регистра сдвига устана ливает в единичное состояние триггер и через элемент ИЛИ объединения циклического переноса первый разряд регистра сдвига. После переключения триггера разрешающий сигнал поступа ет на входы группы элементов И и обеспечивает их работу без учета сигналов с элементов И второй группы. Теперь при даклическом сдвиге кода в регистре код номера задания появится на выходах соответствующих групп элементов И при совпадении одноименных единичных разрядов толь ко в регистре готовности и регистре сдвигд. С выходов групп элементов И йод вьщается в соответствующий процессор, а через элемент ИЛИ первой группы обнуляет соответствующие раз ряды регистра готовности процессоров и сдвига. При обнулении всех разрядов регистра сдвига сигнал с первого выхода блока управления сни мается. Это означает, что задание распределено среди свободных процессоров. Недостатком известного, устройства являются большие аппаратурные затраты, так как распределение заданий, требующих для своего выполнения процессоров конкретного типа, с помощью указанного устройства приводит к существенному увеличению числа этих устройств (по количеству типов процессоров в неоднородной вычислительной системе), т.е. к значительным затратам оборудования. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается , тем, что в устройство для распределения заданий вычислительной системе, содержащее блок управления,- регистр готовности процессоров, три элемента ИЛИ, регистр сдвига, группу блоков элементов И, две группы элементов И, две группы элементов ИЛИ, регистры номеров заданий, схемы сравнения, первую группу элементов И, триггер управления, причем первая группа входов каждой схемы сравнения подсоединена ко входам номера непосредственно предшествующего задания устройства, а вторая группа входов - к соответствующим выходам регистра номера задания, выходы каждой схемы сравнения подсоединены к первым входам соответствующих элементов И первой группы, ко вторым входам которых подсоединены соответствующие выходы регистра готовности процессоров, выход каждого элемента И первой группы подключен к первому соответствующего элемента ИЛИ второ1и группы, ко второму входу которого подключен выход триггера управления, выходы элементов ИЛИ второй группы подсоединены к первой группе входов соответствующего блока элементов И группы, выход второго элемента ИЛИ подключен к нулевом5 входу триггера управления, вход кода числа процессоров устройства подключен ко входам второго эле мента ИЛИ, информационным входам регистра сдвига и к первой группе входов блока управле1шя, к управляющему входу которого подключен выход первого элемента ИЛИ, входы первого элемента ИЛИ подключены к выходам регистра Сдвига, выход синхронизации блока управления подключен к управляющему входу регистра сдвига, а выход сдвига блока управления подключен ко входу сдвига регистра сдвига, J -и выход которого (j 1, .. ., п, где п - максимальное коли- честно процессоров в типе), подключен ко вторым входам блоков элементов И группы, к третьим входам которых подключены выходы соответствующих разрядов регистра готовности, а к четвертым входам - вход номера задания устройства, выход третьего элемента ИЛИ подключен к единичному входу триггера управления, к выходам Каждого блока элементов И Группы подключены входы соответствующих элементов ИЛИ первой группы и входы регистров номера задания выходы каждого элемента ИЛИ первой группы подключены к соответствующим нулевым входам регистра готовности процес-соров, выходы номеров заданий устройства подключены к выходам соответствующих блоков элементов И группы, к единичным входам регистра ГОТОВНОСТИ подключены входы состояния процессоров устройства, выходы регистра готовности подключены ко второй группе входов блока управления, выход которого соединен с выходом отказа устройства, введены дешифратор типа задания, вторая группа элементов И, группа элементов запрета, третья и четвертая группы элементов ИЛИ, выход каяадого разряда регистра сдвига подключен к первому входу соответствующего элемента И второй группы и к информационному входу соответствующего элемента запрета группы, к пятым входам группы блоков элементов И подключены соответствующие выходы дешифратора типа задания, ко входу которого подключен вход типа задания устройства, выходы дешифратора подключены к группе входов типа задания блока управления и через элементы ШШ четвертой группы - ко вторым входам соответствующих элементов И второй группы и к запрещающим входам соответствующих элементов запрета группы, выходы которых подсоединены к группе входов третьего элемента ИЛИ, выход которого подключен ко входу записи в младший разряд регистра сдвига, выход

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

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

На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема блока управления.

Устройство содержит блок управления 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 состояния процессоров устройства. Блок 1 управления, например, содержит группу блоков элементов И 26, элементы ИЖ 27, схему сравнения 28, триггер 29, генератор одиночных импульсов 30, элемент НЕ 31, элемент И 32, элемент задержки 33, генератор импульсов 34, управляющий выход 35, первую группу входов 36, выход синхронизации 37, выход сдвига 38, управляющий вход 39, группу входов 40 типа задания вторую группу входов 41. Устройство работает следующим образом. Распределение заданий вычисли-. тельной системы с учетом типа посту пившего задания и информационно-управляющих Связей между ними в обще случае включает два этапа. На перво этапе выполняется поиск процессоров заданного типа, соответствующего типу поступивщего задания, и завершивщих выполнение задания, непосред ственно предшествующего данному. Если таких процессоров меньше, чем это необходимо для выполнения посту пившего, задания, осуществляется вто рой этап распределения, на котором заданию вьделяются недостающие свободные .процессоры требуемого типа. На первом этапе работы в устройство поступают по входам 9 и 24 соответственно номер и тип задания по входу 8 - код числа процессоров необходимых для выполнения задания а по входу 18 - код номера задания непосредственно предшествующего данному. На регистрах 11 хранятся коды номеров заданий, назначенных на соответствующие процессоры при предшествуюпщх циклах работы. При поступлении кода числа процессоров элемент ИЛИ 16 выдает сигнал, устанавливающий триггер 15 в нулевое состояние, при котором управляющие сигналы с выходов элементов И 13 подаются на входы соответствующих элементов И 5. Дешифратор 23 расшифровывает тип поступивщего задания и на i -м выходе его появляется сигнал, которьй через соответствующие элементы ИЛИ 22 поступает на управляющие входы ., -1 эле.ментов И 21 и элементов запрета 20. Сигнал с -го выхода дешифратора обеспечивает выдачу информации с соответствующих разрядов регистра 2 готовности на вторую группу входов схемы сравнения 28 блока 1. управления, а также подготовку к работе блоков элементов И 5, соответствующих процессорам требуемого типа Если число свободных процессоров требуемого типа меньше числа потребных, схема сравнения сигнал не вьщ,ает, поэтому на выход 10 устройства поступает единичньм. сигнал отказа с инверсного выхода триггере 29, свидетельствующий о невозможности выполнения задания. Если число свободных процессоров требуемого типа ke меньше, чем необходимо для выполнения задания, схема сравнения 28 выдает сигнал, устанавливая триггер 29 в единичное состояние. При переключении триггера 29 в единичное состояние выдается сигнал на запуск генератора одиночных импульсов 30 и на управляющий вход элемента И 32. Генератор одиночных импульсов 30 выдает на выход 37 блока 1 управления сигнал записи кода, поступающего по входу 8 в регистр 4 сдвига. Предположим, что потребное коли чество процессоров отражается в- коде на шинах 8 количеством единиц в соответствующих разрядах. Тогда после записи кода в регистр 4 сдвига на выходах определенных блоков элементов И 5 появятся сигналы кода ;номера задания. Номер блока элементов И 5 определяется совпадением кода, хранящегося на регистрах 11, и кода поступившего по входу 8, совпадением одноименных единичных разрядов в регистрах 2 и 4, а также совпадением типа процессора и типа поступившего задания. С выхода каждого блока элементов И 5 код номера задания вьщается на.выходы номеров заданий устройства и регистр номера задания 11. Через- элемент ИЛИ 6 код номера задания обнуляет соответствующие разряды 111 регистра готовности 2, а через элементы ИЛИ 19 - соответствующие разряды регистра 4 сдвига. Если при этом в регистре 4 сдвига остались единичные разряды, о чем свидетельст вует сигнал на выходе элемента ИЛИ 3, то генератор импульсов 34 вьщает по шине 38 в регистр 4 импульсы сдви га. Информация с выходов регистра 4 через элементы И 21 поступает на входы записи в старшие разряды регистра 4 и записывается в него со сдвигом при поступлении очередного импульса сдви га. Сдвиг информации происходит в пределах такого количества разрядов которое соответствуе;т максимальному количеству процессоров в 1бранного типа, и определяется сигналом с ёыхода дешифратора 23. После определен ного количества сдвигов кода в регистре 4 все разряды будут обнулены, если необходимое количество процессоров не превышает количества процессоров заданного типа, завершивших выполнение непосредственно предшестЗующего задания. При этом сигнал с выхода -элемента ИЛИ 3 снимается, а на выходе элемента НЕ 31 появляется и сбрасывает триггер 29 в нулевое состояние. Это означает, что задание распределено между выбранными процессорами. Если необходимое число процессоров превышает количество процессоров заданного типа, завершивших выполнение непосредственно предшествующего задания, то при сдвиге кода в регистре 4 не все разряды будут обнулены. В этом случае вьтолняется второй этап распределения задания на любой свободный процессор заданного типа. Особенности его выполнения состоят в следующем. Единичный сигнал с выхода разряда регистра 4, соответствующего на ибольшему номеру процессора заданного типа, поступает на информационньй вход элемента запрета 20. Но посколь ку на запрещающем входе этого элемента запрета 20 сигнал с выхода дешифратора 23 равен нулю, то на выходе элемента запрета 20 появляется единичньй сигнал, который поступает на вход элемента ИЛИ 17. Этот сигнал 3 циклического переноса из.текущего старшего разряда регистра 4 сдвига поступает с ьыхода элемента ИЛИ 17 на вход записи в первый младший разряд регистра 4 сдвига, а также на единичный вход триггера 15 управления. При этом нулевой сигнал на выходе элемента И 21, соответствующего наибольшему номеру процессора выбранного типа, запрещает поступление сигналов переноса с выхода соответствующего- элемента И -21 в старшие разряды регистра 4 сдвига, что предотвращает распределение заданий на процессоры других типов. После переключения триггера 15 разрешающий сигнал, снимаемый с единичного выхода триггера, поступает через элемент ИЛИ 14 на управляющие входы блоков элементов И 5 и обеспечивает работу этих элементов без учета сигналов, поступающих с выходов элементов И 13. Теперь при циклическом сдвиге кода в регистре 4 сдвига код номера задания появляется на выходе блоков элементов И 5, для которых имеет место совпадение тольк,о в регистрах 2 готовности и 4 сдвига, а также типа процессора типу поступившего задания. С выходов выбранных блоков элементов И 5 код номера задания вьщается на соответствующие выходы 7 номеров заданий процессорам устройства и регистр 11, а через элементы ИЛИ 6 и 19 обнуляет соответствующие разряды регистра 2 готовности и регистра 4 сдвига. При обнулении регистра 4 сдвига сигнал с выхода элемента ИЛИ 3 снимается. Это обеспечивает переключение триггера 29 в исходное нулевое состояние и появление сигнала на выходе 10 устройства, означающего, что задание распределено среди свободных процессоров требуемого типа. . Таким образом, устройство обеспечивает распределение заданий, требующих для своего вьтолнения конкр.етных типов процессоров при меньших затратах оборудования. Эконоьмческий эффект от внедрения одного образца предлагаемого устройства составит приблизительно 16,7 рублей.