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

)детельство ССР 9/00, 1980 тельство СССР 6 Р 9/00, 198 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО РАСПРЕДЕЛЕНИЯ ЗАДАНИЙПРОЦЕ ССОРАМ(57) Изобретение относится к вычислительной технике и может быть использовано для распределения заданий аппаратным путем в многопроцессорныхвычислительных системах. Цель изобретения - повышение быстродействия устройства. Устройство содержит регистрготовности процессоров, два блокаэлементов И, регистры, схемы сравнения, четыре группы элементов ИЛИ,дешифратор типа задания, блок сравнения, два блока коммутации, группуэлементов И, группу элементов запреа, элементы ИЛИ, элемент задержки,исходном состоянии в устройство эа несена информация о готовности про". цессоров системы и о заданиях, назначенных на процессоры в предыдущих циклах работы устройства. Инициализация устройства осуществляется подачей на .его входы кода номера задания, кода типа задания, количества требуемых процессоров, кода номера задания, непосредственно предшествующего данному. Если требуемое число процессоров превышает количество готовых процессоров данного типа, имеющихся в системе, происходит отказ в распределении задания. В про-. тивном случае осуществляется распре" деление задания по процессорам, причем поступившее задание распределяется по процессорам необходимого типа, завершившим выполнение задания, непосредственно предшествующего данному, и если количество таких процессоров окажется недостаточным, рас пределение задания осуществляется по любым готовым процессорам данного типа. 2 ил.Устройство относится к вычислительной технике и может быть найтиприменение в вычислительных системахдля распределения заданий между процессорами,Цель изобретения - повьппение быстродействия устройстваНа фиг, 1 и 2 представлена структурная схема устройства.Устройство распределения заданийпроцессорам содержит группу регистров 11 - 1 номеров заданий (где Еш - общее число процессоров в1 ссистеме ш, - число процессоров -готипа, п-число типов процессоров),группу входов 2 номера непосредственно предшествующего задания устройства, группу схем 3 -3 сравнения 1группу элементов ИЛИ 4-4 , группуэлементов И 5 -5 , группу элементов6 -6 , запрета, группу элементов ИЛИ7-7, группу блоков элементов И 88 , регистр 9 готовности процессоров,нулевые входы 10 -1 О регистра готов 1ности процессоров устройства, элемент ИЛИ 11, группу входов 121 в 12,кода числа процессоров устройства,группу входов 13 типа задания устройства, группу входов 14 номера задания устройства, первую группу входов15, -15 блока сравнения, вторую группу входов 16 -16блока сравнения,блок 17 сравнения, первый 18 и второй 18 блоки коммутации, регистр 19числа йроцессоров дешифратор 20,группу информационных входов 21первого блока коммутации, группы управляющих входов 22 первого и второго блоков коммутации, первую группувыходов 23,-23 первого блока коммутации, вторую группу выходов 24-24первого блока коммутации, элементИЛИ 25, элемент 26 задержки, группуэлементов ИЛИ 27, регистр 28 назначенных процессоров, группу блоковэлементов И 29-29 группу выходов30 второго блока коммутации группуэлементов ИЛИ 31,-31, группу выходов 32,-32номера заданий устройства, входы 33 и 34 узлов блока сравнения, выходы 35 и 36 узлов блокасравнения, узлы 37,-37блока сравнения, элемент ИЛИ 38, элемент 39задержки, элемент И 40, элемент НЕ 41,группу элементов НЕ 42, группу элементов И 43, группу элементов ИЛИ 44,шинч 45 логического нуля блока срав 1 О 15 20 25 30 35 40 45 55 нения, выход 46 отказа устройства,узлы 47 блока коммутации, шину 48логического нуля блока коммутации,входы 49-51 узлов блока коммутации,вьгходы 52-54 узлов блока коммутациивход.55 сброса регистра назначенныхпроцессоров устройства, элементИЛИ 56 узла блока сравнения, элементНЕ 57, элемент ИЛИ 58, элементы И 59и 60 элемент ИЛИ 6 узла блока коммутации, элемент И 62 узла блокасравнения,Устройство работает следующим образом,1Распределение заданий вычислительной системе осуществляется с учетом типа поступившего задания и информационно-управпяющих связей, Еслидля выполнения поступившего заданиятребуется больше процессоров определенного типа, чем имеется свободныхпрэцессоров этого типа в данный момент в системе, задание снимается собслуживания, если же требуетсяменьше процессоров, чем имеется всистеме, осуществляется назначениепроцессоров для выполнения этогозадания, причем сначала назначаются процессоры, закончившие выполнение задания, непосредственно предшествующего данному, и, если приэтом потребности . задания в процессорах не будут удовлетворены, осуществляется назначение процессоровданного типа иэ числа оставшихся дополного удовлетворения потребностейзадания в процессорах,В результате этого на вход элементов ИЛИ 7 -7 поступает информация оготовности процессоров -го типа,имеющихся в системе. При этом сигналсостояния первого процессора -го типа поступает на вход элемента ИЛИ 7,второго - на вход элемента ИЛИ 7 ит,д, Вследствие этого появляются единичные сигналы на выходах тех элементов ИЛИ 74 -7 п, которые соответствуютсвободным процессорам 1-го типа. Далее эти сигналы поступают на первуюгруппу входов 15, - 15 блока сравнения,В блоке 17 сравнения осуществляется сравнение числа процессоров,необходимых заданию, с числом свободных процессоров 1.-го типа, име"ющихся в системе,В общем случае состояние процессолав отражается комбинацией нулей и50 единиц, например 01101 для пяти процессоров означает: первый и четвертый процессоры заняты, что соответствует нулю в регистре готовности, второй, третий и пятый процессоры готовы - для них соответствующий разряд регистра готовности установлен в единичное состояние. Необходимое количество процессоров для задания 10 -го типа отражается количеством единиц в разрядах кода начиная с левого первого, Например, комбинация 11110 означает, что заданию требуется четыре процессора, 15Блок 17 сравнения осуществляет преобразование вектора состояния процессоров 1-го типа, т,е. код 01101(для нашего примера) преобразуется в код 11100, характеризующий только .количество готовыхпроцессоров -го типа.Далее осуществляется сравнение кодов.Таким образом, на входы 15, - 15 блока 1 сравнения подается вектор состояния процессоров -го типа. Ос нову блока сравнения составляет итеративная сеть, состоящая из матрицы узлов 37-37 . Узлы сети идентичны- и состоят из элементов И и ИЛИ(фиг,1),С входов 15-15 сигналы поступают на входы 33 узлов первого столбца матрицы, Входы 34 узлов 37, -37 первой строки матрицы подключены к входу 45 блока, который, в свою очередь, подключен к источнику нулевого сигна 35 ла, Таким образом, на первый вход элемента И 62 узла 37 и на второй1вход элемента ИЛИ 56 этого же узла подается нулевой сигнал.Если на вход 15 блока 17 сравнения подается единичный сигнал готовности первого процессора -го типа, то этот сигнал поступает на первый вход элемента ИЛИ 56 и на второй вход элемента И 62 узла 37 , На выходе145 35 этого узла присутствует нулевой сигнал переноса в горизонтальном направлении, который поступает на вход 33 узла 37, далее - на вход 35 этого узла т,д а на выходе 36 узла 37, возникает единичный сигнал11переноса в вертикальном направлении, который, пройдя через все элементы ИЛИ 56 первого столбца, появляется на выходе 36 узла 3755Если на входе 15 блока также при 1сутствует единичный сигнал, то он поступает на вход 33 узла 37 Элемент И 62 этого узла открыт по первому входу единичным сигналом, поступающим с, входа 34 этого узла, итогда на выходе 35 узла 37 появля 21 фется единичный сигнал переноса в горизонтальном направлении, который поступает на вход 33 следующего узла37 . Так как на входе 34 этого узлаприсутствует нулевой сигнал переноса с узла 37 , то на выходе 35 узла37 будет нулевой сигнал переноса,С входа 33 узла 37 единичный сиг 22нал поступает на первый вход элемента ИЛИ 56 этого узла, далее на выход 36 этого узла, проходит черезвсе элементы ИЛИ 56 узлов 37 -37г фвторого столбца и появляется на выходе 36 узла 37,Таким образом, на выходах 36 узлов 37 последней строки получаем преобразованный вектор состояния процессоров, все единицы которого сдвинуты к левой границе, причем числосвободных (готовых) процессоров отражается количеством единиц в преобразованном векторе.Этот вектор поступает на входысоответствующих элементов НЕ 42-42группы, инвертируется и подается напервые входы соответствующих элементов И 43 -43 , На входы этих элементов подается код числа процессоров,необходимых заданию. Причем необходимое число процессоров также отражается количеством единиц в коде,все единицы которого сдвинуты к левой границе (например, код 1111110000означает, что заданию требуетсяшесть процессоров),Элементы И 43 -43 осуществляютпоразрядное сравнение кода числа готовых процессоров с кодом числа процессоров, необходимых заданию. Еслиготовых процессоров больше, чем требуется заданию, то на выходах всехэлементов И 43 -43 присутствуетнулевой сигнал и, как следствие, навыходе последнего элемента ИЛИ 44 также нулевой сигнал,Аналогичная ситуация складываетсяи тогда, когда число готовых процессоров равно числу необходимых процессоров, т,е. на выходе элемента ИЛИ 44присутствует нулевой сигнал.Если же число готовых процессоров1.-го типа в системе меньше, - чем этоготребует задание, то на выходе элемента ИЛИ 44 присутствует единичныйсигнал,1.32 710 бХ = Х(тч Е),у= уЕ = ХЯХУ,Сигнал с выхода элемента ИЛИ 44через элемент НЕ 41 поступает на второй вход элемента И 40, на первыйвход которого подается сигнал с элемента 39 задержки, время задержкипоследнего выбрано таким, чтобы успели завершиться переходные процессы на элементах блока сравнения,На выходе блока 17 появляетсяединичный сигнал в том случае, есличисло готовых процессоров -го типаравно или больше числа процессоров,необходимых заданию для его обработки. В противном случае на этом выходе появляется нулевой сигнал, 15Если процессоров достаточно длявыполнения задания, по переднемуфронту единичного сигнала с выходаблока 17 сравнения разрешается записькода числа необходимых процессоров 20с входов 12 - 12устройства на регистр числа процессоров 19,Единичными сигналами с выхода. регистра 19 числа процессоров черезэлемент ИЛИ 25 запускается элементзадержки, Сигналы с выходов регистра числа процессорон в то же времяпоступают на входы 21, -21 первогоблока коммутации 18 .На входы 22,-22 этого блока ком- ЗОмутации поданы сигналы с выхода. элементов И 5-5группы, Эти сигналыполучены следующим образом,Код номера задания, непосредственно предшествующего данному, посту- З 5пает на вход 2 устройства и далее подается на первые группы входов всехсхем сравнения 31-3 , на вторые группы входов которых с регистров номеров заданий поступают коды номеров 40заданий, назначенных процессорамисистемы на предыдущих циклах работьустройства,Сигналы с выходов схем сравненияпоступают на входы элементов ИЛИ 4- 45С выходов элементов ИЛИ 4 -4сигналы поступают на первые входы элементов И 5-5 , на вторые входы которых с регистра готовности подаются сигналы готовности процессоров1-го типа. Единичные сигналы возникают на выходе тех элементов И 5-5которые соответствуют готовым процессорам -го типа, завершившим выполнение задания, непосредственно предшествующему данному, Сигналы с выходов элементов И 5-5 подаются нанходы 22-22 блока 18 коммутации,В то же время выходы элементовИ 5 -5 подключены к .управляющимвходам элементов б, -б запрета, наинформационные вьгходы которых с регистра 9 готовности подаются сигналыготовности процессоров ь-го типа,Поэтому единичные сигналы присутствуют на выходах тех элементов запрета,которые соответствуют готовым процессорам 1-го типа, но не выполнявшимна предыдущем цикле работы задания,непосредственно предшествующего данному, С выходов элементов б -б запрета сигналы поступают на входы 2222 второго блока 18 коммутации,Таким образом, на входы 22-22первого блока 18 коммутации подаются сигналы готовности процессоров1-го типа, а. на входы 21-21 - кодчисла требуемых процессоров, которыйвыражается количеством единиц н коде,причем эти единицы сдвинуты к началу регистра.Блок 18 коммутации представляетсобой двумерную итеративную сеть, со.держащую тпхтп идентичных узлов 47,На входы 49 узлов первого столбцаматрицы подается с входов 21,-21коммутатора код числа необходимыхпроцессоров,На входы 50 узлов первой строкиматрицы подается с входов 22-22коммутатора вектор готовности процессорон т-го типа,Входы 51 узлов первой строки подключены к нходу 48 блока 18 коммутации, который, н свою очередь, подключен к источнику нулевого сигнала,Узел 47 коммутатора 18, представляет собой конечный автомат без памяти, Если обозначить сигналы на входах и выходах узла 47 следующим образом: 49-Х, 50-У, 51-2., 52-У, 53-Е, 54-Х, - тс система логических Функций, выполняемых узлом, имеет вид Из системы функций нидно, что узел обеспечивает распространение сигналон н двух напранлениях: снерху вниз и слева направо,Каждому процессору 1-го типа н блоке 181 коммутации соответствует столбец матрицы, а каждому необходимому процессору - строка матрицы, Наличие единичных сигналов па входах узла 471, означает: на входе 49 име 1327106ется 1-й запрос на готовый процессор;на входе 50 имеется -й готовый процессор. 25 5При совпадении единичных сигналов 1-го запроса на процессор, поступающего на вход 49 узла 47 , и сигнала готовности 3-го процессора происходит следующее. 10Элемент И 60 данного узла открывается, на его выходе появляется единичный сигнал, который через элемент ИЛИ этого узла появляется на выходе 53 узла. Далее этот сигнал распространяется через все последующие узлы данного стобца и выделяется на выходе 53 последнего узла столбца, Это означает, что 1-й процессор выбирается для выполнения задания, На выходе 54 узла 47 л присутствует нулевой сигнал, который распространяется в горизонтальном направлении и не может измениться до выхода из коммутатора, Этот сигнал означает, что запрос на готовый процессор удовлетворен.Таким образом, если заданию требуется К процессоров 1-го типа и в системе имеется ровно К готовых процессоров этого типа, причем все они завершили выполнение задания, непосредственно предшествующего данному, то все эти процессоры выделяются для выполнения этого задания, На выходах35 24 -24 присутствуют единичные сигналлы, соответствующие готовым процессорам, а на всех выходах 23-23 блока 18, коммутации - нулевые сигналы, означающие, что заданию выделено столь О ко процессоров, сколько оно затребовало.Если же в системе имеется процессоров 1-го типа, завершивших задание непосредственно предшествующее данному, больше чем это требуется заданию (большеК), то на выходах 23,-23, присутствуют нулевые сигналы, а на выходах 24,-24 - ровно К единиц, что означает: только К процессоров из всех готовых и завершивших вы-. полнение непосредственно предшествующего задания выделяются для выполнения поступившего задания.Если.же заданию требуется К про 55 цессоров 1.-го типа, а в системе имеется 8 процессоров этого типа (БЪ К), из которых только Р процессоров (Р К) завершили выполнение задания, непосредственно предшествующего данному,то устройство работает следующим образом.Блок 18 коммутации выделяет всеР процессоров для выполнения задания в соответствии с описанным выше.На выходах 23 -23 блока 18 коммута 1 1 п 1ции присутствуют единичные сигналы,означающие, что потребность заданияв процессорах удовлетворена неполностью и необходимо продолжать распределение задания на любые свободныепроцессоры данного типа, При этомединичные сигналы присутствуют навыходах 23 р 23 ,.,23 коммутатора 18, Эти сигналы поступают наответствующие входы 21 21 рф,.,21 блока 18 коммутации, На входах 22-22 этого блока присутствуютсигналы готовности процессоров -готипа, которые на предыдущем циклевыполняли задание, не являющеесянепосредственно предшествующим данному заданию, т,е, любых свободныхпроцессоров 1.-го типа,Таким образом, создаются условиядля работы блока 18 коммутации.Работа блока 18 аналогична работеблока 18 , поэтому на его выходах24 -24 появляются единичные сигналы, которые указывают, какие из любых свободных процессоров выделяютсядля выполнения задания, причем количество единиц на этих выходах равноразности К РТаким образом, осуществляется выделение необходимого заданию числапроцессоров,С выходов 24, -24 и 30-30 блоков сигналы поступают на входы элементов ИЛИ 27, -27 , Выходы элементов ИЛИ 27 -27 заведены на установочные входы регистра 28 назначенныхпроцессоров, В этот момент на выходеэлемента 26 задержки появляется единичный сигнал, который передним фронтом синхронизирует запись информациив регистр 28, Время задержки элемента 26 выбрано таким, чтобы успели завершиться переходные процессы в блоках коммутацииОдновременно с этим на выходе 46появляется единичный сигнал, озна"чающий, что на задание назначено требуемое число процессоров, Если в системе имеется готовых процессоров д-готипа меньше, чем требуется заданию,то единичный сигнал на выходе 20 бло 1327106 10ка сравнения не вырабатывается, врегистр 19 числа процессоров не записывается код числа процессоров и,как следствие, на выходе 4 б устройства остается нулевой сигнал, означающий невозможность выполнения задания.Сигналы с выходов регистра 28назначенных процессоров поступаютна третьи входы соответствующихблоков элементов И 29 -29 : с выхода первого разряда - на третьи входыблоков элементов И 29, соответствующих первым процессорам всех типов,с выхода второго разряда - на третьи входы блоков элементов И 29, со"ответствующих вторым процессорамвсех типов, и т.д,В то же время на вторые входывсех блоков элементов И 291 -291, подаются сигналы с соответствующйх выходов дешифратора 20 типа задания,Первый выход дешифратора 20 подключен к вторым входам блоков элементовИ 29, соответствующих процессорампервого типа, второй выход дешифратора 20 - к вторым входам блоков элементов И 29, соответствующих процессорам второго типа, и т.д,Таким образом, среди всех блоковэлементов И 29 -29 открытыми оказываются блоки, соответствующие темпроцессорам д-го типа, которые выделены для выполнения задания, Вследствие этого на соответствующих выходах32-321 устройства появляется кодназначаемого задания, который передается на соответствующие процессоры,Единичные сигналы с выходов соответствующих блоков элементов И 29-291,через элементы ИЛИ 31 -31 утанавливают в нулевое состояние соответствующие разряды регистра 9 готовностипроцессоров, сигналом с выхода элемента ИЛИ 11 обнуляется регистр числа процессоров. Кроме того, код задания, выдаваемый на соответствующиевыходы 321 -321 устройства, записывается в соответствующие регистры коданомера задания 1 - 1Когда все выбранные процессоры начинают выполнение задания, на вход 55устройства поступает сигнал, которыйустанавливает регистр 28 в нулевоесостояние, и вместе с этим с входов2, 12-12 , 13-1314-14 убираются соответствующйе коды, которыеотносятся к уже распределенному зада 10 15 20 25 30 35 40 45 50 55 нию, Устройство приводится в исходноесостояние. Очередной. цикл распределения заданий завершается. Формула изобретения Устройство распределения заданий процессорам, содержащее регистр готов ности процессоров, первую группу блоков элементов И, группу регистров номеров заданий, группу схем сравнения, первую группу элементов ИЛИ, дешифратор типа задания, причем первая группа входов каждой схемы сравнения груп. пы подключена к соответствующей группе входов номера непосредственно предшествующего задания устройства, а вторая группа входов каждой схемы сравнения группы соединена с группой выходов соответствующего регистра номера задания группы, группа выходов каждого блока элементов И первой группы соединена с группой входов соответствующего элемента ИЛИ первой группы, с группой входов соответствующего регистра номера задания группы, выход каждого элемента ИЛИ первой группы подключен к соответствующему нулевому входу регистра готовности процессоров, группа выходов номеров заданий устройства подключена к группе выходов соответствующего блока элементов И первой группы, группа единичных входов регистра готовности процессоров является группой входов состояния процессоров устройства, группа входов номера задания устройства подключена к группе входов соответствующего блока элементов И первой группы, к первому входу которого подключен соответствующий выход дешифратора типа задания, группа входов которого является группой входов типа задания устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок сравнения, первый и второй блоки коммутации, регистр числа процессоров, регистр назначенных процессоров, вторая группа блоков элементов И, вторая, третья и четвертая группы элементов ИЛИ, группа элементов И, группа элементов запрета, первый и второй элементы ИЛИ, элемент задержки, причем входы 1-го элемента ИЛИ второй группы соединены с 3-ми выходами каждого блока элементов И второй11 13 группы (1=1, ш; ш - число процессоров одного типа), группа выходов дешифраторов типа задания соединена с группой входов блоков элементов И второй группы, группа входов блока элементов И второй группы соединена с соответствующей группой выходов регистра готовности процессоров, выход 1-го элемента ИЛИ второй группы под. ключен к первому входу -го элемента И группы, к информационному входу -го элемента запрета группы, второй вход -го элемента И группы подключен к выходу 1-го элемента ИЛИ третьей группы, входы которого подключены к выходам схем сравнения -й группы, выход -го элемента ИЛИ второй группы подключен к 1-му входу первой группы входов блока сравнения, вторая группа входов которого является группой входов кода числа процессоров устройства и соединена с группой входов установки в единичное состояние регистра числа процессоров, выход "Больше или равно" блока сравнения подключен к входу записи регистра числа процессоров, группа выходов которого подключена к группе информационных входов первого блока коммутации и к группе входов первого элемента ИЛИ, выход 1-го элемента И группы подключен к управляющему27106 12 входу 1-го элемента запрета группыи к -му вкоду управляющих входовпервого блока коммутации, выход -гоэлемента запрета группы подключен к 51-му входу управляющих входов второго блока коммутации, группа информационных входов которого подключена кпервой группе выходов первого блокакоммутации, -й выход второй группывыходов первого блока коммутацииподключен к первому входу -го элемента ИЛИ четвертой группы, второйвход которого подключен к -му выхоДУ грУппы выходов второго блокакоммутации, выходы элементов ИЛИчетвертой группы подключены к группеинформационных входов регистра назначенных процессоров, вход записикоторого через элемент задержки подключен к выходу первого элементаИЛИ и является выходом отказа устройства, группа выходов регистраназначенных процессоров подключена к 25 вторым входам блоков элементов И первой группы, вход сброса регистра числа процессоров подключен к выходувторого элемента ИЛИ, группа входовкоторого подключена к выходам элементов ИЛИ первой группы, вход сбросаустройства подключен к входу установки в "О" регистра назначенных процессоров, 13210632710 б Составитель М. Сорочанедактор Л, Веселовская Техред Л.Сердюкова Корректор Г, Решетн Подписное За зводственно-полиграфическое предприятие, г, Ужгород, ул. Проектная,90/45 ВНИИПИ по 13035, Тираж б 72Государственного комитета СССРелам иэобретений и открытийосква, Ж, Раушская наб., д.