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

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

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУБЛИК (51) 4 С 06 F 9/46 15 20

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

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3886416/24-24 (22) 19.04.85 (46) 15.01.87. Бюл. В 2 (72) А. Я. Матов, С. Е, Карловский, А. М, Макарчук, В. Н, Дроник и И, М. Якуб (53) 681.325(088.8) (56) Авторское свидетельство СССР

)) - 959083, кл. G 06 F 9/46, )983, Авторское свидетельство СССР .) - 1065856, кл. G 06 F 9/46, 1984, Фет Я. И. Параллельные процессоры для управляющих систем. — M.

Энергоиздат, 1981, e.. 99. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

: ЗАДАНИЙ ПРОЦЕССОРАМ . (57) Изобретение относится к области вычислительной техники и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах, предназначенных для решения задач теории расписаний в специализированных процессорах, Целью изобретения является повышение быстродействия устройства для рас„„SU„„12 А1 пределения заданий за счет того, что в предлагаемом устройстве на каждом шаге его работы могут одновременно распределяться четыре задания, Для этого в соответствии с алгоритмом Джонсона все задания. разбираются на две группы. 1-ю. группу составляют задания, у которых суммарное время ввода и решения меньше либо равно суммарному времени решения и вывода, 2-ю группу — задания, у которых суммарное время решения и ввода больше суммарного времени решения и вывода, Тогда на каждом шаге работы устройства есть возможность распределять: два задания из 1-й группы (с минимальным и максимальным временем ввода и решения); два задания из 2-й группы (с максимальным и минимальным временем решения и вывода), Устройство содержит две группы регистров, группу блоков сравнения, группу элементов И, элемент И, блок регистров, группу элементов ИЛИ, два блока поиска экстремальных кодов, элемент задержки. 5 ил.

1283764

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

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

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

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

Устройство для распределения заданий содержит регистры 1« -1 первой группы, регистры 1, -1 „ второй группы, блоки 2, -2 «сравнения группы, элементы ИЛИ 3 < -3> группы, элементы И 4 -4 группы и блоки

5 и 5 поиска экстремальных кодов, элемент И 6, элемент 7 задержки, блок 8 формирования приоритетов, входы 9 и 10, Блок 2 сравнения содержит элементы ИЛИ вЂ 11, — 11щ (m — разрядность кодов временных на первой, второй группе регистров), узлы 12 — 12 анализа разрядов, которые состоят из узлов 13„, 13г,...13щ поразрядного переноса включающих в свой состав элементы И 14 и элементы

ИЛИ 15, элемент НЕ 16, элемент И 17, выходы 18< и 18г, ВХОды !9« > 19,г, 1

° 1 9 ) ) 9г 1 9г ° е 19г а

Блок 5 поиска экстремальных кодов содержит ячейки 20„,...

0Нг„,1, 20г„. ° °,20„(1, элементы HE 21«»21«(г 1 ° 21 „ ...,?1г!г„,! группы, элементы HE 22

? 2 „группы, элементы И 23» - 23„ группы, группы входов 24 — 24„ г rn

25 — 25(г„,, группу входов 26

2б„, группу входов 27„...,.,27

27„... °,27„, !, группу выходов

28 -28„, 29, — 29п, Ячейка 20 блока поиска экстремальных кодов 5 включает элемент

И 30, элемент ИЛИ 31, элемент И 32, элемент ИЛИ 33, элемент HE 34, элемент И 35, элемент ИЛИ 36, элемент

И 37, элемент ИЛИ 38, входы 39 — 45, выходы 46 — 51, Блок 8 содержит группы элементов

H 52«...,,52,„, 52г„,, °,52 „52 „

52! „, 52»„..., 52»„, элементы

ИЛИ 53 — 53„группы, счетчик 54, группы блоков элементов И 55«,...

55 п 55г„...,55г„, 55з 55зл

554„...,,55»„, блоки элементов ИЛИ

56 — 56 „группы, регистры 57..., . ..., 57„группы, входы 58 и 59, группы входов 60 — 60, 61» — 61„, 62»

62„, 63 — 63» группы выходов 64

64 и H 65 65„°

Устройство работает следующим образом, В исходном состоянии на регистры !

» 11 ° l„H l,, l.ю .° .ю,1, г > гг гл сятся коды, пропорциональные сумме времени ввода и решения задачи и сумме времени решения задачи и вывода результатов решения. Регистры

57, установлены в нулевое состояние.

На вход 9 подается низкий потенциал и тактовые импульсы, поступающие на вход 10, не проходят через элемент

И 6. Коды чисел, записанных на регистрах l „и 1; (c. инверсных выходов), подаются на блок 2; сравнения (i = l...n), Блок 2 сравнения работает следующим образом, На входы 19,,..., 19 подается код числа с регистра l;, а на входы

19z» °,19 „„— код числа с регистра

1 „, В первый момент с помощью узла

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

Высокий потенциал с входов 19н, 19, через элементы ИЛИ 15 узлов 13« и

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

11» появляется низкий потенциал, который подается на первые входы элементов ИЛИ 15 узлов 13<» и 13,, На второй вход элемента 15 узла

13„, подается высокий потенциал, На выходе этого элемента появляется высокий потенциал, который подается на первые входы элементов И 14, разрешая прохождение остальных разрядов первого кода для анализа на узел 122, Второй код не поступает на узел 122, так как на входы элемента ИЛИ 15 узла 13, поступают низкие потенциалы. Если код числа, подаваемого на входы 19», (i=1..., ...,m) больше кодачисла, подаваемого на вход 192<, (k=1,...m), то высокий потенциал появляется на выходе 18,> если же меньше, то на выходе 182, При равенстве кодов высокие потенциалы появляются на выходах элементов 14 узлов 13, и 13„ С выхода

18» этот сигнал подается на элемент

НЕ 16, на выходе которого формируется низкий потенциал, который подается на первый вход элемента И 17, На выходе 182 формируется низкий потенциал. Таким образом, если код, записанный на регистре 1„,, меньше и либо равен коду, записанному на регистре 1, то высокий потенциал по2< является на выходе 18,, если больше — то на выходе 182, 1

Блоки 5„и 5 поиска экстремальных кодов производят выделение строк с минимальным и максимальным кодами из множества кодов, поступающих регистров 1»< > ° ° ° 1< > lz< ° ° °

Блоки поиска экстремальных кодов 5, и 5 представляют собой специализированные однородные процессоры, ориентированные на поиск максимального и минимального кодов.

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

11 2<

1.-х строк матрицы блоков 5„и 52, причем код регистра 1 „ поступает на входы 27 ячеек. 20, „...,20 »< бло283764 4 ка 5, и входы 27 ячеек 20; р „1 >... ...,20; блока 5, код регистра 1, поступает на входы? 7 ячеек 20„ (< <„ >...

20 „(1 блока 51 и входы 27 ячеек 20;..., °, 20; блока 5

На входы 24 и 25 ячеек первой строки подаются граничные значения, равные "0", На входы 26„ ячеек первого столбца блока 5, подключены выходы 18< блоков 2; сравнения, на входы 26; ячеек первого столбца блока 5 — выходы 182 блоков 2; сравнения.

В блоках 5 просмотру на максимум (минцмум) подлежат те строки, которые содержат значения "1" на входе

26, Таким образом, в блоке 5» просмотру подлежат i-e строки, соответствующие i-м заданиям, у которых суммарное время ввода и решения

20 меньше (равно) суммарному времени решения и вывода, а в блоке 52 наоборот.

Каждая ячейка 20 блока 5 содер

30 сигналы переноса от ячейки 20(,<1< вход 44, на который поступает сигнал переноса от ячейки 20, >

1 вход 43, на который поступает значение j-го разряда i-го кода, вы35 ходы 49 и 50, с которых сигналы переноса поступают на входы ячейки

20<„ +,1 следующей строки, выход 46, с которого сигнал переноса поступает на вход ячейки 20 1 (1<) следующе40 го столбца.

Канал поиска минимума аналогичен каналу поиска максимума за исключением того, что в нем используется инверсное значение j-ro разряда 2-го

45 кода (для получения инверсного значения используется элемент НЕ 34), Таким образом, минимум ищется как максимум среди инверсных (обратных) кодов, 50 В каждом столбце устройства просмотру на максимум (минимум) подлежат ячейки, на входе 44 (45) которых значение сигнала равно "1",. На выходе 46 (47) "1" появляется только

55 тогда, когда j-й разряд i-го кода равен "1" ("О») . Для передачи значения " 1" в случае, когда все j- e разряды кодов содержат > 0" ("1"), выходы 50 и 51 ячеек последней »» --й

5 1 строки через элементы HF 2 „(21 ) J соединены с входами 39 (40) ячеек первой строки. При появлении на выходе элементов HE 21„(21 ) высог кого потенциала обеспечивается перенос "1" с входа 44 (45) на выход

46 (47) в том случае, если j-е разряды кодов содержат "0" ("1") .

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

28 блоков 5, которые соответствуют строкам с минимальными кодами, а также на тех выходах 29 блоков 5, которые соответствуют строкам с максимальными кодами.

В случае, если минимальное число равно максимальному (т,е, когда в блоке 5 анализу подлежит только одно число), для исключения одновременного появления сигналов на выходе

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

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

59 в счетчик 54, Пусть на регистре 1„ (i=I...,,n) находится код числа, который меньше или ранен коду на регистре 1,, В этом случае высокий потенциал появляется на первом выходе i-го блока сравнения и поступает на первый вход

i-ro элемента И 4„ группы, С прямого выхода регистра 1,; ш— разрядный код времени поступает на входы элементов ИЛИ 3, . Если на регистре 1, был нулевой код, то на

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

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

f5

Зо

55 выводов 28, (i=I,...,n) блока 5, сигналы подаются на входы 60; блока 8, с выходов 29; блока 5, на входы 61; блока 8, с выходов 28; блока 5 — на входы 62; блока регистров, с выходов 29; блока 5 - на входы 63; блока 8.

Пусть в блоке 5, ьжнимальный и максимальный коды находятся в строках f q соответственно, а в блоке

5 — в строках Ь, h. Тогда высокие потенциалы формируются на выходах

28) и 29 блока 5 и выходах 28 и

291, блока 5, которые передаются на входы 60, 61, 62, 63 блока регистров и дальше на вторые входы элементов И 52«, 52» 52>>, 52 1,.

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

54) на выходах элементов И 52„, 5Q, 52 >, 52 1, появляется импульс, который открывает блоки элементов И 55<<, 55,1, 55, 52<1,, Каждый блок элементов И 55 состоит из (k+ 1) элементов

И (k — разрядность счетчика 54).

По второму входу блоки элементов

И 55 соединены с выходами счетчика

54 (первые k элементов И) и с шинами высокого или низкого потенциала (k+ 1)-й элемент И), причем группа блоков элементов И 55п...,,55,„ соединена с прямым выходом счетчика и шиной низкого потенциала, группа блоков элементов И 55 „ ...,55 „ с инверсным выходом счетчика 54 и шиной низкого потенциала, группа блоков элементов И 55щ,...,55 „ с инверсным выходом счетчика и шиной высокого потенциала, группа блоков элементов И 554„ ...,55 - с прямком выходом счетчика и шиной высокого потенциала. С выходов блоков элементов И 55)), 55), 55 g, 55,!1,, коды с Выходов счетчика и шин высокого или низкого потенциала через блоки элементов ИЛИ 56 (каждый блок ИЛИ 56; включает (k+1) элементов ИЛИ) поступают на входы регистров 57, с выходов элементов 52<,, 52,, 52 ;, 524, ?83764 6 коды, для которых суммарное. время ввода и решения э адания меньше или равно суммарному времени решения и вывода, а в блоке 5 — задания, для которых суммарное время ввода и решения больше суммарного времени решения и вывода, импульс поступает на входы элемента

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

1„; и 1г„, Таким образом, если на входах

60, 61, 621, 631, блока 8 были высокие потенциалы, то коды заносятся на регистры 57, 57% 571, 57 и обнуляются регистры 11, 1г, 1, 12

11 1г 1 ь 1гЬ

С приходом второго тактового импульса анализируется содержимое остальных регистров 1, Регистры 1, и

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

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

Устройство для распределения заданий процессорам, содержащее перВую, вторую группы регистров, группу блоков сравнения, группу элементов И, элемент И, блок формирования приоритетов, причем группа инверсных выходов i"ãî (i=1...,,n; п — число заданий} регистра первой группы со" единена с первыми ВХОдами 1-го блока сравнения группы, вторые входы которого соединены с инверсными выходами i-го регистра второй группы, выход "Больше" или "Равно" i"го блока сравнения группы соединен с

1283764 8 первым входом 1-го элемента И группы, выход элемента И подсоединен к управляющему входу блока формирования приоритетов ВыхОд котОрогО пОд соединен к входам сброса регистров первой и второй групп, тактовый вход и вход запуска устройства соединены соответственно с первым и вторым входами элемента И, о т л и—

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

25 экстремальных .кодов нодсоединена к выходам элементов И группы, вторая группа входов второго блока поиска экстремальных кодов подсоединена к выходам "Меньше" блоков сравнения

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

Е283764

° °

° °

1?гю

1 2837 { .14

Б/гт

Б2

Составитель М, Сорочан

Редактор Л. Пчолинская Техред Л.Олейник Корректор И, Самборская

"Заказ 7443/48 Тираж 670 Подписное

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

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

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