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

25

1131082

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

Цель изобретения - повьяпение быст- 5

родействия устройства. На фиг. 1 показана структурная схе- 4a устройства} на фиг. 2 - структурная схема блока распределения процессоров. О

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

15,блок 16 распределения процессо- 20 ров, регистр 17 готовности процессо- pOBj группу блоков элементов И 18, группу элементов ИЛИ 19, вход 20 запуска устройства, вход 21 останова устройства, вход 22 заявок устройства, группу информационных входов

23 устройства, группу информационных выходов 24 блока 16, группу информационных входов 25 блока 16, управляющий вход 26 блока 16, выход 27 блока

16, группу выходов 28 блока 16, группу выходов 29 блока 16, группу информационных выходов 30 устройства.

Блок 16 распределения процессоров (фиг. 2) содержит регистр 31, элемен- 35 ты задержки 32 и 33, узлы 34.1-34.К распределения процессоров,, группу элементов И 35 первого узла 34.1 распределения .группы элементов И 36 и 37 узлов 34 распределения, группу элементов ШШ 38, группу элементов ИЛИ 39, группу элементов И 40.

Рассмотрим принцип построения и работу устройства.

Исходное состояние устройства 45 характеризуется тем, что триггеры 2 и 11, регистры 1, 14 и 31 установлены в нулевое состояние (не показано) .

Работа устройства начинается по сигналу запуска, поступающему по входу 20 и устанавливающему триггер 2 запуска в состояние 1, и состоит из двух этапов.„

На первом этапе формируется очередь заявок, поступающих по входу 22 в первый регистр 1 хранения и по каяедым тактовым импульсам пере5

5

О

,

0

35

45

„

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

На втором этапе производится распределение свободных процессоров, с 1гналы готовности от которых поступают по входам 23 и фиксирзпотся в соответствующих разрядах регистра готовности процессоров 17. При этом возможны два варианта работы устройства. В первом варианте,когда число свободных процессоров больше либо равно требуемому для принятой заявки в регистр 14, производится их распределение, перемещение заявок в очереди и прием очередной заявки из последнего регистра 1 в регистр 14. Во втором варианте, когда число свободных процессоров меньше требуемых, заявка находится в регистре 14, пока ей не будет вьщелено требуемое число процессоров,, а заявка на входе 22 сохраняется.

Формирование очереди заявок производится следующим образом.

Так как триггеры 11 и регистры 1 и 14 установлены в состояние О, то последний элемент И 5 открыт единичными сигналами с выхода элемента ИПИ-НЕ и с нулевого выхода триггера 11. По тактовым иг-шульсам, поступающим через открытые элементы И 4 и 5 на управляющие входы регистров 1, заявки перемещаются по регистрам 1.

Так как элемент И 10 закрыт по инверсному входу единичным сигналом с выхода элемента ИЛИ-НЕ 15, то им- ; пульсы генератора 3 не изменяют состояние триггера 11.

Ввиду того, что элемент И 8 открыт единичным сигналом с выхода элемента ИЛИ-НЕ 15 и при перемещении заявок по регистрам 1, пока первая из них не окажется в последнем регистре 1, на входах регистра 14 присутствует нулевая информация, по каждому импульсу генератора 3 нулевое состояние регистра 14 подтверждается.

Когда по очередному импульсу генератора 3 первая заявка из последнего регистра 1 перемещается в регистр 14, единичный сигнал на выходе элемента ИЛИ-НЕ снимается. Через некоторое время, определяемое элементом задержки 7, нулевым сигналом с

313

выхода элемента ИЛИ-НЕ 15 гго инверсному входу открывается элемент И 10 и закрываются элементы И 5 и 9. Элемент задержки 7 обеспечивает прохождение импульса генератора 3 через элемент 6 без исках ения за счет удержания в открытом состоянии пос- леднего элемента И 5, при изменении состояния регистра .14. Кроме того

08214

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

5 31 вид 0111. Для решения задачи требуется три процессора, при этом код числа требуеьп.х процессоров в регистре 14 имеет вид 1110,

При данных условиях блок 16 рабоэлемент задержки 7 необходим для соз 0тает следующим образом.

Дания условия надежного приема инфор- Элементам И 35 в узле 34.1 произмации в регистр 14,водится выбор первой -единицы из позиВремя задержки элемента 6 опре-циокного кода регистра 31 причем ноделяется временем переходных процес-мер возбуя-денного эле 1ента И 35 соот25

сов В элементе И 8, регистре 14 и элементе-ИЛИ-НЕ и выбирается таким образоМ; чтобы до перемещения заявок по регистрам 1 содержимое последнего регистра 1 принялось в регистр 14.

Импульсом с выхода элемента задержки 6 происходит перемещение заявок в регистрах 1, Одновременно с передачей заявки в предпоследний регистр 1 происходит установка в 1 триггера 11 через открытьй элемент И 10. При этом нулевым сигналом с нулевого выхода триггера 11 блокируется воздействие последующих .импульсов генератора 3 на регистры 1 и 14, а единичным сигналом с единичного его выхода открывается элемент И .13.

. По очередному импульсу генератора 3 начинается второй этап работа устройства.

Каждая заявка, принятая в регистр 14,, включает в себя код числа требуемых процессоров для решения задачи и код номера заявки. Код числа тре- . буемых процессоров указывается позиционным кодом. При этом максимальное число разрядов групп равно числу процессоров в вычислительной системе. Отсюда разрядность группы ра-гистра . ., 14 5 регистра 17 готовности процессо - ров и регистра 31 одинакова; Номер задачи указывается двоичным кодом в группе разрядов кода номера задачи -в регистрах 1 и 14,

5 ветствует номеру свободного процессора,; а отсюда - номеру возбужденных . элементов ИЛ1-1 39, И 40, ИЖ 38 и .соответствующих выходов 28 и 29,

В каждом из узлов 34 посредством

элементов И 37 производится определение оставшихся свободных процессоров для выделения одного из них оче- peднo гy единичном сигналу в регистре 14, Затем с помощью элемента И 37 обеспечивается выбор крайней левой единицы.

В каждом узле 34 элементь: И 37 блокируются по инверсным входам еди- 30 ничнь -т сигнала ш с выходов одноименных элементов И 35 первого узла 34 и элемен-тов И 37 всех предыдущих узлов.

40

I

По завершении переходных процес35 сов в узлах 34s элементах ИЛИ 38 и 39 на выходе 27 блока 16 появляется сигнал5 задержанный элементом задерж- ки 32, По сигналу через соответствующие открытые блоки элементов И 18 сигналами с выходов 28 блока 16 в соответс-твующи« выходные информационные Е1ННЫ 30 для выбранных процессоров передается код номера задачи из группы разрядов регистра 14. Одновременно на выходах соответствующих элементов РПИ 19 формируются единичные сигналы, устанавливающие в О соответствующие разряды регистра 17 готовности процессоров, переводя тем caMbLM процессоры из состояния Свободен в состояние Занят,

50

По импульсу генератора 3,, проходя- через открытый элемент И 13 по управляющему входу 26 блока 16 на синхронизирующий вход регистра 31; содержимое регистра 17 готовности процессоров на одного цию1а распределения передается в регистр 31 по входам 24.

214

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

31 вид 0111. Для решения задачи требуется три процессора, при этом код числа требуеьп.х процессоров в регистре 14 имеет вид 1110,

При данных условиях блок 16 рабо

ветствует номеру свободного процессора,; а отсюда - номеру возбужденных элементов ИЛ1-1 39, И 40, ИЖ 38 и .соответствующих выходов 28 и 29,

В каждом из узлов 34 посредством

элементов И 37 производится определение оставшихся свободных процессоров для выделения одного из них оче- peднo гy единичном сигналу в регистре 14, Затем с помощью элемента И 37 обеспечивается выбор крайней левой единицы.

В каждом узле 34 элементь: И 37 блокируются по инверсным входам еди- ничнь -т сигнала ш с выходов одноименных элементов И 35 первого узла 34 и элемен-тов И 37 всех предыдущих узлов.

., 40

I

По завершении переходных процес35 сов в узлах 34s элементах ИЛИ 38 и 39 на выходе 27 блока 16 появляется сигнал5 задержанный элементом задерж- ки 32, По сигналу через соответствующие открытые блоки элементов И 18 сигналами с выходов 28 блока 16 в соответс-твующи« выходные информационные Е1ННЫ 30 для выбранных процессоров передается код номера задачи из группы разрядов регистра 14. Одновременно на выходах соответствующих элементов РПИ 19 формируются единичные сигналы, устанавливающие в О соответствующие разряды регистра 17 готовности процессоров, переводя тем caMbLM процессоры из состояния Свободен в состояние Занят,

Через некоторое время, определяемое элементом задержки 33, устанавливается в О регистр 31 и через открытые соот-ветствуюы1ие элементы И 40 возбз жденными элементами ИЛИ 39 по выходам 29 - соответствующие разряды групп регистра 14.

0

5

Элемент задержки 33 необходим для вьфавнивания моментов формирования единичных сигналов установки в О разрядов регистров 17 и 14.

Так как для рассматриваемого примера все разряды группы числа процессоров регистра 14 оказываются в нулевом состоянии, то на выходе элемента ИЛИ-НЕ 15 формируется единичный сигнал, которым по инверсному входу закрывается элемент И 10, а открывается элемент И 9. Поэтому задержанным сигналом с выхода 27 блока -16 триггер устанавливается в О.

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

13108216

группой информационных входов устройства, первый элемент И, группу из п (п - число заявок) элементов И группу блоков элементов И, группу из

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

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

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

ное число процессоров для решения за-35 триггер управления, буферный регистр.

дачи, на выходе элемента. ИЛИ-НЕ 15 удерживается нулевой сигнал. Этим самым элемент И 9 остается в закры- том состоянии, поэтому триггер 11 сохраняет единичное состояние. Так как нуЛевьм сигналом с нулевого выхода триггера 11 последний элемент И 5 закрыт, а единичным сигналом с единичного выхода триггера 11 откры элемент И 13, то по очередным импульсам генератора 3 продолжается распределение процессоров задаче. При этом заявка в регистре 14 будет находиться до тех пор, пока задаче не будет вьщелено требуемое число процессоров.

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

входом пятого элемента И и с третьим

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

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

элемент ИПИ-НЕ, блок распределения процессоров и- генератор импульсов, выход которого подключен к первому входу первого элемента И, второй

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

группы, вьгход элемента ШГО-НЕ через первый задержки соединен с первыми входами третьего элемента и четвертого элемента И, иннерсньм

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

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

50

выход каждого элемента И первой группы узлов распределения группы, начиная с второго, соединен с вторым прямым входом одноименного элемента И второй группы своего узла, выход каждого элемента И первой группы всех узлов распределения группы, начиная с второго, соединен с соответствующим инверсным входом всех последующих элементов И второй группы своего y3Jia, выход каждого элемента И второй группы всех узлов распределения группы, начиная с второго, соединен с соответствующим инверсным

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

O

5 0

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

0

5

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

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

выход каждого элемента И первой группы узлов распределения группы, начиная с второго, соединен с вторым прямым входом одноименного элемента И второй группы своего узла, выход каждого элемента И первой группы всех узлов распределения группы, начиная с второго, соединен с соответствующим инверсным входом всех последующих элементов И второй группы своего y3Jia, выход каждого элемента И второй группы всех узлов распредеения группы, начиная с второго, соединен с соответствующим инверсным

у131082110

распределения группы соединен с пер-ных узлов соединены с входами одновым входом одноименного элемента ИЛИименного элемента RHH второй группы

второй группы блока распределенияблока распределения процессоров, выпроцессоров, выход каждого элементаходы элементов ИЛИ второй группы блоИ группы первого узла распределения 5ка распределения процессоров являются

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

(Suif

фг«г Составитель Г.Пономарева

Ж

«

и

Ш

fS

а

Редактор М.Дылын Техред Н.Глущенко

Заказ 2350 Тираж 672Подписное

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

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

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

Корректор М.Демчик

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Цепь изобретения г повьппение быстродействия устройства. Устройство содержит регистр готовности процессоров, элемент И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ. Новым в устройстве является использование триггера запуска, четырех элементов И, трех элементов задержки, триггера управления, буферного регистра, элемента ШШ-НЕ, генератора импульсов, блока распределения, состоящего из регистра распределения, двух элементов задержки, группы элементов И, двух групп элементов ИЛИ, группы узлов распределения, вьшолненньгх, кроме первого, на двух группах элементов И, а первьй - на одной группе элементов И. Устройство работает в два этапа. На первом этапе формируется очередь заявок, поступающих в первый регистр импульсов, перемещающихся по регистрам хранения груп пы. На втором этапе производится распределение свободных процессоров. При этом возможны два варианта работы устройства. В первом из них, когда число свободных процессоров больше либо равно требуемому для принятой заявки, производится их распределение, перемещение заявок в очереди и прием очередной заявки из последнего регистра хранения в буферный регистр. Во- втором варианте, когда число свободных процессоров меньше требуемых, заявка находится в буферном регистре, пока ей не будет вьщелено требуемое число процессоров. 2 ил. & СО 00 ю