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

 

В.A.Tèòoâ, Н,Н.Брянцев, А.В.Чугунов и В.Л.Г дуков ов

Вр Д;1х1 gg, (72) Авторы изобретения (71) Заявитель (4) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

ПРОЦЕСCE)PAM

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

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

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

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

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

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

15 Поставленная цель достигается тем, что в устройство для распределения заданий процессорам, содержащее элемент ИЛИ, n/2 каналов (n - число ре,шаемых задач в пакете), каждый из ко о торых содержит два сдвигающих регистра, два элемента И, две схемы сравнения и два триггера, причем выходы первого и второго сдвигающих регист3 96669 ров каждого канала соединены соответственно с первыми выходами первого и второго сдвигающих регистров и соответствующих элементов И канала, выходы которых соединены с первыми входами соответственно первой и второй схем сравнения канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами первой и второй схем сравнения 10 каждого канала, выходы которых соединены соответственно с первыми входами первого и второго триггеров канала, выходы которых соединены соответственно с вторыми входами перво-,1

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

ИДИ-НЕ каждого канала соединен с соответствующим входом блока элементов

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

i-ro канала соединен с вторым входом элемента ИЛИ i-ro канала и с выходом элемента ИЛИ (i+1) -го канала, первый и второй входы элемента ИЛИ-НЕ соединены соответственно с выходами первого триггера и элемента ИЛИ первого канала.

Сущность изобре-.ения заключается в том, что, используя имеющиеся узлы известного устройства и введя дополнительные узлы с соответствующими связями, становится возможным по параметрам решаемых задач (например, требу- 55 емом времени для решения задачи) составить некоторое расписание порядка реализации набора задач. Такая дис7 4 циплина реализации пакета задач в мультипроцессорной вычислительной системе обеспечивает минимальное среднее время пребывания задач в системе;

На чертеже представлена структурная схема устройства для распределения заданий процессором.

Устройство содержит кольцевые сдвигающие регистры 1„, 1 .. .,1, где в ° ° ° ю и °

n - число решаемых задач в пакете, элементы И 2„, 2,,...,2„, триггеры

° 3, 3,...,3,„, схемы сравнения 4, 4г. . 4и, элементы НЕ 52, 5,...,5„„ элементы ИЛИ 6, 6>,.. °,6,, элементы ИЛИ-НЕ 7„, 7,...,7„ „, информационный регистр 8, блок элементов И 9, элемент ИЛИ 10, счетчик 11 с коэффициентом пересчета, равным числу m где m - число разрядов в кольцевом сдвигающем регистре 1. Кроме того, на чертеже обозначены выход 12 устройства, синхронизирующие входы 13, 14 и 15 устройства.

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

В регистрах 1 первоначально. находятся m-разрядные коды, соответствующие длительностям решения задач в пакете, триггеры 3 находятся в единичном состоянии, а регистр 8 находится в нулевом состоянии. Поэтому на выходах триггеров 3 присутствует высокий потенциал, и сигнал с выхода триггерА старшего разряда (на чертеже эти триггеры не показаны) регистр 1„ (i=1, n) через элемент

И 2 поступает на 1-й вход элемента

ИЛИ 1О, на выходе которого возникает сигнал, если в сравниваемых разрядах хотя бы одного из кодов имеется единица. Этот сигнал поступает на первые входы каждой схемы сравнения 4„., на выходах которых возникает сигнал сброса соответствующего триггера 3„, в том случае, если информация в сравниваемом разряде данного сдвигающего регистра 1 совпадает с 1 нулем. С триггера 3„- на элемент И

2„ поступает запрещающий (низкий) потенциал перед началом сравнения следующих разрядов чисел.

После процедуры сравнения старших разрядов кодов чисел происходит подача импульса сдвига на вход 13 уст" ройства, в результате чего в кольцевых сдвигающих регистрах 1 происходит сдвиг кодов на один разряд, и процесс сравнения очередных разрядов продолжается, и так далее до тех пор, 5 966 пока число таких сдвигов и сравнений не будет равно числу m о чем свидетельствует сигнал переполнения счетчика 11. Сигнал переполнения счетчика 11 поступает на первый вход блока элементов И 9, выходы которых подсоединены к входу регистра 8. К моменту появления сигнала переполнения на выходе счетчика 11, закончится процесс определения максимального кода te (или кодов, если их несколько), При одновременном единичном состоянии нескольких триггеров 3 на выходе 12 уст ройства (и на вторых входах групп элементов И 9) появляется единичный сигнал только на одной i-ой шине, причем i a j, где i=1, n; j=1, n, т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач, имеющих одинаковое требуе- 2р мое время.для решения. Это достигается тем, что высокий потенциал с выхода триггера 3 подается через элементы ИЛИ 6 на первые входы предыдущих элементов ИЛИ-HE 7, вторые входы ко- д торых подсоединены к выходам одноименных элементов НЕ 5.

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

8, подается на выход 12 устройства, а также обеспечивает сброс соответствующего регистра 1„ в нулевое состояние. После назначения выбранной задачи (программы) для реализации в

35 вычислительной системе по входу 15 подается сигнал сбрасывания регист" .ра 8 в исходное нулевое состояние, по входу 14 - сигнал установки триггеров 3 в единичное состояние, а

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

Таким образом, применение данного устройства позволяет расширить область применения устройства и расширить его функциональные возможности 54 за счет обеспечения выбора одной из задач пакета при реализации его в многопроцессорной вычислительной системе, Формула изобретения

l устройство для распределения заданий процессорам, содержащее элемент

697 6

ИЛИ, n/2 каналов (n - число решаемых задач е пакете), каждый из которых содержАт два сдвигающих регистра, два элемента И, две схемы сравнения и два триггера, причем выходы первого и вто. рого сдвигаюн1их регистров каждого канала соединены соответственно с первыми входами первого и второго сдвигающих регистров и соответствующих элементов И этого же канала, выходы которых соединены с первыми входами соответственно первой и второй схем сравнения канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами первой и второй схем сравнения каждого канала, выходы которых соединены соответственно с первыми входами первого и второго триггеров канала, выходы которых соединены соответственно с вторыми входами первого и -второго элементов И, первый и второй синхронизирующие входы устройства соединены соответственно с вторыми входами первого и второго сдвигающих регистров и первого и второго триггеров всех каналов, отличающееся тем, что, с целью расширения области применения, в него введены информационный регистр, счетчик, блок элементов

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

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

ИЛ1 i-го канала и с выходом элемента ИЛИ (i+I)-го канала, первый и вто рой входы элемента ИЛИ-НЕ соединены соответственно с выходами первого триггера и элемента ИЛИ первого канала.

Составитель Г. Пономарева

Редактор Л.Авраменко Техред И. Гергель

Корректор С.йекмар

/ 7 Тираж 731

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

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

Заказ, 7

11одпис Нор.

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

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

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

Н 548859, кл. 1 06 F 8/46, 1974, 966697,8

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

N 620976, кл. 6 06 F 7/02, 1977 (прототип).