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

СОВЕТСКИХ ИСТИЧЕСНИХ ЛИН СОЮСОЦИА сп 9) 9 46 Со 2 ИСАНИЕ ИЗОБРЕТЕНИ СВИДЕТЕЛЬСТВУ А ВТОРСНО(56) Ав У 95908Автор 7 0658Фет Я ры для Энергои тво СССР 1983,о СССР 6, 1984. процессо- М,:орское свидетелькл. С 06 Р 9/4 ское свидетельст 6, кл. С 06 Г 9/И, Параллельны правляющих систе дат, 1981, с, 99 в,ОСУДАРСТВЕННЫИ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относится к области вычислительной техники и можетбыть использовано при организациипакетной обработки в ЭВМ, а такжев устройствах, предназначенных длярешения задач теории расписаний вспециализированных процессорах, Целью изобретения является повышениебыстродействия устройства для распределения задании за счет того,что в предлагаемом устройстве накаждом шаге его работы могут одновременно распределяться четыре задания, Для этого в соответствии салгоритмом Джонсона все задания, разбираются на две группы. 1-ю. группусоставляют задания, у которых суммарное время ввода и решения меньше либо равно суммарному временирешения и вывода, 2-ю группу - задания, у которых суммарное времярешения и ввода больше суммарноговремени решения и вывода, Тогда накаждом шаге работы устройства естьвозможность распределять: два задания из 1-й группы (с минимальными максимальным временем ввода и решения); два задания из 2-й группы(с максимальным и минимальным временем решения и вывода), Устройство содержит две группы регистрогруппу блоков сравнения, группуэлементов И, элемент И, блок регистров, группу элементов ИЛИ, два блока поиска экстремальных кодов, элемент задержки. 5 ил.Иобретение относит( я к вычиспительной технике и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах, предназначенных для решения задач теории расписаний в специализированных процессорах.Цель изобретения - повышение быстродействия устройства путем обеспечения одновременного распределениячетырех задач на каждом шаге работыу:тройства,Устройство ранжирует задания впакете с учетом суммы времени вводаи решения задачи и суммы времени решения и вывода результатов в соответствии с алгоритмом Джонсона, причем на каждом шаге работы вочередь на обслуживание ставятсячетыре задачи.На фиг, 1 приведена структурнаясхема предлагаемого устройства; нафиг, 2 - схема блока сравнения; нафиг, 3 - структурная схема блокапоиска экстремальных кодов; нафиг, 4 - схема ячейки матрицы блокапоиска экстремальных кодов;на фиг. 5 "блок формирования приоритетов.Устройство для распределения заданий содержит регистры 1 -1 первой группы, регистры 1, -1второйгруппы, блоки 2, -2сравнениягруппы, элементы ИЛИ 3 -3, группы,элементы И 4-4 т, группы и блоки5 и 5 поиска экстремальных кодов,элемент И 6, элемент 7 задержки,блок 8 формирования приоритетов,входы 9 и 10,Блок 2 сравнения содержит элементы ИЛИ-НЕ 11, -11 щ (та - разрядностькодов временных на первой, второйгруппе регистров), узлы 12 - 12 Панализа разрядов, которые состоятиз узлов 13, 13,13 щ поразрядного переноса включающих в свойсостав элементы И 14 и элементыИЛИ 15, элемент НЕ 16, элемент И 17,выходы 18 и 18, входы 9 , 191, 19;, 19, 19, 19,.Блок 5 поиска экстремальныхкодов содержит ячейки 20,40 45 50 55 5 10 15 20 25 30 35 Ъ2 ,т 1, трппу нходовЯчейка 20 блока поиска экстремальных кодов 5 включает элементИ 30, элемент ИЛИ 31, элемент И 32,элемент ИЛИ 33, элемент НЕ 34, элемент И 35, элемент ИЛИ 36, элементИ 37, элемент ИЛИ 38, входы 39 - 45,выходы 46 - 51,Блок 8 содержит группы элементовИ 52 н5252, 52 5 2 э52 , 52, 52, элементыИЛИ 53 - 53 группы, счетчик 54,группы блоков элементов И 55 н,55 пф 55 еф5 Ъи 55 м55 и55455, блоки элементов ИЛИ56 - 56 группы, регистры 57, ,, 57 группы, входы 58 и 59, группывходов 60 - 60 61 - 61, 6262, 63, - 63 д, группы выходов 6464 и и 6565 пУстройство работает следующимобразом,В исходном состоянии на регистрыя 1 ф 1 и 1 1 ф ф 1 заноч ялсятся коды, пропорциональные суммевремени ввода и решения задачи исумме времени решения задачи и вывода результатов решения. Регистры57, установлены в нулевое состояние.На вход 9 подается низкий потенциали тактовые импульсы, поступающие навход 10, не проходят через элементИ 6, Коды чисел, записанных на регистрах 1и 1, (с инверсных вы"ходов), подаются на блок 2; сравнения ( = 1 . п),Блок 2 сравнения работает следующим образом,На входы 1919 подаетсякод числа с регистра 1;, а на входы19 д,.,19- код числа с регистра1 , В первый момент с помощью узла12 анализа разрядов анализируются старшие разряды кодов. Если старшие разряды обоих кодов равны нулю,то на выходе элемента ИЛИ-НЕ 11 т появляется высокий потенциал, которыйчерез элемент ИЛИ 15 поступает напервые входы элемента И 14, обеспечивая прохождение кодов на следующийузел 121 анализа разрядов, которыйработает аналогичным образом. Еслистаршие разряды обоих кодов равныединице, то на выходе элемента ИЛИНЕ 11 появляется низкий потенциал.Высокий потенциал с входов 19 н, 19через элементы ИЛИ 15 узлов 13 и13 поразрядного переноса поступагет на первые входы элементов И 14,разрешая кодам проходить на следующий узел 12 г анализа разрядов,Если старший разряд первого числаравен единице, а второго числа -нулю, то на выходе элемента ИЛИ-НЕ11 появляется низкий потенциал,который подается на первые входыэлементов ИЛИ 15 узлов 13 и 13На второй вход элемента 15 узла13, подается высокий потенциал, Навыходе этого элемента появляетсявысокий потенциал, который подаетсяна первые входы элементов И 14, разрешая прохождение остальных разрядов первого кода для анализа наузел 12 г, Второй код не поступаетна узел 12 г так как на входы элемента ИЛИ 15 узла 13, поступаютнизкие потенциалы. Если код числа,подаваемого на входы 19, (=1,и) больше кодачисла, подаваемогона вход 19 г, (1 с=1,ш) то высокийпотенциал появляется на выходе 18,если же меньше, то на выходе 18 г,При равенстве кодов высокие потенциалы появляются на выходах элементов 14 узлов 13 , и 13,. С выхода18 этот сигнал подается на элементНЕ 16, на выходе которого формируется низкий потенциал, который подается на первый вход элемента И 17,На выходе 18 г формируется низкийпотенциал, Таким образом, если код,записанный на регистре 1 меньше илибо равен коду, записанному на регистре 1 , то высокий потенциал пог(является на выходе 18 если больше - то на выходе 18 г,Блоки 5 и 5 г поиска экстремальных кодов производят выделение строкс минимальным и максимальным кодами из множества кодов, поступающихиз регистров 1 1 1 , . 1 .Блоки поиска экстремальных кодов 5,и 5 г представляют собой специализированные однородные процессоры,ориентированные на поиск максимального и минимального кодов.Блоки 5 и 5 г выполнены в видематрицы ячеек 20 одинаковой структуры, содержащей п строк и 2 х шстолбцов. Коды времени с -х регистров 1 и 1 г поступают на входы 271( г(1-х строк матрицы блоков 5 и 5причем код регистра 1поступаетна входы 27 ячеек. 20, 20; бло 283764 4ка 5 и входы 27 ячеек 20; 120;( блока 5, код регистра 1,поступает на входы 7 ячеек 201.20( 1 блока 51 и входы 27ячеек 20,.., , 20; блока 5На входы 24 и 25 ячеек первойстроки подаются граничные значения,равные "0", На входы 26 ячеек первого столбца блока 5, подключены О выходы 18 блоков 2; сравнения,на входы 26; ячеек первого столбца блока 5 - выходы 18 г блоков 2;сравнения.В блоках 5 просмотру на максимум(минцмум) подлежат те строки, которые содержат значения "1" на входе26, Таким образом, в блоке 5 просмотру подлежат г.-е строки, соответствующие 1.-м заданиям, у которыхсуммарное время ввода и решения 20 меньше (равно) суммарному временирешения и вывода, а в блоке 5наоборот.Каждая ячейка 20блока 5 содержит независимые каналы поиска максимума и минимума, Канал поиска максимума каждой ячейки включает элементы И 30, ИЛИ 31, И 32, ИЛИ 33 и входы 40 и 41, на которые поступают30 сигналы переноса от ячейки 20(,вход 44, на который поступает сигнал переноса от ячейки 20;(вход 43, на который поступает значение -го разряда х-го кода, выходы 49 и 50, с которых сигналы переноса поступают на входы ячейки201+ следующей строки, выход 46,с которого сигнал переноса поступает на вход ячейки 201 следующе 40 го столбца.Канал поиска минимума аналогиченканалу поиска максимума за исключением того, что в нем используетсяинверсное значение 1-го разряда г.-го45 кода (для получения инверсного значения используется элемент НЕ 34),Таким образом, минимум ищется какмаксимум среди инверсных (обратных)кодов,50 В каждом столбце устройства просмотру на максимум (минимум) подлежат ячейки, на входе 44 (45) которых значение сигнала равно , Навыходе 46 (47) "1" появляется только55 тогда, когда 3-й разряд д-го кодаравен "1" ("О). Для передачи значения "1" в случае, когда все 1-еразряды кодов содержат 0" (" 1"),выходы 50 и 51 ячеек последней-й5строки через элементы НЕ 2(21 ) соединены с входами 39 (40) ячеек первой строки. При появлении на выходе элементов НЕ 21 (21 г ) высог кого потенциала обеспечивается перенос " 1" с входа 44 (45) на выход 46 (47) в том случае, если 1-е разряды кодов содержат "О" ("1").На выходе 46 (47) ячеек последнего столбца " 1" устанавливается в тех строках, которые содержат максимальное (минимальное) число, Высокий потенциал появляется на тех выходах 28 блоков 5, которые соответствуют строкам с минимальными кодами, а также на тех выходах 29 блоков 5, которые соответствуют строкам с максимальными кодами.В случае, если минимальное число равно максимальному (т,е, когда в блоке 5 анализу подлежит только одно число), для исключения одновременного появления сигналов на выходе 28; и 29 блока 5 в каждую строку введены элементы НЕ 22; и И 23, В этом случае высокий потенциал на выходе 28, через элемент НЕ 22; и элемент И 23; устанавливает низкий потенциал на выходе 29; . Работа устройства начинается сподачи на вход 9 высокого потенциала, Первый тактовый импульс черезэлемент И 6 поступает на вход элемента 7 задержки и в блок 8 регистров, где записывается "1" по входу59 в счетчик 54,Пусть на регистре 1 (1=1,п)находится код числа, который меньшеили ранен коду на регистре 1 г Вэтом случае высокий потенциал появляется на первом выходе 1-го блокасравнения и поступает на первый вход1-го элемента И 4 группы,С прямого выхода регистра 1 ш -разрядный код времени поступает навходы элементов ИЛИ 3,. Если на регистре 1, бып нулевой код, то навыходе элемента ИЛИ 3, имеется низкий потенциал, который поступает навторой вход элемента И 4,. Низкийпотенциал с выхода последнего поступает на вход 26; блока 5, и 1.-ястрока с нулевым кодом не участвует в просмотре на максимум (минимум)Хотя коды с регистров 1,; и 1 гпоступают на входы блоков 5, и 5 гв блоке 5 просмотру на максимум2837 64 6коды, для которых суммарное. времяввода и решения э адания меньше илиравно суммарному времени решенияи вывода, а в блоке 5 - задания,решения и вывода,10 15 40 45 50 ф 55 20 25 30 35 для которых суммарное время вводаи решения больше суммарного времени выводов 28, (1=1п) блока 5, сигналы подаются на входы 60, блока 8, с выходов 29; блока 5, на входы 61; блока 8, с выходов 28; блока 5 г - на входы 62; блока регистров, с выходов 29; блока 5 - на входы 63; блока 8.Пусть в блоке 5, ьжнимальный и максимальный коды находятся в строках 1 и соответственно, а в блоке 5 - в строках Ь Ь, Тогда высокие потенциалы формируются на выходах 28 и 29 блока 5 и выходах 28 и 291, блока 5 гкоторые передаются на входы 60 р 61 62 63 блока регистров и дальше на вторые входыэлементов И 52152 г 5252 ц 1,фС приходом тактового импульса с элемента 7 задержки на вход 58 и входы элементов И 52 (тактовый импульс в элементе задержки задерживается на время срабатывания счетчика 54) на выходах элементов И 52 52 52 1, 521, появляется импульс, который открывает блоки элементов И 55, 55 г 55521 Каждый блок элементов И 55 состоит из (1+1) элементов И (Ы - разрядность счетчика 54).По второму входу блоки элементов И 55 соединены с выходами счетчика 54 (первые 1 элементов И) и с шинами высокого или низкого потенциала (1+ 1)-й элемент И), причем группа блоков элементов И 55 п,55, соединена с прямым выходом счетчика и шиной низкого потенциала, группа блоков элементов И 55 г,.55 с инверсным выходом счетчика 54 и шиной низкого потенциала, группа блоков элементов И 55 н553 а с инверсным выходом счетчика и шиной высокого потенциала, группа блоков элементов И 5541,55 - с прямком выходом счетчика и шиной высокого потенциала, С выходов блоков элементов И 55,55,55,55,1,коды с выходов счетчика и шин высокого или низкого потенциала через блоки элементов ИЛИ 56 (каждый блок ИЛИ 56; включает (1+1) элементов ИЛИ) поступают на входы регистров 57, с выходов элементов 52,52 г,52;524,импульс поступает на входы элемента ИЛИ 53, с выхода которого он направляется на входы синхронизации регист ров 57 и через выход 65; блока регистров на входы сброса триггеров 1, и 1 г,Таким образом, если на входах 60, 61, 621 631, блока 8 были высокие потенциалы, то коды заносятся на регистры 57, 57, 57, 57 и обнуляют ся р е Ги стры 11 р1 гр 1р 1 г 11 Ьф 1 гЬф 1 ье 1 гьС приходом второго тактового импульса анализируется содержимое остальных регистров 1, Регистры 1, и 1;, установленные в нулевое состояние, на работу устройства влияния не оказывают, так как, хотя на первом выходе блоков сравнения 2; и появляется высокий потенциал, он не проходит через элемент И 4; на вход блока 5,. Устройство заканчивает свою работу после присваивания номеров всем заданиям пакета, На обслуживание задания выбираются по минимальному коду на регистрах 57. Формула изобретения Устройство для распределения заданий процессорам, содержащее первую, вторую группы регистров, группу блоков сравнения, группу элементов И, элемент И, блок формирования приоритетов, причем группа инверсных выходов х"го 1=1 и; п - число заданий) регистра первой группы со" единена с первыми входаьж 1-го блока сравнения группы, вторые входы которого соединены с инверсными выходами 1-го регистра второй группы, выход "Больше" или "Равно" 1"го блока сравнения группы соединен с 1283764 8первым входом 1.-го элемента И группы, выход элемента И подсоединен куправляющему входу блока формирования приоритетов, выход которого подсоединен к входам сброса регистровпервой и второй групп, тактовыйвход и вход запуска устройства соединены соответственно с первым и вторым входами элемента И, о т л и -10 ч а ю щ е е с я тем, что, с цельюповышения быстродействия устройства, в него введены группа элементов ИЛИ, первый, второй блоки поиска экстремальных кодов, элемент за 15 держки, причем прямые выходы 1-горегистра первой группы соединены свходами 1-го элемента ИЛИ группы,выход которого соединен с вторымвходом 1-го элемента И группы, пря 20 мые выходы регистров первой и второйгрупп подсоединены к первой группевходов первого и второго блоковпоиска экстремальных кодов, втораягруппа входов первого блока поиска25 экстремальных .кодов нодсоединена квыходам элементов И группы, втораягруппа входов второго блока поискаэкстремальных кодов подсоединена квыходам "Меньше" блоков сравнения30 группы, первая и вторая группы выходов первого блока поиска экстремаль"ных кодов подключены к первой и второй группам инФормационных входовблока формирования приоритетов соотЗ 5 ветственно, первая и вторая группывыходов второго блока поиска экстремальных кодов подсоединены к третьейи четвертой группам информационныхвходов блока формирования приорите 40 тов, выход элемента И соединен свходом элемента задержки, выход которого соединен с входом записи блока формирования приоритетов.62 Заказ 7443/ ПодписноеСР Тираж 670 ударственного комитета изобретений и открыти ва, Ж, Раушская на ВНИИПИ Го по делам13035, Моск