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

 

Устройство для распределения заданий процессорам ОТНОСИТСЯ к вычислительной технике. Цель изобретения - упрощение устройства. Для этой цели в устройство введены блок 2 памяти , мультиплексор 10, формирователь 11 импульсов, элемент 12 задержки , два элемента ИЛИ 14,15, дешифратор 6, два регистра 3,4. Устройство может найти применение в многомашинных и многопроцессорных вычислительных системах для распределения нагрузки между процессорами, в частности в отказоустойчивых вычислительных системах и системах, характеризующихся неравнодоступностью процессов для различных типов запросов. В устройстве при занятости всех процессоров , способных выполнить запрашиваемую функцию, блокировки работы устройства не происходит и сразу, не. дожидаясь завершения распределения, начинается распределение следующего по очереди запроса (из блока 1 памяти ) . 1 ил. § |(Л

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

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

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

re) 4 G 06 F 9/46

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

К A BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3894836/24-24 (22) 14 ° 05 85 (46) 23.01,87 Бюл. У 3 (72) В.А. Богатырев (53) 681. 325 (088. 8) (56) Авторское свидетельство СССР

Ь 982005, кл. G 06 F 9/46, 198 1.

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

У 1205144, кл, G 05 F 9/46, 1985. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАИ (57) Устройство для распределения заданий процессорам относится к вычислительной технике. Цель изобретения — упрощение устройства. Для этой цели в устройство введены блок 2 памяти, мультиплексор 10, формирователь 11 импульсов, элемент 12 задержки, два элемента ИЛИ 14,15, дешифратор 6, два регистра 3,4. Устройство может найти применение в многомашинных и многопроцессорных вычислительных системах для распределения нагрузки между процессорами, в частности в отказоустойчнвых вычислительных системах и системах, характеризующихся неравнодоступностью процесч сов для различных типов запросов. В устройстве при занятости всех процессоров, способных выполнить запрашиваемую функцию, блокировки работы устройства не происходит и сразу, не дожидаясь завершения распределения, начинается распрецеление следующего по очереди запроса (из блока 1 памяти). 1 ил.

1 128547

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

Цель изобретения — упрощение уст ройства.

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

Устройство содержит блоки 1 и 2 памяти, регистры 3 и 4, первый счетчик 5, дешифратор 6, элемент И 7, генератор 8 импульсов, второй счетчик 9, .мультиплексор 10, формирователь 11 импульса, элементы 12 и 13 задержки, элементы ИЛИ 14 и 15, выходы 16-18, входы 19-22.

Работа устройства заключается в следующем,.

Устройство осуществляет динамичес кое распределение запросов. Сущность динамического распределения состоит в том, что при извлечении каждого запроса из общей очереди происходит его распределение с учетом функциональных воэможностей процессоров. Если все процессоры, способные выполнить запрашиваемую функцию, заняты, то блокировки распределения ос; альных запросов не происходит, при этом устройство переходит к распределению остальных запросов из очереди, а через некоторое время попытка распределейм ранее не загруженного запроса 35 повторяется.

Блок 1 памяти предназначен для хранения очереди запросов, а блок 2 памяти — для отображения функциональных возможностей процессоров. При 40 этом в ячейке ij блока 2 памяти со— держится "1", если j-й процессор способен выполнить функцию, f, в противном случае в ней находится "0" (i

1,2,3,...,n; j = 1,2,3,...,m). Pe- 45 гистр 4 хранит информацию о занятости процессоров: j-разряд регистра 4 содержит "1", если 3-процессор не за .ият, в противном случае он содержит

"0". Обнуление j-го разряда регистра 50

4 осуществляется устройством при загрузке j-го процессора, а запись в этот разряд "1" осуществляется j-м процессором при завершении обслуживания загруженного в него запросами. 55

Перед началом распределения на вход 22 регистра 3 подается потенци° ал, по которому происходит обнуление

4 2 регистра 3. При этом перед началом работы по распределению запросов на вход 20 запрос абонентом (источником запросов) не выдается и- на входе 21 отсутствует сигнал сопровождения запроса (на входах 20 и 21 блока 1 памяти содержится нулевой код) . На инверсном выходе первого разряда регистра 3 содержится "1" — в этом случае сигнал переноса со счетчика 9, проходя через элементы И 7 и ИЛИ 15, поступает на вход записи блока 1 памяти.

По этому сигналу осуществляется запись "нулевого" кода с входов 20 и 21 в блок 1 памяти по адресу с выхода счетчика 5 (происходит обнуление ячейки блока 1 памяти по адресу счетчика 5), С некоторой задержкой на элементе 12 по сигналу переноса со счетчика 9 осуществляется увеличение на 1 содержимого счетчика 5. При этом по следующему сигналу переноса осуществляется обнуление следующей ячейки блока 1 памяти и т.д. После завершения цикла (одного или нескольких) обнуления всех ячеек блока 1 памяти абонент (источник запросов) может подавать запросы в устройство для их распределения по процессорам, причем к этому времени сигнал с входа 22 обнуления регистра 3 снимается. Запрос (код запрашиваемой функции) выдается абонентом на вход 20, а сигнал сопровождения ("1") на вход 21.

При поступлении первого запроса на

1 инверсном выходе первого разряда регистра 3 находится "1" (так как в регистре 3 находится нулевой код, т.е. с блока 1 памяти не выдан запрос, предназначенный для распределения), при этом выборки мультиплексора 10 не происходит и сигнал переноса со счетчика 9 передается через элементы И 7 и ИЛИ 15 на вход записи блока 1 памяти (при наличии сигнала на выходе элемента ИЛИ 15 происходит запись кода с входа 20 и 21 в блок 1 памяти по адресу с выхода счетчика 5, а при отсутствии этого сигнала — чтение из блока 1 памяти по тому же адресу). Таким образом,. по сигналу переноса со счетчика 9 код запроса с входа 20 и сигнал с входа 21 записываются в блок 1 памяти по адресу со счетчика 5 (сигнал с входа 21 записывается в первый разряд ячейки памяти, содержимое которой при считывании заносится в первый разряд регистра

1285474

3). Кроме того, по сигналу переноса со счетчика 9 с задержкой (задержка определяется временем записи в блоке

1 п;мяти) на элементе 12 содержимое счетчика 5 увеличивается на "1", при- 5 чем к этому моменту импульсный сигнал на выходе элемента ИЛИ 15 отсутствует и происходит чтение из блока

1 памяти. Но сигналу с элемента 13 задержки (задержка определяется временем чтения содержимого блока 1 памяти по новому адресу со счетчика 5) происходит обнуление счетчика 9 и считывание содержимого блока 1 памяти по новому адресу счетчика 5 в регистр

3. Абонент, получив сигнал, вырабатываемый в момент занесения запроса в блок 1 памяти (в очередь), снимает (через время записи в память) с входов 20 и 21 запрос и при необходимости выставляет новый.

Если в регистр 3 заносится код с ячейки блока памяти, содержащий запрос (" 1" в первом разряде регистра

3), то на инверсном выходе первого разряда регистра 3 появляется "0", блокирующий элемент И 7 и осущест- г вляющий выборку мультиплексора 10.

При поступлении каждого импульса с генератора 8 через мультиплексор 10 осуществляется последовательное подключение к входу выборки блока 2 памяти разрядов регистра 4 (информации о занятости процессоров с 1-го по

m-й). Последовательное подключение 35 разрядов регистра 4 осуществляется до момента появления на выходе блока

2 памяти сигнала. Этот сигнал вырабатывается, если процессор, определяемый счетчиком 9, не занят (сигнал с выхода мультиплексора 10 осуществляет выборку блока 2 памяти) и способен выполнить запрашиваемую функцию f( (на выход блока 2 памяти выдается

"1" с его ячейки, адрес строки кото- 45 рой йоступает с регистра 3, а адрес столИца — с выхода счетчика 9). При появлении сигнала на выходе блока 2 памяти осуществляется выборка дешифратора 6, на j-м выходе которого (j определяет адрес с выхода счетчика 9) появляетсж сигнал 18 загрузки j-ro

«! процессора. Выбранный процессор (j é) загружается на выполнение запроса, код которого снимается с выхода 16 устройства. По сигналу j-ro выхода

18 дешифратора 6 осуществляется обну-. ление j-ro разряда регистра 4, что приводит к исчезновению сигнала выборки блока 2 памяти и, соответственно. к пропаданию сигнала на выходе блока 2 памяти. По заднему фронту сигнала на выходе блока 2 памяти на формирователе 11 вырабатывается сигнал, по которому в ячейку блока 1 памяти по адресу с выхода счетчика

5 записывается код запроса с входа 20 и сигнал сопровождения с входа 21.

Если абонент запроса не выставил, то в адресуемую ячейку блока 1 памяти заносится нулевой код с входа 20 и

2i. По сигналу 17 абонент через время, достаточное для занесения инфор-:; мации в блок памяти, снимает запрос и при необходимости выставляет новый.

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

ИЛИ 15 уже отсутствует и происходит чтение с блока 1 памяти. По сигналу с выхода элемента 13 задержки (за-. держка равна времени считывания информации с блока 1 памяти по новому адресу с выхода счетчика 5) происходит занесение кода с выхода блока 1 памяти в регистр 3. В результате этого в регистр 3 заносится запрос, хранимый по адресу блока 1 памяти, определяемому увеличенным содержимым счетчика 5 (или нулевой код, если по этому адресу запроса не занесено).

Кроме того, по сигналу с элемента 13 задержки обнуляется счетчик 9.

Если за полный цикл работы счетчика 9 (от его обнуления до формирования сигнала переноса) не найден свободный процессор, способный выполнить запрашиваемую функцию, то по сигналу переноса счетчика 9 содержимое счетчика 5 увеличивается на " 1" и в регистр 3 записывается запрос, хранимый в блоке 1 памяти по новому адресу со счетчика 5. В ячейке по старому адресу 1 нераспределенный" запрос сохраняется, а занесения запроса в очередь (блок 1 памяти) по этому адресу не происходит и сигнал на выходе 17 устройства не формируется. При этом абонент сохраняет на входах 20 и 21 старый, не поставленный в очередь, запрос. Через время

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

Техред А.Кравчук Корректор Н.Король

Редактор E.Ïàïï

Заказ 7526/51 Тираж 670 Подписное

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

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

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

5 128 перебора счетчиком 5 всех ячеек блока 1 памяти попытка распределения

"нераспределенного на предыдущем цикле запроса повторяется.

Таким образом, при занятости всех процессоров, способных выполнить запрашиваемую функцию, блокировки работы устройства не происходит, и сразу без дожидания завершения рас1 пределения, начинается распределение следующего по очереди запроса 1,из блока 1 памяти).

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

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

5474 6 выходов запроса ус1ройстна и с перной группой информационных входов первого регистра, вторая группа информационных входов которого соединена с группой входов занятости процессора устройства, информационные выходы первого регистра соединены с информационными входами мультиплексора, выход которого соединен с

l0 входом выборки второго блока памяти, выход BTopol блока памяти соединен с управляющим входом дешифратора и с входом формирователя импульсов, выход которого соединен с первыми входами первого и второго элементов

ИЛИ, выход первого элемента ИЛИ соединен с входом второго элемента задержки, выход которого соединен со счетным входом второго счетчика и

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