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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК Э 11. З(59 С 06 Г 9/00 АНИЕ ИЗОБРЕТЕ ЕТЕЛЬСТВУ ТОР СНО,84 Бюл. И 24анитулин, А.И.Шнкив25 (Оторсккл, Срскоекл С ключен к управленияров устройвторого нным входам ой группек управодключен ИЛИ, входы ключены 629538,2. Авто 913377,прототипы вГОСУДАРСТВЕННЫЙ КОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ 88.8)ое свидетельство СССР06 Г 9/00, 1977.свидетельство СССР06 Р 9/00, 1980(54)(57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНИЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ, содержащее блок, управления, регистрготовности процессоров, три элемента ИЛИ,регистр сдвига, группу блоковэлементов И, две группы элементовИЛИ, регистры номеров заданий, схемысравнения, первую группу элементов И, триггер управления, причемпервая группа входов каждой схемысравнения подсоединена ко входамномера непосредственно предшествующего задания устройства, а втораягруппа входов - к соответствующим выходам регистра номера задания, выходыкаждой схемы сравнения подсоединенык первым входам соответствующих элементов И первой группы, ко вторымвходам которых подсоединены соответствующие выходы регистра готовностипроцессоров, выход каждого элемен-.та И первой группы подключен к первому входу соответствующего элемента ИЛИ второй группы, ко второмувходу которого подключен выход триггера управления, выходы элементовИЛИ второй группы подсоединены кпервой группе входов соответствующего блока элементов И группы, выход второго элемента ИЛИ поднулевому входу триггеравход кода числа процессоства подключен ко входамэлемента ИЛИ, информациорегистра сдвига и к перввходов блока управления,ляющему входу которого ивыход первого элементапервого элемента ИЛИ под к выходам регистра сдвига, выходсинхронизации блока управленияподключен к управляющему входурегистра сдвига, а выход сдвигаблока управления подключен ко входу сдвига регистра сдвига,-йвыход которого (= 1П где Пмаксимальное количество процессоров в типе)подключен ко вторым входам элеме 1 гов И группы, к третьимвходам которых подключены выходысоответствующих разрядоь регистраготовности, а к четвертым входам -вход номера задания устройства,выход третьего элемента ИЛИ подключен к единичному входу триггеруправления, к выходам каждого блокэлементов И группы подключены входы соответствующих элементов ИЛИпервой группы и входы регистровномера задания, выходы каждогоэлемента ИЛИ первой группы подключены к соответствующим нулевымвходам регистра готовности процессров, выходы номеров заданий устройства подключены к выходам соответствующих блоков элементов И группк единичным входам регистра готоности подключены входы состоянияпроцессоров устройства, выходы регистра готовности подключены ко вт100623 1 рой группе входов блока управленияР выход которого соединен с выходом отказа устройства, о т л и ч а ю - щ е е с я тем, что, с целью сокращения аппаратурных затрат, устройство содержит дешифратор типа задания, вторую группу элементов И, группу элементов запрета, третью и четвертую группы элементов ИЛИ, выход каждого разряда регистра сдви.га подключен к первому входу соответствующего элемента И второй груп,пы и к информационному входу соот. - ветствующего элемента запрета группы, к .пятым входам группы блоков элементов И подключены соответствующие выходы дешифратора типа задания ко входу которого подклю чен вход типа задания устройства, выходы дешифратора подключены к группе входов типа задания блока управления и через элементы ИЛИ чет вертой группы - ко вторым входам соответствующих элементов И второй группы и к запрещающим входам соответствующих элементов запрета груп пы, выходы которых подсоединены к группе входов третьего элемента ИЛИ, выход которого подключен ко входу записи в младший разряд регистра сдвига, выход 1 -го элемента И второй группы подключен ко входу записи в старший разряд регистра сдвига, выход каждого элемента ИЛИ третьей группы подключен соответственно к нулевому входу каждого разряда регистра сдвига, выход-го элемента ИЛИ первой группы подключен ко входу 1 -го элемента ИЛИ третьей группы, выход старшего разряда регистра сдвига подключен ко входутретьего элемента ИЛИ, причем блокуправления содержит схему сравнения,группу блоков элементов И, элемент Игенератор одиночных импульсов, элементы ИЛИ, элемент НЕ, триггер, генератор импульсов, элемент задержки, первая группа входов блока управления подключена к первой группевходов схемы сравнения, ко второйгруппе входов которой подключены выходы элементов ИЛИ, ко входам 1 -гоэлемента ИЛИ подключены-е выходыкаждого блока элементов И группык первым входам 1 -го блока элементов И группы подключена группа входов типа задания блока управленияко вторым входам блоков элементов Игруппы подключена вторая группа вхо"дов блока управления, выход схемысравнения подключен к единичномувходу триггера, к нулевому входукоторого подключен выход элемента НЕвход которого соединен с управляющимвходом блока управления, нулевойвыход триггера подключен к управляющему выходу блока управления, а единичный выход триггера - ко входугенератора одиночных импульсов и кпервому входу элемента И, ко второмувходу которого подключен выход генератора импульсов, выход элемента Иподсоединен через элемент задержки квыходу сдвига блока управления, выход генератора одиночных импульсовподсоединен к выходу синхронизацииблока управления, Изобретение относится к,вычислительной технике и может найти применение в вычислительных системах для ,распределения нагрузки между процессорами. 5Известно устройство для распределения заданий процессорам содержащее регистр готовности процессоров,. группы элементов И, элемент ИЛИ окончания распределения, регистр сдвига Ю выходы которого подсоединены к управляющим входам группы элементов 1,Недостатком данного устройстваявляется большое время выполнениясвязанных заданийНаиболее близким к изобретениюявляется устройство для распределения заданий процессорам, содержащее блок управления, регистр готовности прогрессоров, элемент ИЛИ окончания распределения, регистр сдвига,110062 группы элементов И, первую и вторую группы элементов ИЛИ, процессоры, шины кода числа процессоров, шины номера задания, шину отказа, регистры номера задания, элементы И, триггер управления, элемент ИЛИ сбро. са триггера, элемент ИЛИ объединения циклического переноса из старшего в младший разряд регистра сдвига, шины номера непосредственного пред О шествующего задания, узлы сравнения, к первым входам которых подсоединена группа шин кода номера непосредственно предшествующего задания, а ко вторым входам - выходы соответ. ствующего регистра задания, выходы каждого узла сравнения подсоединены к первым входам соответствующих элементов И, ко вторым входам которых подсоединены единичные выходы соот ветствующих триггеров регистра готовности, выход каждого элемента И подключен к первому входу соответствующего элемента ИЛИ второй группы, ко второму входу которого подсоединен 25 единичный выход триггера, выход каж дого элемента ИЛИ второй группы соединен с четвертым входом соответствующей группы элементов И, единичный вход триггера соединен с выходом 30 старшего разряда регистра сдвига и первым входом элемента ИЛИ объединения циклического переноса, а нулевой вход - с выходом элемента ИЛИ сброса триггера, второй вход элемента ИЛИ объединения циклического переноса соединен с первой шиной кода числа процессоров, а выход - с входом первого разряда регистра сдвига, шины кода числа процессоров подсоединены ко входам элемента ИЛИ сброса триггера, к третьему входу блока управления и ко входам гегистра сдвига (кроме первого разряда), к первому. входу блока управления подключен вы ход элемента ИЛИ окончания распре деления, а ко второму входу - выходы регистра готовности, первый выход блока управления подсоединен ко входу, управляющему приемом кода из 50 шин в регистр сдвига, а второй вы-, ход - ко входу, управляющему сдвигом в регистре, выходы регистра сдвига подсоединены ко входам элемента ИЛИ окончания распределения и к первым 55 входам соответствующих групп элементов И, ко вторым входам которых подключены соответствующие разряды 3 4регистра готовности, а к третьимвходам, подключены шины номера задания, к выходам каждой группы элементов И подключены входы соответствующих элементов ИЛИ первой группыи регистров номера задания, выходыкаждого элемента ИЛИ первой группыподключены к нулевым входам соответствующих триггеров регистра сдвигаи регистра готовности, ко входампроцессоров подключены выходы соответствующих групп элементов И, выходы процессоров подсоединены к единичным входам триггеров регистраготовности 2 . Работа известного устройства заключается в следующем.На первом этапе по шинам кода числа процессоров в блок управления поступает код числа необходимых для выполнения заданий процессоров, Блок управления сравнивает потребное число процессоров с количеством свободных процессоров, данные о готовности которых хранятся в регистре готовности процессоров. Элемент ИЛИ сброса триггера вьдает сигнал, устанавливающий триггер в нулевое состояние, Блок управления вьдает по первому выходу сигнал записи кода числа необходимых для выполнения задания процессоров в регистр сдвигаОдновременно с этим по шинам номера задания на группы элементов И поступает код номера задания, а по шинам номера непосредственно предшест вующего задания подается код номера задания, непосредственно предшествующего данному. На регистрах номеров заданий хранятся коды номеров заданий, назначенных на соответствующие процессоры при предшествующих циклах работы устройства.После записи кода в регистр сдвига на выходах определенных групп элементов И появятся сигналы кода номера задания. Номер группы элементов И определяется совпадением единичных разрядов в регистре готовности и сигналов, вырабатываемых узлами сравнения, а также при совпадении одноименных единичных разрядов в ре. гистрах готовности процессоров и сдвига. С выхода каждой группы элементов И код йомера задания вьдается в соответствующий процессор и регистр номера задания, а через элемент ИЛИ первой группы обнуляет соот3 1100 б 23 ветствующие разряды регистров готовности процессоров и сдвига. Если при этов в регистре сдвига остались единичные разряды, о чем свидетельствует сигнал на выходе элемента ИЛИ 5 окончания распределения, то блок управления выдает в регистр сдвига импульсы сдвига.Если для выполнения задания потре буется количество процессоров, не превышающее число процессоров, завер шивших реализацию непосредственно предшествующего задания, то после определенного количества сдвигов кода в регистре сдвига все его разряды будут обнулены. При этом сигнал с первого входа блока управления снимается, Это означает, что задание распределено между теми процессора ми, которые завершили реализацию 20 непосредственно предшествующего задания. Если необходимое число процессоров превышает количество процессоров, 25 завершивших реализацию непосредственно предшествующих заданий, ть при сдвиге кода в регистре сдвига не все разряды будут обнулены. В этом случае выполняется второй этап рас- ЗО пределения задания на любой свободный процессор. Особенности его выполнения состоят в следующем. Единичный сигнал с выхода старшего разряда регистра сдвига устанав 35 ливает в единичное состояние триггер и через элемент ИЛИ объединения циклического переноса первый разряд регистра сдвига. После переключения40 триггера разрешающий сигнал поступает на входы группы элементов И и, обеспечивает их работу без учета сигналов с элементов И второй группы, Теперь при циклическом сдвиге45 кода в регистре код номера задания появится на выходах соответствующих групп элементов И при совпадении одноименных единичных разрядов толь. ко в регистре готовности и регистре сдвига, С выходов групп элементов И,50 код выдается в соответствующий процессор, а через элемент ИЛИ первой группы обнуляет соответствующие разряды регистра готовности процессоров и сдвига. При обнулении всех разрядов регистра сдвига сигнал с первого выхода блока управления снимается . Это означает, что задание распределено среди свободных процес- соров.Недостатком известного. устройства являются большие аппаратурные затраты, так как распределение заданий, требующих для своего выполнения процессоров конкретного типа, с помощью указанного устройства приводит к существенному увеличению числа этих устройств (по количеству типов процессоров в неоднородной вычислительной системе), т.е. к значительным затратам оборудования. Цель изобретения - сокращение аппаратурных затрат.Поставленная цель достигается тем, что в устройство для распределения заданий вычислительной системе, содержащее блок управления, регистр готовности процессоров, три элемента ИЛИ, регистр сдвига, группу блоков элементов И, две группы элементов И, две группы элементов ИЛИ, ре гистры номеров заданий, схемы сравнения, первую группу элементов И, триггер управления, причем первая группа входов каждой схемы сравнения подсоединена ко входам номера непосредственно предшествующего задания устройства, а вторая группа входов - к соответствующим выходам регистра номера задания, выходы каждой схемы сравнения подсоединены к первым входам соответствующих элементов И первой группы, ко вторым входам которых подсоединены соответствующие выходы регистра готовности процессоров, выход каждого элемента И первой группы подключен к первому входу соответствующего элечмента ИЛИ второй группы, ко второму. входу которого подключен выход триггера управления, выходы элементов ИЛИ второй группы подсоединены к первой группе входов соответствующего блока элементов И группы, выход второго элемента ИЛИ подключен к нулевому входу триггера управления, вход кода числа процессоров устройства подключен ко входам второго эле мента ИЛИ, информационным входам регистра сдвига и к первой группе входов блока управления, к управляющему входу которого подключен выход первого элемента ИЛИ, входы первого элемента ИЛИ подключены к выходам регистра 1 двига, выход синхронизации блока управления подключен к управ45 ляющему входу регистра сдвига, а выход сдвига блока управления подключен ко входу сдвига регистра сдвига, 1 -й выход которого (1где й - максимальное коли- - 5 чество процессоров в типе) подклю-.Эчен ко вторым входам блоков элементов И группы, к третьим входам которых подключенывыходы соответствующих разрядов регистра готовности, а к четвертым входам - вход номера задания устройства, выход третьего элемента ИЛИ подключен к единичному входу триггера управления, к выходам каждого блока элементов И Группы 15 подключены входы соответствующих элементов ИЛИ первой группы и входы регистров номера задания выходы каждого элемента ИЛИ первой группы подключены к соответствующим нулевым 20 входам регистра готовности процессоров, выходы номеров заданий устройства подключены к выходам соответствующих блоков. элементов И группы, к единичным входам регистра 25 готовности подключены входы состояния процессоров устройства, выходы регистра готовности подключены ко второй группе входов блока управления, выход которого соединен с выходом отказа устройства, введены дешифратор типа задания, вторая группа элементов И, группа элементов запрета, третья и четвертая группы элементов ИЛИ, выход каждого35 разряда регистра сдвига подключен к первому входу соответствующего элемента И второй группы и к ин- формационному входу соответствующего элемента запрета группы, к пятым входам группы блоков элементов И подключены соответствующие выходы дешифратора типа задания, ко входу которого подключен вход типа задания устройства, выходы дешифратора подключены к группе входов типа задания блока управления и через элементы ИЛИ четвертой группы - ко вторым входам соответствующих элементов И второй группы и к запрещающим входам соответствующих элементов запрета группы, выходы которых подсоединены к группе входов третьего элемента ИЛИ, выход которо. го подключен ко входу записи в млад" ший разряд регистра сдвига, выход-го элемента И второй группы подключен ко входу записи в старший раз ряд регистра сдвига, выход каждого элемента ИЛИ третьей группы подключен соответственно к нулевому входу каждого разряда сдвига, выход-го элемента ИЛИ первой группы подклю - чен ко входу 1 -го элемента ИЛИ третьей группы, выход старшего разря да регистра сдвига подключен ко входу третьего элемента ИЛИ, причем блок управления содержит схему сравнения, группу блоков элементов И, элемент И, элементы ИЛИ, элемент НЕ, триггер, генератор одиночных импульсов, генератор импульсов, элемент задержки, первая группа входов блока управления подключена к первой группе входов схемы сравнения, ко второй группе входов которой подключены выходы элеменВтов ИЛИ, ко входам-го элемента ИЛИ подключены 1 -е выходы каждого блока элементов И группы, к первым входам, 1 -го блока элементов И группы подключена группа входов типа задания блока управления, ко вторым входам блоков элементов И группы подключена вторая группавходов блока управления, выход схемы сравнения подключен к единичному входу триггера, к нулевому входу которого подключен выход элемента НЕ, вход которого соединен с управляющим входом блока управления, нулевой выход триггера подключен к управляющему выходу блока управления, а единичный выход триггера - ко входу генератора одиночных импульсов и к первому входу элемента И; ко второму входу которого подключен выход генератора импульсов, выход элемента И подсоединен через элемент задержки к выходу сдвига блока управления, выход генератора одиночных импульсов подсоединен к выходу синхронизации блока управления.На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема блока управления.Устройство содержит блок управления 1, регистр 2 готонности процессоров, первый элемент ИЛИ 3, регистр 4 сдвигагруппу блоков элементов И 5, первую группу элементов ИЛИ 6, выходы 7 номеров заданий устройства вход 8 кода числа процессоров устройства, вход 9 номера задания устройства, выход 1 О отказа устройства, регистры 11 номеров заданий,. схемы. сравнения 12, первую группу элемен25 При поступлении кода числа про 55цессоров элемент ИЛИ 16 вьдаетсигнал, устанавливающий триггер 15в нулевое состояние, при которомуправляющие сигналы с выходов элетов И 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 типа заданиявторую группу входов 4 1.Устройство работает следующимобразом.Распределение заданий вычислительной системы с учетом типа поступившего задания и информационно-управляющих Связей между ними в общем 30случае включает два этапа. На первомэтапе выполняется поиск процессоровзаданного типа, соответствующеготипу поступившего задания, и завершивших выполнение задания, непосредственно предшествующего данному.Если таких процессоров меньше, чемэто необходимо для выполнения поступившего задания, осуществляется втоР.ой этап Распределениями на которо 40заданию вьделяются недостающие свободные.процессоры требуемого типа.На.первом этапе работы в устройство поступают по входам 9 и 24соответственно номер и тип задания,по входу 8 - код числа процессоров,необходимых для выполнения задания,а по входу 18 - код номера задания,непосредственно предшествующегоданному. На регистрах 11 хранятсякоды номеров заданий, назначенныхна соответствующие процессоры припредшествующих циклах работы. ментов И 13 подаются на входы соответствующих элементов И 5. Дешифратор 23 расшифровывает тип поступившего задания и на-м выходе его появляется сигнал, который через соответствующие элементы ИЛИ 22 поступает на управляющие входы 11 -1 элементов И 21 и элементов запрета 20. Сигнал с 1 -го выхода дешифратора обеспечивает вьдачу информации с соответствующих разрядов регистра 2 готовности на вторую группу входов схемы сравнения 28 блока 1 управления, а также подготовку к работе блоков элементов И 5, соответствующнх процессорам требуемого типа Если число свободных процессоров требуемого типа меньше числа потребных, схема сравнения сигнал не вьдает, поэтому на выход 10 устройства поступает единичный. сигнал отказа с инверсного выхода триггера 29, свидетельствующий о невозможности выполнения задания. Если число свободных процессоров требуемого типа не меньше, чем необходимо для выполнения задания, схема сравнения 28 вьдает сигнал, устанавливая триг гер 29 в единичное состояние. При переключении триггера 29 в единичное состояние вьдается сигнал на запуск генератора одиночных импуль сов 30 и на управляющий вход элемента И 32. Генератор одиночных импульсов 30 вьдает на выход 37 блока 1 управления сигнал записи кода,поступающего по входу 8 в регистр 4 сдвига.Предположим, что потребное коли чество процессоров отражается в коде на шинах 8 количеством единиц в соответствующих разрядах. Тогда после записи кода в регистр 4 сдвига на выходах определенных блоков элементов И 5 появятся сигналы кода номера задания,.Номер блока элементов И 5 определяется совпадением кода, хранящегося на регистрах 11, и кода поступившего по входу 8, совпадением одноименных единичных разрядов в1регистрах 2 и 4, а также совпадением типа процессора и типа поступившего задания. С выхода каждого блока элементов И 5 код номера задания вьдается на выходы номеров заданий устройства и регистр номера задания 11.1Через элемент ИЛИ 6 код номера задания обнуляет соответствующие разрядырегистра готовности 2, а через эле менты ИЛИ 19 - соответствующие разряды регистра 4 сдвига, Если при этом в регистре 4 сдвига остались единичные разряды, о чем свидетельст вует сигнал на выходе элемента ИЛИ 3, то генератор импульсов 34 выдаетпо шине 38 в регистр 4 импульсы сдвига. Информация с выходов регистра 4 через элементы И 21 поступает на входы записи в старшие разряды регистра 4. и записывается в него со сдвигом при поступлении очередного импульса сдвига. Сдвиг информации происходит в пределах такого количества разрядов, 15которое соответствует максимальному количеству процессоров выбранного типа, и определяется сигналом с выхода дешифратора 23. После определен ного количества сдвигов кода в ре гистре 4 все разряды будут обнулены, если необходимое количество процессоров не превышает количества процессоров заданного типа, завершивших выполнение непосредственно предшествующего задания, При этом сигнал с выхода элемента ИЛИ 3 снимается, а на выходе элемента НЕ 31 появляет. ся и сбрасывает триггер 29 в нулевое состояние. Это означает, что за дание распределено между выбранными процессорами.Если необходимое число процессоров превышает количество процессоров заданного типа, завершивших выполнение непосредственно предшествующего задания, то при сдвиге кода в регистре 4 не все разряды будут обнулены. В этом случае выполняется второй этап распределения зада ния на любой свободный процессор заданного типа. Особенности его выполнения состоят в следующем.Единичный сигнал с выхода раз- ряда регистра 4, соответствующего на 45 ибольшему номеру процессора заданно-, го типа, поступает на информационный вход элемента запрета 20. Но поскольку на запрещающем входе этого элемента запрета 20 сигнал с выхода дешифратора 23 равен нулю, то на выходе элемента запрета 20 появляется единичный сигнал, который поступает на вход элемента ИЛИ 17. Этот сигнал циклического переноса из,текущего старшего разряда регистра 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 рублей.1100623 Составитель А. ГанитулВолощук Техред С. Легеза орректор И Ред 45 одписное 4 илиал ЛПП "Патент", г. Ужгород, ул, Проек 37 ТираНИИПИ Государпо делам изо 035, Москва,699 венного коми етений и от 35, Раушска тета СССР рытий наб., д. 4/5