Приоритетное устройство

 

Изобретение относится к цифровой вычислительной технике и может быть использовано в. вычислительных системах , имеющих несколько активных источников информации, подключенных к общему ресурсу. Целью изобретения является расширение области применения путем организации любого числа запросных входов при упрощении устройства . Устройство приоритета содержит блок 1 формирования разрешений, блок 2 анализа запросов, блок 3 памяти, запросные входы 4, выходы 5, входы 6 блока 2 анализа запросов, управляющие входы 7 блока 1, тактовый вход 8. Новое выполнение блока формирования . разрешений в виде треугольной матрицы и упрощение конструкции узла приоритета , позволяет организовать произвольное число запросных входов и упростить конструкцию устройства. 10 ил. 1 табл. с S (Л со о N о to СП

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

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

РЕСПУБЛИК

„„Яи„„1З04025 А (51)4 С 06 F 9/46

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

Н А BTOPCKOMV СВИДЕТЕЛЬСТВУ с

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3961095/24-24 (22) 04.10.85 (46) 15.04.87. Бюл. № 14 (71) Институт технической кибернетики

АН БССР (72) Г.А. Буткин, N.М. Иаханек, В.Е. Чернявский и А.Г. Ярусов (53) 681.325(088.8) (56) Авторское свидетельство СССР № 955068, кл. С 06 F 9/46, 1980.

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

¹ 1027727,,кл. С 06 F 9/46, 1982. (54) ПРИОРИТЕТНОЕ УСТРОЙСТВО (57) Изобретение относится к цифровой вычислительной технике и может быть использовано в. вычислительных системах, имеющих несколько активных источников информации, подключенных к общему ресурсу. Целью изобретения является расширение области применения путем органиэации любого числа запросных входов при упрощении устройства. Устройство приоритета содержит блок 1 формирования разрешений, блок

2 анализа запросов, блок 3 памяти, запросные входы 4, выходы 5, входы 6 блока 2 анализа запросов, управляющие входы 7 блока 1, тактовый вход 8 ° Новое выполнение блока формирования . разрешений в виде треугольной матрицы и упрощение конструкции узла приоритета, позволяет организовать произвольное число запросных входов и упростить конструкцию устройства. 10ил.

1 табл.

1 130402

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

Цель изобретения — расширение области применения путем организации любого числа запросных входов при упрощении устройства. 10

На фиг. 1 приведена функциональная схема устройства; на фиг. 2 — схема блока формирования резрешений; на фиг. 3 — схема логического узла; на фиг.4-10 — мнемонические схемы, пояс- 15 няющие принцип работы устройства.

Устройство содержит блок 1 формирования разрешений, блок 2 анализа запросов, блок 3 памяти, запросные входы 4 устройства, выходы 5 разрешений устройства, выходы 6 блока 2 анализа запросов, управляющие входы 7 блока 1 формирования разрешений и тактовый вход 8 устройства.

Блок 1 формирования разрешений содержит треугольную матрицу 9 из

N(N-1),. узлов 10 приоритета с первым

11, вторым 12, третьим 13 входами и первым 14 и вторым 15 выходами.

У Вход Вход Вход Выход Выход и/п 11 12 13 14 15

0 0 х 0

0 1 х 0

1 0 х 1

1 1 0 0

1 1 1 1

Блок 1 формирования разрешений осуществляет разрешение конфликтов

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

При отсутствии запросных. сигналов ("0" на всех входах 4) на всех выходах 5 разрешений также формируются сигналы "0", свидетельствующие об отсутствии,разрешений.

При наличии сигнала "1" только на

30 одном из запросных входов 4 . этот

t сигнал проходит через все встречающиеся на его пути логические блоки

10 и поступает в виде сигнала 1" на соответствующий выход разрешений

5; независимо от значения кода на управляющих входах 7.

Если на входы 4 устройства одновременно поданы несколько сигналов

"1", то эти сигналы, встречаясь в

40 узлах 10 треугольной матрицы 9, подвергаются отбору в соответствии со значением кода на управляющих входах

7. На выходы 5 проходит только один единичный сигнал.

45 Значение кода на управляющих входах 7 устанавливается в соответствии с требуемой приоритетиой дисциплиной обслуживания.

Допустим требуется обеспечить сле50 дующую дисциплину обслуживания запросных входов 4 -4 пятивходового прио5 ритетного устройства:

Узел 10 приоритета содержит элемент И 16, первый 17, второй 17, и

1 третий 17 элементы запрета.

На мнемонических схемах (фиг.4-10) узловые точки обозначают логические блоки 10. Стрелка на первом 11 или втором 12 входе блока 10 показывает приоритет этого входа по отношению к входу, не имеющему стрелки. Управляющие (третьи) входы 13 блоков 10 на мнемосхемах не показаны. Утолщенными линиями изображены траектории прохождения запросных сигналов, поступивших с входов 4 через логические блоки 10 на выходы 5 устройства.

Узел приоритета 10 реализует функцию двувходового арбитра по отношению к сигналам, поступающим на его входы

11 и 12. При отсутствии конфликтов между входными сигналами (комбинации

"00", "01", "10"), они передаются на соответствующие выходы 14 и 15 независимо от сигнала на управляющем входе 13. При наличии конфликтной ситуации на входе (комбинация "11") узел 10 приоритета отдает приоритет тому или иному сигналу в зависимости от сигнала на управляющем входе 13.

5 2

Работа узла 10 приоритета описывается таблицей истинности.

Таблица истинности узла 10 приоритета

4 — + 4 — о 4 — 4 — 4

3, 2

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

Для обеспечения указанной дисциплины обслуживания код на управляющем

3 13040 входе 7 блока 1 формирования разрешений должен управлять узлами приоритета 10 следующим образом:

4 — 4 4 — 4 ° 4 — 4 4 4

Э$ g 4 $ g 2$ 5 ($ 5

4 — 4 ° 4 4 4 — 4

З 4$ З 2$ Э

4 42; 4. 4$1

42

1О

N(N 1) входов 7 равно С „ = и равно числу разрядов управляющего кода,то возможное число вариантов настройки

С равно 2 ", которое за исключением ранее рассмотренных И! жестких режимов, определяется гибким распределением приоритетов между запросами, Гибкие режимы характеризуются тем, 40 что приоритет между запросными сигналами определяется не только управляющим кодом, подаваемым на управляющие входы 7 блока 1, но и зависит от числа поступивших запросов и их распре- 45 деления по запросным входам 4 °

Если в ранее рассмотренном примере изменить значение только одного (восьмого) бита в управляющем коде, а именно бита, определяющего взаимоот- 50 ношение между входами 4, и 4, то условие 45 42 изменится на противоположное: . 4, - 4э .

B bToM случае управляющий код при-55 мет вид: 1111101011 и при наличии всех сигналов запроса на входах 4, — 45дисциплина приоритетного обслуживания будет следующая: 4 4 4 4, Реализация этих условий задается значением сигнала ("0" или "1"), поданного на соответствующие узлам 10 приоритета управляющие входы 7. Например, для заданной дисциплины обf5 служивания значение кода на десяти управляющих входах 7 и на соответствующих третьих входах узлов приори. тета 10„, 102,, 10, 10,, 10 щее 1111101111 (фиг. 4).

Аналогичным образом можно задавать любую приоритетную дисциплину обслуживания входов 4. Причем количество таких дисциплин равно числу перестановок номеров входов: Р„ = И!$ где

N — - число запросных входов. Однако число N! еще не охватывает все возможные режимы работы устройства.

Так как количество управляющих

25 4

4, так как сигнал по входу 42, который мог бы победить сигнал 4 в

5 узле 10 приоритета, будет побежден сигналами по входам 4, и 4, соответствен о в узлах 1022 и 10, приоритета.

Очевидно, что при отсутствии запросных сигналов на входах 4 и 4 приоЭ 4 . ритетная дисциплина обслуживания примет вид: 4 - 4 . 4, (фиг. 5).

Если в управляющий код внести еще изменения во 2-м, 4-м, 7-м и 10-м разрядах, то он примет вид 1010100010 (приоритет прохождения сигналов через узлы приоритета 10 при таком управляющем коде показаны стрелками на мнемосхеме фиг. 6).

Из фиг. 6 следует, что при наличии запросных сигналов на всех входах

4,-4 дисциплина приоритетного обслуживания сохраняется заданной: 4 4 з — + 4 — 4 — 4

4 2 $

При отсутствии запросного сигнала только на входе 4, дисциплина приоритетного обслуживания принимает вид:

4, 4 4 + 44, (фиг. 7) .

При отсутствии запросного сигнала только на входе 4, дисциплина приоритетного обслуживания имеет другой вид:

4 — 4, — 4, — -4 (фиг. 8), Если запросные сигналы отсутствуют одновременно на входах 4, и 4э,то дисциплина приоритетного обслуживания принимает новый вид: 4; 4 — $4 (фиг, 9).

Таким образом, при управляющем коде 1111101111, определяющем жесткую дисциплину приоритетного обслуживания, заданная дисциплина обслуживания

4, 4, 4, 4 4, сохраняется вне зависимости от числа и распределения сигналов запроса по входам

4, — 4 (фиг. 4). При управляющем коде 1010100010, определяющем гибкую дисциплину приоритетного обслуживания, заданная дисциплина приоритетного обслуживания 4 — 4 — . 4 — 4 — 4

Э 4 2 4 будет при наличии сигналов запроса на всех входах (фиг. 6). Если отсутствует один или несколько запросных сигналов на определенных входах 4, то дисциплины приоритетного обслуживания становятся другими (фиг. 7 — 9).

Таким образом, блок 1 разрешений предложенной структуры при N = 5 запросных входах можно настроить на одну из 2 s = 1024 дисциплин приоритетного обслуживания, причем имеется

51=120 дисциплин жесткого и 2 — 5!

5 13040 — 904 дисциплины гибкого задания при,оритетов.

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

Если при выбранной приоритетной дисциплине обслуживание всех поступающих на входы 4 запросов происходит н 20 приемлемые времена (ни один из запросов не находится в состоянии ожидания обслуживания больше установленного для него прогоного времени ожидания), то на выходах блока 2 анализа эапро- 25 сов имеются нулевые сигналы и заданный на входах 7 управляющий код не изменяется.

Если какие-либо запросы долгое время не обслуживаются, то на соответст- 30 вующих выходах 6 блока 2 анализа запросов появляются единичные сигналы, свидетельствующие о необходимости перестройки дисциплины приоритетного обслуживания в напранлении повышения вероятности обслуживания этих запросов. Перестройка дисциплины обслуживания осуществляется изменением кода на управляющих входах 7 блока 1 формирования разрешений. Значения управ- yg ляющего кода, соответствующие определеннымсдисциплинам обслуживания, находятся в ячейках блока 3 памяти.Адрес ячеек формируется за счет появления единиц на выходах 6 блока 2 анализа запросов, соответствующих необслуживаемым запросным входам.

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

4 4 4 4 — 4 и управэ я 2 1 ляющем коде 1010100010 (фиг. 6) вход

4 долгое время не обслуживается.

Тогда на первом выходе выходов 6 блока 2 анализа запросов появляется сигнал "1". На входах блока 3 памяти

25 6 формируется код 10000 по которому находится управляющих код, соответствующий, например, дисциплине приоритетного обслуживания нида: 4 - 4z

4 4, 4 1ля данной дисциплины приоритетного обслуживания управляющий код может, например, иметь вид 0000010000 (фиг. 10) .

После обслуживания входа 4), на первом выходе выходов 6 блока 2 анализа запросов устанавливается сигнал "0" и по адресу 00000 из блока 3 памяти на входы 7 блока. 1 разрешений снова поступает управляющий код 1010100010.

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

Приоритетное устройствб, содержа" щее блок формирования разрешений, блок анализа запросов и блок памяти, а блок анализа запросов содержит группу из N счетчиков и группу из N элементов ИЛИ (N — число запросных входов устройства), причем группа информационных входов блока формирования резрешений является группой запросных входов устройства и соединена с входами сброса соответствующих счетчиков группы блока анализа запросов,группа выходов старших разрядов которых соединена с первыми входами соответст" вующих элементов ИЛИ группы блока анализа запросов и группой адресных входов блока памяти„ группа информационньгх выходов которого соединена с группой входов изменения приоритета блока формирования разрешений, группа выходов которого является группой выходов разрешения обслуживания устройства, тактовый вход устройства соединен с вторыми входами элементов

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

7 1304025 8 (д = Г,Я)соединен с первым входом соединен с первым входом первого элепервого элемента запрета и первым вхо- мента запрета и первым входом элемендом элемента И (i-1)-ra узла приори- та И узла приоритета (i-1)-й строки тета первого столбца матрицы, первый. (j+1)-го столбца (при 1 c i), выход информационный вход блока формирова- 5 третьего элемента запрета узла приония разрешений соединен с.первыми ритета (i-1)-й строки j""го столбца входами второго и третьего элемектов соединен с вторым входом второго и запрета первого узла приоритета пер- третьего элементбв запрета узла привога столбца матрицы, вторые входы оритета i-й строки j-го столбца (нри элементов И и второго элемента запре- 10 j + i, i p N), выход третьего элемента каждого узла приоритета матрицы та запрета узла приоритета (N-1)-й соединены с соответствующими входом строки 1-го .столбца соединен с j-u изменения приоритета группы блока входом блока формирования разрешений, формирования разрешений, выход эле- выход первого элемента запрета узла мента И каждого узла приоритета блока 15 приоритета (i-1)-й строки j-го столбб формирования разрешений соединен с ца (прн i-1=j; i g И) соединен с втовторым входом третьего элемента запре- рыми входами второго и третьего элета этого же узла приоритета, выход ментов запрета узла приоритета i-6 второго элемента запрет а каждого уз- строки (j+1)-ro столбца, выход первола приоритета блока формирования раз- 20 то элемента запрета узла приоритета решений соединен с вторым входом пер- (N-1)-й строки (N-.1)-ro столбца соевого элемента запрета узла приоритета динен с N-м выходом блока формирова (-1)-й строки j --ro столбца (j=l,N-1) ния разрешений.

ФУЙ 2

1304025

4, Sg 5у 5» 5s

48 Фг 4» 4841

Упрадляющцй oo:

11 l 170.7 7 77 Риг.4

5, 5г 5у 5» 5 у "Ь 4

Мпробляюш,ий код

7 11 7107011

Фиг.5

1304025

Quz. У

5 5 5у 5а 5s

4 у Ф,, 4 "4

9прабяяющий юР:

101О1 О ОО 1 а

Voz.8

5, 5г 5у 5. 5, 2 41

Упрабляющий над:

1010 1 0 0 046

Vuz.8

5у 5g 5у 5 Юу 4

Уаробляющцй нод:

101 01000 10

5 5 5у 5

4 "4 Ь

Упрабляющий над

10 70 7 000 10

1304025 2 ф

Ю 5у 5 5j 1 Ь 44 Ь

Улрабляющий юУ: о оооо оооо

Фиг. 70

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

Техред М.Ходанич

ХорректоР Е. Рошко

Редактор Л.Пчелинская

Заказ 1312/49 . Тираж 673

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

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

Подписное

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