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

 

ОП ИСАЙИ Е

И306РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Соеэ Соввтсиих

Социалистических

Рес ублик (iii 964643 (6l ) Дополнительное к авт. спид-ву(22) Заявлено 19. 12. 80 (21) 32/4700/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 07. 10. 82. Бюллетень М 37

Дата опубликования описания 09. 1 0 . 82 (5! )М. Кл.

С 06 F 9/46

9жудвретвциах квинтет

СССР ао делам веабретенвй н открытка (53) УДК 681. . 325 (088. 8) (72) Автори изобретения

В.А. Титов, А.И. Алещенко, В.Л. Гайдуков Й Л.ф(.фММЗНЛФ лТИТНо ткхничксиля

ЙМДИОТЕЫА (7!) Заявитель (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

ПРОЦЕССОРАИ менты ИЛИ (1).

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

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

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

"веса" задачи первые элементы И, вто.рые элементы ИЛИ-НЕ, поразрядные узлы переноса в составе групп вторых элементов И и вторых элементов ИЛИ, 5 входы каждого из которых подсоединены к выходу одновременно с узлом переноса второго элемента ИЛИ-НЕ, первый вход каждого второго элемента И подсоединен к выходу второго . элемента И предыдущего узла переноса, второй вход - к выходу одноименного второго элемента ИЛИ, первый вход которого подсоединен к выходу второго элемента И соответствующего старшего разряда .предыдушего узла переноса, второй вход — к выходу одноименного второго элемента ИЛИ-НЕ, входы которого подсоединены к выхо20 дам вторых элементов И .старших разрядов предыдущего узла переноса, нулевой выход каждого первого триггера подсоединен к первым входам со9646 ответствующих первых элементов И, первые входы вторых триггеров подсоединены к выходам вторых элементов И последнего узла переноса, первый выход второго триггера подсоединен к первому входу первого элемента ИЛИ, второй выход - к первому входу первого элемента ИЛИ-НЕ, второй вход которого и второй вход первого элемента ИЛИ подсоединены к вы- 10 ходу первого элемента ИЛИ, соответствующего очередному по старшинству номеру задачи в пакете f2)

Недостаток этого устройства заклю-чается в невозможности использования 15 его для распределения заданий процес сорам в мультипроцессорной или вычисt лительной машинах в многомашинной вычислительной системе по критерию минимума среднего времени ожидания щ задачи -e пакете.

Цель изобретения - расширение функциональных возможностей устройства за счет осуществления режима наименьшего среднего времени ожида- д ния решения задачи.

Поставленная цель достигается тем, что в устройство для распределения заданий процессорам, содержащее п каналов, каждый из которых состоит из триггера и первой группы из m элементов И,,а также общие для всех каналов шифратор, группу из и триггеров, группу из п-2 элементов ИЛИ, группу из и-1 элементов ИЛИ-НЕ, причем выход триггера каждого канала подключен к первым входам всех элементов И первой группы, вторые входы элементов И первой группы всех каналов объединены и. подключены к входу режима минимального времени реализации пакета устройства, третьи входы всех элементов И первой группы каждого канала подключены к соответствующим кодовым входам устройства, входы триггеров каждого канала подключены к установочным входам устройства, установочные входы всех триггеров группы объединены и подключены к входу сброса устройства, информационные входы триггеров группы подключены к соответствующим выходам шифратора, прямой выход к-го триггера группы (к 1,...,n) подключен к первому входу к-го элемента ИЛИ группы (к=2,,«".,n-1), второй вход которого соединен с первым входом (к- 1)-го эле30

3$

4 3 4 мента ИЛИ группы и первым входом (к-1)тго элемента ИЛИ-НЕ группы (к=1,...,n-1), выход которого является информационным,выходом (к-1)-го разряда устройства (к=1,...,n) выход и-го триггера первой группы подключен к выходу и-го разряда устройства, к первому входу (и-1)-го элемента ИЛИ группы и первому входу (и-1)-го элемента ИЛИ-НЕ группы, выход первого триггера группы подключен к первому входу .первого элемента

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

Сущность предлагаемого изобретения заключается в том, что, используя имеющиеся узлы и вводя дополнительно группы элементов НЕ, ИЛИ и

И с соответствующими связями, становится возможным осуществлять не только режим минимального времени реализации пакета задач (как в известном устройстве), но и режим наименьшего среднего времени ожидания задач в пакете.

На фиг. 1 представлена структурная схема устройства для распределения заданий процессорам; на фиг. 2— структурная схема шифратора.

Устройство содержит и-каналов (n - число решаемых задач в пакете), каждый из которых содержит триггер 1 признака решения задачи (фиг.. 1), элемент НЕ 2, первые 3 и вторые 4 группы элементов И .группу элементов ИЛИ 5, и общие для всех каналов

% 9646 шифратор 6, группу из и триггеров 7, группу элементов ИЛИ 8, группу элементов ИЛИ-НЕ 9, вход 10 устройства, входы 11 и 12 режима работы устройства, группу установочных входов 3

13 „13, ..., 13 и группы кодовых входов 14и, 14, ..., 14,„„группу информационных выходов 15< 15, 15 и устройства. Шифратор 6, выполняющий функцию определения позиционного номера максимального кода из некоторого массива чисел (фиг. 2) содержит по числу m разрядов в коде числа, соответствующего "весу" задачи, элементы ИЛИ-НЕ 16, поразряд- 1% ные узлы переноса 17, группы элементов И и ИЛИ 18,И, 18,1, ..., 18 яп, состоящие из элементов ИЛИ 19 и элементов И 20, входы 21, 2I 1, 2101 1, подсоединейные к выходам соот- 20 ветствующих элементов ИЛИ 5, выходы

221, ..., 2211, подсоединенные к первым входам соответствующих триггеров 7.

Устройство работает. следующим об- 25 разом.

В исходном состоянии все триггеры 1 (фиг. 1) находятся в нулевом состоянии, их нулевые выходы подсоединены к первым входам первых эле- Э0 ментов И 3 и к первым входам вторых элементов И 4. На кодовые входы 14 устройства поступают m-разрядные коды и чисел, а на установочные входы 13, по мере решения „задач, поступают единичные сигналы — признаки решения задач, которые перебрасывают соответствующие триггеры 1 в единичное состояние. Устройство может функционировать в двух режимах: в режиме наименьшего времени реализации пакета задач (как это предусмотрено в известном устройстве), в этом случае подается единичный сигнал на вход 11 устройства, и в режиме наименьшего среднего времени ожидания задачи в пакете, для чего единичный сигнал подается на вход 12 устройства.

При одновременном единичном состоянии нескольких триггеров 7 на выходе устройства появится единичный сигнал только в одной выходной 1-ой шине, причем iyj, где

В режиме наименьшего времени реализации пакета задач коды "весов" вершин поступают на входы 14 устройства, далее через открытые элемент ты И 4, затем через элементы ИЛИ 5— на входы шифратора 6, на входы первого узла переноса. В режиме наименьшего среднего времени ожидания задачи в пакете коды "весов" задач

43 б также поступают на входы 14 устройства, далее через элемент НЕ 2, открытые элементы И 3, затем через элементы ИЛИ 5 обратные коды "весов" задач поступают также на входы первого узла переноса 17 шифратора 6.

Шифратор работает следующим образом.

В первый момент анализируются старшие разряды кодов чисел. Если хотя бы один из старших разрядов кодов равен 1, то на выходе элемента

ИЛИ-НЕ 16 сформируется О, при этом, если старший разряд i-го числа (i=l,n) равен О, то все разряды i-го числа не проходят через элементы

И 20 i-ой группы первого поразрядного узла 17<. Если старший разряд

i-ro числа равен 1, то все разряды

1-го числа проходят через элементы

И 20 i îé группы первого узла переноса.

Если старшие разряды всех кодов чисел равны О, то на выходе элемента ИЛИ-HE 16 сформируется 1, которая дает разрешение на прохождение всех и кодов чисел через элементы

И 20 первого узла переноса. Таким образом, на выходе элементов И 20 первого узла переноса 17 формируются коды чисел, начиная с второго по m-ый разряд.

Вторым элементом ИЛИ-НЕ 16Z поразрядного узла переноса 17> анализируются вторые по старшинству разряды чисел таким же образом, как и старших разрядов, и т.д. Таким образом, код номера экстремального числа (мако симального, если единичный сигнал подается на вход 11 устройства, или минимального, если единичный сигнал подается на вход 12 устройства), получается путем совпадения всех

m сигналов запрета, сформированных в каждом поразрядном узле переноса

17. При единичных сигналах на одном или более выходах элементов И 20 последнего поразрядного узла переноса 17 m формируется код 1 на триггерах 7, соответствующих экстремальным кодаи чисел (в решаемом пакете задач могут быть задачи, требующие одинаковое время для решения).

9646

1, и, т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач, требующих одинакового времени для своего решения. Это достигается тем, что ,высокий потенциал с выхода триггера

7, соответствующего решаемой задаче со старшим порядковым номером, подается через элемент ИЛИ 8 на первые входы предыдущих элементов ИЛИ-НЕ 9, 10 вторые входы которых подключены к одноименным нулевым выходам триггеров 1. 8 результате позиционный код номера экстремального числа получается на выходах устройства. 1$

При назначении очередной i-ой задачи пакета на решение подается единичный сигнал на соответствующий триггер 1, в результате чего прекращается подача кода i-ro числа 20 с выходов элементов И или 4 для последующего сравнения, а также на вход 10 устройства для переброса триггеров 7 в исходное (нулевое) состояние, и работа устройства по выбо- 2$ ру очередной задачи из, пакета происходит далее аналогично.

Таким образом, введение новых элементов и связей позволит существенно расширить область применения $0 устройства.

Формула изобретения

3$

Устройство для распределения заданий процессорам, содержащее и каналов, каждый из которых состоит из триггера и первой группы из N элементов И, а также общие для всех каналов шифратор, группу из 11 триггеров, группу из 11-2 элементов ИЛИ, группу из Ф -1 элементов ИЛИ-НЕ, причем выход триггера каждого канала подключен к первым входам всех элементов И первой группы, вторые входы элементов И первой группы всех каналов объединены и подключены к входу режима минимального времени реализации пакета устройства, третьи входы

Ю всех элементов И первой группы каждого канала подключены к соответствую-щим кодовым входам устройства, входы триггеров каждого канала подклЮчены к установочным входам устройства, установочные входы всех триггеров груп$$

43 8 пы объединены и подключены к входу сброса устройства, информационные входы триггеров группы подключены к соответствующим выходам шифратора, прямой выход к-го триггера группы (к= l,...,n) подключен к первому входу к-го элемента ИЛИ группы (к=.2, ...,n-1), второй вход кдторого соединен с первым входрм (к-1)-го элемента ИЛИ группы и первым входом (к- 1)-го элемента ИЛИ-НЕ группы (к=l,..., п-l), выход которого является информационным выходом (к-1)-го разряда устройства (к1, .;,n), выход n-ro триггера первой группы подключен к выходу n-ro разряда устройства, первому входу (n-1)-ro элемента ИЛИ группы.и первому входу (и-1)-ro элемента ИЛИ-НЕ группы, выход первого триггера группы подключен к первому входу первого элемента ИЛИ-НЕ. группы, о-т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет осуществления режима наименьшего среднего времени ожидания решения задачи, в каждый канал введены группа из е элементов

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

N 548859 кл. G 06 F 9/46, 1974.

2. Авторское свидетельство СССР по заявке М 2904436/24 кл. G 06 F 9/46, 1979.

964643

Г Р/д Р/ / у

Составитель П. Чистобородов

Редактор А. Козориз Техред А.Бабинец Корректор Г. Огар

Заказ 7 31/29 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретенйй и открытий

113035, Москва, Ж-35, Раушская наб., д 4/5

Филиал ППП Патент, r. Ужгород, ул. Проектная,