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

(2 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТМИ ПИСАНИЕ И 1) 3911362/24-24(56) Авторское свидетельство СССР В 548859, кл. С 06 Р 9/46, 1974.Авторское свидетельство СССР В 966697, кл. С 06 Р 9/46, 1982. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относится к вычислительной технике и может быть использовано при органиэации вычислительного процесса по обработке пакета или потока задач в многопроцессорной или многомашинной вычислительной системе. Целью изобретенияявляется повышение быстродействия.Устройство содержит элементы И, ИЛИ,блок элементов ИЛИ, группы по числузадач в пакете двух элементов И,элементов ИЛИ-НЕ, регистров, счетчиков, элементов НЕ, элементов задержки и блоков элементов И с соответствуюп 1 ими связями, Устройство, кромераспределения фиксированного пакетазадач по критерию минимума среднеговремени решения задач или минимумасреднего времени пребывания в пакете, может распределять поток задачпо процессорам вычислительной системы по критерию минимума среднеговремени пребывания в очереди на обслуживание. 1 ил.1 1290322 2 Изобретение относится к вычисли- на одном из них (например, 1 -м,тельной технике и может быть исполь =1, , п) не зафиксируется кодзовано при организации вычислительного процесса по обработке пакетаили потока задач в многопроцессорной или многомашинной вычислительной системе.Цель изобретения - повышениебыстродействия.На чертеже представлена структурная схема устройства для распределения заданий процессорам.Устройство содержит группу регистров 1 , , 1, где п-максимальное число заданий в пакете (очереди), группу вычитающих счетчиков2 , 2, группу триггеров 3Згруппу элементов И 4,4, группу блоков элементов И 55, группу элементов задержкиб , б, группу элементов ИЛИ-НЕ7 , 7, группу элементов И 88, группу элментов НЕ 9,9 группу элементов И 10 , 1010, элемент ИЛИ 11, элемент- -И 12, блок элементов ИЛИ 13, выходы14 и 15, входы 16 и 17.В исходном состоянии все триггеры 3, регистры 1 и вычитающие счетчики 2 находятся в нулевом состоянии. По входу 17 последовательно вустройство заносятся на регистры 1номера заданий (задач или программ),на счетчики 2 - "веса" заданий (например, время реализации), на триггеры 3 - код единицы, свидетельствующий о необходимости решения задачи.В результате на выходах элементов И 8 будут нулевые потенциалы,следовательно, на обратном выходеэлемента ИЛИ 11 будет высокий потенциал, который подается на первыйвход элемента И 12.1Работа устройства начинается после подачи последовательности тактовых импульсов по входу 16, которыедалее через элемент И 12 поступают на первые входы элементов И 4.В исходном состоянии все тригге. ры 3 находятся в единичном состоянии, поэтому на вторых входах элементов И 4 будут присутствовать высокие потенциалы с прямых выходов одноименных триггеров 3, и счетные импульсы будут далее поступать на входы вычитающих счетчиков 2. Подсчет импульсов на счетчиках 2 продолжается до тех пор, пока хотя быОдновременно с появлением высокого потенциала на ь -м входе элемента ИЛИ 11 высокий потенциал поступает на входы элемента задержки би второй вход блока элементов И 5.,1/ йв результате код номера задачи свыхода регистра 1; поступает через 40 блок элементов И 51 и далее черезблок элементов ИЛИ 13 на выход 14устройства.Элемент задержки 6 обеспечивает1задержку сигнала на время передачи 45 кода номера наиболее приоритетнойзадачи на выход 14 устройства. Поистечении времени на выходе элемента задержки 6, появляется высокийпотенциал, который сбрасывает триггер 3 в нулевое состояние, Появление нулевого потенциала на выходетриггера 3 и на одном из входовИ 4; запрещает подачу тактовых импульсов на счетчик 21. Одновременнонизкий потенциал с выхода триггера3 запрещает подачу высокого потенциала с выхода элемента И 8; навход схемы приоритета, в результатетактовые импульсы будут вновь пос 5 1 О 15 20 25 30 нуля. В результате этого на выходеэлемента ИЛИ-НЕ 7 , входы которогоподсоединены к прямым выходам счетчика 2 появится единичный сигнал,который далее поступает на первыйвход элемента И 8., на второй вход1которсго поступает единичный сигналс прямого выхода триггера 3,Единичные сигналы с выходов элементов И 8 поступают далее на входысхемы приоритета, собранной на элементах НЕ 9 , 9 и элементахИ 10 , , 10. Эта схема обеспечивает появление единичного сигнала только на одном из своих выходовпо поступлении нескольких единичныхсигналов на ее вход, При появленииединичного сигнала на выходе элемента И 10; (1 =2, , и) или на выходе элемента И 8, на выходе 15 устройства (с прямого выхода элементаИЛИ 11) появляется единичный сигнал,свидетельствующий о выборе устройством номера очередной наиболее приоритетной задачи. Кроме того, низкий потенциал с инверсного выходаэлемента ИЛИ 11 запрещает прохождение тактовых импульсов через элемент И 12.тупать с входа 16 через открытый элемент И 12, открытые элементы И 4, (3=1;и, .1 г ) на входы вычитающих счетчиков 2 , и работа устройства продолжается аналогичным образом.Формула изобретенияУстройство для распределения заданий процессорам, содержащее элемент ИЛИ, группу регистров, группу триггеров, группу блоков элементов И, группу элементов ИЛИ-НЕ, группу элементов НЕ, выход каждого регистра группы соединен с первым входом соответствующего блока элементов И группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены группа элементов задержки, первая, вторая, третья группы элементов И, группа вычитающих счетчиков, элемент И, блок элементов ИЛИ, причем выход каждого блока элементов И группы соединен с соответствующим входом блока элементов ИЛИ, выход которого является выходом кода номера задачи устройства, прямой выход каждого триггера группы соединен с первыми входами соответствующих элементов И первой и второй групп, выходы элементов И первой группы соединены со счетными входами соответствующих вычитающих счетчиков группы, выходы которых соединены с входами соответствующих элементов ИЛИ-НЕ группы, выходы ко-торых соединены с вторыми входами соответствующих элементов И второй группы, выход первого элемента Ивторой группы соединен с первымвходом элемента ИЛИ, входом первогоэлемента НЕ группы, вторым входомпервого блока элементов И группы,входом первого элемента задержкигруппы, выход-го=2, , п,где и-число заданий) элемента Ивторой группы соединен с входом-го (1=2, , п) элемента НЕгруппы и первым входом 1-гоЦ=1, , и) элемента И третьейгруппы, выход последнего элементаИ второй группы соединен с первымвходом последнего элемента И третьейгруппы, выход 1-го (=1, , и)элемента НЕ группы соединен с (1+1)-мвходом (+1)-го и всех последующихэлементов И третьей группы, выход1-го (1=1, , и) элемента И третьей группы соединен с (1+ 1)-м входом элемента ИЛИ, вторым входом соответствующего блока элементов И 25группы и входом соответствующегоэлемента задержки группы, выходыэлементов задержки группы соединеныс входами соответствующих триггеровгруппы, прямой выход элемента ИЛИявляется выходом выбора номера приоритетной задачи устройства, инверсный выход элемента ИЛИ соединен спервым входом элемента И, второйвход которого является тактовым входом устройства, выход элемента И со единен с вторыми входами элементовИ первой группы, информационный входустройства подключен к информационнымйходам регистров группы, вычитающихсчетчиков группы и триггеров группы,1290322 Составитель В.ГудовскийТехред А. Кравчук Корректор М актор М.Бандура оши Заказ 7903 Т дписно Производственно-полиграФическое предприятие, г.ужгород, ул,Проектная НИИПИ Госуд по делам 13035, Моск