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

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

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

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

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

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

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

Блок 1 памяти предназначен для хранения очереди запросов, а блок 2 памяти - для отображения функциональ ных возможностей процессоров. При этом в ячейке ij блока 2 памяти содержится 1, если j-й процессор способен выполнить функцию, f; , в протином случае в ней находится О (i « 1,2,3,...,nj j 1,2,3,...,m). Ре- гистр 4 хранит информацию о занятост процессоров: j-разряд регистра 4 содержит 1, если j-процессор не за- ият, в противном случае он содержит О. Обнуление j-ro разряда регистра 4 осуществляется устройством при загрузке j-ro процессора, а запись в этот разряд 1 осуществляется j-м процессором при завершении обслуживания з агруженного в него запросами.

Перед началом распределения на

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

5

О

S

0

5

О 50 5

регистра 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.

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

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

3

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

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

Если в регистр 3 заносится код с ячейки блока 1 памяти, содержащий запрос (1 в первом разряде регистр 3), то на инверсном выходе первого разряда регистра 3 появляется О, блокирующий элемент И 7 и осуществляющий выборку мультиплексора 10. При поступлении каждого импульса с генератора 8 через мультиплексор 10 осуществляется последовательное подключение к входу выборки блока 2 памяти разрядов регистра 4 (информации о занятости процессоров с 1-го по т-й). Последовательное подключение разрядов регистра 4 осуществляется до момента появления на выходе блока

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

1 с его ячейки, адрес строки которой поступает с регистра 3, а адрес столВца - с выхода счетчика 9). При появлении сигнала на выходе блока 2 памяти осуществляется выборка дешифратора 6, на J-M выходе которого (j определяет адрес с выхода счетччка 9)

появляется- сигнал 18; загрузки j-ro процессора. Выбранный процессор (j-й) загружается на выполнение запроса, код которого снимается с выхода 16 устройства. По сигналу j-ro выхода 18 дешифратора 6 осуществляется обнуление j-ro разряда регистра 4, что

0

5

5

приводит к исчезновению сигнала выборки блока 2 памяти и, соответственно, к пропаданию сигнала на выходе блока 2 памяти. По заднему фронту сигнала на выходе блока 2 памяти на формирователе 11 вырабатьгоается сигнал, по которому в ячейку блока 1 памяти по адресу с выхода счетчика 5 записывается код запроса с входа 20 и сигнал сопровождения с входа 21. Если абонент запроса не выставил, то в адресуемую ячейку блока 1 памяти заносится нулевой код с входа 20 и 21. По сигналу 17 абонент через время, достаточное для занесения инфор-.

0

5

0

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

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

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

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

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

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

Редактор Е.Папп Заказ 7526/51

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

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

Тираж 670Подписное

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

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

5

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

0

5

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