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

1

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

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

На фиг.1-3 приведена функциональная схема предлагаемого устройства на фиг.4 - структура запроса, поступающего на устройство.

Устройство содержит первый 1 и второй 2 блоки памяти, первый 3 - пятый 7 регистры, первый 8 - шестой 13 счетчики, первый 14 - восемнадца- тый 31 элементы И, первый 32 и второй

33 мультиплексоры, выход 34 запрета, информационный вход 35, первый 36 - восьмой 43 элементы ИЛИ, генератор 44 тактовых импульсов, вход 45 запроса, первый 46 - шестой 51 триггеры, элемент НЕ 52, первый 53 и второй 54 элементы И-НЕ, первый 55 и второй 56 элементы ИЛИ-НЕ, вход 57 пуска, вход 58 останова, дешифратор 59, группу коммутаторов 60, первую 61 - пятую 65 группы элементов И, группу сигнальных входов 66, первый 67 и второй 68 элементы задержки, группу элементов ИЛИ 69, блок 70 приоритета, группу сигнальных выходов 71 устройства, группу информационных выходов 72 устройства,

Устройство работает следукнцим образом.

нЈь |

ОЭ Ј 0

ОЭ

Церед началом работы, подачей импульса на вход 58 устройства все элементы памяти переводятся в исходное нулевое состояние (цепи сброса не

показаны), При этом на сигнальном выходе 34 устройства устанавливается единичный сигнал, разрешающий подачу на устройство запросов на распределение, а на выходах 71 и 72 присутст- вуют нулевые уровни сигналов.

Работа устройства начинается с приходом сигнала пуска на вход 57 устройства, по которому триггер 51 переводится в единичное состояние и высоким уровнем сигнала на своем прямом выходе разрешает работу генератора 44 тактовых импульсов.

Работа устройства состоит в приеме от источника запросов запроса на распределения задания, занесений запроса по признаку в одну из очередей и последующей выдачи по признаку на один из процессоров многопроцессорной системы,

На фиг,4 приведена структура запроса, поступающего на кодовый вход 35 устройства, В разрядах l - м кодируется номер процессора, требуе мого для выполнения данного задания, а разряды м содержат код но-, мера задания. При этом, нулевое содержимое разрядов l - м означает, что задания не требует для своего выполнения конкретный процессор и может быть распределено на любой свободный процессор системы. На основании этого ключевогр признака и производится формирование в блоке 1 памяти очереди заданий на конкретный процессор системы, а в блоке 2 памяти очереди заданий, не требующих для своего конкретного процессора. Параллельно с формированием очередей в устройстве идет процесс распределения заданий на процессоры системы, который допускает при соблюдении соответствующих условий, одновременную выдачу заданий из очередей. Такое совмещение операций достигается за счет исполь- зования регистра 3 и регистров 4 и 5.

Рассмотрим детальнее операции, составляющие рабочий цикл устройства. Прием запроса состоит в фиксации

.в регистре 3 кода запроса с последующим формированием условия для протекания операции занесения запроса в очередь.

с

ю

J5

20 5

30 ,с v 40 д§ CQ

55

Условием операции приема является наличие единичного уровня сигна- . па на сигнальном выходе 34 устройства, означающего, что приемный регистр свободен и есть место в очередях запросов. Источник запросов через кодовый вход 35 устройства заносит в регистр 3 код запроса и выставляет единичный сигнал на вход 45 запроса устройства, который по заднему фронту синхроимпульса 7ц запоминается в триггере. 46, Перевод в единичное состояние триггера 46 вызывает появление на сигнальном выходе 34 запрета нулевого уровня, после чего источник запросов снимает единичный сигнал с входа 45 устройства. Выходы разрядов - м регистра 3 поступают на одноименные входы элемента ИЛИ 36, который анализирует поступивший запрос по признаку и совместно с элементами НЕ 52, И 15 - 18, ИЛИ 57 и 58 вырабатывает условия для перехода устройства по следующему синхроимпульсу ti к выполнению соот-., вествующей операции, Например, поступил запрос с заданием требующим для своего исполнения конкретный процессор. Тогда единичные уровни сигналов на прямом выходе триггера 46 и элемента ИЛИ 36 открывают для синхроимпульса t элементы И 16 и 17 и создают условия для перехода в единичное состояние триггера 47, соответствующего операции занесения запроса в очередь запросов на конкретный процессор системы, Синхроимпульс fa поступает также через элемент ИЛИ 38 на синхровход триггера 50, соответствующего операции выдачи кода задания из очереди заданий, не требующих для своего исполнения конкретный процессор, и проверяет наличие условий для совмещения операций,

По заднему фронту синхроимпульса триггер 47 устанавливается в единичное состояние и открывает элементы И 2 1 и И-НЕ 53, При этом нулевой уровень сигнала на выходе элемента ИЛИ-НЕ 55 разрешает обращение к блоку 1 памяти, а единичный уровень сигнала на выходе элемента И 19, разре- шает подачу на адресный вход блока 1 памяти через мультиплексор 32 адреса верхней границы очереди, отслеживаемой с помощью счетчика 10, Синхроимпульс проходит через элемент

И-НЕ 53 и формирует команду Запись по которой в блоке I памяти запоминается содержимое регистра 3 с 1-го по n-й разряды. Синхроимпульс C j проходит через элемент И 21 на счетный вход счетчика 10 и корректирует верхнюю границу очереди. Этот же сигнал через элемент ИЛИ 39 осуществляет сброс триггера 46 и очистку регистра 3, Длина очереди запросов контролируется с помощью реверсивного счетчика 8, на соответствующие входы кото- го поступают сигналы, сопровождающие операции записи и чтения из очереди.

По синхроимпульсу ty устройство приводится в исходное состояние и анализируется наличие вновь поступившего запроса.

Прием и занесение в очередь запроса, допускающего исполнение на любом процессоре системы осуществляются аналогично с той лишь разницей, что в блоке 2 памяти запоминается содержимое регистра 3 с м-го по г.-й разряды.

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

Условием для перехода к операции выдачи задания из очереди является наличие заданий в очереди (обнаруживается по единичному сигналу на вторых сигнальных выходах счетчиков 8 и 9) и наличие свободного буферно- го регистра, Выполнение этих условий соответствует наличию единичного сигнала на выходе элементов И 27 и 28. Опрос условий производится по синхроимпульсу t в двух случаях. Во- первых, если поступившее задание должно быть занесено в очередь на конкретный процессор, то опрашивается условие выдачи задания из очереди заданий, допускающих исполнение на любом процессоре системы и наоборот, И во-вторых, если запросов не поступало, то сброшенный триггер 46 открывает сигналом на инверсном выходе элемент И 15 и создает условия для прохождения синхроимпульса L через элементы И 15, ИЛИ 37 и 38 на синхро- входы триггеров 49 и 50. Таким об- разом, опрашиваются условия выдачи из обеих очередей,

Допустим, что вьшолнлРТ-СЯ условие для выдачи задания ич очереди заданий на конкретный процессор, то тогда по заднему фронту очередного синхроимпульса Ј триггер 49 переродится в единичное состояние и открывает высоким уровнем сигнала на прямом

5 выходе элемента И 23 и 25. Этот же сигнал проходит через элемент ИЛИ-НЕ 55 на улравлякжни вход блока 1 памяти и разрешает доступ к его содержимому. Нулевой уревегь сигнала на

Q выходе элемента И 19 поступает на адресный вход мультиплексора 32 и разрешает прохождение на адресный вход блока 1 памяти адреса нижней границы очереди, который отслеживается с по5 мощью счетчика 12. Таким образом, на информационном выходе блока 1 памяти выдается содержимое ячейки по адресу, задаваемо / содержимым счетчика 12. Следующий синхроимпульс T.q

0 формирует на выходе элемента II 23 сигнал, по которому в регистре 4 запоминается состояние информационных выходов блока 1 памяти. По этому же сигналу корректируется значение длины очереди в счетчике 8. Информационные выходы регистра 4 с 1-го по м-й поступают на одноименные входы элемента ИЛИ информационные входы дешифратора 59, а информационные выходы

Q с м-го по д-й поступают на коммутаторы 60 группы. По синхроимпульсу , на выходе элемента И 25 формируется сигнал, корректирующий нижнюю границу очереди. Этот же сигнал поступает на

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

5 пают на элементы И 61 и 62 первой и второй групп. На вторые входы элементов И 61 группы поступают сигналы с информационных выходов регистра 6, в котором фиксируются по t значения

5

состояний процессоров Свободен или Занят.

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

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

выдачу на выбранный процессор кода

номера задания. По синхроимпульсу 4 на выходе элемента И 29 формируется сигнал Принять код задания, который поступает на вход элемента 67 25 задержки, а также проходит через элементы И 62 и ИЛИ 69 группы, соответствующие выбранному процессору, на выход 71 группы. По этому сигналу

8

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

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

выбранный процессор принимает код за- 30 памяти, вторая группа информациондания с соответствующего выхода 72 группы информационных выходов устройства и выставляет нулевой сигнал на соответствующий сигнальный вход 66 группы, Задержанный сигнал с выхода элемента 67 задержки сбрасывает регистры 4 и 5, после чего устройство готово к выдаче следующего задания.

Если на текущем такте выдачи требуемый процессор оказался занят, то выдача заданий из очереди блокируется до момента освобождения процессора,

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

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

0

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

5

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

0

0

5

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

0

5

0

5

0

5

1 114

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

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

группы соединены соответственно с

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

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

пятой группы соединены соответственно с вторыми управляющими входами коммутаторов группы, выходы которых являются группой информационных выходов устройстйа.

/троцессорсе

фигЬ

Момер задания