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

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Соеэ СоветскихСоциалистическихРеспублик ои 964643(5 )М, Кл. С 06 Г 9/46 9 жудврстеаемВ кветат ИьР в двлаи вэфбрвтеввй и вткрытвя(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАИ менты ИЛИ 11. 1Изобретение относится к вычислительной технике и может быть ис, пользовано при организации вычислительного процесса по обработке пакета задач в многопроцессорной или многомашинной вычислительной системе.Известны устройства для распределения заданий процессорам, содержащие блок управления, регистр, шифратор, блоки очередности, коммутаторы и элеНедостатком этого устройства является то, что оно обеспечивает эффективную обработку только случайного потока задач без учета априорной информации об их параметрах на основе обслуживания запросов на решение в порядке поступления.Наиболее близким техническим ре" шением является устройство, содержащее по числу решаемых в пакете задач первые и вторый триггеры, первые элементы ИЛИ и первые элементы ИЛИ-НЕ,по числу двоичных .разрядов в коде"веса" задачи первые элементы И, вто.рые элементы ИЛИ-НЕ, поразрядные узлы переноса в составе групп вторыхэлементов И и вторых элементов ИЛИ, 5входы каждого из которых подсоединены к выходу одновременно с узломпереноса второго элемента ИЛИ-НЕ,первый вход каждого второго элемента И подсоединен к выходу второго .элемента И предыдущего узла переноса, второй вход - к выходу одноименного второго элемента ИЛИ, первыйвход которого подсоединен к выходувторого элемента И соответствующегостаршего разряда,предыдушего узлапереноса, второй вход - к выходуодноименного второго элемента ИЛИ-НЕ,входы которого подсоединены к выхо дам вторых элементов И .старших разрядов предыдущего узла переноса,нулевой выход каждого первого триггера подсоединен к первым входам со 964643 4ответствующих первых элементов И, первые входы вторых триггеров подсоединены к выходам вторых элементов И последнего узла переноса, первый выход еторого триггера подсоединен к первому входу первого элемента ИЛИ, второй выход - к первому входу первого элемента ИЛИ-НЕ, второй вход которого и второй вход первого элемента ИЛИ подсоединены к выходу первого элемента ИЛИ, соответствующего очередному по старшинству номеру задачи в пакете (21.Недостаток этого устройства заклю чается в невозможности использования его для распределения заданий процессорам в мультипроцессорной или вычислительной машинах в многомашинной вычислительной системе по критерию минимума среднего времени ожидания задачи -е пакете.Цель изобретения - расширение функциональных возможностей устройства за счет осуществления режима наименьшего среднего времени ожидания решения задачи. Поставленная цель достигается тем, что а устройство для распределения заданий процессорам, содержащее и каналов, каждый из которых состоит из триггера и первой группы из щ элементов И, а также общие для всех каналов шифратор, группу из и триггеров, группу из иэлементов ИЛИ, группу из иэлементов ИЛИ-НЕ, причем выход триггера каждого канала подключенк первым входам всех элементов И первой группы, вторые входы элементов И первой группы всех каналов объединены и. подключены к входу режима минимального времени реализации пакета устройства, третьи входы всех элементов И первой группы каждого канала подключены к соответствующим кодовым входам устройства, входы триггеров каждого канала подключены к установочным входам устройства, установочные входы всех триггеров группы объединены и подключены к входу сброса устройства, информационные входы триггеров группы подключены к соответствующим выходам шифратора, прямой выход к-го триггера группы (к,1, ,и) подключен к первому входу к-го элемента ИЛИ группы (к=2,,и), второй вход которого соединен с первым входом (к)-го эле 5 10 15 20 25 30 55 40 45 мента ИЛИ группы и первым входом (к)тго элемента ИЛИ-НЕ группы (к=1и), выход которого является информационным,выходом (к)-го разряда устройства (к=1и), выход и-го триггера первой группы подключен к выходу и-го разряда устройства, к первому входу (и)-го элемента ИЛИ группы и первому входу (и)-го элемента ИЛИ-НЕ группы, выход первого триггера группы подключен к первому входу .первого элемента ИЛИ-НЕ группы, в каждый канал введены группа из е элементов НЕ, группа из щ элементов ИЛИ и вторая группа из в элементов И, причем выходы каждого элемента И второй группы подключены к первому входу соответствующего элемента ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И первой груп" иы, выходы элементов ИЛИ группы кажцого канала подключены к соответствующим входам шифратора, первый вход каждого элемента И второй группы подключен к выходу соответствующего элемента НЕ группы, входы которых подключены к соответствующим кодовым входам устройства, вторые входы всех элементов И второй группы объединены и подключены к выходу триггера, третьи входы всех элементов И второй группы всех каналов объединены и подключены к входу режима минимального среднего времени ожидания решения задачи устройства.Сущность предлагаемого изобретения заключается е том, что, используя имеющиеся узлы и вводя дополнительно группы элементов НЕ, ИЛИ и И с соответствующими связями, становится возможным осуществлять не только режим минимального времени реализации пакета задач (как в известном устройстве), но и режим наименьшего среднего времени ожидания задач в пакете.1 На фиг. 1 представлена структурная схема устройства для распределения заданий процессорам; на фиг. 2 - структурная схема шифратора.Устройство содержит и-каналов (и- число решаемых задач в пакете), каждый из которых содержит триггер 1 признака решения задачи (фиг 1), элемент НЕ 2, первые 3 и вторые 4 группы элементов И .группу элементов ИЛИ 5, и общие для всех каналов3 9646шифратор 6, группу из и триггеров 7,группу элементов ИЛИ 8, группу элементов ИЛИ-НЕ 9, вход 10 устройства,входы 11 и 12 режима работы устройства, группу установочных входов 3131, 13 у13 л и группы кодовыхвходов 14 и , 14 , , 14 , группуинформационных выходов 15, 1515 устройства. Шифратор 6, вы.полняющий функцию определения пози- Вционного номера максимального кодаиз некоторого массива чисел (фиг. 2)содержит по числуразрядов в кодечисла, соответствующего "весу" задачи, элементы ИЛИ-НЕ 16, поразрядные узлы переноса 17 группы элементов И. и ИЛИ 18,И, 181 18 р,п,состоящие из элементов ИЛИ 19 и элементов И 20, входы 21 , 211121111, подсоединейные к выходам соответствующих элементов ИЛИ 5, выходы22,1 , 221 подсоединенные к первым входам соответствующих триггеров 7,Устройство работает. следующим образом.В исходном состоянии все триггеры 1 (фиг. 1) находятся в нулевомсостоянии, их нулевые выходы подсоединены к первым входам первых эле- Эфментов И 3 и к первым входам вторыхэлементов И 4. На кодовые входы 14устройства поступают -разрядныекоды и чисел, а на установочныевходы 13, по мере решения задач,поступают единичные сигналы - признаки решения задач, которые перебрасывают соответствующие триггеры 1в единичное состояние. Устройствоможет функционировать в двух режимах: в режиме наименьшего времениреализации пакета задач (как этопредусмотрено в известном устройстве), в этом случае подается единичный сигнал на вход 11 устройства,и в режиме наименьшего среднего времени ожидания задачи в пакете, длячего единичный сигнал подается навход 12 устройства. При одновременном единичном состоянии нескольких триггеров 7 на выходе устройства появится единичный сигнал только в одной выходной "ой шине, прицем 1 1, где 50В режиме наименьшего времени реализации пакета задач коды "весов" вершин поступают на входы 14 устройства, далее через открытые элемент ты И 4, затем через элементы ИЛИ 5 - на входы шифратора 6, на входы первого узла переноса. В режиме наименьшего среднего времени ожидания задачи в пакете коды "весов" задач 43 бтакже поступают на входы 14 устройства, далее через элемент НЕ 2, открытые элементы И 3, затем черезэлементы ИЛИ 5 обратные коды "весов"задач поступают также на входы первого узла переноса 17 шифратора 6,Шифратор работает следующим образом.В первый момент анализируютсястаршие разряды кодов чисел. Еслихотя бы один из старших разрядовкодов равен 1, то на выходе элементаИЛИ-НЕ 16 сформируется О, при этом,если старший разряд -го числа(=1,и) равен О, то все разряды 1-гочисла не проходят через элементыИ 20 -ой группы первого поразрядного узла 17. Если старший разряд-го числа равен 1, то все разряды-го числа проходят через элементыИ 20 1-ой группы первого узла переноса.Если старшие разряды всех кодовчисел равны О, то на выходе элемента ИЛИ-НЕ 16 сформируется 1, которая дает разрешение на прохождениевсех и кодов чисел через элементыИ 20 первого узла переноса. Такимобразом, на выходе элементов И 20первого узла переноса 17 формируются коды чисел, начиная с второгопо в-ый разряд.Вторым элементом ИЛИ-НЕ 162 поразрядного узла переноса 172 анализируются вторые по старшинству разрядычисел таким же образом, как и старших разрядов, и т.д. Таким образом,код номера экстремального числа (макосимального, если единичный сигналподается на вход 11 устройства, илиминимального, если единичный сигналподается на вход 12 устройства),получается путем совпадения всехсигналов запрета, сформированныхв каждом поразрядном узле переноса17. При единичных сигналах на одномили более выходах элементов И 20последнего поразрядного узла переноса 17 и формируется код 1 на триггерах 7, соответствующих экстремальным кодаи чисел (в решаемом пакетезадач могут быть задачи, требующиеодинаковое время для решения),96461, и, т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач, требующих одинакового времени для своего решения. Это достигается тем, что,высокий потенциал с выхода триггера 7, соответствующего решаемой задаче со старшим порядковым номером, подается через элемент ИЛИ 8 на первые входы предыдущих элементов ИЛИ-НЕ 9, 10 вторые входы которых подключены к одноименным нулевым выходам триггеров 1. 8 результате позиционный код номера экстремального числа получается на выходах устройства. 1При назначении очередной 1-ой задачи пакета на решение подается единичный сигнал на соответствующий триггер 1в результате чего прекращается подача кода 1-го числа 20 с выходов элементов И 3 или 4 для последующего сравнения, а также на вход 10 устройства для переброса триггеров 7 в исходное (нулевое) состояние, и работа устройства по выбо ру очередной задачи из, пакета происходит далее аналогично.Таким образом, введение новых элементов и связей позволит существенно расширить область применения Зо устройства,формула изобретения3Устройство для распределения заданий процессорам, содержащее и каналов, каждый из которых состоит из триггера и первой группы из м элементов И, а также общие для всех каналов шифратор, группу из 11 триггеров, группу из 11-2 элементов ИЛИ, группу из Ф -1 элементов ИЛИ-КЕ, причем выход триггера каждого канала подключен к первым входам всех элементов И первой группы, вторые входы элементов И первой группы всех каналов объединены и подключены к входу режима минимального времени реализации пакета устройства, третьи входыЮ всех элементов И первой группы каждого канала подключены к соответсвующим кодовым входам устройства, входы триггеров каждого канала подклЮчены к установочным входам устройства, установочные входы всех триггеров груп 43 8пы объединены и подключены к входусброса устройства, информационныевходы триггеров группы подключены ксоответствующим выходам шифратора,прямой выход к-го триггера группы(к= 1. ,и) подключен к первому входу к-го элемента ИЛИ группы (к=.2,,и), второй вход кдторого соединен с первым входрм (к)-го элемента ИЛИ группы и первым входом (к)-гоэлемента ИЛИ-НЕ группы (к=1и) выход которого является информационным выходом (к)-го разрядаустройства (к 1, ,;,и), выход и-готриггера первой группы подключенк выходу и-го разряда устройства,первому входу (и)-го элемента ИЛИгруппы.и первому входу (и)-го элемента ИЛИ-НЕ группы, выход первоготриггера группы подключен к первомувходу первого элемента ИЛИ-НЕ. группы,о.т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвозможностей за счет осуществлениярежима наименьшего среднего времениожидания решения задачи, в каждыйканал введены группа из е элементовНЕ, группа из в элементов ИЛИ и вторая группа из а. элементов И, причемвыходы каждого элемента И второйгруппы подключены к первому входу соответствующего элемента ИЛИ группы,вторые входы которых подключены квыходам соответствующих элементов Ипервой группы, выходы элементов ИЛИгруппы каждого канала подключены,ксоответствующим входам шифратора,первый вход каждого элемента И второй группы подключен к выходу соответствующего элемента НЕ группы, входы которых подключены к соответствующим кодовых входам устройства,вторые входы всех элементов И второйгруппы объединены и подключены к выходу триггера, третьи входы всехэлементов И второй группы всех каналов объединены и подключены к входурежима минимального среднего времениожидания решения задачи устройства.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРН 548859 кл. 6 06 Г 9/46, 1974.2, Автооское свидтельство СССРпо заявке 8 2904436/24.кл. С 06 Г 9/46, 1979964643 Г 4 ю Уу Р 2 Уу аказ 7 31/29 Тираж 731 ВНИИПИ Государственного комитета ССС по делам изобретенйй и открытий 113035, Москва, Ж"35, Раувская наб., одписное илиал ППППатент, г. Ужгород, ул. Проект Составитель П, ЧистобородовРедактор А, Козориз Техред А.Бабинец Корректор Г, Огар