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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (И) (5р 4 С 06 F 9/46

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТМЙ (21) 3911362/24-24 (22) 12.06.85 (46) 15.02.87. Бюл. У 6 (72) В.А.Титов, В.Л.Гайдуков и Г.А.Беркетов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N 554488885599, кл. С 06 F 9/46, 1974.

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

В 966697, кл. С 06 F 9/46, 1982. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано при органиэации вычислительного процесса по обработке паке-! та или потока задач в многопроцессорной или многомашинной вычислительной системе. Целью изобретения является повышение быстродействия.

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

1 1290322 2 . Изобретение относится к вычисли- на одном из них (например, i -м, тельной технике и может быть исполь- i =t, ..., и) не зафиксируется код зовано при организации вычислительного процесса по обработке пакета или потока задач в многопроцессорной или многомашинной вычислительной системе.

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

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

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

2,, ..., 2„, группу триггеров 3,, 3„, .группу элементов И 4,,..., 4„, группу блоков элементов И 5,, 5„, группу элементов задержки

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

7,, ..., 7„, группу элементов И 8;, 8„, группу элментов НЕ 9,,..., 9„,, группу элементов И 10, 10

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

И 12, блок элементов ИЛИ 13, выходы

14 и 15, входы 16 и 17.

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

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

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

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

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

40 блок элементов И 5I и далее через блок элементов ИЛИ 13 на выход 14 устройства.

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

1 задержку сигнала на время передачи

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

И 4; запрещает подачу тактовых импульсов на счетчик 21. Одновременно низкий потенциал с выхода триггера

3 запрещает подачу высокого потенциала с выхода элемента И 8; на вход схемы приоритета, в результате тактовые импульсы будут вновь пос5 l0

30 нуля. В результате этого на выходе элемента ИЛИ-HF. 7,, входы которого подсоединены к прямым выходам счетчика 2,, появится единичный сигнал, который далее поступает на первый вход элемента И 8., на второй вход

1 которсго поступает единичный сигнал с прямого выхода триггера 3, Единичные сигналы с выходов элементов И 8 поступают далее на входы схемы приоритета, собранной на элементах HE 9,, ..., 9„ и элементах

И 10, ..., 10„. Эта схема обеспечивает появление единичного сигнала только на одном из своих выходов по поступлении нескольких единичных сигналов на ее вход. При появлении единичного сигнала на выходе элемента И 10; (1 =2, ..., n) или на выходе элемента И 8, на выходе 15 устрой. ства (с прямого выхода элемента

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

1290322 тупать с входа 16 через открытый элемент И 12, открытые элементы И 4

1 (j=1, ..., n, jфi ) на входы вычитающих счетчиков 2 „, и работа устройства продолжается аналогичным образом.

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

Устройство для распределения заданий процессорам, содержащее элемент ИЛИ, группу регистров, группу триггеров, группу блоков элементов

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

I группы, выход первого элемента И второй группы соединен с первым входом элемента ИЛИ, входом первого элемента НЕ группы, вторым входом первого блока элементов И группы, входом первого элемента задержки группы, выход i -ro (i =2, ..., п-1, где и-число заданий) элемента И второй группы соединен с входом

j-ro (j=2, ..., п-1) элемента НЕ группы и первым входом j-го (j=1, ..., n-2) элемента И третьей группы, выход последнего элемента

И второй группы соединен с первым входом последнего элемента И третьей группы, выход j ro (j=1, ..., и-1) элемента НЕ группы соединен с (j+1)-м входом (j+1)-го и всех последующих элементов И третьей группы, выход

j-го (j=1, ..., n-1 ) элемента И третьей группы соединен с (j+1)-м входом элемента ИЛИ, вторым входом соответствующего блока элементов И

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

И первой группы, информационный вход устройства подключен к информационным йходам регистров группы, вычитающих счетчиков группы и триггеров группы.

1290322

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

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

Редактор M.Áàíäóðà

Заказ 7903/47 Тираж 673

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

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

Подписное

Производственно-полиграфическое предприятие, r.Óæãîðîä, ул.Проектная,4