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

ОЮЗ СОВЕТСКИХ ЦИАЛИСТИЧЕСНИХСПУБЛИК 119) 111) 4 006 Е 9 ОПИСАН ОБРЕТЕНИЯЕПЬСТВУ АВТОРСКОМУ(56) Авторское свидетельство СССРУ 1285473 ь кл, О 06 Р 9/46, 1985,(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относится к вычислительной технике и может быть использовано. в качестве аппаратного диспетчера программ, готовых к выполнениюдля их распределения по процессораммногопроцессорной системы. Цель изобретения - расширение области примене м тон приоро 2 Изобретение относится к вычислиельной технике и может быть исполь зовано в качестве аппаратного диспетчера прогоамм, готовых к выполнению, дпя их распределения по процессорам многопроцессорной системы,Цель изобретения - расширение обсти применения устройства за счетспределения конкретного задания назаданный процессор,На фиг.1-3 приведена функциональная схема предлагаемого устройства;на фиг4 - структура запроса, поступаю)цего на устройство.Устройство содержит первый 1 ивторой 2 блоки памяти, первый 3 -пятый 7 регистры, первый 8 - шестой.13 счетчики, первый 14 - восемнадцатый 31 элементы И, первый 32 и второй ла ра а ОСУДАРСТВЕННЫИ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯРИ ГКНТ СССР ния устройства за счет распределения конкретного задания на заданный процессоо, Устройство для распределения заданий процессорам содержит пять регистров, шесть счетчиковносе надцать элементов И, дна мультиплексора, восемь элементов ИЛИшесть триггеров, элемент НЕ, дна элемента И-НЕ, два элемента ИЛИ-НЕ, группу коммут атор о в, пят ь групп эл емен И, группу элементов ИЛИ, блок ритета, дна блока памяти. Устройство не только распределяет конкретное задание на заданный процессор, но и блокирует распределение на этот и цессор зацаний, допускающих . исполне- с ние на любом процессоре, 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Перед началом работы, подачей импульса на вход 58 устройства все эле-.менты памяти переводятся в исходноенулевое состояние (цепи сброса непоказаны),При этом на сигнальномвыходе 34 устройства устанавливаетсяединичный сигнал, разрешающий подачуна устройство запросов на распр еде"ление, а на выходах 71 и 72 присутст вуют нулевые уровни сигналов,Работа устройства начинается сприходом сигнала пуска на вход 57устройства, по которому триггер 51переводится в единичное состояние и 15высоким уровнем сигнала на своемпрямом выходе разрешает работу генератора 44 тактовых импульсов.Работа устройства состоит в приеме от источника запросов запроса нараспределения задания, занесений зап.роса по признаку в одну из очередейи последующей выдачи по признаку наодин из процессоров многопроцессорнойсистемы 25На фиг, 4 приведена структура запроса, поступающего на кодовый вход35 устройства, В разрядах 11 - м 1кодируется номер процессора, требуемого для выполнения данного задания, 30а разряды м 1 - п содержат код номера задания. При этом, нулевое содержимое разрядов 11 - 1 м означает,что задания не требует для своего выполнения конкретный процессор и может 35быть распределено на любой свободныйпроцессор системы. На основании этого ключевогр признака и производитсяформирование в блоке 1 памяти очереди заданий на конкретный процессор 40систеж, а в блоке 2 памяти очередизаданий, не требующих для своего конкретного процессора, Параллельно сформированием очередей в устройствеидет процесс. распределения заданий 45на процессоры системы, который допускает при соблюдении соответствующих условий, одновременную выдачузаданий из очередей, Такое совмещениеопераций достигается за счет использования регистра 3 и регистров 4 и 5. Рассмотрим детальнее операции,составляющие рабочий цикл устройства,Прием запроса состоит в фиксации;в регистре 3 кода запроса с последу-,1ющим формированием условия для протекания операции занесения запроса вочередь,Условием операции приема являет"ся наличие единичного уровня сигна-,ла на сигнальном выходе 34 устройства, означающего, что приемный регистр свободен и есть место в очередях запросов, Источник запросовчерез кодовый вход 35 устройства заносит в регистр 3 код запроса и выставляет единичный сигнал на вход45 запроса устройства, который позаднему фронту синхроимпульса 8 запоминается в триггере. 46, Перевод вединичное состояние триггера 46 вызывает появление на сигнальном выходе34 запрета нулевого уровня, после чего источник запросов снимает единич."ный сигнал с входа 45 устройства. Выходы разрядов 11 - м 1 регистра 3поступают на одноименные входы элемента ИЛИ 36, который анализируетпоступивший запрос по признаку и совместно с элементами НЕ 52, И 15 - 18,ИЛИ 57 и 58 вырабатывает условия дляперехода устройства по следующемусинхроимпульсук выполнению соот-,вествующей операции, Например, посту-,пил запрос с заданием, требующим длясвоего исполнения конкретный процессор, Тогда единичные уровни сигналовна прямом выходе триггера 46 и элемента ИЛИ 36 открывают для синхроимпульсаэлементы И 16 и 17 и создают условия для перехода в единичноесостояние триггера 47, соответству-ющего операции занесения запроса вочередь запросов на конкретный процессор системы, Синхроимпульсгпоступает также через элемент ИЛИ 38на синхровход триггера 50, соответствующего операции выдачи кода задания из очереди заданий, не требующихдля своего исполнения конкретный про"цессор, и проверяет наличие условийдля совмещения операций,По заднему фронту синхроимпульса б триггер 47 устанавливается в единичное состояние и открывает элементы И 21 и И-НЕ 53, При этом нулевой уровень сигнала на выходе элемента ИЛИ-НЕ 55 разрешает обращение к блоку 1 памяти, а единичный уровень сигнала на выходе элемента И 19, разре- шает подачу на адресный вход блока 1 памяти через мультиплексор 32 адреса верхней границы очереди, отслеживаемой с помощью счетчика 10, Синхроимпульспроходит через элементИ-НЕ 53 и формирует команду "Запись",по которой в блоке 1 памяти запоми 11нается содержимое регистра 3 с 1-гопо и-й разряды. Синхроимпульс э проходит через элемент И 21 на счетныйвход счетчика 10 и корректирует верхнюю границу очереди, Этот же сигнапчерез элемент ИЛИ 39 осуществляетсброс триГгера 46 и очистку регистра 103 Длина очереди з апросов контролируется с помощью реверсивного счетчика 8, на соответствующие входы котого поступают сигналы, сопровождающиеоперации записи и чте 1 пя из очереди, 15По синхроимпул ьсу 1 4 устр ой ст Воприводится в исходное состояние ианализируется начичие вновь поступившего запроса,Прием и занесение в очередь запроса, допускающего исполнение на любом процессоре системы осуществляются аналогично с той лишь разницей,что в блоке 2 памяти запоминается содержимое регистра 3 с м-го по и-й 25разряды,На фиг, 3 приведены временные диаграммы, описывающие последовательность действий устройства по занесению поступающих загросов в очереди, 30На такте Т проходит запрос с заданием К, не требующем конкретный процессор и запоминается в блоке 2 памяти на такте Т+1, На этом же тактеприходит з апр о с с з ад ание м 1 на конкретный процессор и на такте Т+2 запоминается в блоке 1 памяти,Условием для перехода к операциивыдачи з адания из очереди явля ется наличие з аданий в о чер еди (обнаруживается по единичному сигналу на вторых сигнальных выходах счетчиков 8 и9) и наличие свободного буферного регистраВыполнение этих условий 45соответствует наличию единичного сигнала на выходе элементов И 27 и 28,Опрос условий производится по синхроимпульсу в двух случаях, Вопервых, если поступившее задание 50должно быть занесено в очередь на конкретный процессор, . то опрашиваетсяусловие выдачи задания из очереди заданий, допускающих исполнение на любом процессоре системы и наоборот, Иво-вторых, если запросов не поступало, то сброшенный триггер 46 открывает сигналом на инверсном выходе элемент И 15 и создает условия для прохождения синхронмпул ье а счереэ элементыы И 15, ИЛИ 37 и 38 на синхровходы триггеров 49 и 50. Таким образом, опрашиваются условия выдачи изобеих очередей,Допустим, что ьыцолня ется условие для выдачи задания из очереди заданий на конкретный процессор, то тогда по заднему фронту очередного синхроимпульса " триггер 49 переводится в единичное состояние и открывает высоким уровнем сигнала на прямом выходе элемента И 23 и 25. Этот же сигнал проходит через элемент 10 И-НЕ 55 на управляющий ход блока 1 памяти и разрешает доступ к его содержимому, Нулевой уровень сигнала на выходе элемента И 19 поступает на адресный вход мультиплексора 32 и разрешает прохождение на адресный вход блока 1 памяти адреса нижней границы очереди, который о. слеживается с помощью счетчика 12. Таким образом, на информационном выходе блока 1 памяти выдается содержимое ячейки поадресу, задаваемо.ьу содержимым счетчика 12. Следуюшчй спнхропмп;гльс Гл форьирует на выходе элемгнга И 23 сигнал, по которо в регистре 4 запоминается состояние ипформа тиоцных выходов блока 1 па.яги, По этому жг сигнилу корректируется значение длины очереди в счетчике 8, Информационные выходы регистра 4 с 1 - го пс м-й поступают на одноименные входы элемента ИЛИ 40 и информационные входы дешифратора 59, а информационные выходы с м-го по л - й поступают на коммутаторы 60 группы, По синхроимпульсу ь на выходе элемента И 25 формируется сигнал, корректирующий нижнюю границу очереди. Этот же си гн ал пс ступает на управпяюый вход дешифратора 59, в результате чего на его информационном выходе, соответствующем номеру требуемого процессора, форируется импульсный сигнал, поступающий на одноименный единичный вход регистра 5, .Таким образом, по синхроимпульсу сэ в регистр 7 заносится в унитарном коде номер требуемого процессора, Прямые выходы разрядов регистра 7 посту" пают на элементы И 61 и 62 первой и второй групп, На вторые входы элементов И 61 группы поступают сигналы с информационных выходов регистра 6, в котором фиксируются по ь, значения1476466"Занят",Инверсные выходы разрядов регистра 7 с помощью группы элементов И 635блокируют прбхождение на блок приоритета сигнала "Свободен" от соответствующего процессора, Таким образом,процессор, требуемый текущему заданию из очереди заданий на конкретный 10процессор, не участвует в распределении заданий из второй очереди.Если на текущем такте требуемыйпроцессор свободен, то на выходесоответствующего элемента И 61 групы формируется единичжй сигнал, который через элемент ИЛИ 42 открывает элемент И 29, а также поступаетна управляющий вход одноименногокоммутатора 60 группы и разрешаетвыдачу на выбранный процессор коданомера задания, По синхроимпульсу Р 4йа выходе элемента И 29 формируется сигнал "Принять код задания", который поступает на вход элемента 67 25задержки, а также проходит через элементы И 62 и ИЛИ 69 группы, соответствующие выбранному процессору, навыход 71 группы, По этому сигналувыбранный процессор принимает код задания с .соответствующего выхода 72группы информационных выходов устройства и выставляет нулевой сигнална соответствующий сигнальный вход66 группы, Задержанный сигнал с выхода элемента 67 задержки сбрасываетрегистры 4 и 5, после чего устройство готово к выдаче следующего зада-.ния,Если на текущем такте выдачи требуемый процессор оказался занят, товыдача заданий из очереди блокируетсядо момента освобождения процессора,Формул а из обр ет ения 45Устройство для распределения заданий процессорам, содержащее первый и второй блоки памяти, первый и второй регистры, первый и второй счет 50 чики, дешифратор, первый элемент И, генератор тактовых импульсов, первый мультиплексор, первый и второй элементы задержки, первый и второй элементы ИЛИ, причем информационнныеф 55 выходы первого блока памяти соединены с информационными входами регистра, выход переполнения первого счетчика соединен с первым входом перного элемента И, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет распределения конкретного задания на заданныйпроцессор, оно дополнительно содержитс третьего по пятый регистры, стретьего по шестой счетчики, с второ"го по восемнадцатый элементы И, второй мультиплексор, с третьего повосьмой элементы ИЛИ, первый и второй элементы И-НЕ, первый и второйэлементы ИЛИ-НЕ, элемент НЕ, с первого по шестой триггеры, блок приоритета, с первой по пятую группы эле"ментов И, группу элементов ИЛИ игруппу коммутаторов, причем информационный выход первого мультчплексорасоединен с адресным входом первогоблока памяти, выход переполнениявторого счетчика соединен с вторымвходом первого элемента И, выход ко-.торого является выходом запрета устройства, информационный вход устройства соединен с информационнымвходом и синхровходом первого регистра, первая группа информационныхвыходов которого соединена с группойинформационных входов первого блокапамяти, вторая группа информационных выходов первого регистра соединена с входами первого элемента ИЛИи группой входов данных второго блока памяти, выход второго блока памяти соединен с информационным входомтретьего регистр а, первый выход генератора тактовых импульсов соединенс первыми входами второго и третьегоэлементов И и синхровходом четвертого регистра, вход запроса устройствасоединен с информационным входомпервого триггера, инверсный выходкоторого соединен с третьим входомпервого и вторым входом второго элементов И, выход второго элемента Исоединен с первыми входами второгои третьего элемейтов ИЛИ, выход первого элемента ИЛИ соединен с информационным входом второго триггера, спервым входом четвертого элемента И,а также через элемент НЕ с информационным входом тр ет ье го три г гер а ипервым входом пятого элемента И, выход четвертого элемента ИЛИ соединенс входом сброса первого регистра инулевым входом первого триггера,прямой выход которого соединен с вторым входом третьего элемента И и пер"выми входами шестого и седьмого эле1476466 20 30 40 50 55 ментов И, выход третьего элементаИ соединен с синхронходамч второгои третьего триггеров и вторыми входами четвертого и пятого элементовИ, выходы которых соединены соответственно с вторыми входами третьегои второго элементов ИЛИ, прямой выход второго триггера соединен с вторым входом шестого элемента И, а так же с первыми входами восьмого элемента И, первого элемента И-НЕ и первого элемента ИЛИ-НЕ, прямой выход третьего триггера соединен с вторым входом седьмого элемента И, а также с первыми входами девятого элемента И,второго элемента И-НЕ и второго элемента ИЛИ-НЕ, второй выход генератора тактовых импульсов соединен с вторыми входами первого и второго элементов И-.НЕ и первыми входами десятогои одиннадцатого элементов И, третий выход генератора тактовых импульсов соединен с вторыми входами восьмогои девятого элементов И и первымивходами двенадцатого и тринадцатогоэлементов И, выход второго элементаИЛИ соединен с синхровходом четвертого триггера, прямой выход которогосоединен с вторыми входами первогоэлемента ИЛИ-НЕ, десятого и двенадцатого элементов И, выход третьего элемента ИЛИ соединен с синхровходсм пятого триггера, прямой выход которого соединен с вторыьи входами второго элемента ИЛИ-НЕ, одиннадцатого и тринадцатого элементов И, выходы признака обнуления первого и второго счетчиков соединены соответственно с прямыми входами четырнадцатого и пятнадцатого элементов И, выходы которых соединены соответственно с информационными входами четвертого и пятого триггеров, четвертый выход генератора тактовых импульсов соединен с синхровходом первого триггера, с нулевыми входаз триггеров с второго по четвертый, а также с первыми входами шестнадцатого и семнадцатого элементов И, вход пуска устройствасоединен с единичным входом шестоготриггера, прямой выход которого сое-.динен с входом запуска генератора импульсов, вход останова устройствасоединен с нулевым входом шестоготриггера, выходы шестого и седьмого элементов И соединены соответственнос адресными входами первого и второго мультиплексоров, выход второго мультиплексор В соедНен с адреснь 1входом второго блока 1 амяти выходьвосьмого и девятого элементов И соединены соответственно с первым ивторым входами четвертого элементаИЛИа также со счетыми входамитретьего и четвертого счетчиков, выходы которых соединень соответственно с первыми информационными входамипервого и второго мультиплексороввыходы десятого и одиннадцатого элементов И соединены соответственно с синхровходами второго и третьего регистров, а также с вычитаюшими входами первого и второго счетчиков, выхоГо двенапцатогс и тринадцатого элементов И ссединень. соответственно со счеткми входами пятого и шестого счетчиков, выходы которых соединенысоответственно с вторым информационными входами первого и второго мультиплексоров, выход двенадцатого элемента И соединен со стробрующиы входом дешифратора выходы первого и второго элементов И-НЕ соединены соответственно со счетными входами гервого и второго счетчиков, а также свходами записи первого и второго блоков памяти, выходы первого и второгоэлементов ИЛИ-НЕ соединенсоответственно с входами разрешениядоступа первого и второго блоков памяти, первая группа выходов второго регистра соединена с входами пятого элементаИЛИ и инфорацисными входами дешифратора а вторая группа выходов вто -рого регистра соединена с. первымигруппами инфорыацисных входов коммутаторов группы, группа выходовтретьего регистра соединена с входамишестого элемента ИЛИ, а также с вторыми группаи информационных входовкоммутаторов группы, выходы пятогои шестого элементов ИЛИ. соединенысоответственно с инверсными входамичетырнадцатого и пятнадцатого элементов И, выход шестого элемента ИЛИсоединен с вторым входом семнадцатого и первым входом восемнадцатогоэлементов И, группа выходов дешифратора соединена с группой единичщхвходов пятого регистра, прямые выходы которого соединены соответственно а первыми входами элементов И первой и второй групп, а инверсные выходы которого соединены соответственно с первыми входами элементов Иб б 11 14764 третьей групгы, группа входов освобождения процессора устройства соединена с группой информационных входов четвертого регистра, вых.,я которого соединены соответственно с вторыми входами элементов И первой и третьей групп, выходы элементов И первойгруппы соединены соответ-венно с первыми управляющими вхо;.ими комму ртаторов группы и одноименными входами седьмого элемента ИЛИ, выход которого соединен с вторым входом шестнадцатого элемента И, выход шестнадцатого элемента И соединен с вторыми входами элементов И второй группы,а также через первый элемент э адержки с входами сброса второго и пятого регистров, выхопы элементов И второй группы соединены соответственно 20с первыми входами элементов ИЛИ группы, выходы элементов И третьей группы соединены соответственно с входамиблока приоритета, выходы которой соединены соответственно с первыми вхо 66 12дами элементов И четвертой и пятойгрупп, а также с одноименными входами восьмого элемента ИЛИ, выход семнадцатого элемента И соединен с вторыми входами элементов И четвертойгрупгы, а также через втброй элементзадержки с входом сброса третьего регистра, выходы элементов И четвертойгруппы соединены соответственно свторыьи входами элементов ИЛИ группы,выходы которых являются группой сигнальных выходов устройства, выходвосьмого элемента ИЛИ соединен стретьим входом семнадцатого элементаИ, а также с вторым входом восемнадцатого элемента И,выход которогосоединен с вторыми входами элементовИ пятой групи, выходы элементов Ипятой группы соединены соответстввнно с вторыми управляющими входами коммутаторов группы, выходы которь 1 х являются группой информационных выходов устройства, 1 47646 Ь, Сороча орректор Э.Лончаков Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1 Сост авительРедактор Ю, Середа Техред М.Дид Заказ 2157/49 Тираж 669 ВНИИПИ Государственного комитета по изобретени 113035, Москва, Ж, РаушскаяПодписноем и открытиям при ГКНТ СССРнаб., д. 4/5