Приоритетное устройство

 

1.ПРИОРИТЕТНОЕ УСТРОЙСТВО, содержащее блок формирования разрешений , информационные входы которого являются запросяыми входам, устройства , а выходы - выходами разрешений устройства, отличающееся тем, что, с целью рвсширения функциональных возможностей путем увеличения числа режимов обработки и адаптации к входному потоку запросов, устройство содержит блок анализа запросов , блок памяти, причем блок формирования разрешений содержит группу из матриц логических-блоков (где 2 - число информационных входов устройства, an- любое целое Мисло), состоящую из п подгрупп, j-я подгруппа включает JB себя. матриц размерностью 2, где j п, п-1, 2, 1, выходы строк матрицы i-й подгруппы, i п, где п 1,2, соединены с входами строк и столбцов матриц

СОЮЗ СОВЕТСНИХ СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (111

y(5g G 06 F 9/46 с

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГГИЙ

H ABTOPCH0MV СВИДЕТЕЛЬСТВУ (21) 3407818/18-24 (22) 15 03. 82 (46) 07.07.83. Бюл. и 25 (72) Л.И. Петрова, Э.П. Овсянникова-.

Панченко и Б.В. Шевкопляс .(53) 681 325(088.8) (56) 1. Авторское свидетельство СССР

N 717770, кл. G 06 F 9/46, 1977.

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

М 955068, кл..G 06 F 9/46, 1980 (прототип). (54)(57)1.ПРИОРИТЕТНОЕ УСТРОЙСТВО, содержащее блок формирования разрешений, информационные входы которого являются запросными входами, устройства, а выходы - выходами разрешений устройства, о т л и ч а ю щ е е с я тем, что, с целью рвсширения функциональных возможностей путем увеличения числа режимов обработки и адаптации к входному потоку запросов, устройство содержит блок анализа запросов, блок памяти, причем блок формирования разрешений содержит группу из 2" " матриц логических блоков п (где 2 - число информационных входов устройства, а n - любое целое число), состоящую из и подгрупп,,j --я подгруппа включает .в себя. 2 " матриц размерностью 2 ° 2, где

= n n-1, 2, 1, выходы строк матрицы 1-й подгруппы, i = n, где и =

= 1,2, соединены с входами строк и столбцов матриц (i-1)-й подгруппы, входы строк и столбцов матрицы и-й подгруппы являются информационными входами блока формирования разрешений, выходы строк и столбцов матриц первой подгруппы являются выходами блока формирования разрешений, группы управляющих входов всех матриц являются группой управляющих входов блока формирования разрешений, матрица j-й подгруппы содержит

22(1 логических блоков, первые

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

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

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

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

7727

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

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

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

15 запросов подключена к первой группе входов приоритетного блока, группа входов блока хранения маски является. второй группой входов устройства(1 )

Недостатком устройства является

20 сложность и полное отключение низкоприоритетных каналов при обработке групповых запросов высокоприоритетных каналов, Наиболее близким по технической

25 сущности к предлагаемому является многоканальное приоритетное устройство, содержащее блок- формирования раз решений, информационные входы которого являются запросными входами уст" З0 ройства, а выходы - выходами разрешений,.управляющие входы блока формирования разрешений являются управляющими входами устройства, блок формирования разрешений содержит логи- 35 ческие блоки.

Логические блоки в устройстве соединены в виде пирамидальной структуры. Если устройство содержит 2 запросных входов, то число возможных способов задания приоритетов между каналами равно 2(©" "> (n1,2....)(2 j.

Это число, однако, не обеспечивает полной свободы в задании приоритетов, для чего требуется (2 )",1 спо" собов задания, соответствующих всем возможным перестановкам номеров вход-. ных каналов. Ограниченность возможностей управления приоритетами определяет достаточно узкую область применения устройства. Кроме того, отсутствие аппаратных средств анализа потока входных запросов затрудняет адаптацию устройства к этому потоку.

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

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

5 !

О анализа запросов, выходы старших разрядов счетчиков соединены с вторыми входами соответствующих элементов

ИЛИ и являются выходами, блока анали25 . эа запросов, входы установки нуля счетчиков являются входами блока анализа запросов.

На фиг. 1 приведена функциональная схема устройства; на фиг. 2З0 .то же, блок формирования разрешений; на фиг..3 - то же, логического блока;. на фиг. 4 - то же, блок анализа запросов; на фиг. 5 и 6 - мнемонические схемы, поясняющие принцип работы устройства.

35.

Устройство (фиг. 1) содержит блок

1 формирования разрешений, запросные входы 2 устройства, выходы 3 разрешений устройства, блок 4 анализа запро4 сов, выходы 5 блока памяти, блок 6 памяти, выходы 7 блока 4, тактовый вход 8 устройства.

Блок формирования разрешений со50

3 102 ков (где 2" — число информационных входов устройства, а n - любое целое число), состоящую из и подгрупп, j-я подгруппа включает .в себя 2 и матриц размерностью 2 2 ", где j =

1-1 .

= n, п-1,2,1, выходы строк матрицы

i-й подгруппы, i = n, где п-1,2, соединены с входами строк и столбцов матриц (i-1)-й подгруппы, входы строк и столбцов матрицы и-й подгруппы являются информационными входами блока формирования разрешений, выходы строк и столбцов матриц первой подгруппы являются выходами блока формирования разрешений, группы управляющих входов всех матриц явля-. ются группой управляющих входов блока формирования разрешений, матрица

3-й подгруппы содержит 22(Г11 логических блоков, первые входы логических блоков первой строки являются входами столбцов матрицы, вторые входы логических блоков первого столбца являются входами строк матрицы, первые входы логических блоков последней строки являются выходами столбцов матрицы, вторые выходы логических блоков последнего столбца являются выходами строк матрицы, первые и вторые входы остальных логических блоков соединены соответственно с первым выходом логического блока того же столбца предыдущей строки и с вторым выходом логического блока той же строки предыдущего столбца, группа входов блока. анализа запросов соединена с группой информационных входов устройства, rpynna выходов блока. анализа запросов соединена с группой адресных входов блока памяти, информационные выходы которого соединены с управляющими входами блока . формирования разрешений, тактовый вход устройства соединен .с тактовым входом блока анализа запросов. Логик

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

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

l держит матрицы 9-15 логических бло" ков, логические блоки 16, входы 17 и 18 логических блоков, выходы 19 и 20 логических блоков, вход 21 логического блока.

Лагический блок (фиг. 3) содержит инверторы 22 и 23, элементы И 24-26, элементы ИЛИ 27 и 28.

Блок анализа запросов (фиг. 4) содержит счетчики 29, элементы ИЛИ 30.

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

1027727

Сигналы пlп входные

Вход 17

Выход 20

Вход 18 Вход 21

Выход 19

КЗ вЂ” К5 КЗ К4

К2-ъК5, К2--ъК4, К8-+К5, К8-+К4, Кб-ьК5, Кб-зК4, К7-+К5, К7-ъК4, К1 К5 К1 — К4, K5 — ъК4 .

K3 K2", КЗ-+К8, КЗ-ьК6, КЗ-К7, К2-+К8, К2 Кб, К2->К7, К8- К6, К8-ьК7, Кб-+К7

КЗ К1

К2-ь К1, К8- К1, Кб — К1, ° К7-ъ К1, I

Логический блок 16 выполняет функцию двухвходового арбитра по отношению к сигналам, поступающим на входы 20

17 и 18. При отсутствии конфликтов между этими сигналами, т.е. при комбинациях 00, 0l и 10, они транслируются на выходы 19 и 20 независимо от значения сигнала на управляющем 2$ входе 21 (символ Х в таблице).

При обнаружении конфликта между сигналами на входах 6 и 7 (комбинация 1l) логический блок отдает предпочтение тому или иному сигналу в за-Зв висимости от значения сигнала на управляющем входе 21.

Таким образом, на выходах 19 и 20 логического блока 5 исключается одновременное наличие логических единиц.

Блок 1 предназначен для разрешения конфликтов между запросными сигналами, подаваемыми на входы 2 в виде логических единиц. При отсутствии запросных сигналов сигналы разрешений

40 также отсутствуют, т.е. на всех выходах 3 сформированы логические нули (см. верхнюю строку приведенной выше таблицы), При наличии одиночного потенциального сигнала запроса на одном иэ входов группы 2 этот сигнал проходит через все встречающиеся на его пути логические блоки 16 и поступает на соответствующий выход группы в виде единичного потенциального сигнала. В этом случае код на управляющих входах может быть любым (см. символ Х в строках 2 и 3 приведенной выше таблице) .

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

Взаимоотношения между любой парой конкурирующих запросных сигналов однозначно определяются управляющим кодом, поданным на выходы 5 (см, строки 4 и 5 приведенной выше таблицы).

Пусть, например, требуется обеспечить следующую приоритетность входов 2 К1-К8 (нумерация приведена на фиг. 1):.

КЗ К2 8 К6 К7 1 5 Ê4, Стрелка в такой записи направлена от более приоритетного входа к менее приоритетному. Для обеспечения указанного режима управляющий код на выходах 5 должен настроить логические блоки в узлах решетки следующим образом:

Такое изменение, как показано ниже, приводит к получению одного из гибких режимов.

Предположим, что запросные сигналы гюступили по всем входам Kl -: К8.

На фиг. 5 утолщенными линиями показаны траектории распространения запросных сигналов через блок 1. Видно, что при взаимодействии сигналов К4 и К5 побеждает сигнал по входу К5, так .как соответствующий узел решетчатой структуры настроен на приоритетную передачу сигнала по входу К5 при возникновении конфликта между

К5 и К4 (K5 K4). Указанный сигнал далее взаимодействует с сигналом по входу К3 и на этот раз прекращает существование, так как не выдерживает конкурентной борьбы с сигналом по входу К3 (К3- К5). Результирующий сигнал с входа К3 последовательно побеждает сигналы по входам К6, К7, К8, К2 и Kl и, поскольку в узле, помеченном знаком +, уже нет конкури- рующего сигнала по. входу К4 (К4 †>К3), 7 lO2

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

Аналогично можно задать любой приоритетный порядок между каналами.

Число таких режимов равно числу перестановок между номерами каналов:

РВ = 40320.

Однако это число не исчерпывает все возможные режимы работы устройства.

Действительно, поскольку число управляющих входов равно в данном примере Ся 28, то возможны 2 28 =

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

Смысл этих режимов состоит в том, что приоритет между каналами определяется не только управляющим кодом, : поданным на входы блока 4, но также зависит от числа поступивших запросов и их распределения по каналам. Если в предыдущем примере изменить значение только одного бита .в управляющем коде, а именно, бита, определяю" щего взаимоотношения между входами К3 и К4, то условие К3 -ъК4, помеченное ранее знаком с, изменится на противогюложное: К4-ъК3.

7727 8 беспрепятственно проходит на выход блока.

Входной сигнал по К2, .хотя и имеет более высокий приоритет по отноше5 нию к сигналам с входов К5 -: К8, не встречается с ними на своем пути, так как последние подавлены сигналом по

К3, сигнал К2, пройдя до встречи с сигналом по каналу К3, прекращает о существование (К3 †К2). Входной сиг- . нал Кl имеет сравнительно низкий приоритет (пять стрелок из семи стремятся отклонить сигнал К! при конфликтах), однако, не встречая на своем

15 пути конкурентов, он достаточно глубоко проникает в структуру и прекращает существование лишь встретившись с сигналом по каналу К3.

Таким образом, при данной настрой2О ке узлов решетки и при поступлении всех без исключения запросных сигналов на выход пройдет сигнал.К3. Однако из этого нельзя сделать вывод о том, что К3 - самый сильный. Дейст15 вительно, как показано ниже, при no"" ступлении запросов не IlO восьми, а по четырем входам Кl -; К4, выигрывает не К3, а К4.

Рассмотрим схему взаимодействия входов, приведенную на фиг. 6. Сигналы Кl и К2, встречаясь с сигналом . К3, выбывают из конкуретной борьбы.

Сигнал К4, не встречая сопротивле" ния со стороны К5 К8 и К2, проходит до узла, помеченного знаком «-, 35 и приостанавливает распространение . сигнала К3, поскольку по условию

К4 — К3. Таким образом, канал К4 имеет максимальный приоритет. при числе запросов, равном четырем, и их рас- пределении по каналам согласно

Фиг. 5.

Подводя итоги по рассмотрению работы блока 1, можно сделать следующие заключения. Блок 1 можно настро45 ить на работу. в одном из 2 2В режимов, среди которых имеются 8 режимов жесткого задания приоритетов и (2

-8!) гибких или демократичных режимов.

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

55 ным приоритетом не имеет воэможности на выигрыш в конкурентной борьбе с любым другим сигналом. Последнее обстоятельство приводит к тому, что низ9 10277

I коприоритетные каналы вообще не получат обслуживания при достаточно высокой суммарной интенсивности потока запросов по более высокоприоритетным каналам. ° 5

Любой из гибких режимов в той или иной мере устраняет отмеченный выше недостаток. Приоритеты каналов уже не являются абсолютными, а имеют вероятностный характер. Низкоприоритетные 1О каналы не оттесняются высокоприориг тетными, а периодически реализуют шансы (пусть даже невысокие) на обслуживание. Высокоприоритетные каналы, в свою очередь, периодически усту- 15 пают место низкоприоритетным, так как приоритет между каналами является функцией числа и распределения запросов по каналам.

Блок 21 предназначен для сбора ин- 2О формации о потоке входных запросов.

Каждому входу 2 поставлен в соответствие счетчик 29 времени ожидания обслуживания. При отсутствии запросов на входы 2 поданы нулевые сигналы, все счетчики установлены а "00" по входам сброса; При поступлении одного или нескольких запросных сигналов соответствующие счетчики начинают подсчет времени ожидания обслуживания.

27 10

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

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

Применение изобретения позволяет расширить функциональные возможности устройства путем адаптации его ко входному потоку запросов.

102) 27

1027727

1027727

1027727

Тираж 706 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

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

Редактор Н. Гришанова Техред С.Мигунова Корректор В. Бутяга

Заказ 4742/54