Устройство циклического приоритета

 

Изобретение относится к вычислительной технике, а именно к устройствам для приоритетного обслуживания запросов, и может быть использовано в многопроцессорных ЭВМ и информационно-вычислительных системах для обслуживания запросов абонентов на магистраль передачи данных и другие разделяемые ресурсы. Цель изобретения - повышение быстродействия устройства за счет параллельного анализа запросов. Устройство циклического приоритета содержит регистр, элемент, НЕ и два узла анализа запросов, каждый из которых имеет две группы элементов НЕ, Два элемента И, (N+2) - групп элементов И (2N - число запросных входов устройства), группу элементов ИЛИ-НЕ, элемент ИШ-НЕ, элемент развязки. Устройство позволяет обслуживать запросы как в циклическом режиме (тогда в каждом цикле устройства в регистр заносится код запроса , поступившего на обслуживание),, так и в приоритетном режиме(информа- .ция в регистре не меняется}. 1 ил., 1 табл. (Л с:

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

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

РЕСПУБЛИК (5g 4 0 06 F 9/46

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4138554/24-24 (22) 20.11.86 (46) 23.07.88. Бюл. М - 27 (71) Институт технической кибернетики АН БССР (72) М.М.Маханек, В.Е.Чернявский и А.Г.Ярусов (53) 681.325(088.8) (56) Авторское свидетельство СССР

11 1198522, кл. G 06 F 9/46, 1984.

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

11 1126960, кл. G 06 F 9/46, 1983. (54) . УСТРОЙСТВО ЦИКЛИЧЕСКОГО ПРИОРИТЕТА (57) Изобретение относится к вычисли. тельной технике, а именно к устройствам для приоритетного обслуживания запросов, и может быть использовано в многопроцессорных ЭВМ и информационно-вычислительных системах для об.80„1411746 А1 служивания запросов абонентов на магистраль передачи данных и другие разделяемые ресурсы. Цель изобретения - повьппение быстродействия устройства за счет параллельного анализа запросов. Устройство циклического приоритета содержит регистр, элемент

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

14)1746

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

Цель изобретения †повышен быстродействия, устройства за счет парал" лельного анализа запросов.

На чертеже представлена функцио нальная схема предлагаемого устрой- 15 ства, Устройство содержит регистр 1, . элемент НЕ 2, узлы 3 и 4 анализа запросов первую группу элементов НЕ 5, вторую группу элементов НЕ 6, (N+2)-ю 20 группу иэ М элементов И,7, первый и второй 9 элементы И, (N-1) групп по (N-i) элементов И 10 в i-й группе, N-ю группу из (N-1) элементов И 11, (0+1)-ю группу из N элементов И 1.2, 25

, элемент ИЛИ-НЕ 13, группу из (M+1), элементов ИЛИ-НЕ 14, элемент 15 раз(M=log N) ° !

На чертеже обозначены запросные . входы 16 устройства, адресные входы 30 ! (17 узлов анализа запросов, адресныи выход 18 устройства, информационный выход 19 устройства, первый 20, второй 21 и третий 22 информационные вы ходы узлов анализа запросов.

Устройство обеспечивает режим циклического обслуживания источников за просов и режим приоритетного обслужи(,вания.

Для обоих режимов значение текуще- 40 го кода приоритета, поступающего по адресным входам 17 в узлы 3 и 4 анализа запросов с выходов регистра 1, определяет порядок распределения приоритетов по запросным входам, Если 45 величина кода текущего приоритета равна А 6 1 0,2N-1 3 то номера запросных входов в порядке убывания их приоритетов (приоритетный ряд) располагаются следующим образом, А+1,А+2,...,2N.

1,2,...,А.

Если А=О, то приоритетный ряд имеет вид 1,2,...,2N если А=З, приоритетный ряд имеет вид 4,5,6...,,2N, 1,2,3.

В результате срабатывания устрой-, ства разрешение будет дано запросному входу, имеющему высший приорйтет среди входов, выставивших сигналы запросов. При этом на информационном выходе 19 появляется логический нуль (свидетельствующий о наличии на входах устройства по меньшей мере одного запроса), а на адресном выходе 18 устройства будет выработано двоичное число, соответствующее номеру входа, получившего разрешение на обслуживание. При этом входам с номерами 1 (2N-i) на выходе 18 устройства соответствуют числа 1 — (2Н-1), а входу с номером 2N - число О.

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

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

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

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

В каждом узле анализа запросов имеются три схемы выбора. Первая состоит из элементов И 10, группы элементов И 7 и элемента И 8. Вторая и третья схемы выбора состоят из элементов И 12 и 11 соответственно.

При 0 А < N устройство работает следующим образом.

Так как А <Н, то (М+1)-й разряд адресного входа 17 узла 3 анализа запросов равен единице, а узла 4 анализа запросов — нулю. Эти сигналы соответственно поступают на входы всех элементов И первых схем выбора узлов 3 и 4. В результате первая схема выбора узла 4 закрыта, а срабатывание первой схемы узла анализа 3 разрешено. Кроме того, заданное значение (М+1)- го разряда закрывает тре"

1411746 тью схему выбора узла 4 анализа и вторую схему выбора узла 3 анализа, Первая схема выбора узла 3 выделяет запрос с наименьшим номером k из диапазона А < k N, вторая схема

5 выбора узла 4 — из диапазона N < k <

<2И, а третья схема выбора узла 3— из диапазона 1 «k < А.

Если существует значение К из диапазона А

Если же значение k в диапазоне

A(К < N отсутствует, то первая схема выбора узла 3 закрыта.

Предположим, что значение k принадлежит диапазону N < k <2И. В этом случае на выходе элемента И 9 узла

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

40 анализа запросов. Этот единичный сигнал приводит к появлению на адресном выходе 18 устройства кода, соответствующего запросу с номером k.

В случае, когда значение Е не принадлежит диапазону А < k < 2N, на выходе элемента И 9 узла 4 будет логическая единица, и третья схема выбора узла 3 становится единственной схемой выбора, готовой к работе. При появлении запроса с номером 1 <К <А на выходе k-го элемента И 11 узла 3 появляется единичный сигнал, который приводит к появлению кода k на адресном выходе 18 устройства.

В случае:, когда на входах устройства отсутствуют запросы, на информационном выходе 19 устройства будет единичный сигнал.

В случае Г! < А < 2N первая схема выбора узла 4 анализа запросов осуществляет выбор запроса в диапазоне А <

Связи между элементами в устройстве при N=8 приведены в таблице.

Пример. Иэ регистра 1 поступает код А=0010, а запросы поступили на первый и десятый входы.

Так как A < N, то разрешение на работу будет у первой и третьей схем выбора узла 3 анализа и второй схемы выбора узла 4. Однако, так как запрос с номером k в диапазоне A=2 < k <

< 8=N отсутствует, то ни один из элементов первой схемы выбора не срабатывает. А так как запрос поступил на вход с номером N < k=10 < 2N, то на выходе элемента И 9 узла 4 будет логический нуль, который закрывает третью схему выбора узла 3 анализа запросов, Таким образом, единичный сигнал будет только на выходе десятого элемента И второй схемы выбора узла 4 анализа, Этот сигнал в соответствии с проложенными связями поступает на выходы первого и третьего элементов

ИЛИ-НЕ 13 группы, что приводит к появлению кода 1010 =10 на адресном выходе 18 устройства, Формула изобретения

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

И и (!!+2)-ю группу из М элементов И, 14117

5 элемент ИЛИ-НЕ, группу из (М+!)-ro элемента ИЛИ-НЕ, элемент развязки, причем k-й запросный вход (k=1 N) первого узла анализа запросов явля5 ется k-м, à k-й запросный вход второго узла анализа запросов является (N+k)-м запросным входом устройства, k-й запросный вход каждого узла ана( лиза запросов подключен к входу k-го 10 элемента НЕ первой группы, j-й за(I просный вход (j=l И-2) узла ана1, лиза запросов подключен к (М+1+1)-му (1=1...;,7) входу 1-го элемента И ($-1+1)-й группы (1=var при j=const) »5 . выход $-го элемента ЙЕ первой группы подключен к (М+1+1)-му входу (1+1)-го и всех последующих элементов И (j(-1+I )-й группы (1=var прп j=const), .вылов IN-I I-го элемента НЕ первой ур группы подключен к (N+M — i+! )-му вхо, ду (N-i)-ro элемента И и i-й группы, l N-й запросный вход устройства подклю,чен к (М+11-i+2)-му входу (N-i)-го элемента И i-й группы и (М+2)-му вхо- 25 . ду первого элемента И, а (N-1)-й запросный вход — к третьим входам всех ! элементов И (И+2)-й группы, (М+1)-й ,выход регистра текущего приоритета подключен к входу элемента HE и к ЗО ,(M+1)-му адресному входу второго уз1 ,ла анализа запросов, выход элемента

НЕ соединен с (М+1)-м адресным вхо дом первого узла анализа запросов, (m-й (m=1,...,N) выход регистра текущего приоритета соединен с m-ми адресными входами первого и второго уз. лов анализа запросов, группы m-x u (М+1)-х адресных входов всех узлов анализа запросов соединены соответ- 40 ственно с входами.m-го и (М+1)-ro элементов НЕ второй группы, m-й адресный вход узла анализа запросов подключен к m-м входам всех элементов И (2 Р„;2 +1),...,(2 Р,„) х групп с но- 45 мерами, меньшими N, (Р =1,...,N2 ) и к m-му входу первого элемента И, выход m-го элемента НЕ второй группы

Подключен к m-м входам всех элементов И (2 Р -2 +1),...,(2 Р -2 )-х групп, выход m-ro элемента НЕ второй группы подключен к второму входу ш-ro элемента И (0+2)-й группы, (М+

+1)-й адресный вход узла анализа запросов соединен с (М+1)-ми вхоцами элемента И i-й группы (i=1 N-l), первого элемента И, с первыми входами элементов И (N+2)-й группы и с первыми входами всех элементов И N-й

46 6 группы, вторые входы всех элементов

И N-й группы подключены к первому информационному входу узла анализа за" просов, а третьи входы всех элементов И N-й группы — к второму информационному входу другого узла анализа запросов, i-й запросный вход- узла анализа запросов подключен к (3+i)-му входу i-ro элемента И N-й группы, выход g-ro элемента НЕ первой группы подключен к (3+))-му входу (,7+1,..., (N-1)-ro элементов И N-й группы, выход (M+1)-го элемента НЕ второй группы соединен с первыми„ а первого информационного входа узла анализа запросов — с вторыми входами всех элементов И (И+1)-й группы, k-й запросный вход узла анализа запросов подключен к (2+k)-му входу k-го элемента И (!1+1) — и группы, выход i-ro элемента НЕ второй группы подключен к (2+i)-му входу (7+1)„...,N-ro, элементов И (N+1)-й группы, выход (N-Б+1)-гс (H !i+1,,N) элемента И i-й группы подключен к (2 k+4((Б-i)-k2 -2 +

+1)-му входу i-й группы Входов m-го элемента ИЛИ-НЕ группы (1 = ((Б i)2

ГО, Х (07

lCX j= Х Х 0 ) ), если в представ/ лении числа (Б-i) в виде (Б-i)=1+

+2 d1+2" d2+ ° ..+2 йм з выход (11-i)-го элемента И i-й группы подключен к i-му входу (N-1)-й груп" пы входов m-ro элемента ИЛИ-НЕ, выход первого элемента И подключен соответственно к N-му входу (N-1)-й группы входов m-го элемента ИЛИ-НЕ,выходы (N-i)-х элементов И И-й и (И+1)-й групп подключены соответственно к (2 .1+ д fi-12 -2 +1) )-м1у входу N-й и к (1+2 1+ с! (i-12 -2 +1) )-му входу (N+1)-й групп (где 1=)i 2 3 входов m-го элемента ИЛИ-НЕ группы, если в представлении числа i в виде

i=1+2 d. +2"й +. ° .+2 d.> значение й,„=

=1, выход N-ro элемента И (И+1)-й группы подключен к первому входу (11+1)-й группы входов m-го элемента

ИЛИ-НЕ, выход g-ro (g=l,...,N-i) элемента И i-й группы соединен с g-м входом -й группы входов (М+1)-го элемента ИЛИ-НЕ группы, выход первого элемента И соединен с N-м входом (N-1)-й группы входов, а выход m-ro элемента И (N+2)-й группы соединен с

m-м входом N-й группы входов (М+1)-го элемента ИЛИ-НЕ группы, ВыхОД котО7 14117 рого является первым информационным выходом узла анализа запросов, во втором узле анализа запросов выход (N-i}-ro элемента И i-й группы под5 ключен к i-му входу элемента ИЛИ-НЕ этого узла, выход первого элемента

И второго узла подключен к N-му входу элемента ИЛИ-НЕ, выход N-го элемента И (N+1)-й группы подключен к (N+1)-му входу элемента ИЛИ-НЕ, в первом узле анализа запросов выход

h-ro (h=1... .,N-J-1) элемента И в -й группе (h=var, J= const подключен. к h-му входу )-й группы входов эле- 35 мента ИЛИ-НЕ, выход m-ro элемента И (N+2)-й группы подключен к m-му входу (N-1.)-й группы входов элемента ИЛИНЕ, выходы i-x элементов И N-й и (N+1)-й групп подключены к 1-му входу zp соответственно N-й и (И+1)-й групп входов элемента ИЛИ-НЕ, в каждом узле анализа запросов выход k-го элемента

НЕ первой группы подключен к k-му входу второго элемента И, выход ко- 25 торого соединен с входом элемента раз»

46 . 8 вязки и является вторым информационным выходом узла анализа запросов, выход элемента развязки является третьим информационным выходом узла анализа запросов, первые информационные выходы узлов анализа запросов соединены между собой через "монтажное И" и подключены к первым информационным входам обоих узлов анализа запросов, третьи информационные выходы узлов анализа запросов соединены между собой через монтажное И и является информационным выходом устройства, выходы элементов ИЛИ-НЕ узлов анализа соединены между собой через "монтажное И", подключены к (И+1}-му информационному входу регистра текущего приоритета и являются (М+1)-м разрядом адресного выхода устройства, выходы

m-x элементов ИЛИ-НЕ групп обоих узлов анализа соединены между собой через "монтажное И", подключены к

m-му информационному входу регистра текущего приоритета и являются m-м разрядом адресного выхода устройства.

141 174б

1 " второй зап росный номер злемента s группе вход подклю чен к входу с номе" ром ром

8 н н н н 1 3

О 4

О 5

О 6 н н н. н н н

О н

О 8

О 7 О 8

О 7 О 8

О 9

110

О1) 0 9,010

1 Н

) 5 н.О 5 н

О 6

3 H

0 5 н

О 5

О 6

8 Н н

5 Н

О 7

0 В

6 Н н 6 н н н

Я е

0 5 О 6

4 Н

0 6

О 7 1 8 Я

0 5

О 1 . О 8, 0 5 О б н н пе рвый зал» росный вход подключен к входу с номером

1 1 5 н

2 0 5 1 6

3 О 5 0 б

О 5 О 6

5 0 5 О 6

6 0 5 О 6

0у О 6

1 " третий запросный вход подклю" чен к входу с номе" ром

1 - чет" ° вертый запросный вход подключен к входу с номером

1 - ия" тый зап" росный вход подклю" чен к . входу с номе

1 - mecтой запросный вход подключен к входу с номе" ром

1 - седь" мой запросный вход

rroдключен к . входу с номе" ром.

14 1746

1 - четвертый адрес ный вхо,i подключен к входу с номе" ром

I - первый

I — третий адресный вход подклю чен к! - второй адресный вход подключен к

1 " первый и информа" циониый вход подклю» чен к входу с номе".

" вто. рой информа" ционный вход подкаю" . чен к входу с номером

I - восьмой 9ап» росный вход подклю» чеи к адресный вход подключен к входу с иомевходу с номером входу с номевходу с номером ром ром ром

I2.

1О

02 н

02 н н

I 4

О 8. н

О. 2

1 4

О 1

1 4 н о о

О 2 о

0 2 н о н

О .2 н о о г,о

3 н

I. 4 н

О 2 н

1 4

0 )

1 о г

О 2

) 4

0 I н

О н н г н н г н о о

1 2 .

1 4 н

2 4 н

I)0

О I О 2

2 4 О 1 О 2 о о г

i 4 О ) О 2.1 4 . О 1 I 2 н Н .н н ог н з. н н н о з н о з н о з н о 3 н о 3 н о э н о э н з н

1 3 н

3 н

) 3 н з н

0 3 Н о з н о з . н о з н о з н

1 3 н

1411746

2, Н Н

Н. 0 5 I. 6

Н О 5 0 6 о и

° е1

H Ф

3 Н Н

4 Н Н

Н 0 S 0 6 О н Н

О 5

l 6

И Н - Н Н О 5

0 б

Н Н Н

Н Н Н н Н Н

Н Н

И Н н Н

1 1 4 . Н

2 0 4 1 5

3 0 4 . 0 5

Н Н

Н н Н! 6 Н Н 1

4 0 4 0 5 " О 6 1 7 И

О 6 0 7 1 8 Н

S 0 4 0 5

О 6 О 7 0 8

Ъ

О. Ь О 7 О 8

Н Н Н

6 0 4 О 5

7 О 4 0 5

1 Э

О 3

Н,Н Й

3 0 3 О 4

4 0 3 О 4

1 б Н

О 5

0 5 0 6 3 7

5 О 3

6 0 3

О 5

О 4

О 6 О 7 3 8

7 0.3 0 4 о О 5 О 6 0 7

О 8

8 0 3 0 4

О 6 О 7

0 5

П р и м е ч а н и е: Символ Н еооэиачает отеутствие еввви

О " пер-. вый НЕ5 первой группы подключен к элемен" ту е вкодом номер

0 - второй НЕ5 первой гррппы подключен к элемент5т с входом номер

О - третий НЕ5

aepsoO г щ ппы подклвиен к элемеитр с вводом номер

О - четвертый

НЕ5 пер вой rpynm» подкличек к элемеит Г с вкодом номер

О - аатый НЕ5 первой грязны

Йо дкл30" чен к элеме» ту е вкодом иоФжр

0 - аео" той HRS первой гряшм подключен х элемея": т с вкодом номер

1 1

9 10

0 I 1 2 I 3... . И

И 1 .4

Я 1 4

1 9 4

Я 4

H l 4

l 8 I 4

0 1 I 2 3 Н

0 1 1 2 1 3 Н ! I 0 2 0 3 .Н

l 5 0 2 0 Э Н

0 8

1 1 0 2

0 2

1 4

1 I 0 2 .1 1 2

7 I 4 ! 6. I 4

Н 1 1

0 6 Н.Н

1 Э

Н . H

Н ° !

1 Э

H I 1

Н 1 1

Н . I 1

Н I I

l. 3

l 2

Я

1 2 l 3

Ф

1 3

I Н

Н I 2

Н .Н

Н 1 2

110

Н Н

Н 0 1 Н И

Н 1 2

Н 1 2. H

Н И

Н Н

Н . 0 1

Н 0 1

Н I 2 И

Н . 1 2 И

Н I 2 Н

И l. 2 Я

Н . 0 1 Н -Н

0 1

Н 0 1

Н 0 1

Н 2 н I 2

° H

0 9

IL0 0 1 денного входе(вааоде янвертора) с эленеятом.

0 "седьмой НЕ5 первой группы подключен к элечен . .ту с

ВХОДОМ

НОВАР

0 - soch». ной ИЕ5 первой группы подклв" чен к элемен-, ту с

ВХОДОН номер с

0 - выход четвертого

НЕ6. второй груааы подклв чен к входу

С НОМЕ«

И Н

Н Н

Н ° Н

Н Н

Н Н

Н- Н

Н Н

Н Н

0- выход 0-выход первого второго

ИЕ6 вто- НЕ6 второй груп- рвй пы аод группы ключе я подклюк входу чея к с номе+ вкоду

РОМ С HOHEPoll

1".. " Х55родолкение тЩущщ

0 3 Н

1 Э И

l 3 Н

0 3 . Н

Н 1 2

Н 1 2

Н 1 2

0 - выход третье.го НЕ6. второй группы аодклв» чен к входу с яонеРОМ

1411746

Составитель И.Сорочан .Редактор П.Гереши Техред И. Ходанич

Корректор Л.Патай

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

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

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

Заказ 3655/44

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