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

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

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

Устройство ранжирует задания в пакете с учетом суммы времени ввода и решения задачи и суммы времени решения и вывода результатов в соответствии с алгоритмом Джонсона, причем на каждом шаге работы в очередь на обслуживание ставятся четыре задачи,

На фиг, 1 приведена структурная схема предлагаемого устройства; на фиг, 2 - схема блока сравнения; на 4иг, 3 - структурная схема блока поиска экстремальных кодов; на фиг, 4 - схема ячейки матрицы блока поиска экстремальных кодов; на фиг, 5 блок формирования приоритетов.

Устройство дпя распределения заданий содержит регистры 1„ -1, первой группы, регистры 1, -1„ь второй

группы, группы,

блоки 2 I -2 , элементы ИЛИ 3, -3.

Ч сравнения

элементы И 4 . -4

группы блоки

I И

группы и

5( и 5 поиска экстремальных кодов, элемент И 6, элемент 7 задержки, блок 8 формирования приоритетов, входы 9 и 10,

Блок 2 сравнения содержит элементы ИЛИ-НЕ 11, -1 ,„ (т - разрядность кодов временных на первой, второй группе регистров), узлы 124 т анализа разрядов, которые состоят из узлов 13„, ,,,, поразрядного переноса включаюпщх в свой состав элементы И 14 -и элементы ИЛИ 15, элемент НЕ 16, элемент И 17 выходы 18( и 185, входы 19„ , 19, , , , , 1 (ffi , 192, I i 5 « ,192,

Блок 5 поиска кодов содержит 20,(,„) , 202,,.

экстремальных ячейки 20j,,,, ,, ,20;,(,,, элементы НЕ 21„ ,,, , ,21 ,(2,„ t 21,2,,,,, ,,,,21(2 группы, элементы НЕ 224 22 группы, элементы И 23,, групшл, группы входов 241 - , 25, - 25,

26,

(m)

группу входов 26, группу входов 27„ ,, ,, ,27(,2т)

j

//,,,.,. , /(j :8, -28„, 29 , , группу 29,

пыходов

п ---1 - Г

Ячейка 20 блока поиска экстре- 5

мальных кодов

включает элемент

5

0

5

И 30, элемент Ш1И 31, элемент И 32, элемент ИЛИ 33, элемент НЕ 34, элемент И 35, элемент ИЛИ 36, элемент И 37, элемент ИЛИ 38, входы 39 - 45, выходы 46 - 51,

Блок 8 содержит группы элементов И 52,,,,,,52,, 52j,,, , , , , 52.

52

)n «

JA, ,, , , , з2,

4n

31

элементы

ИЛИ 53 - 53п группы, счетчик группы блоков элементов И 55,

54,

55

1п

jj,j,, , , I ,j,, ЬЬ-,,, , , , ,ЬЗ,

bj/j.,, , , , Ь,

Уп

бло ки

.,,,,,, . элементов ИЛИ

56 4 - 56 п группы, регистры 57, ,,,. ,,,,57 группы, входы 58 и 59, группы входов 60( - 60f, , 61 ч - 6 IP , Ь2, - 62„ , 63 ( - 63, группы выходов 64 - 64 „ и 65, - 65f, ,

Устройство работает следуклдим образом,

В исходном состоянии на регистры

ч

11

in

1,1,1,2 -гп

зано

сятся коды, пропорциональные сумме времени ввода и решения задачи и сумме времени решения задачи и вывода результатов решения. Регистры 57, установлены в нулевое состояние. На вход 9 подается низкий потенциал и тактовые импульсы, поступающие на вход 10, не проходят через элемент И 6, Коды чисел, записанных на ре- гистрах 1, и (с инверсных выходов) , подаются на блок 2, нения (i 1,.,,,п),

срав0

5

0

Блок 2 сравнения работает следую- шим образом.

На входы 19,,,, ,, ,19(„ подается код числа с регистра 1,, а на входы 19j,,,, , , 19 - код числа с регистра 1,

2,. 12

В первый момент с помощью узла , анализа разрядов анализируются старшие разряды кодов. Если старшие разряды обоих кодов равны нулю, то на выходе элемента ИЛИ-НЕ 1 If появляется высокий потенциал, который через элемент ИЛИ 15 поступает на первые входы элемента И 14, обеспечивая прохождение кодов на следующий узел 12 анализа разрядов, который работает аналогичным образом. Если 5 старшие разряды обоих кодов равны единице, то на выходе элемента ИЛИ- НЕ 11 появляется низкий потенциал. Высокий потенциал с входов 19(4, 19j,, через элементы ИЛИ 15 узлов 13„ и

13

17

3

поразрядного переноса поступает на первые входь) элементов И 14, разрешая кодам проходить на следующий узел 12 анализа разрядов.

Если старший разряд первого числ равен единице, а второго числа - нулю, то на выходе элемента ИЛИ-НЕ 11, появляется низкий потенциал, который подается на первые входы элементов ИЛИ 15 узлов 13 и 13,2. На второй вход элемента 15 узла 13, подается высокий потенциал. На выходе этого элемента появляется высокий потенциал, который подается на первые входы элементов И 14, разрешая прохождение остальных разрядов первого кода для анализа на узел 2, Второй код не поступает на узел 122, так как на входы эле- мента ИЛИ 15 уэла 13, поступают низкие потенциалы. Если код числа, подаваемого на входы 19); (,.,. . ,га) больше кода числа, подаваемого на вход 192k (,,..m), уо высокий потенциал появляется на выходе 18,s если же меньше, то на выходе 18. При равенстве кодов высокие потенциалы появляются на выходах элементов 14 узлов 13, и . С выхода 18 этот сигнал подается на элемен НЕ 16, на выходе которого формируется низкий потенциал, который подается на первый вход элемента И }7 На выходе 18 формируется низкий потенциал. Таким образом, если код, записанный на регистре 1,; , меньше и либо равен коду, записанному на регистре L-, то высокий потенциал появляется на выходе iSj, если больше - то на выходе 18.

Блоки 5, и 5 поиска экстремальных кодов производят выделение стро С минимальным и максимальным кодами из множества кодов, поступающих из регистров 1,,,... 1,„ , Ij,,... Ц. Блоки поиска экстремальных кодов 5, и 5 представляют собой специализированные однородные процессоры, ориентированные на поиск максимального и минимального кодов.

Блоки 5 и 5 выполнены в виде матрицы ячеек 20 одинаковой структуры, содержащей п строк и 2 х m столбцов. Коды времени с i-x регистров Ij,; и поступают на входы 27 i-x строк матрицы блоков 5, и 52 причем код регистра 1,, поступает на входы 27 ячеек. 20;,,... ,20, бло837644

ка 5 j и входы 27 ячеек 20, (+,) ,... ...,20,(,Ч блока 5, код регистра ; поступает на входы 27 ячеек 20;(n,,,-j,. . . .,,, 20 i(- блока 5| и входы 27 5 ячеек 20;,, . , , ,20, блока 3.

На ВХОД. 24 и 25 ячеек первой строки подаются граничные значе.ния, равные О. На входы 26; ячеек первого столбца блока 5, подключены О выходы 18, блоков 2; сравнения, на входы 26, ячеек первого столбца блока 3 - выходы 182 2; сравнения.

В блоках 5 просмотру на максимум 5 (минимум) подлежат те строки, которые содержат значения 1 на входе 26, Таким образом, в блоке 5 просмотру подлежат i-e строки, соответ- ствуюшие i-M зад.аниям, у которых 20 суммарное время ввода и решения меньше (равно) суммарному времени решения и вывода, а в блоке 5 - наоборот.

Каждая ячейка 20;; блока 5 содер- 2 жит независимые каналы поиска максимума и минимума. Канал поиска макси- кума каждой ячейки включает элементы И 30, HIW 31, И 32, ИЛИ 33 и входы 40 и 41, на которые поступают 50 сшгналы переноса от ячейки 20(,.,); , вход 44, на который поступает сигнал переноса от ячейки 20, (;,) , вход 43, на который поступает значение j-ro разряда i-ro кода, вы- 35 ходы 49 и 50, с которых сигналы переноса поступают на входы ячейки 20 (j;, следующей строки, выход 46, с которого сигнал переноса поступает на вход ячейки 20 , /;.,) следующе- 40 го столбца.

Канал поиска минимума аналогичен каналу поиска максимума за исключением того, что в нем используется инверсное значение j-ro разряда i-ro 5 кода (для получения инверсного значения используется элемент НЕ 34), Таким образом, минимум ищется как максимум среди инверсных, (обратных) кодов.

0 В каждом столбце устройства просмотру на максимум (минимум) подлежат ячейки, на входе 44 (45) которых значение сигнала равно На выходе 46 (47) 1 появляется только 5 тогда, когда j-й разряд i-ro кода равен 1 (О). Для передачи значения I в случае, когда все j-e разряды кодов содержат О (I), выходы 50 и 51 ячеек последней п -и

троки через элементы НР 2 1 ,j ( ) оединены с входами 39 (40) ячеек ервой строки. При появлении на выоде элементов НЕ 21, (215- ) высо- сго потенциала обеспечивается пеенос 1 с входа 44 (45) на выход 46 (47) в том случае, если j-e разяды кодов содержат О (1).

На выходе 46 (47) ячеек последнего столбца 1 устанавливается в тех строках, которые содержат макси- мяльное (минимальное) число. Высокий потенциал появляется на тех выходах 28 блоков 5, которые соответствуют строкам с минимальными кодами, а также на тех выходах 29 блоков 5, которые соответствуют строкам с мак- а1мальными кодами.

В случае, если минимальное число равно максимальному (т,е, когда в блоке 5 анализу подлежит только одно число), для исключения одновременного появления сигналов на выходе 28J и 29- блока 5 в каждую строку введены элементы НЕ 22; и И 231,- В этом случае высокий потенциал на выходе 28 через элемент НЕ 22; и элемент И 23; устанавливает низкий потенциал на выходе 29; .

Работа устройства начинается с подачи на вход 9 высокого потенциала. Первый тактовый импульс через элемент И 6 поступает на вход элемента 7 задержки и в блок 8 регистров, где записывается 1 по входу 59 в счетчик 54,

Пусть на регастре 1,; (i,.,,,п) находится код числа, который меньше или равен коду на регистре , В этом случае высокий потенциал появляется на первом выходе i-ro блока сравнения и поступает на первый вход 1-го элемента И 4; группы,

С прямого выхода регистра 1,; m - разрядный код времени поступает на входы элементов ИЛИ 3j, Если на регистре 1 j был нулевой код, то на выходе элемента ИЛИ 3 J имеется низкий потенциал, который поступает на второй вход элемента И 4j, Низкий потенциал с выхода последнего поступает на вход 26} блока 5, и i-я строка с нулевым кодом не участвует в просмотре на максимум (минимум)

Хотя коды с регистров и Ц; поступают на входы блоков 5 и 5, в блоке 5{ просмотру на максимум (минимум) подвергаются ненулевые

837646

коды, для которых суммарное время ввода и решения задания меньше или равно суммарному времени решения и вывода, а в блоке 5 - задания,

для которых суммарное время ввода и решения больше суммарного времени решения и вывода.

ь выводов 28 (,,,,,п) блока 5, сигналы подаются на входы 60;

)0 блока 8, с выходов 29; блока 5, - на входы 61; блока 8, с выходов 28; блока 5 - на входы 62; блока регистров, с выходов 29; блока 5 - на входы 63; блока 8,

15 Пусть в блоке 5, гжнимальный и максимальный коды находятся в строках t, q соответственно, а в блоке 5 - в строках Ь, h. Тогда высокие потенциалы формируются на выходах

20 28g и 29 блока 5, и выходах 28| и 29), блока 5г , которые передаются на входы 60f, 6Ц, 62);, 63 блока регистрюв и дальше на вторые входы элементов И 52,р, 52, ,, 52,

25 С приходом тактового импульса с элемента 7 задержки на вход 58 и входы элементов И 52 (тактовый импульс в элементе задержки задерживается на время срабатывания счетчика

30 54) на выходах элементов И 52,, 52j,, 52,1, 52(ц появляется импульс который открывает блоки элементов И ЗЗ,, , 35з|,, 3241,, Каждый блок элементов И 55 состоит из (k+1) элементов

j И (k - разрядность счетчика 54),

По второму входу блоки элементов И 55 соединены с выxoдa я 54 (первые k элементов И) и с шина- 1 высокого или низкого потенциала

40 (k+l)-й элемент И), причем группа блоков элементов И 55„,,,,,33,„ соединена с прямым выходом счетчика и шиной низкого потенциала, группа блоков элементов И 55,j,,,,, ,35/гп

45 с инверсным выходом счетчика 54 и шиной низкого потенциала, группа блоков элементов И 53,,,,,, ,559 - с инверсным выходом счетчика и шиной высокого потенциала, группа блоков

5Q элементов И ЗЗ,,,, , ,334ц выходом счетчика и шиной высокого потенциала, С выходов блоков элементов И 33,j, , ЗЗз,, 554},, коды с выходов счетчика и шин высокого или

5 низкого потенциала через блоки элементов ИЛИ 36 (каждый блок ИЛИ 36, включает (k+l) элементов ИЛИ) поступают на входы регистров 37, с выходов элементов 32,;, , 32,;, 32,;

импульс поступает на входы элемента ИЛИ 53, с выхода которого он направляется на входы синхронизации регисров 57 и через выход 65, блока регистров на входы сброса триггеров Ь; и 1,; .

Таким образом, если на входах 60j , 61о, 62(,, 63, блока 8 были высокие потенциалы, то коды заносятся на регистры 57 g, 57, 57j , 57 и об Ч (}

нуляются регистры l,j, , Ь, 1

I.

1,

Ь

Ь Mh приходом -второго тактового импульса анализируется содержимое остальных регистров 1, Регистры и 1|, установленные в нулевое состояние, на работу устройства влияния не оказывают, так как, хотя на первом выходе блоков сравнения 2, и появляется высокий потенциал, он не проходит через элемент И 4; на вход блока 5,. Устройство заканчивает свою работу после присваивания номеров всем заданиям пакета. На обслуживание задания выбираются по минимальному коду на регистрах 57,

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

Устройство для распределения заданий процессорам, содержащее первую, вторую группы регистров, группу блоков сравненияj группу элементов И, элемент И, блок формирования приоритетов, причем группа инверсны выходов i-ro (i),,.,,n; n - число заданий) регистра первой Группы соединена с первыми входами i-ro блока сравнения группы, вторые входы которого соединены с инверсными выходами i-ro регистра второй rpyniw, иыход Больше или Равно i-ro блока сравнения группы соединен с

O

5

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

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

5

tpue.l

19ft O-

/ЛН о

/J/r

-r

о-

IW

I3a

f2i

i

frtrm---

-ffL

fluf.2

Изобретение относится к области вычислительной техники и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах, предназначенных для решения задач теории расгшсаний в специализированных процессорах. Целью изобретения является повышение быстродействия устройства для распределения заданий за счет того, что в предлагаемом устройстве на каждом шаге его работы могут одновременно распределяться четыре задания. Для этого в соответствии с алгоритмом Джонсона все задания, разбираются на две группы. I-ML группу составляют задания, у которых суммарное время ввода и решения меньше либо равно суммарному времени решения и вывода, 2-ю группу - задания, у которых суммарное время решения и ввода больше суммарного времени решения и вывода. Тогда на каждом шаге работы устройства есть возможность распределять: два задания из 1-й группы (с минимальным и максимальным временем ввода и решения); два задания из 2-й группы (с максимальным и минимальным временем решения и вывода). Устройство содержит две группы регистров, группу блоков сравнения, группу элементов И, элемент И, блок регистров, группу элементов ИЛИ , два блока поиска экстремальных кодов, элемент задержки. 5 ил. (Л ю 00 00