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

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

Цель изобретения - повышение быстродействия.

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

Устройство содержит группу регистров 1

1

где п-максимальное число заданий EI пакете (очереди) , группу вычитающих счетчиков

-1

.

1

. ., 2 , группу триггеров J, 3rt группу элементов И 4, ,

И 5

1 5, группу элементов задержки

группу блоков элементов г 6

8

группу элементов ИЛИ-Н „ , группу элементов И , nt группу элментов НЕ 9,,..., группу элементов И 10,, 10,

10, элемент ИЛИ 11,

г .-3 элемент-

И 12, блок элементов ИЛИ 13, выходы 14 и 15, входы 16 и 17.

В исходном состоянии все триггеры 3, регистры 1 и вычитающие счетчики 2 находятся в нулевом состоянии. По входу 17 последовательно в устройство заносятся на регистры 1 номера заданий (задач или программ) на счетчики 2 - веса заданий (например, время реализации), на триггеры 3 - код единицы, свидетельствующий о необходимости решения задачи

В результате на выходах элементов И 8 будут нулевые потенциалы, следовательно, на обратном выходе элемента ИЛИ 11 будет высокий потенциал, который подается на первый

вход элемента И 12. (,

Работа устройства начинается после подачи последовательности тактовых импульсов по входу 16, которые далее через элемент И 12 юступают первые входы элементов И 4.

В исходном состоянии все триггеры 3 находятся в единичном состоянии, поэтому на вторых входах элементов И 4 Ьудут присутствовать высокие потенциалы с прямых выходов одноименных триггеров 3, и счетные импульсы будут далее поступать на входы вычитающих счетчиков.2. Подсчет импульсов на счетчиках 2 про- должается до тех пор, пока хотя бы

, входы которого прямьп выходам счетна одном из них (например, i-м, , ..., п) не зафиксируется код нуля. В результате этого на выходе элемента ИЛИ-НЕ 7 подсоединены к чика 2- , появится единичный сигнал, который далее поступает на первый вход элемента И 8j, на второй вход которого поступает единичный сигнал с прямого выхода триггера 3 .

Единичные сигналы с выходов элементов И 8 поступают далее на входы схемы приоритета, собранной на эле5

0

ментах И 10

НЕ 9,

и элементах

Ч

чивает

и-, .... 10, Эта схема обеспепоявление единичного сигнала только на одном из своих выходов по поступлении нескольких единичных сигналов на ее вход. При появлении единичного сигнала на выходе .элемента И 10- (i 2,п)

или на выхо25

30

де элемента И 8, на выходе 15 устройства (с прямого выхода элемента ИЛИ 11) появляется единичный сигнал, свидетельствующий о выборе устройством номера очередной наиболее приоритетной задачи. Кроме того, низкий потенциал с инверсного выхода элемента ИЛИ 11 запрещает прохождение тактовых импульсов через элемент И 12.

5

0

Одновременно с появлением высо- 1 кого потенциала на i-м входе элемента ИЛИ 11 высокий потенциал поступает на входы элемента задержки 6j. и второй вход блока элементов.И 5.,, в результате код номера задачи с выхода регистра 1 поступает через блок элементов И Sj и далее через блок элементов ИЛИ 13 на выход t4 устройства.

Элемент задержки 6-. обеспечивает

ч.

задержку сигнала на время передачи кода номера наиболее приоритетной задачи на выход 14 устройства с По истечении времени на выходе элемента задержки 6 появляется высокий потенциал, который сбрасывает триг50

гер 3; в нулевое состояние. Появление нулевого потенциала на выходе триггера 3, и на одном из входов И 4 запрещает подачу тактовых импульсов на счетчик 2 . Одновременно ,г низкий потенциал с выхода триггера 3 j запрещает подачу высокого потенциала с выхода элемента И 8 на вход схемы приоритета, в результате тактовые импульсы будут вновь поступать с входа 16 через открытый элемент И 12, открытые элементы ИAJ (j 1, ..., п, ) на входы вычитающих счетчиков 2, и работа устроства продолжается аналогичным образом.

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

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

группы, выход первого элемента И второй группы соединен с первым входом элемента ИЛИ, входом первого элемента НЕ группы, вторым входом 5 первого блока элементов И группы, входом первого элемента задержки группы, выход i-го (L 2, ..., п-1, где п-число заданий) элемента И второй группы соединен с входом. О j-ro (, ... , п-1) элемента НЕ группы и первым входом j-ro (, ..., п-2) элемента И третьей группы, выход последнего элемента И вт&рой группы соединен с первым 5 входом последнего элемента И третьей группы, выход j-ro (, .., п-1) элемента НЕ группы соединен с (j+1)-M входом (j+1)-ro и всех последующих

элементов И третьей группы, выход 0 j-ro (, ..., п-1) элемента И третьей группы соединен с (j+1)-M входом элемента ИЛИ, вторым входом соответствующего блока элементов И группы и входом соответствующего элемента задержки группы, выходы элементов задержки группы соединены с входами соответствующих триггеров группы, прямой выход элемента ИЛИ является выходом выбора номера приоритетной задачи устройства, инверсный выход элемента ИЛИ соединен с первым входом элемента И, второй вход которого является тактовьм входом устройства, выход элемента И со- 5 единен с вторыми входами элементов И первой группы, информационный вход устройства подключен к информационным йходам регистров группы,вычитающих счетчиков группы и триггеров группы.

5

Редактор М.Бандура

Составитель В.Гудовский

Техред А.Кравчук; Корректор М.Шароши

Заказ 7903/47Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производстц.енно-прлиграфическое предприятие, г.Ужгород, ул.Проектная,4

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