Устройство для приоритетного обслуживания запросов

 

Изобретение относится к вычислительной технике, а именно к устройствам для приоритетного обслуживания запросов с переменными приори- . тетами, и может быть использовано в многопроцессорных ЭВМ и информационно-вычислительных системах. Цель изобретения - повьшение быстродействия устройства. Устройство для прио- -ритетного обслуживания запросов содержит матрицу m X п узлов анализа (где m - разрядность кода приоритета; п - число запросных входов устройства ) и п элементов развязки Узел (j, i) анализа содержит элементов И-НЕ и элемент ИЛИ. Работа устройства позволяет производить опережающий анализ кодов приоритета: анализ последующего (более младшего) разряда начинается сразу после формирования на выходах элементов И-НЕ группы узлов анализа предьщущего разряда инверсного старшего разряда кода приоритета, не дожидаясь преоб - разования сигналов, присутствующих на запросных входах устройства„2 ил. ю

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

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

РЕСПУБЛИК

<5g 4 С 06 Р 9/46

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

Н,А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

l10 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4225463/24-24 (22) 07.04.87 (46) 28.0?.89. Бюл. М 8 (71) Институт технической кибернетики АН БССР (72) В.Е.Чернявский, N.И.Иаханек и А.Г.Ярусов (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 1005055, кл. С 06 F 9/46, 1981.

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

Ф 1295394, кл. О 06 Р 5/46, 1985. (54) УСТРОЙСТВО ДЛЯ ПРИОРИТЕТНОГО

ОБСЛУЖИВАНИЯ ЗАПРОСОВ (57) Изобретение относится к вычис..лительной технике, а именно к устройствам для приоритетного обслуживания запросов с переменными приори- . тетами, и может быть использовано в многопроцессорных ЗВ11 и информацион1

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

Цель изобретенная — IloBbBIleHHe быстродействия устройства.

На фиг.1 изображена функциональная схема предлагаемого устройства; на фиг.2 — функциональная схема уз лов анализа i-ro канала для разрядности m = 4 (т.е. 1=1,2,3,4).

Устройство содержит m кп (где m— разрядность кода приоритета, n —„„Я0„„1462310 А 1 но-вычислительных системах. Цель изобретения — повышение быстродействия устройства. Устройство для прио.ритетного обслуживания запросов содержит матрицу m x п узлов анализа (где m — разрядность кода приоритета; n — число запросных входов устройства) и п элементов развязки.

1-1

Узел (1, i) анализа содержит 2 элементов И-НЕ и элемент ИЛИ. Работа устройства позволяет производить опережающий анализ кодов приоритета . анализ последующего (более младшего) разряда начинается сразу после формирования на выходах элементов И-НЕ группы узлов анализа предыдущего

С> разряда инверсного старшего разряда кода приоритета, не дожидаясь преоб разования сигналов, присутствующих

HB запросных входах устройства.2 ил.

2 число запросных входов устройства) узлов анализа. узел (j,i) служит для анализа j-ro разряда i-й группы кодовых входов устройства, т.е. а;

Каждый узел j-й группы узлов анализа содержит 2 элементов И-НЕ 1 и элемент ИЛИ 2.

Позициями 3, и 4; обозначены соответственно i-й запросный вход и -й выход устройства. Позицией 5. обозначен элемент развязки, связывающий запросный вход 3, с соответствующим выходом 4; устройства. На чертеже символом А, обозначена i-я группа кодовых входов устройства а,, а а ;, причем левый разряд кода, по14623!О ступающий по входу а „, является старшим. Позицией 6; обозначена шина, снязывающая выходы всех элементон ИНЕ 1 j-й группы узлов анализа.

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

На кодовые входы А; и запросные входы 3, устройства одновременно поступают коды приоритетов а „,...,а сопровождаемые сигналами запросов.

Единичный сигнал на входе 3, соот :ветствует запросу на обслуживание.

:: Допускается совпадение кодов на вхо :дах устройства.

Первая группа узлов (1,1),..., (1,n) анализирует значения старших разрядов а„ кодов, принимая во вни" мание наличие в соответствующих кана" лах сигналов запросов.

При отсутствии запроса в i-м ка,нале "О" с входа 3; этого канала независимо от значения разрядов а„,... а, устанавливает единичные значения на выходах всех элементов И-НЕ 1 данного канала, не препятствуя тем самым взаимодействию на шинах б по монтажной логике И разрядов остальных кодов. Кроме того, нулевой сигнал (отсутствия запроса ) на входе 3 гарантирует отсутствие разрешения на обслуживание на выходе 4; данного канала в силу связи входа с выходом через элемент 5 развязки. Таким образом, нсе каналы, не имеющие запросов на входах 3;, будут исключены из анализа и не смогут .оказать влияния на анализ остальных кодов.

Рассмотрим теперь все каналы, выставившие запросы на обслуживание.

В первой группе узлов анализа (1,1), . ° °,(1,n) сравниваются старшие разряды всех кодов. Если хотя бы один из разрядов а, был равен единице, то на выходе элемента И-НЕ 1 в со,ответствующем канале образуется нулевой сигнал, который будет поддерживать нулевой потенциал на шине 6,.

Тогда все те каналы, старший разряд которых не совпадал с максимальным (т.е, равен нулю), будут исключены из дальнейшего анализа, так как нулевое значение старшего разряда после прохождения закрь:того по первому входу элемента ИЛИ 2 данного канала . обеспечит нулевой сигнал на соответствующем разрешающем выходе 4; устройства. Если же все старшие разряды были равны нулю, то на шине 6 образуется единичный сигнал, не исключающий продолжение анализа последующих разрядов всех кодов. Заметим, что на шине 6, образовался сигнал, 5 инверсный максимальному, В j-й группе узлов анализа происходит анализ j-x разрядов всех тех кодов, значения предыдущих ()-1) раэ10 рядов которых совпали с максимальными. На шинах 6,,...,6;, образован код, инверсный максимальному коду предыдущих j""1 разрядов. Этот максимальный код имеет одно из 2 воз-; можных значений, Тогда 2 элементов И-НЕ 1 в (j, i)-м узле анализа распознают, совпадают ли предыдущие j"i- старших разрядов кода данного канала с максимальным кодом и

20 при единичном сигнале на входе а;; устройства установят нулевой сигнал на шине 6„ .

Если во всех каналах сравниваемые j-е разряды равны нулю, то на

25 второй вход всех элементов И-НЕ

j-й группы узлов. анализа поступит нулевой сигнал. Он обеспечит единичное состояние шины 6 j а значит и элемента ИЛИ 2 во нсех каналах.

30 В j-м канале разрешение на выходе 4, будет в том и только н том случае, когда имеется запрос на входе 3t и выходы всех элеме:;тон ИЛИ 2 н узлах (1фi)р ° р(шуi) находя ся н состоянии 1,так как выходы этих

tt н элементов соединены по монтажной логике И между собой и с помощью элемента 5; развязки с входом запроса на обслуживание канала. Но единич4О ные сигналы на выходах всех элементов ИЛИ 2 канала будут лишь н том случае, когда значения сигналов на кодовом входе А; совпадают с инверсными значениями кода на шинах 6 (т.е. совпадают с прямым максимальным кодом).

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

Пусть на входы устройства поступают три трехразрядных коца А,= 1 i 1, А = О О,,А = О О 1, причем запросы (в ниде "i") имеются только во втором и третьем каналах.

Рассмотрим работу первой группы узлов анализа.

На выходах элементов И-НЕ будут следующие сигналы: И-HE 1 узла анализа (1,1) 1 (отсутствует запрос);

И-НЕ 1 (1,2) =1 (старший разряд равен

I 5 l4 нулю); И-НЕ 1 (1,3) = 1 (старший разряд равен нулю).

Во второй группе узлов анализа на выходах элементов И-HE l будут следующие сигналы: первый и второй И-HE

1 (2,1) = 1 (отсутствует запрос); первый И-НЕ 1 (2,2) = 1 (старший разряд равен нулю); второй И-НЕ 1 (2,2)=

О (элемент определил совпадение старшего разряда кода данного канала с максимальным, а также наличие в среднем разряде кода единицы).

Первый И-НЕ 1 (2,3) = 1 (старший разряд равен нулю), второй И-НЕ

1 (2,3) = 1 (средний разряд равен нулю).

В третьей группе узлов анализа: первый — четвертый И-НЕ 1 (3,1) = 1 (отсутствует запрос); первый — четвертый И-НЕ 1 (3,2) = 1 (младший разряд равен нулю); первый И-НЕ 1 (3,3)= — 1 (старший и средний разряды равны нулю); второй И-НЕ 1 (3,3) = 1 (средний разряд равен нулю); третий И-НЕ

1 (3,3) = 1 (старший разряд равен нулю); четвертый И-НЕ 1 (3,3) = 1 (на шине 6 присутствует нулевой сигнал, инверсный максимальному).

Таким образом, на шинах 6. образовались сигналы 6, =1, 6 = О, 6 =1 т.е. код 10! является инверсным по отношению к максимальному.

На выходах элементов ИЛИ 2 в пер вом канале будут следующие сигналы:

ИЛИ 2 (1,1) = ИЛИ 2 (2,1) = ИЛИ 2 (3,1) = 1. Однако нулевой запрос на входе 3 обеспечит нулевой сигнал на выходе 4, . На выходах элементов ИЛИ ,2 во втором канале будут сигналы:

ИЛИ 2 (1,2) = ИЛИ 2 (2,2) = ИЛИ 2 (3,2) = 1 и в силу наличия единичного сигнала запроса на входе 3, на выходе 4 появится разрешение на обслуживание.

Наконец на выходе элементов ИЛИ

2 в третьем канале будут сигналы:

ИЛИ 2 (1,3) = 1; ИЛИ 2 (2,3) =0; .ИЛИ 2 (3,3) = 1 °

623!О

Нулевой сигнал на выходе ИЛИ 2 третьего канала узла анализа второй группы узлов анализа "снимет" pasразрешение Йа обслуживание своему каналу.

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

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

Устройство для приоритетного обслуживания запросов, содержащее m групп по и узлов анализа (m — разрядность кодов приоритетов, n — число запросных входов устройства), и

1О элементов развязки, причем i-й (i= — 1, °... n) узел анализа j -й (j =1,... . ° ° °,m) группы узлов анализа содержит элемент ИЛИ и первый элемент

И-НЕ, первый вход первого элемента

И-НЕ i-го узла анализа первой группы подключен к i My запросному входу устройства и к входу i-го элемента развязки, выход которого соединен с выходом элемента ИЛИ i-го узла анализа первой группы узлов анализа, вторые входы элемента ИЛИ и первого элемента И-НЕ i-ro узла анализа j-й группы узлов анализа соединены между собой и подключены к j-му входу i-й

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

j-й группы узлов анализа введены

35 (2 — 1) (j +1) входовых элементов

И-НЕ, причем в i-м узле анализа r-й (r=2,...,m) группы узлов анализа пер. вые входы всех элементов И-НЕ соединены с i-и запросным входом устрой40 ства, второй вход р-ro (р=2,3,..., 2 ) элемента И-НЕ соединен с j ì входом -й группы кодовых входов устройства, (2+1)-й вход (1=1,..., j-l) S-го (S=1,2,...,2 ) элемента

45 И-НЕ соединен с 1-и входом i-й группы кодовых входов устройства.при

-! 12

oL =1 в разложении $=2 -2 eL —

-2" оС вЂ” ... -2 о,, а при ь =

=О соединен с выходами элементов

-HE всех узлов анализа 1-й группы узлов анализа, выходы всех элементов

И-НЕ всех узлов анализа j-й группы узлов анализа соединены между собой через МОНТАЖНОЕ И, выход элемен55 та ИЛИ i-го узла анализа r-й группы узлов подключен к выходу i-го элемента развязки и является -м выходом устройства.

Зе

1)

Фис.1

+r.i Й

Og,1

Фиа2

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

Редактор lO.Середа Техред А.Кравчук Корректор С. Черни

Заказ 713/47 Тираж 667 Подписное

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

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

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