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

 

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

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

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

РЕСПУБЛИК (19) (11) (51) 4 G 06 Е 9!46

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

И ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКР)>(ТИЯМ

ПРИ ГКНТ СССР (21) 4336818/24-24 (22) 26. 10. 87 (46) .30.04.89. Бюл. ) > 16 (72) С.Н,Ткаченко, И,А,Ручка, Г. Н, Тимонькин и В. С, Харченко (53) 681.325(088.8) (5e) Авторское свидетельство СССР

У 1285473> кл, G 06 F 99//446 6> 1985, (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано. в качестве аппаратного диспетчера программ, готовых к выполнению, для их распределения по процессорам многопроцессорной систем). Цель изобретения — расширение области применеИзобретение относится к вычислительной технике и может быть использовано в качестве аппаратного дис петчера программ, готовых к выполнению, дпя их р аспредел ения по процессорам многопроцессорной системы, Цель изобретения — расширение области применения устройства за счет распределения конкретного задания на заданный процессор, На фиг. 1-3 приведена функциональная схема предлагаемого устройства; на фиг ° 4 — структура запроса, поступаю)цего на устройство.

Устройство содержит первый 1 и второй 2 блоки памяти, первый 3— пятый 7 регистры, первый 8 — шестой13 счетчики, первый 14 — восемнадца тый 31 элементы И, первый 32 и второй ния устройства за счет распредепеш)я конкретного з адания на заданный процессор . Устройство для р аспр еделения заданий процессорам содержит пять регистров, шесть счетчиков „восемнадцать элементов И, дна мультиплексора, восемь элементов ИЛИ„шесть триггеров, элемент НЕ, дна элемента

И-НЕ, два элемента ИЛИ-HF, группу коммут атор о в, пят ь групп эл емент он

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

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 устройства, Устройство работает следующим образом.

1476466

11еред началом работы, подачей импульса на вход 58 устройства все эле-. менты памяти переводятся в исходное нулевое состояние (цепи сброса не показаны) . При этом на сигнальном выходе 34 устройства устанавливается единичный сигнал, разрешающий подачу на устройство запросов на распр еде" ление, а на выходах 71 и 72 присутст- 10 вуют нулевые уровни сигналов, Работа устройства начинается с приходом сигнала пуска на вход 57 устройства, по которому триггер 51 переводится в единичное состояние и высоким уровнем сигнала на своем прямом выходе разрешает работу генератора 44 тактовых импульсов.

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

На фиг, 4 приведена структура запроса, поступающего на кодовый вход

35 устройства. В разрядах (11 — (м) кодируется номер процессора, требуемого для выполнения данного задания, 30 а р азряды t м) — fn) содержат код номера задания. При этом, нулевое содержимое разрядов (11 — (м) означает, что задания не требует для своего выполнения конкретный процессор и может 35 быть распределено на любой свободный процессор системы. На основании этого ключевогр признака и производится формирование в блоке 1 памяти очереди заданий на конкретный процессор 40 системы, а в блоке 2 памяти очереди заданий, не требующих для своего конкретного процессора, Параллельно с формированием очередей в устройстве идет процесс распределения заданий 45 на процессоры системы, который допускает при соблюдении соответ ствующих условий, одновременную выдачу заданий из очередей, Такое совмещение операций достигается за счет исполь- >50 зования регистра 3 и регистров 4 и 5.

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

;в регистре 3 кода запроса с последу-, I I ющим формированием условия для протекания операции занесения запроса в очер едь, Условием операции приема являет" ся наличие единичного уровня сигна-, ла на сигнальном выходе 34 устройства, означающего, что приемный регистр свободен и есть место в очередях запросов, Источник запросов через кодовый вход 35 устройства заносит в регистр 3 код запроса и выставляет единичный сигнал на вход

45 запроса устройства, который по

7» заднему фронту синхроимпульса с q запоминается в триггере. 46, Перевод в единичное со стояние три г гер а 46 вызывает появление на сигнальном выходе

34 запрета нулевого уровня, после чего источник запросов снимает единичный сигнал с входа 45 устройства. Выходы разрядов 1 1) — (м1 регистра 3 поступают на одноименные входы элемент а ИЛИ 36, который анализирует поступивший запрос по признаку и совместно с элементами НЕ 52, И 15 — 18, ИЛИ 57 и 58 вырабатывает условия для перехода устройства по следующему синхроимпульсу к выполнению соот-, вествующей операции, Например, посту-: пил запрос с заданием, требующим для своего исполнения конкретный процессор, Тогда единичные уровни сигналов на прямом выходе триггера 46 и элемента HJIH 36 открывают для синхроимпульса элементы И 16 и 17 и cosдают условия для перехода в единичное состояние триггера 47, соответству- ющего операции занесения запроса в очередь запросов на конкретный процессорр си ст емы. Синхр оимпул ьс г поступает также через элемент ИЛИ 38

HB синхровход триггера 50> соответствующего операции выдачи кода задания из очереди заданий, не требующих для своего исполнения конкретный процессор, и проверяет наличие условий для совмещения опер аций, По заднему фронту синхроимпульса б триггер 47 устанавливается в единичное состояние и открывает элементы И 21 и И-НЕ 53. При этом нулевой уровень сигнала на выходе элемента

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

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

14 76466

И-НЕ 53 и формирует команду "Запись", по которой в блоке 1 памяти запоми1

1 нается содержимое регистра 3 с I-го по и-й разряды. Синхроимпульс Lp проходит через элемент И 21 на счетный вход счетчика 10 и корректирует верхнюю границу очереди, Этот же сигнап через элемент ИЛИ 39 осуществляет сброс триггера 46 и очистку регистра 1О

3, Длина очереди з апросов контролируется с помощью реверсивного счетчика 8, на соответствующие входы котого поступают сигналы, сопровождающие операции записи и чтеп»я из очереди, По синхроимпул bcy I 4 устр ой ст Во приводится в исходное состояние и анализируется наличие вновь поступившего запроса, Прием и занесение в очередь зап- 20 роса, допускающего исполнение на любом процессоре системы осуществляются аналогично с той лишь разницей, что в блоке 2 памяти запоминается содержимое регистра 3 с м-го по r.— é 25 разряды, На фиг, 3 приведены временные диаграммы, описывающие последовательность действий устройства по занесению поступающих загросов в очереди, З0

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

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

55 на управляюш»й вход б,ока 1 памяти и разрешает доступ к его содержимому. Нулевой уроне»b сигнала на выходе элемента И 19»осòóïàeò на адресный вход ".льтиплексора 32 и разрешаетт пр охожден .е на а.—,р е снь1й вход блока 1 памят» адреса нижне» границы очереди, который о.-слеживается с помощью счетчика 12. Таким образом, на информационном выходе блока 1 памяти выдается содерж»мое ячейки по адресу, задаваемому содержимым счетчика 12. Следуюш»и с»нхро»мпульс Гл формирует на выходе элемянга !! 23 c»гнал по которому в ряг»стре 4 э а»0 минается cOcтоян»е»»формационных Bbl ходов блока 1 паня г». По этому же сигналу корректируется э начян»е длины очереди в счетчике 8. И»форма»»онные выходы регистра 4 с 1 — го пс м-й поступают на одноименные входы элемента

ИЛИ 40 и»нформационные входы дешифратора 59, а информационные выходы с м-го по . — и поступают на коммутаторы

60 группы, По синхроимпульсу на выходе элемента И 25 форсируется сигнал, корр ектирующий нижнюю гр гницу очереди. Этот же сигнал поступает на управпяюый вход деш»фратора 59, в результате чего на егo»нформационном выходе, соответствующем номеру требуемого процессора, формируется импульсный сигнал, поступающий на одноименный единичный вход регистра 5, .Таким образом, по синхроимпульсу сЗ в регистр 7 заносится в унитарном коде номер требуемого процессора, Прямые выходы разрядов регистра 7 посту пают на элементы И 61 и 62 первой и второй групп, На вторые входы элементов И 61 группы поступают сигналы с информационных выходов регистра 6, в котором фиксируются по,, значения

\1476466 состояний процессоров "Свободен" или "Занят", Инверсные выходы разрядов регистра 7 с помощью группы элементов И 63

5 блокируют прбхождение на блок приоритета сигнала "Свободен" от соответствующего процессора, Таким образом, процессор, требуемый текущему заданию из очереди заданий на конкретный i ð процессор, не участвует в распределении заданий из второй очереди.

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

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

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

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

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

20

40

55 ментов И, выход третьего элемента

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

И, выходы которых соединены соответственно с вторыми входами третьего и второго элементов ИЛИ, прямой выход второго триггера соединен с вторым входам шестого элемента И, а так- 10 же с первыми входами восьмого элемента И, первого элемента И-HE и первого элемента ИЛИ-НЕ, прямой выход трет ьего триггера соединен с вторым входом седьмого элемента И, а также с первыми входами девятого элемента И, второго элемента И-НЕ и второго элемента ИЛИ-НЕ, второй выход генератора тактовых импульсов соединен с вторыми входами первого и второго элементов И-.НЕ и первыми входами десятого и одиннадцатого элементов И, третий выход генератора тактовых импульсов соединен с вторы>и входами восьмого и девятого элементов И и первыми входами двенадцатого и тринадцатого элементов И, выход второго элемента

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

ИЛЛ, а также со счет>ыми входами третьего и четвертого счетчиков, выходы которых соединены соответственно с первыми информационными входами первого и второго мультиплексоров, выходы десятого и одиннадцатого элементов И соединены соответственно с синхровхсдаьи второго и третьего регистров, а также с вычитаюшими входами первого и второго счетчиков, выходы двенапцатогс и тринадцатого элементов И ссединень. cooòâåòñòâåííî со счеты.и входами пя-ого и шестого счетчиков, выходы которых соединены соответственно с вторыми информационными входами первого и второго мультиплексоров, выход двенадцатого элемента И соединен со стрсбирующим входом дешифратора> выходы первого и второго элементов И-НЕ соединены соответственно со счетными входами гервого и второго счетчиков, а также с входами записи первого и второго блоков памяти, выходы первого и второго элементов ИЛИ-НЕ соединены соответственно с входами разрешения доступа первого и второго блоков памяти, первая группа выходов второго регистра соединена с входами пятого элемента

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

2 а5

al2

01б

nlT

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

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

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

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

1476466 а д а!

ol а! а1

1476466

Р Г 4

Со ст ави тел ь М, Сорочан

Редактор Ю, Середа Техред M.Äèäüê

Корректор Э.Лончакова

Заказ 2157/49 Тираж 669 . Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101