Устройство приоритета Советский патент 1991 года по МПК G06F9/46 

оэ ее

ОЗ К5 Ј

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

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

На фиг.1 приведена структурная схема устройства; на фиг.2 - функциональная, схема узла анализа первой группы; на фиг.З - функциональная схема узла анализа последней группы; на фиг.4 - функциональная схема узла анализа средней группы; на фиг.5 - 7 - примеры узлов анализа первой группы для случаев анализа соответственно 1,2 и 3 разрядов; на фиг.8- 10 - примеры узлов анализа последней группы для случая анализа соответственно 1, 2 и 3 разрядов;на фиг.11- - 13 - примеры узлов анализа средней группы для (m;4, m;) (1,1), (2,1) и (1, 2), где т. , т; - число анализируемых разрядов кода приоритета; на фиг.14 - пример узла анализа средней группы для случая (2, 2); на фиг. 15 - пример построения устройства для m п .

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

Устройство приоритета содержит узлы 1 анализа первой группы, узлы 2 анализа средней группы, запросные входы 3 устройства, выходы 4 устройства, запросные выходы 5 узлов 1 анализа первой группы, запросные входы 6 узлов 2 анализа средней труп- пы, запросные выходы 7 узлов 2 анализа средней группы, узлы 8 анализа последней группы с запросными входами 9. Узлы 1 анализа первой группы содержат элемент 10 развязки и элементы И-НЕ 11 группы. Узлы 8 анализа последней группы содержат элементы ИЛИ 12 группы, а узлы 2 анализа средней группы содержат элемент 13 развязки, элементы ИЛИ 14 группы и элементы И-НЕ 15 группы.

Кроме того на чертежах приняты следующие обозначения: А - вход кода приоритета, состоящий из группы разрядных входов Эк(л) , ...,,j узлов анализа; 1,...,1В(- группы логических шин устройства.

Пусть запросы сопровождаются т- разрядными кодами приоритетов А. Предположим количество установок на шинах 1 не должно превышать числа Т. Тогда устройство должно состоять из двух типов узлов. В первом типе

m-Rr Cm -f

узлов анализируются по

+ 1

разрядов, а во втором

DI-RT т

разрядов, где RTQif - остаток от деления m на Т. При этом число узлов первого типа равно , а второго . Кроме того, для сокращения объема оборудования необходимо в качестве первого и последнего выбрать узлы первого типа (при их наличии), а также при Rftj1 1 2 чередовать в устройстве узлы первого и второго типов. Например, при числе установок и числе разрядов в кодах приоритета группы узлов будут последовательно анализировать либо по 4, 3, 4, 3, 3, 4,либо по 4, 3, 3, 4, 3, 4 разряда. При любом другом расположении групп узлов или при изменении размерностей узлов объем оборудования устройства возрастает.

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

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

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

Если в предыдущих узлах 2 было обнаружено несовпадение с соответст5 16

вующими разрядами максимального кода, то на входе 6 узла 2 будет присутствовать сигнал логического нуля, который обеспечит нулевой сигнал Отсутствие разрешения на обслуживание на выходе 7 данного узла, а следовательно и на соответствующем выходе 4. Кроме того, на выходах элементов И-НЕ 15 данного и всех последующих узлов будут присутствовать сигналы логических единиц, которые не будут препятствовать анализу кодов во всех ос- . тальных каналах.

Если на входе 6 имеется сигнал логической единицы (разрешение на продолжение анализа), то группа элементов ИЛИ 14 анализирует совпадают ли все разряды (1-1)-й группы данного канала с соответствующими разрядами (1-1)-й группы максимального кода. В случае совпадения на выходах всех элементов ИЛИ 14 будут присутствовать единичные сигналы, которые обеспечат единичный сигнал на выходе 7 данного узла. На первые входы элементов И- НЕ 15 поступит с входа 6 сигнал, разрешающий шифрацию. Элементы И-НЕ 15 преобразуют поступающие на их входы сигналы в специальный ход, который удобен для сравнения на логических шинах. После смешивания все/ специальных кодов на логических ш- ,:х образуется смешанньй код. Нулевые сигналы, образовавшиеся на шинах, являются маскирующими для всех тех каналов, которые выставили разряды, отличные от максимальных. В этих каналах в последующем (i+t)-M логическом узле на группе элементов ИЛИ 14 будет установлено отличие кода приоритета канала от максимального,.,а на выходе 7 (i+1)-ro угла вырабатывается нулевой сигнал.

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

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

93246

Рассмотрим трехканальное устройство, на входы А которого поступили -- коды приоритета N,101000, N2 100101, N.111111, а запросы имеются только на первом и втором входах 3.

На разрядные входы в узлы 1, 12, поступят двухразрядные коды, а именно 0 В узле : а, 1 .

В узле а (1 .

В узле 1 : .

На- запросных входах будут сигналы 3(, . На выходах элементов 15 10 развязки и на выходах 5 узлов первой группы появятся сигналы 5 (5 1, , т.е. третий канал будет исключен из дальнейшего анализа.

На выходах элементов И-НЕ 11 сфор- 20 мируются сигналы.

В первом канале: И-НЕ 11( , И-НЕ .

Во втором канале: И-НЕ , И-НЕ .

25 В третьем канале: И-НЕ 11,11д .

На логических шинах 1 после реализации операции монтажной логики И образуются сигналы (j 1, lf(. 30 Сигналы с логических шик первой группы вместе с сигналами запросов b поступают на дальнейший анализ во вторые узлы 2 средней грзгплы.

Вторая группа разрядных входов , состоит из одного разряда. В первом канале: , во втором канале , в третьем канале а 1.

На входах элементов 13 развязки вторых узлов 2 будут сигналы. В пер- 4Q вом и втором каналах: элемент развязки , в третьем канале: элемент развязки .

На выходах элементов ИЛИ 14 всех вторых узлов 2 будут сигналы логи- ,г ческой единицы.

На выходе второго элемента И-НЕ 15 второго узла 2 первого канала будет нулевой сигнал, который обеспечит такой же сигнал на логической шине 0.

50

Рассмотрим работу третьей группы

узлов. В первом канале элементы установятся: элемент развязки , элемент ИЛИ , т.е. на выходе 7 -, -узла будет единичный сигнал - разрешение на дальнейший анализ. Во втором канале: элемент развязки , элемент ИЛИ , следовательно, сигнал на выходе 7 будет 0. Этот сигнал га10

20

25

рантирует нулевой сигнал на выходе 4 , второго канала.

Таким образом, после анализа трех разрядов из процедуры дальнейшего арбитража будут исключены запросы второго и третьего каналов. При этом нулевые сигналы запрета обеспечат единичные сигналы на выходах всех элементов И-НЕ 15 во втором и третьем каналах во всех последующих узлах. Б первом канале (после выставления 4, 5, b разрядов и проверки элементами ИЛИ 13 их на.совпадение с разрядами максимального кода) на выходе 4 первого канала образуется единичный сигнал разрешения на обслуживание.

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

Устройство приоритета, содержащее группы узлов анализа, причем в каждой группе содержится п узлов анализа (п - число запросных входов устройства), группа запросных входов устройства соединена с запросными входами узлов анализа первой группы, запросные выходы узлов анализа( группы, где , (Б-1), В - число групп узлов анализа) соединены с запросными входами соответствующих узлов анализа (d+D-й группы, запросные выходы узлов анализа В-и группы являются выходами устройства, отличающееся тем, что, с целью повышения быстродействия, оно содержит в

каждом узле янализа первой группы

2т л ......, .-1

элементов И-НЕ, в каждом узле анализа i-й группы 1 i В (если В 3) содержится элемент разяязки, группа из 2тм-1 элементов ИЛИ и 2т;-1 по 2т элементов анализа последней

п™ 6-1

ся группа из 2.

В-1 (m, + 2Lm разрядность кодов приори15 2.

тетов канала), причем в каждом узле анализа первой группы первые входы всех элементов И-НЕ соединены с вхо дом элемента развязки и с запросным входом узла анализа, выход элемента развязки соединен с запросным выходом узла анализа, разрядный пход зщ( узла анализа, где К(1) € Ј|,. .. ,г - к (О

,1,

16193248

элемента И-НЕ (1,12™ -1)-группы, если в представлении числа 1

1 Jв виде 1, 2L2 b где b; j- J J

значение bk 1, выход элемента И-НЕ группы с номером 1,. соединен с 1 -и логической шиной первой группы логических шин, в каждом узле анализа i-й группы первый вход If.,-го (}„, 1,...,2 ) элемента ИЛИ группы подключен к (.-, )-й шине (i-1) группы логических шин, разрядный вход

15 ) Узла анализа (К (i-D 6 Ј1 ,.. ., ,HI- )

30

40

и z -1 групп И-НЕ, в каждом узле В-й группы содержит- 1 элементов ИЛИ,

45

,- 50

m

1ч

входу если

Н подключен к ()-му

Г Г 1;,-го

элемента ИЛИ группы, представлении числа ,, в

i

m;-i

виде 1Ч

JJ

(где Ь- е

0,1 )}

значение bt (;,1, выходы элементов ИЛИ группы объединены через монтажное И и подключены к выходу элемента развязки и к запросному выходу узла анализа, первые входы всех элементов И-НЕ группы узла анализа подключены к входу элемента развязки и к запросному входу данного узла анализа, разрядный вход узла анализа (K(i) e Јl,...,m; которого подключен

35 к (1+

кС)

Ь„)-му входу первой группы т

входов каждого элемента И-НЕ 1, -и группы (,...,2 -1), если в представлении

ч j

числа

в виде

,1

1

Ь (ЬбЈо,1 Нзначение

Ч м;

1, выходы всех элементов И-НЕ 1,-и группы соединены с 1| -и шичой I -и группы логических шин устройства, разрядный вход а л-. узла анализа (K(i-1) , ... ,m -,) подключен к ИМ (21Ьр)-му входу второй группы вхоОп1

r Ifll-l

дов (2 -1;,,)-х элементов И-НЕ каждой группы, если в представлении

nn;-i

числа виде

значение Ь , Чli-S

j-если в

Г

ь;

представле№, - ,

подключен к

(1+21Ьа)-му входу

1, -го

,1,

0

m

1ч

входу если

Н подключен к ()-му

Г Г 1;,-го

элемента ИЛИ группы, представлении числа ,, в

i

m;-i

виде 1Ч

JJ

(где Ь- е

0,1 )}

значение bt (;,1, выходы элементов ИЛИ группы объединены через монтажное И и подключены к выходу элемента развязки и к запросному выходу узла анализа, первые входы всех элементов И-НЕ группы узла анализа подключены к входу элемента развязки и к запросному входу данного узла анализа, разрядный вход узла анализа (K(i) e Јl,...,m; которого подключен

35 к (1+

кС)

Ь„)-му входу первой группы т

0

входов каждого элемента И-НЕ 1, -и группы (,...,2 -1), если в представлении

ч j

числа

в виде

,1

1

Ь (ЬбЈо,1 Нзначение

Ч м;

-

45

50

1, выходы всех элементов И-НЕ 1,-и группы соединены с 1| -и шичой I -и группы логических шин устройства, разрядный вход а л-. узла анализа (K(i-1) , ... ,m -,) подключен к ИМ (21Ьр)-му входу второй группы вхоОп1

r Ifll-l

дов (2 -1;,,)-х элементов И-НЕ каждой группы, если в представлении

nn;-i

числа виде

значение Ь , Чнии числа 1

li-S

j-если в

Г

ь;

в виде

представле№, - ,

т u l;., V j

if (i-0

значение Ь,. 0, то (1-Ьр)-й

, вход третьей группы входов (2

ких шин устройства, разрядный вход

B-i VfB-i)

(К(В-1) e{l, .. . ,тпв.,. узла анак -;

л. х- . Л f у 114.4.EU ОЛ ,и,.1Э , Л. .-..

элемента И-НЕ каждой (1, 5 лиза п°Дключен к +2- -Ьр)-Му входу

...,2 -1)-й группы подключен к

л, -, K(i-ib« IJp1 n, (2 -2- X 2П 1- )-й шине

h«fcf,4

Р)

10 -го элемента ИЛИ группы, если в

°

представлении числа 0, в виде

f.i J i

(i-П-й группы логических шн устрой- 10 2 Ь (гДе )1 } ства, в каждом узле анализа послед- , .

ней В-й группы узлов анализа первыйние Ьк(в-) 1 выходы элементов ИЛИ

вход Ь ,-го элемента ИЛИ группы „группы ализа У11™ соединены

(1В., 1,.:., 2WBH-1) подключен к (2 -с запросными входом и вькодом узла

-,„,)-и шине (В-1)-й группы логичес-анализа.

°к(7;

16193241°

ких шин устройства, разрядный вход

(К(В-1) e{l, .. . ,тпв.,. узла анак -;

.-..

лиза п°Дключен к +2- -Ьр)-Му вход

Р)

10 -го элемента ИЛИ группы, если в

°

представлении числа 0, в виде

f.i J i

2 Ь (гДе )1 } , .

Изобретение относится к вычис тельной технике.и может быть йспольz/ зовано при создании систем параллельной обработки информации, з которых несколько активных абонентов требуют разрешения на доступ к общесистемным разделенным ресурсам. Цель изобретения - повышение быстродействия устройства. Устройство приоритета содержит узлы 1 анализа первой группы, узлы 2 анализа средней грулпы0 узлы 8 анализа последней группы,, запросные входы 3 и выходы 4j, входа А кодов приоритета. Устройстве поззолке1 анализировать в каждом узла анализа произвольное число разрядов хзда приоритета. 15 ил. Ч в-1 (О

е-;

&К1В-1}

3

Фиг.3

Фиг 4

Фиг.6

Фиг.7

1я.

в-i

Фиг.9

фагЛО

акгп)

6 k-l

п

ак(Н)

ч п

нмг

«F и

/«72

а«и)

7

-

W

4

Фиг. 11

г/й 13

tpusi

Фиг. 15