Устройство циклического приоритета Советский патент 1988 года по МПК G06F9/50 

j

о:,

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

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

На чертеже представлена функциональная схема предлагаемого устройства.

Устройство содержит регистр 1, элемент НЕ 2, узлы 3 и 4 анализа запросов, первую группу элементов НЕ 5, вторую группу элементов НЕ 6, (К+2-)-ю группу из М элементов И,7, первый и второй 9 элементы И, (N-l) групп по (N-i) элементов И 10 в i-й группе, N-ю группу из tU-l) элементов И 11, (N+l)-ro группу из N.элементов И- 1.2, элемент ИЛИ-НЕ 13, группу из (М+1) элементов ИЛИ-НЕ 14, элемент 15 развязки, (M logjN).

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

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

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

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

1 1 ,,-.

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

0

5

5

0

с

Q. 5 0

0

5

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

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

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

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

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

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

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

тью схему выбора узла 4 анализа и вторую схему выбора узла 3 анализа.

Первая схема выбора узла 3 выделяет запрос с rfiaHMeHbraHM номером k из диапазона А k N, вторая схема выбора узла 4 - из диапазона N - k 2N, а третья схема выбора узла 3 - из диапазона 1 k А,

Если существует значение k из диапазона А k , то на выходе по меньшей мере одного элемента И первой схемы выбора появляется единичный сигнал. Этот сигнал поступает на вход элемента ИЛИ-НЕ 14, что приводит к появлению нулевого сигнала на информационном выходе 20 узла 3 анализа. Этот нулевой сигнал поступает на входы всех элементов И второй и третьей схем сравнения обоих узлов, закрывая их. Таким образом, на входы элементов ИЛИ-НЕ 14 обоих узлов поступает единственный единичный сигнал с выхода элемента И только с первой схемы выбора узла 3 анализа. Согласно описанным связям это приводит к появлению кода k на адресном выходе 18 устройства.

Если же значение k в диапазоне отсутствует, то первая схема выбора узла 3 закрыта.

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

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

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

1746

В случае N Л 2N первая схема выбора узла 4 анализа запросов осуществляет выбор запроса в диапазоне А . Если же запрос из такого диапазона отсутствует, то вторая схема выбора узла 3 осуществляет поиск в диапазоне 1 k N. Если же запроса нет и в этом диапазоне, то третья

Q схема выбора узла 4 осуществляет поиск запроса-в диапазоне N+1 k А.

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

П р и м е р. Из регистра посту пает код , а запросы поступили на первый и десятый входы. J, Так как А N, то разрешение на работу будет у первой и третьей схем выбора узла 3 анализа и второй схемы

Q выбора узла 4. Однако, так как запрос с номером k в диапазоне k отсутствует, то ни один из элементов первой схемы выбора не срабатывает. А так как запрос поступил на

5 вход с номером N ; 2N, то на

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

Q Таким образом, единичный сигнал будет только на выходе десятого элемента И второй схемы выбора Узла 4 анализа. Этот сигнал в соответствии с проложенными связями постзшает на выходы первого и третьего элементов PUHi-HE 13 группы, что приводит к появлению кода 10102 10, на адресном выходе 18 устройства.

0

5

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

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

: элемент ИЛИ-НЕ, группу из (М-И )-го элемента ИЛИ-НЕ, элемент развязки, причем k-й -запросный вход (,..,N) первого узла анализа запросов является К-м, а k-й запросный вход второго узла анализа запросов является ; (N+k)-M запросным входом устройства, j k-й запросный вход каждого узла ана- 1 лиза запросов подключен к входу k-ro I элемента НЕ первой группы, j-й за- просный вход (,...,N-2) узла ана- I лиза запросов подключен к (М+И-1)-му (..;5J) входу 1-го элемента И 1 (-1+1)-й группы (, при j.const,) , { выход j-ro элемента НЕ первой группы I подключен к (М+1+1)-му входу (l+l)-ro и всех последующих элементов И (j- f-l+1 )-и группы ( i const) , .выход (И-1)го элемента ,НЕ первой группы подключен к (N+M-i+l)-My вхо- Iду (N-i)-ro элемента И и i-й группы, N-й запросный вход устройства подключен к (M+N-i+2)-My входу (K-i)-ro

группы,

вторые входы всех-элементов И N-й группы подключены к первому информационному входу узла анализа запросов, а третьи входы всех элементов И N-й группы - к второму информационному входу другого узла анализа запросов, i-й запросный вход узла анализа запросов подключен к (3+1)-му

10 входу i-ro элемента И N-й группы, выход j-ro элемента НЕ первой группы подключен к (3+j)-My входу (j+1,..., (N-l)-ro элементов И N-й группы, выход (М+1)-го элемента НЕ второй груп15 пы соединен с первыми, а первого информационного входа узла анализа запросов - с вторыми входами всех элементов И (Н+1)-й группы, k-й запросный вход узла анализа запросов под20 ключен к (2+k)-My входу k-ro элемента И {М+1)-й группы, выход i-ro элемента НЕ второй группы подключен к (,2+1)-му входу (J + I),,.. ,N-ro, элементов И (N+l)-й группы, выход (N-S+O-rc

элемента И 1-й группы и (М+2)-му вхо- 25 (,..,N) элемента И i-й группы

.. - л.™, Т1 /-лт 1 .. ..«-, - / П 1,1.л г/г . О I

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

30

подключен к- ( 2 k+cr(S-i) + + 1)-му входу i-й группы входов т-го элемента ИЛИ-НЕ группы (k (S-i), лг.т Г О, X

cfLXJ |j, J.-7/OJ представлении числа (S-i) в виде (S-i,) I-i- i-2°di+2 d2+.. . + значение , выход (N-i)-ro элемента И i-й группы подключен к i-му входу (К-1)-й групю-й (,...,N) выход регистра теку- „р. пы входов т-го элемента ИЛИ-НЕ, выход щего приоритета соединен с т-ми ад- первого элемента И подключен соот- ресными входами первого и второго уз- .ветственно к N-му входу (И-1)-й груп лов анализа запросов, группы га-х и пы входов т-го элемента ИЛИ-НЕ,выхо;(М+1)-х адресных входов всех узлов .ды (N-i)-x элементов И N-й и (Ш+1)-й

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

40

(),...,( )-х групп мерами, меньшими N, ( ,... ,N2 ) и к ш-му входу первого элемента И, выход ш-го элемента НЕ второй группы подключен к т-м входам всех элемен- тов и () ,.. . ,( групп, выход т-го элемента НЕ второй группы подключен к второму входу т-го элемента И (К+2)-й группы, (М+ +1)-й адресный вход узла анализа запросов соединен с (М+1)-ми входами элемента И i-й группы (,,.,,N-1), первого элемента И, с первыми входами элементов И (N+2)-й группы-и с первыми входами всех элементов И N-й

групп подключены соответственно к (2 - -l+Dr i-12 -2 +n)-My входу N-й и к (l+2 - -l+ i-12 -2 V)-My входу (Ш+1)-й групп (где ) .входов т-го элемента ИЛИЧЖ группы, ес45 ли в представлении числа i в виде

i i+2 d +2 d +. ..+2 dM значение d 1, выход N-ro элемента И (Ш+1)-й группы подключен к первому входу (N+l)-й группы входов т-го элемента

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

55 (К-1)-й группы входов, а выход т-го элемента И (К+2)-й группы соединен с т-м входом N-й группы входов (М+1)-го элемента ИЛИ-НЕ группы, выход кото11746

группы,

вторые входы всех-элементов И N-й группы подключены к первому информационному входу узла анализа запросов, а третьи входы всех элементов И N-й группы - к второму информационному входу другого узла анализа запросов, i-й запросный вход узла анализа запросов подключен к (3+1)-му

10 входу i-ro элемента И N-й группы, выход j-ro элемента НЕ первой группы подключен к (3+j)-My входу (j+1,..., (N-l)-ro элементов И N-й группы, выход (М+1)-го элемента НЕ второй груп15 пы соединен с первыми, а первого информационного входа узла анализа запросов - с вторыми входами всех элементов И (Н+1)-й группы, k-й запросный вход узла анализа запросов под20 ключен к (2+k)-My входу k-ro элемента И {М+1)-й группы, выход i-ro элемента НЕ второй группы подключен к (,2+1)-му входу (J + I),,.. ,N-ro, элементов И (N+l)-й группы, выход (N-S+O-rc

(,..,N) элемента И i-й группы

.. ..«-, - / П 1,1.л г/г . О I

подключен к- ( 2 k+cr(S-i) + + 1)-му входу i-й группы входов т-го элемента ИЛИ-НЕ группы (k (S-i), лг.т Г О, X

cfLXJ |j, J.-7/OJ представлении числа (S-i) в виде (S-i,) I-i- i-2°di+2 d2+.. . + значение , выход (N-i)-ro элемента И i-й группы подключен к i-му входу (К-1)-й груп

групп подключены соответственно к (2 - -l+Dr i-12 -2 +n)-My входу N-й к (l+2 - -l+ i-12 -2 V)-My входу (Ш+1)-й групп (где ) .входов т-го элемента ИЛИЧЖ группы, еси в представлении числа i в виде

i i+2 d +2 d +. ..+2 dM значение d 1, выход N-ro элемента И (Ш+1)-й группы подключен к первому входу (N+l)-й группы входов т-го элемента

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

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

рого является первым информационным выходом узла анализа запросов, во втором узле анализа запросов выход (N-i)-ro элемента И i-й группы подключен к i-му входу элемента ШШ-НЕ этого узла, выход первого элемента И второго узла подключен к N-му входу элемента ИЛИ-НЕ, выход N-ro элемента И (N+l)-ft группы подключен к (N+l)-My входу элемента ИЛИ-НЕ, в первом узле анализа запросов выход h-ro (,...,N-J-1) элемента И в j-й группе (h,var,v J,const3 подключен к h-му входу j-й группы входов элемента ИЛИ-НЕ, выход т-го элемента И (К+2)-й группы подключен к т-му входу (N-l)-ft группы входов элемента ИЛИ- НЕ, выходы i-x элементов И N-й и (Н+)-й групп подключены к i-му входу соответственно N-й и (Н+1)-й групп входов элемента ИЛИ-НЕ, в каждой узле анализа запросов выход k-ro элемента НЕ первой группы подключен к k-му входу второго элемента И, выход ко-, торого соединен с входом элемента раз117468

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

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

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

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

{Даявого .(в1аода ииввртора) с лш«е1ггом;

«

11

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

/и

/7

1

ff

JL

В

щ

о

7/

К

1Z

22

5

2Г

гг