Устройство для распределения заданий процессорам Советский патент 1982 года по МПК G06F9/50 G06F15/163 

1

Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного процесса по обработке пакета задач в многопроцессорной или многомашинной вычислительной системе.

Известны устройства для распределения заданий процессорам, содержащие блок управления, регистр, шифратор, блоки очередности, коммутаторы и элементы ИЛИ 1 .

Недостатком этого устройства является то, что оно обеспечивает эффективную обработку только случайного потока задач без учета априорной информации об их параметрах на основе обслуживания запросов на решение в порядке поступления.

Наиболее близким техническим решением является устройство, содержащее по числу решаемых в пакете задач первые и вторые триггеры, первые элементы ИЛИ и первые элементы ИЛИ-НЕ,

по числу двоичных .разрядов в коде веса задачи первые элементы,И, вторые элементы ИЛИ-НЕ, поразрядные узлы переноса в составе групп вторых элементов И и вторых элементов ИЛИ, входы каждого из которых подсоединены к выходу одновременно с узлом переноса второго элемента ИЛИ-НЕ, первый вход каждого второго элемент та И подсоединен к выходу второго

10 элемента И предыдущего узла переноса, второй вход - к выходу одноименного второго элемента ИЛИ, первый вход которого подсоединен к выходу

., второго элемента И соответствующего старшего разряда .предыдущего узла переноса, второй вход - к выходу одноименного второго элемента ИЛИ-НЕ, входы которого подсоединены к выходам вторых элементов И .старших разрядов предыдущего узла переноса,

нулевой выход каждого первого триггера подсоединен к первым входам соответствующих первых элементов И, первые входы вторых триггеров подсоединены к выходам вторых элементов И последнего узла переноса, пер вый выход второго триггера подсоеди нен к первому входу первого элемента ИЛИ, второй выход - к первому входу первого элемента ИЛИ-НЕ, второй вход которого и второй вход пер вого элемента ИЛИ подсоединены к вы ходу первого элемента ИЛИ, соответствующего очередному по старшинс ву номеру задачи в пакете z. Недостаток этого устройства закл чается в невозможности использовани его для распределения заданий проце ,сорам в мультипроцессорной или вычи лительной машинах в многомашинной вычислительной системе по критерию минимума среднего времени ожидания задами-в пакете. Цель изобретения - расширение функциональных возможностей устройства за счет осуществления режима наименьшего среднего времени ожидания решения задачи. Поставленная цель достигается тем, что в устройство для распределения заданий процессорам, содержащее п каналов, каждый из которых состоит из триггера и первой группы из m элементов И, а также общие для всех каналов шифратор, группу из п триггеров, группу из п-2 элементов ИЛИ, группу из п-1 элементов ИЛИ-НЕ, причем выход триггера каждого канала подключенк первым входам всех элементов И первой груп пы, вторые входы элементов И первой группы всех каналов объединены и подключены к входу режима минимального времени реализации пакета устройства, третьи входы всех элементов И первой группы каждого канала подключены к соответствующим кодовым входам устройства, входы тригге ров каждого канала подключены к установочным входам устройств, устан вочные входы всех триггеров группы объединены и подключены к входу сброса устройства, информационные входы триггеров группы подключены к соответствующим выходам шифратора прямой выход к-го триггера группы (,...,п) подключен к первому вхо ду к-го элемента ИЛИ группы (, .,п-1), второй вход которого соединен с первым входом {к-1)-го эле34мента ИЛИ группы и первым входом (к-1)тго элемента ИЛИ-НЕ группы (,,,.,п-1), выход которого является информационным .выходом (к-1)-го разряда устройства (,,..,п), выход п-го триггера первой группы hoдключен к выходу п-го разряда устройства, к первому входу (п-1)-го элемента ИЛИ группы и первому входу (п-1)-го элемента ИЛИ-НЕ группы, выход первого триггера группы подключен к первому входу первого элемента ИЛИ-НЕ группы, в каждый канал введены группа из т элементов НЕ, группа из m элементов ИЛИ и вторая группа из m элементов И, причем выходы каждого элемента И второй группы подключены к первому входу соответствующего элемента ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И первой группы, выходы элементов ИЛИ группы каждого канала подключены к соответствующим входам шифратора, первый вход каждого элемента И второй группы подключен к выходу соответствующего элемента НЕ группы, входы которых подключены к соответствующим кодовым входам устройства, вторые входы всех элементов И второй группы объединены и подключены к выходу триггера, третьи входы всех элементов И второй группы всех каналов объединены и подключены к входу режима минимального среднего времени ожидания решения задлчи устройства. Сущность предлагаемого изобретения заключается в том, что, используя имеющиеся узлы и вводя дополнительно группы элементов НЕ, ИЛИ и И с соответствующими связями, становится возможным осуществлять не только режим минимального времени реализации пакета задач (как в известном устройстве), но и режим наименьшего среднего времени ожидания задач в пакете. На фиг. 1 представлена структурная схема устройства для распределения заданий процессорам; на фиг. 2 структурная схема шифратора. Устройство содержит п-каналов (п-- число решаемых задач в пакете) , каждый из которых содержит триггер 1 признака решения задачи (фиг. 1), элемент НЕ 2, первые 3 и вторые k группы элементов И j pynny элементов ИЛИ 5 и общие для всех каналов шифратор 6, группу из п триггеров 7 группу элементов ИЛИ 8, группу элементов ИЛИ-НЕ 9f вход 10 устройства входы 11 и 12 режима работы устройства , группу установочных входов 13, 132 Зп группы кодовы входов l , , ..., «nm групп информационных выходов IS/j, IS 15п устройства. Шифратор о, вы полняющий функцию определения позиционного номера максимального кода из некоторого массива чисел (фиг, 2 содержит по числу т разрядов в коде числа, соответствующего весу задачи, элементы ИЛИ-НЕ 16, поразрядные узлы переноса 17, группы элемен тов Ни ИЛИ 18, 18, ,,., I8mn, состоящие из элементов ИЛИ 19 и эле ментов И 20, входы 21 21 , .,,, 21(f)n подсоединенные к выходам соот ветствующих элементов ИЛИ 5 выходы 22, подсоединенные к пер вым входам соответствующих триггеров 1. Устройство работает следующим об разом. В исходном состоянии все триггеры 1 {фиг, 1) находятся в нулевом состоянии, их нулевые выходы подсое динены к первым входам первых элементов И 3 и к первым входам вторых элементов И , На кодовые входы И устройства поступают т-разрядные коды, п чисел, а на установочные входы 13, по мере решения адач, поступают единичные сигналы - признаки решения задач, которые перебра сывают соответствующие триггеры 1 в единичное состояние. Устройство может функционировать в двух режимах: в режиме наименьшего времени реализации пакета задач (как это предусмотрено в известном устройстве) , в этом случае подается единичный сигнал на вход 11 устройства, и в режиме наименьшего среднего времени ожидания задачи в пакете, для чего единичный сигнал подается на вход 12 устройства, В режиме наименьшего времени реализации пакета задач коды весов вершин поступают на входы Ш устройства, далее через открытые элемент ты И i, затем через элементы ИЛИ 5 на входы шифратора 6, на входы первого узла переноса. В режиме наименьшего среднего времени ожидания задачи в пакете коды весов задач г ,6 также поступают на входы I устройства, далее через элемент НЕ 2, открытые элементы И 3 затем через элементы ИЛИ 5 обратные коды весов задач поступают также на входы первого узла переноса 17 шифратора 6. Шифратор работает следующим образом, В первый момент анализируются старшие разряды кодов чисел. Если хотя бы один из старших разрядов кодов равен 1, то на выходе элемента ИЛИ-НЕ 1б сформируется О, при этом, если старший разряд i-ro числа ((1,п) равен О, то все разряды i-ro числа не проходят через элементы И 20 i-ой группы первого поразрядного узла 17f. Если старший разряд i-ro числа равен 1, то все разряды i-ro числа проходят через элементы И 20 1-ой группы первого узла переноса. Если старшие разряды всех кодов чисел равны О, то на выходе элемента ИЛИ-НЕ 1б-( сформируется 1, которая дает разрешение на прохождение всех п кодов чисел через элементы И 20 первого узла переноса. Таким образом, на выходе элементов И 20 первого уяпа переноса 17 формируются коды чисел, начиная с второго по т-ый разряд. Вторым элементом ИЛИ-НЕ 1б2 поразрядного узла переноса 172 знализируются вторые по старшинству, разряды чисел таким же образом, как и старших разрядов, и т,д. Таким образом, код номера экстремального числа (максимального, если единичный сигнал подается на вход 11 устройства, или минимального, если единичный сигнал подается на вход 12 устройства), получается гТутем совпадения всех m сигналов запрета, сформированных в каждом поразрядном узле переноса 17. При единичных сигналах на одном или более выходах элементов И 20 последнего поразрядного узла переноса 17ш формируется код 1 на триггерах 7, соответствующих экстремальным кодам чисел (в решаемом пакете задач могут быть задачи, требующие одинаковое время для решения). При одновременном единичном остоянии нескольких триггеров 7 на выходе устройства появится едиичный сигнал только в одной выходной i-ой шине, причем , где 1. л, т.е. предпочтение отдастся той задаче, порядковый номер которой наибольший среди задач, требующих одинакового времени для своего решения. Это достигается тем, что .высокий потенциал с выхода триггера 7, соответствующего решаемой задаче со старшин порядковым номером, подается через элемент ИЛИ 8 на первые входы предыдущих элементов ИЛЙ-НЕ 9 вторые входы которых подключены к одноименным нулевым выходам триггеров 1. В результате позиционный код номера экстремального числа получартся на выходах устройства. При назначении очередной i-ой задачи пакета на решение подается единичный сигнал на соответствующий триггер Ij, в результате чего прекращается подача кода i-ro числа с выходов элементов И J или 4 для последующего сравнения, а также на вход 10 устройства для переброса .триггеров 7 в исходное (нулевое) сос тояние, и работа устройства по выбору очередной задачи из.пакета происходит далее аналогично. Таким образом, введение новых элементов и связей позволит с оцественно расширить область применения устройства. Формула изобретения Устройство для распределения за|)аний процессорам, Содержащее п каналов, каждый из которыхсостоит из триггера и первой группы из m элементов И, а также общие для всех каналов шифратор, группу из п тригге ров, группу из П-2 элементов ИЛИ, группу из 11 -1 элементов ИЛИ-НЕ, причем выход триггера каждого канала подключен к первым входам всех элементов И первой группы, вторые входы элем.ентов И первой группы всех каналов объединены и подключены к входу режима минимального времени реализации пакета устройства, третьи входы всех элементов И первой группы каждо го канала подключены к соответствующим кодовым входам устройства, входы триггеров каждого канала подключены к установочным входам устройства, ус тановочные входы всех триггеров груп .38 пы объединены и подключены к входу сброса устройства, информационные входы триггеров группы подключены к соответствующим выходам шифратора, прямой выход к-го триггера группы (,...,п) подключен к первому входу к- го элемента ИЛИ группы (, ...,п-1), второй вход которого соединен с первым входом (к-1)-го элемента ИЛИ группы и первым входом (к-1)-го элемента ИЛИ-НЕ группы (,..., п-1), выход которого является информационным выходом (к-1)-го разряда устройства (,...,п), выход п-го триггера первой группы подключен к выходу п-го разряда устройства, первому входу (п-1)-го элемента ИЛИ группы.и первому входу (n-l)-ro элемента ИЛИ-НЕ группы, выход первого триггера группы подключен к первому входу первого элемента ИЛИ-НЕ группы, Отли чающееся тем, что, с целью расширения функциональных возможностей за счет осуществ.ления режима наименьшего среднего времена ожидания решения задачи, в каждый канал введены группа из m элементов НЕ, группа из m элементов ИЛИ и вторая группа из т. элементов И, причем выходы каждого элемента И второй группы подключены к первому входу соответствующего элемента ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И первой группы, выходы элементов ИЛИ группы каждого канала подключены-;к соответствующим входам шифратора, первый вход каждого элемента И второй группы подключен к выходу соответствующего элемента НЕ группы, входы которых подключены к соответствующим кодовых входам устройства, вторые входы всех элементов И второй группы объединены и подключены к выходу триггера, третьи входы всех элементов И второй группы всех кана лов объединены и подключены к входу режима минимального среднего времени ожидания решения задачи устройства. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР ff SfSesS, кл. G 06 F 9/«6, 197. 2.Автооское свидетельство СССР по заявке № 290 Зб/2 . , кл. G 06 F , 1979.

% /w f r /4 /4

/

r

Фг/г.

/./ // ///J /