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

 

УСТРОЙСТВО ,ТЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ, содержащее Л каналов ( р - число решаемых задач ), каждый из которых, кроме первого и п-го, содержит четыре элемента И, три элемента ИЛИ, элемент ИЛИ-НЕ и триггер, первый канал Содержит четьфе элемента И, два элемента ИЛИ и триггер, а п -и канал содержит четыре элемента И, два элемента ИЛИ, элемент ИЛИ-НЕ и триггер , причем в каждом канале выходы первого и второго элементов И соединены с соответствующими входами первого элемента ИЛИ, выходы третьего и четвертого элементов И соединены с соответствующими входами второго элемента ИЛИ, нулевой выход триггера канала (i 2 П-1) соединен с первым входом третьего элемента ИЛИ i-го канала, второй вход которого, кроме второго канала, соединен с выходом третьего элемента ИЛИ ( i - 1)-го канала и первым входом элемента ИДИ-НЕ i -го канала, единичный выход триггера i-ro канала соединен с вторым входом элемента ИЛИ-НЕ i -го канала, нулевой выход триггера первого канала соединен с вторым входом третьего элемента ИЛИ и первым входом элемента ИЛИ-НЕ второго канала, единичный выход триггера п-го канала соединен с первым входом элемента ИЛИ-НЕ п-го канала, второй вход которого соединен с выходом третьего элемента ИЛИ (п-1)-го канала, отличающееся тем, что, с целью расширения области применения, оно содержит генератор тактовых импульсов , элемент задержки, элемент И, счетчик импульсов, схему сравнения, i регистр, два триггера, два элемента ИЛИ-НЕ, а в каждом i-м канале (Л сдвигающий регистр, пятый и шестой элементы И, четвертый и пятый элементы ИЛИ и элемент И-НЕ, а первый и п-й каналы содержат сдвигающий регистр, пятый и шестой элементы И, третий и 1етвертый элементы ИЛИ и элемент И-НЕ, причем выход генера00 тора тактовых импульсов соединен со со с первым входом элемента И, второй вход которого соединен с единичным О) выходом первого триггера, единич ный вход которого соединен с входом пуска устройства, нулевой ° вход первого триггера соединен с выходом схемы сравнения, с входом сброса счетчика импульсов, с первыми входами пятых элементов И всех каналов и через элемент задержки с нулевыми входами триггеров всех каналов, единичные входы которых соединены с выходами элементов И-НЕ соответствующих каналов, пер- . вые входы которых соединены с выходами третьих элементов ИЛИ пер

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

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

РЕСПУБЛИК (19) (И)

А (>l)4 G 06 F 9/46

С БРЕТН-ця ": -

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

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

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

)1- 548859, кл. С 06 F 9/46, 1974.

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

У 964643, кл. G 06 F 9/46, 1980. (54)(57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ, содержащее каналов (П вЂ” число решаемых задач), каждый из которых, кроме первого и n --ro содержит четыре элемента И, три элемента ИЛИ, элемент ИЛИ-НЕ и триггер, первый канал содержит четыре элемента И, два элемента ИЛИ и триггер, а и -й канал содержит четыре элемента И, два элемента ИЛИ, элемент ИЛИ-НЕ и триггер, причем в каждом канале выходы первого и второго элементов И соединены с соответствующими входами первого элемента ИЛИ, выходы третьего и четвертого элементов И соединены с соответствующими входами второго элемента ИЛИ, нулевой выход триггера 1-)го канала ((=2,..., и -1) соединен с первым входом третьего элемента ИЛИ j -ro канала, второй. вход которого, кроме второго канала, соединен с выходом третьего элемента ИЛИ (j — - 1)-го канала и первым входом элемента ИЛИ-НЕ

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

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

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

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

И-НЕ соответствующих каналов, пер- . вые входы которых соединены с выходами третьих элементов ИЛИ пер 1183967 лов вого и h --го каналов и четвертых элементов ИЛИ всех остальных каналов и первыми входами шестых элементов И соответствующих каналов, вторые входы которых соединены с выходами первых элементов ИЛИ соответствующих каналов, выход шестого элемента И 1-го канала (1 2,. ° ., n -1) соединен с первым входом пятбго элемента ИЛИ 1 -ro канала и с -м входом первого элемента ИЛИ-НЕ, выходы шестых элементов И первого и h -го каналов соединены с первыми входами. четвертых элементов ИЛИ соответственно первого и и -го каналов и с соответствующими входами .первого элемента ИЛИ-НЕ, выход которого соединен с вторыми входами четвертых элементов. ИЛИ первого и п -го каналов и пятых элементов ИЛИ всех остальных каналов, выходы четвертого элемента ИЛИ первого и и --го каналов соединены с вторыми входами элементов И-НЕ соответственно с первого и и-го каналов, выход пятого элемента ИЛИ -го канала соединен с вторым входом элемента И-НЕ i-ro канала, единичный выход триггера первого канала соединен с вторым входом пятого элемента И и первыми входами с первого по четвертый элементов

И первого канала, единичный выход триггера -го (1 =2,... n ) канала соединен с первыми входами с первого по четвертый элементов И j --r o канала,.выход элемента ИЛИ-НЕ i --ro канала соединен с вторым входом пятого элемента И i-го канала, выходы пятых элементов И всех каналов являются выходами устройства, выхоцы вторых элементов ИЛИ первого и n --ro каналов соединены с первыми входами третьих элементов ИЛИ соответственно первого и и -го каналов и с соответ-. ствующими входами второго элемента

ИЛИ-НЕ, выход второго элемента ИЛИ

i -го канала (1 = 2,..., 5 -!) соединен с первым входом четвертого элемента ИЛИ i-го канала и с ! -м входом второго элемента ИЛИ-НЕ, выход которого соединен с вторыми входамп третьих элементов ИЛИ первого и n -ro каналов и четвертых элементов ИЛИ i --x каналов, вторые входы первого и второго элементов

И каждого канала соединены с соответствующими выходами (ln — 1) разряда (— число запросов) сдвигающего регистра своего канала, вторые входы третьего и четвертого элементов И каждого канала соединены с соответствующими выходами

ln --ГО РаЗРЯДа СДВИГаЮЩЕГО РЕГИСтра своего канала, информационный вход которого соединен.с соответствующим входом кода приоритета устройства, выход элемента И соединен со счетным входом счетчика импульсов и с входами сдвига сдвигаюющих регистров всех каналов, выход счетчика импульсов соединен с первым входом схемы сравнения, второй вход которой соединен с выходом регистра, информационный вход которого соединен с входом кода коэффициента пересчета устрОйства, вход режима которого соединен с входом второго триггера, единичный и нулевой входы которого соединены с третьими входами соответственно первого и третьего элементов И и второго и четвертого элементов И всех канаИзобретение относится к вычислительной технике, и может быть использовано при организации вычислительного процесса по обработке пакета задач в многопроцессорной (многомашинной) вычислительной

1 системе.

Цель изобретения — расширение области применения.

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

Устройство содержит: m — разрядные сдвигающие (со сдвигом на два разряда в сторону старших разрядов) регистры 1 1 — 1 „ (n - количество задач в пакете) по числу задач в пакете первые 2 — 2 вто J

"- h рые 1 — э и, третьи 41 — 4 и и

67 з 11839 четвертые 5 — 5,1 элементы И, вторые 6„ 7„ 7„ элементы ИЛИ, элементы ИЛИ 3„ - 6 шестые элементы И 9„ — 9п, элементы ИЛИ 10„ — 10„, элементы И-НЕ 5

11„- 11„, триггеры 12 — 12п элементы HJIH 132 — 13п, элемен; ты ИЛИ-НЕ 144 — I4n, пятые элементы Ч 15, — 15, второй элемент

ИЛИ-НЕ 16, первый элемент ИЛИ-НЕ 17, второй триггер 18, элемент 19 задержки, регистр 20, схему 21 сравнения, счетчик 22 импульсов, пер-, вый триггер 23, элемент И 24, генератор 25 тактовых импульсов, вход 15

26 режима работы, информационные входы 27 — 27, пусковой вход

28, установочный вход 29, выходы 30.,—

30„ устройства.

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

1„ — 1„ находятся коды, соответствуюгие весам задач и заносимые по входам 27„ - 27„ . Все триггеры 12 устанавливают в нулевое состояние (уста-! новочные входы не показаны). 25

На триггер 18 по входу 26 заносится код режима работы устройства, а на регистр 20 по входу 29 — код ко-. эфа1ициента пересчета счетчика 22, равного числу m/2-1, (m — разрядность зО регистров 1). Единичному (нулевому) состоянию триггера 18 соответствует режим распределения задач по процессорам вычислительной системы по критерию минимума (максимума)

35 веса задачи соответственно.

Работа устройства начинается после сброса триггеров 12 установки триггера 23 по входу 26, в результате чего открывается элемент И 24. К этому .40 времени коды с выходов двух триггеров старших разрядов m -го и (m — 1)го регистров 1 поступают через одноименные элементы И 2 или И 3, на третьи. входы которых подается высокий потенциал с обратных выходов одноименных триггеров 12, и элемент

ИЛИ 7 для (m — 1)-го разряда, и элемент И 4 или И 5 (в зависимости от состояния триггера 18) для m-го

50 разряда для последующего анализа.

В начале анализируются старшие разряды и кодов. Для этого сигнал с выхода элемента ИЛИ 6 (i = 1, .n) поступает на i-й вход элемента ИЛИНЕ 16 и на первый вход элемента

ИЛИ 8., на второй вход которого поступает сигнал с выхода элемента ИЛИНЕ 16. Если во всех старших m-x разрядах регистров 1 храйится нуль, то на выходе элемента ИЛИ-НЕ 16 будет сигнал логической единицы, во всех других случаях на выходе элемента ИЛИ-НЕ 16 сигнал логического нуля. Сигнал с выхода элемента ИЛИ 8 поступает, на первый вход элемента

И-НЕ 11 и первый вход элемента И 9

1 второй вход которого подсоединен к выходу элемента ИЛИ /., на котором находится сигнал состояния (m-1)-ro триггера регистра 11 . Сигнал с выхода элемента И 9,. поступает на i-й вход элемента ИЛИ-НЕ 17 и на первый вход элемента ИЛИ 10 второй вход которого подсоединен к выходу элемента ИЛИ-НЕ 17, а выход — к второму входу элемента

И-НЕ 11

Таким образом, если хотя бы на одном, например, i-м регистре 1; (i = 1,, n) в (m I)-м разряде содержится код единицы,то на выходе элемента И 9 будет сигнал логической единицы, который поступает на

i-й вход элемента ИЛИ-НЕ 17 (при наличии хотя бы одного единичного сигнала на триггерах m-го и (ш-1)ro разрядов регистра 1, j = 1,...

n). С выхода элемента ИЛИ-НЕ 17 сигнал логического нуля поступает на один из входов элементов ИЛИ IO на второй вход каждого из которых поступает сигнал логической единицы с выхода элемента И 9 . Поэтому, 1 если на выходе элемента ИЛИ 6 высокий потенциал, то на выходе элемента И-НЕ 11. нулевой потенi циал. В случае, если значение

m-го разряда регистра 1. равню ну

1 лю, то на выходе элемента ИЛИ 6 °

1 будет сигнал логического нуля, на выходе элементов ИЛИ 8., ИЛИ

10 — также сигнал логического нуля, а на выходе элемента И-НЕ 11. пояI вится сигнал логической единицы, который перебросит триггер 12: в

1 единичное состояние, после чего прекращается подача высокого потенциала с обратного выхода. триггера 12; на третьи входы элементов

И 2; и И 3, (1 = 1,...п).

Аналогична работа устройства и при других комбинациях старших двух разрядов регистров 1.

Для анализа следующей пары разрядов сравниваемых кодов с вы1i 93967

ВН КИПИ

Тираж 709

Заказ 6272/49

Подписное

JP р Юе

Mr JOg хода генератора 25 через элемент

И 24 поступает очередной импульс сдвига на регистры 11 - 1,„, по которому информация в регистрах

1 сдвигается на два разряда вправо, а к содержимому счетчика 22 прибавляется единица. После сдвига информации в регистрах 1 аналогич- . но анализируется следующая па- 10 ра разрядов.

Сдвиг информации на. регистрах 21 продолжается до тех пор, пока не произойдет сравнение в схеме 1, после чего триггер 23 и счетчик 15

22 сбрасываются.

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

30 устройства (выходах открытых элементов И 151 — 15„появится единичный

:сигнал только на одном выходе 30, 1 Э причем i c j, где i, j = 1,...n, т.е. предпочтение отдается той задаче, порядковый номер которой наименьший среди задач, имеющих одинаковое требуемое время для решения. Это дос-.. тигается тем, что высокий потенциал с единичного выхода триггера 12 по1 дается через элементы ИЛИ 131 (z

2,. ° .n — 1) на первые входы последующих элементов ИЛИ-НЕ 14; „, вследствие чего на всех последующих выходах 30 (j Ъ з.)будет нулевой сиг3 нал. Сигнал сравнения с выхода схемы

21 через элемент t 9 задержки сбрасывает в нулевое состояние триггеры 12, подготавливая тем самым устройство к новому циклу работы. Кроме того, для выбранной задачи (пусть ее номер будет равным i, i = 1,...n) сбрасывается регистр 1 если триггер

18 установлен в нулевое состояние для режима минимального времени

t реализации пакета задач, или устанавливается в единичное состояние, если триггер 18 установлен в единичное состояние для ре-: жима минимального среднего времени ожидания задачи в пакете. Нпп ППП "Патент" ,г.ужгород, ул.Проектная, 4