Приоритетное устройство Советский патент 1983 года по МПК G06F9/50 G06F9/52 G06F13/366 

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

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

Изобретение относится к цифровой вычислительной технике и может быть использовано в вычислительных системах, содержащих несколько активных источников информации, подключенных к устройству общего пользования, например к общей памяти. Известно приоритетное устройство, содержащее блок хранения запросов, блок хранения маски, приоритетный блок, группу элементов И, причем гру па входов блока хранения запросов яв ляется первой группой входов устройс ва, а группа выходов блока хранения запросов подключена к первой группе входов приоритетного блока, группа входов блока хранения маски является второй группой входов устройства l }. Недостатком устройства является сложность и полное отключение низкоприоритетных каналов при обработке групповых запросов высокоприоритетных каналов. Наиболее близким по технической сущности к предлагаемому является многоканальное приоритетное устройст во, содержащее блок- формирования раз решений , информационные входы которого являются запросными входами уст ройства, а выходы - выходами разреше ний, -управляющие входы блока формирования разрешений являются управляющими входами устройства, блок фор мирования разрешений содержит логичёские блоки. Логические блоки в устройстве соединены в виде пирамидальной структуры. Если устройство содержит 2 запросных входов, то число возможных способов задания приоритетов между каналами равно 2(2n--i; (,2... )С2 . Это число, однако, не обеспечивает полной свободы в задании приоритетов, для чего требуется (2 )/ способов задания, соответствующих всем возможным перестановкам номеров входных каналов. Ограниченность возможностей управления приоритетами определяет достаточно узкую область применения устройства. Кроме того, отсутствие аппаратных средств анализа потока входных запросов затрудняет адаптацию устройства к этому потоку. Таким образом, недостатком устройства являются ограниченные функциональные возможности. Целью изоб эетения является расширение функциональных возможностей устройства путем увеличения числа режимов обработки и адаптации устройства к входному потоку запросов. Поставленная цель достигается тем, 4то в приоритетное устройство, содержащее блок формирования разрешений, информационные входы которого являются запросными входами устройства, а выходы - выходами разрешений устройства, введены анализа запросов и блок памяти, причем, блок формирования разрешений содержит г группу из матриц логических блоков (где 2 - число информационных входов устройства, an- любое целое число), состоящую из п подгрупп, j-я подгруппа включает .в себя 2 матриц размерностью , где j п, п-1,2,1, выходы строк матрицы i-й подгруппы, i п, где п-1,2, соединены с входами строк и столбцов матриц {|-1)-й подгруппы, входы строк и столбцов матрицы п-й подгруппы являются информационными входами блока формирования разрешений, выходы строк и столбцов матриц первой подгруппы являются выходами блока формирования разрешений, группы управляющих входов всех матриц являются группой управляющих входов блока формирования разрешений, матрица j-й подгруппы содержит логических блоков, первые входы логически х блоков первой строки являются входами столбцов матрицы, вторые вхо ды логических блоков первого столбца являются входами строк матрицы, первые входы логических блоков последней строки являются выходами столбцов матрицы, вторые выходы логических блоков последнего столбца являются выходами страк матрицы, первые и вторые входы остальных логических блоков соединены соответственно с первым выходом логического блока того же столбца предыдущей строки и с вторым выходом логического блока той же строки предыдущего столбца, группа входов блока анализа запросов соединена с группой информационных входов устройства, группа выходов блока.анализа запросов соединена с группой адресных входов блока памяти информационные выходы которого соеди нены с управляющими входами блока формирования разрешений, тактовый вход устройства соединен с тактовым входом блока анализа запросов. Логический блок содержит три элемента И, два элемента ИЛИ и два инвертора, первый вход логического блока подключен к первому входу первого элемента И, к первому входу второго эле мента И и к первому входу первого эл мента ИЛИ, второй вход логического блока подключен к второму входу первого элемента ИЛИ, к второму входу второго элемента И и к входу первого инвертора, выход которого соединен с 10 вторым входом первого элемента И, управляющий вход логического блока подключен к третьему входу второго элемента И, выходы первого и второго элементов И соединены с входами второго элемента ИЛИ, выход которого является первым информационным выходом логического блока и через второй инвертор подключен к первому входу третьего элемента И, выход которого является вторым информационным выходом логического блока, выход первого эле мента ИЛИ соединен с вторым входом третьего элемента И. Блок анализа запросов содержит группу счетчиков и группу элементов ИЛИ, выходы которых соединены со счетными входами соответствующих счетчиков, первые входы всех элементов ИЛИ объединены и соединены с входом синхронизации блока анализа запросов, выходы старших разрядов счетчиков соединены с вторыми входами соответствующих элементов ИЛИ и являются выходами.блока анализа запросов, входы установки нуля счетчиков являются входами блока анализа запросов. На фиг. 1 приведена функциональная схека устройства; на фиг. 2 то же, блок формирования разрешений; на фиг. 3 то же, логического блока; на фиг. Ц - то же, блок анализа запросов; на фиг. 5 и 6 - мнемонические схемы, поясняющие принцип работы устройства. Устройство (фиг. 1) содержит блок 1 формирования разрешений, запросные входы 2 устройства, выходы 3 разрешений устройства, блок / анализа запросов, выходы 5 блока памяти, блок 6 памяти, выходы 7 блока , тактовый вход 8 устройства, Блок формирования разрешений содержит матрицы 9-15 логических блоков, логические блоки 16, входы 17 и 18 логических блоков, выходы 19 и 20 логических блоков, вход 21 логического блока. Лагический блок (фиг. 3) содержит инверторы 22 и 23, элементы И , элементы ИЛИ 27 и 28. Блок анализа запросов (фиг. ) содержит счетчики 29, элементы ИЛИ 30. Функции, выполняемые логическим блоком 16, определяются таблицей. Логический блок 16 выполняет функ цию двухвходового арбитра по отношению к сигналам, поступающим на входы 17 и 18, При отсутствии конфликтов между этими сигналами, т.е. при комбинациях 00, 01 и 10, они транслируются на выходы 19 и 20 независимо от значения сигнала на управляющем входе 21 (символ X в таблице). При обнаружении конфликта между сигналами на входах 6 и 7 (комбинация 11) логический блок отдает предпочтение тому или иному сигналу в saвисимости от значения сигнала на управляющем входе 21. Таким образом, на выходах 19 и 20 логического блока 5 исключается одновременное наличие логических единиц Блок 1 предназначен для разрешения конфликтов между запросными сигналами, подаваемыми на входы 2 в виде логических единиц. При отсутствии запросных сигналов сигналы разрешений также отсутствуют, т.е. на всех выходах 3 сформированы логические нули (см. верхнюю строку приведенной выше таблицы). При наличии одиночного потенциального сигнала запроса на одном из входов группы 2 этот сигнал проходит через все встречающиеся на его пути

, , , ,

K2--S.K6, К2-9-К7, , , ,

, , , , , .

, К6-Ж1, , К6--Ж4,

., , ,

, ,

. логические блоки 16 и поступает на соответствующий выход группы в виде единичного потенциального сигнала. В этом случае код на управляющих входах может быть любым (см. символ X в строках 2 и 3 приведенной выше таблице). Если на входы 2 устройства одновременно поданы несколько сигналов логических единиц, то эти сигналы, встречаясь каждый с каждым в соответствующих узлах решетки, подвергаются отбору, в результате чего на выходы 3 попадает лишь один сигнал. Взаимоотношения между любой парой конкурирующих запросных сигналов однозначно определяются управляющим кодом, поданным на выходы 5 (см. строки 4 и 5 приведенной выше таблицы). Пусть, например, требуется обеспечить следующую приоритетность входов 2 К1-К8 (нумерация приведена на фиг. 1): КЗ- К2-Ж8- К6- К7-Ж1-Ж5-Ж, Стрелка в такой записи направлена от более приоритетного входа к менее приоритетному. Для обеспечения указанного режима управляюи1ий код на выходах 5 должен настроить логические блоки в узлах решетки следующим образом:

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

Аналогично можно задать любой приоритетный порядок между каналами. Число таких режимов равно числу перестановок между номерами каналов: Pg 40320.

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

Действительно, поскольку число управляющих входов равно в данном прил. OQ

мере Сд 28, то возможны 2 268 3545б вариантов настройки, которые, за исключением ранее рассмотренных , характеризуются гибким распределением приоритетов между каналами .

Смысл этих режимов состоит в том что приоритет между каналами определяется не только управляющим кодом, поданным на входы блока k, но также зависит от числа поступивших запросов и их распределения по каналам. Если в предыдущем примере изменить зна чение только одного бита в управляющем коде, а именно, бита, определяющего взаимоотношения между входами К и К, то условие , помеченное ранее знаком , изменится на противоположное: . Такое изменение, как показано ; ниже, приводит к получению одного из гибких режимов. Предположим, что запросные сигналы поступили по всем входам К1 f К8. На фиг. 5 утолщенными линиями показаны траектории распространения запросных сигналов через блок 1. Видно что при взаимодействии сигналов К4 и К5 побеждает сигнал по входу К5, так как соответствующий узел решетчатой cтpyкtypы настроен на приоритетную передачу сигнала по входу К5 при возникновении конфликта между К5 и К4 (). Указанный сигнал далее взаимодействует с сигналом по входу КЗ и на этот раз прекращает существование, так как не выдерживает конкурентной борьбы с сигналом по входу КЗ (). Результирующий сигнал с входа КЗ последовательно побеждает сигналы по входам Кб, К7, К8, К2 и К1 и, поскольку в узле, помеченном знаком-jt, уже нет конкури рующего сигнала по входу К4 ()

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

Входной сигнал по К2, хотя и более высокий приоритет по отношению к сигналам с входов К5 Кб, не встречается синими на своем пути, тёк клк последние подавлены сигналом по КЗ 1 сигнал К2, пройдя до встречи с сигналом по каналу КЗ, прекращает

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

15 пути конкурентов, он достаточно глубоко проникает в структуру и прекращает существование лишь встретившись с сигналом по каналу КЗТаким образом, при данной настрой20 Кб узлов решетки и при поступлении всех без исключения запросных сигналов на выход пройдет сигнал КЗ. Однако из этого нельзя сделать вывод о том, что КЗ - самый сильный. Действительно, как показано ниже, при поступлении запросов не по восьми, а по четырем входам К1 т КЦ, выигрывает не КЗ, а К4. Рассмотрим схему взаимодействия входов, приведенную на фиг. 6. Сигналы К1 и К2, встречаясь с сигналом КЗ, выбывают из конкуретной борьбы. Сигнал К4, не встречая сопротивления со стороны КБ К8 и К2, проходит до узла, помеченного знаком , и приостанавливает распространение сигнала КЗ, поскольку по условию . Таким образом, канал К имеет максимальный приоритет, при числе запросов, равном четырем, и их распределении по каналам согласно фиг, 5Подводя итоги по рассмотрению работы блока 1, можно сделать следующие заключения. Блок 1 можно настроить на работу в одном из 2 режимов, среди которых имеются 8 / режимов жесткого задания приоритетов и (.) гибких или демократичных режимов . Любой из жестких режимов характеризуется установленной субординацией каналов. Приоритетный-порядок абсолютен , Самый приоритетный сигнал всегда выигрывает, сигнал с минимальным приоритетом не имеет возможности на выйгрыш в конкурентной борьбе с любым другим сигналом. Последнее обстоятельство приводит к тому, что низкоприоритетные каналы вообще не получат обслуживания при достаточно высокой суммарной интенсивности потока запросов по более высокоприоритетным каналам.

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

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

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

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

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

фаг,