Устройство приоритета для выбора групповых заявок

 

Изобретение относится к вычислительной технике и может найти применение в многопроцессорных вычислительных системах. Цель изобретения повышение быстродействия. Устройство содержит регистр запросов, пять групп регистров, генератор импульсов , группу счетчиков, три группы злементов И, группу дешифраторов, четыре элемента И, четыре элемента задержки, три элемента ИЛИ, группу блоков злементов ИЛИ, две группы блоков элементов И, два регистра. Устройство обеспечивает полную либо частичную загрузку процессоров при обслуживании однои разнотипных заявок, что дает возможность аппаратным путем организовать процесс параллельной обработки операндов по нескольким командам программы процессорами вычислительной системы. 1 ил. (Л |mjr СО 4 СО

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

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

РЕСПУБЛИК (50 4 G 06 F 9 46

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3982117/24-24 (22) 25.11 ° 85 (46) 15.06.87. Бюл. N- 22 (72) А. Х. Ганитулин и В. Г. Попов (53) 684.325(088.8) (56) Мультипроцессорные системы и параллельные вычисления. Под ред.

Ф. Г. Экслоу. N. Мир, 1976, с. 7374, рис. 223.

Авторское свидетельство СССР

У 1259265, кл. G 06 F 9/46, 1985. (54) УСТРОЙСТВО ГРИОРИТЕТА 1ЛЯ ВЫБОРА ГРУППОВЫХ ЗАЯВОК (57) Изобретение относится к вычислительной технике и может найти применение в многопроцессорных вычислительных системах. Цель изобретения—

„„Я0„„1 17437 А 1 повьцпение быстродействия. Устройство содержит регистр запросов, пять групп регистров, генератор импульсов, группу счетчиков, три группы элементов И, группу дешифраторов, четыре элемента И, четыре элемента задержки, три элемента ИЛИ, группу блоков элементов ИЛИ, две группы блоков элементов И, два регистра.

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

1 ил.

1317437

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

Цель изобретения — повышение быстродействия.

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

Устройство содержит регистр 1 запросов, регистры 2 группы, группу схем 3 сравнения, группу элементов

И 4, генератор 5 импульсов, элемент

И 6, счетчик 7, элемент ИЛИ 8, триггер 9, элемент И 10, элемент ИЛИ 11, элементы 12-14 задержки, регистры 15 группы, группу блоков элементов И 16, группу блоков элементов ИЛИ 17, группу блоков элементов И 18, группу схем 19 сравнения, третью группу элементов И 20, регистры 21 группы, элемент ИЛИ 22, группу. элементов. И 23, регистр 24, регистры 25 группы, группу элементов И 26, группу регистров

27, группу счетчиков 28, группу схем

29 сравнения,, группу дешифраторов

30, элемент И 31, элемент ИЛИ-НЕ 32, элемент И 33, элемент 34 задержки, группу запросных входов 35 устройства, группы входов 36 кодов приоритета устройства, входы 37 кодов числа свободных функционалыых блоков устройства, вход 38 запуска устройства, ответный вход 39 устройства, группы входов 40 типа ресурса устройства, группы входов 41 типа заявки устройства, группу информационных входов

42 устройства, группу информационных выходов 43 и сигнальный выход 44 устройства.

Устройство работает следующим образом.

Исходное состояние устройства характеризуется тем, что триггер 9, счетчики 7 и 28, а также регистры 21 и 24 установлены в состояние "0" (не показано).

Перед началом цикла работы по входам 36 на входы регистров 2 поступают коды приоритетов, определяющие приоритет соответствующих заявок, а в регистры 15 по входам 41 — двоичные коды типа заявки, означающие требуемый тип ресурса. Наибольшее значение приоритетного кода устанавливается наиболее приоритетному запросу (абоненту ), а двоичный код типа заявки соответствует двоичному коду, установленному для функционального блока

Так как в регистрах 27 имеются ненулевые двоичные коды, а счетчики

28 установлены в состояние "0", то на выходах "Больше" всех схем 29 сравнения сформированы единичные сигналы, которыми открыты элементы

И 18 всех блоков. На выходе элемента

И 31 установлен сигнал "0", которым по инверсному входу открыт элемент

И 33.

На первых выходах всех дешифраторов 30 установлены сигналы "1" ко(ресурса). Коды типа заявки могут быть и одинаковыми. В регистры 25 по входам 40 поступают ненулевые двоичные коды номеров функциональных блоков (тип ресурса), устанавливаемые программным путем1 В соответствующие регистры 27 по входам 37 принимаются двоичные коды свободных блоков (ре10 сурсов) одного типа. Запросы заявки от абонентов или требование на исполнение определенной команды программы принимаются в соответствующие разряды регистра 1, число разрядов которого равно числу абонентов по входам

35, а двоичный код требуемого ресурса соответствующей заявки в соответствующий регистр 15 — по входам 41.

Работу устройства рассмотрим при следующих исходных данных.

Пусть число абонентов п = 15, число функциональных блоков различных типов S = 5, число функциональных блоков каждого типа в вычислительной системе одинаково (X = 3).

На момент распределения заявок в регистр 1 по входам 36 в регистры 2 приняты коды приоритетов для 15 абонентов, отличающиеся друг от друга единицей младшего разряда, в каждый из регистров 27 — код числа трех свободных функциональных блоков, в регистры 25 — коды типов пяти функциональных блоков, в регистр 1 приняты запросы от 1, 3 и 5-го абонентов.

Этим абонентам установлены приоритетные коды чисел 15, 10, 13 соответственно. Для обслуживания заявок требуются функциональные блоки для 1 и

3-го абонентов одного типа,. а для

5-го абонента — второго типа, коды которых приняты в регистры 15, 15 и 151 соответственно.

При этих условиях до поступления сигнала начального пуска состояние элементов устройства следующее.

1317437 торыми открыты элементы И 20 „

И 20, Работа устройства начинается по сигналу начального пуска, поступающему по входу 38. Этим сигналом через элемент ИЛИ 8 подтверждается нулевое состояние счетчиков 28, устанавливается в "1" счетчик 7, на выходах которого формируется код числа 15, Через некоторое время, опре- 10 деляемое элементом 12 задержки, устанавливается в "1" триггер 9.

После установки триггера 9 и счетчика 7 в состояние "l" открывается по обоим инверсным входам элемент

И 6 нулевыми сигналами с выхода элемента ИЛИ-НЕ 32 и с нулевого выхода триггера 9. Поэтому первый импульс генератора 5 через элемент И 6 поступает на вход элемента 13 задержки. 20

Так как для 1-го абонента установлено в регистре 2„ максимальное значение кода приоритета (15), то на. выходе схемы 3„ сравнения формируется единичный сигнал, который через открытый элемент И 4„ поступает на управляющие входы элементов И 16,, И 23 . При этом код типа заявки из регистра 15„ через блоки )6, 17 поступает на информационные входы от крытых блоков 18, которые передают код типа заявки на вторые входы всех схем 19 сравнения..Совпадение кодов происходит только в схеме 19, сравнения, которая формирует единичный 35 сигнал, открывающий по первым входам элементы И 20« — И 20, И 26, и через элемент ИЛИ 22 по первым входам— элементы И 23„ — И 23

Задержанный элементом 13 задержки импульс генератора 5 устанавливает в "1" через открытый элемент И 20„ соответствующий разряд регистра 2), а в счетчике 28, через открытый элемент И 26„ устанавливается код еди 45 ницы.

Через некоторое время, определяемое элементом 14 задержки, через открытый элемент И 23, устанавливается в "1" первый разряд регистра 24 и в

50 состояние "0" — первый разряд регистра 1, исключая тем самым из анализа в последующем такте запрос первого абонента.

Так как элемент И 33 удерживается в открытом состоянии через элемент

И 31 в счетчике 7 формируется код числа 14.

Поскольку в регистре 1 нет запроса с приоритетным кодом 14, то ни один из элементов И 4 не формирует единичный сигнал. Состояния элементов устройства по задержанным сигналам с выходов элементов 13 и очередным импульсам генератора не меняются.

Импульсом с выхода элемента 34 задержки через открытый элемент И 33 в счетчике 7 устанавливается очередной код числа 13. При этом элементом

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

Схемой 19 сравнения формируется единичный сигнал, по которому в соответствующий разряд регистра 21 записывается единица, в счетчике 28 устанавливается код единицы, пятый разряд регистра 24 устанавливается в

"1", а пятый разряд регистра 1 — в

"0"

Так как элемент И 33 удерживается в открытом состоянии, импульсом с выхода элемента 34 задержки в счетчике 7 формируется код числа 12.

По очередному импульсу генератора

5 состояние элементов схемы не меняетея, а в счетчике 7 формируется код числа ll. Po этому коду состояние элементов устройства не меняется.

Следующим задержанным импульсом генератора в счетчике 7 устанавливается код числа 10. По очередному сигналу генератора, поскольку элементом И 4 формируется единичный сигнал, состояния элементов устройства аналогично рассмотренному выше изменяются следующим образом.

Схемой 19 сравнения формируется единичный сигнал, по которому второй разряд первого регистра 21 устанавливается в "1", так как в счетчике 29„ хранится код единицы, открывающий через дешифратор 30,. второй элемент И 20„, третий разряд регистра 24 устанавливается в "1", третий разряд регистра 1 — в "0", а в счетчике 281 формируется код числа 2.

Так как элемент И 33 удерживается в открытом состоянии, то содержимое счетчика 7 уменьшается на единицу и становится равным 9, Последующими импульсами генерато-, ра 5 состояния элементов устройства

1317437 не меняются. Регистр 1 установлен в состояние "0". В счетчике 7 последо-! вательно формируются коды убывающей последовательности чисел. Как только в счетчике 7 установится нулевой код на выходе элемента ИЛИ-НЕ 32 формируется единичный сигнал, который поступает на выход 44 устройства, закрывает элемент И 6 по второму инверсному входу и устанавливает в "0" триггер

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

Но окончании обслуживания заявок в регистры 27 заносятся коды чисел свободных функциональных блоков, по входу 39 устанавливаются в "0" регистры 21 и 24 и, если имеются заявки

25 в регистре 1, через открытый элемент

И 10 сигналом с выхода элемента

ИЛИ 11 устанавливается в состояние

"1" счетчик 7, а в "0" — счетчики

28. При этом единичный сигнал с выхо- З0 да элемента ИЛИ-BE 32 снимается и триггер 9 устанавливается в "1" задержанным импульсом с выхода элемента 12 задержки. После установки . триггера 9 в состояние "1" начинается 35 новый цикл работы устройства.

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

"Равно" единичный сигнал. При этом на выходе элемента И 31 возникает единичный сигнал, который закрывает по инверсному входу элемент И 33, запрещая тем самым подачу импульса на счетный вход счетчика 7. Одновременно .сигналом с выхода элемента И 31 устанавливается в "О" счетчик 7. В дальнейшем процесс обслуживания заявок и новый цикл работы устройства аналогичны рассмотренным вьппе.

При необходимости перераспределения приоритетов заявок устройство приводится к исходному состоянию, в регистры 2, 15 и 25 принимаются соот-.

55 ветствукнцие двоичные коды, в регист- . ры 27 подаются коды числа свободных функциональных блоков и устройство запускается сигналом по входу 38.

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

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

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

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

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

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

30 второй группы соединена с группой выходов одноименного регистра третьей группы, группа информационных входов каждого регистра третьей группы является группой входов типа ресурса устройства, группа выходов первого регистра является первой группой информационных выходов устройства, выходы элементов И второй группы соединены с информационными входами первого регистра, входы третьего элемента ИЛИ соединены с выходами схем сравнения второй группы, выход третьего элемента ИЛИ соединен с первыми входами элементов И второй группы, выходы которых соединены с входами сброса регистра запросов, вход сброса первого регистра соединен с ответным входом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит четвертую группу из k регистров (где k — количестно типов заявок), k групп:элементов И, группу дешифраторов, груп55 пу счетчиков, третью группу элементов И, третий и четвертый элементы

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

1317437

Составитель M. Кудряшев

Редактор А. Мановская Техред В.Кадар Корректор М. 1 1ароши

Заказ 2425/44

Тираж 6?2 Подписное

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

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

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