Устройство для выбора по приоритету

 

УСТРОЙСТВО ДЛЯ ВЫБОРА ПО ПРИОРИТЕТУ, содержащее И групп по и блоков опроса, где Y -число источиНИКОВ запросов, Vl блоков анализа,и группу элементов ИЛИ, причем каждый информационный выход i -го блока опроса -и группы, где i 1,2, ..., И-1, соединен с информационным входом 1-го разряда i -го блока опроса ( i +1)-й . грухшы, информационный выход каждоххэ i -го разряда каждого блока опроса VI -и группы подключен к соотъет ствующему входу л -го элемента ИЛИ, i -и информахшокный вход каждого опроса i -и группы соединен с первым управляющим входом этого блока опроса и с соответствующим входом i -го блока анализа, выход которого подключен к вторым управл5пошим входам блока опроса i-й группы, третьи управляющие входы всех блоков опроса соединены с тактовым входом устройства, каждый блок опроса содержит элемент ИЛИ, элемент 2 И-ИЛИ и и -разрядный регистр, информационные входы которого соединены с информационными входами блока опроса, вход управления приемом числа в регистр соединен с выходом элемента 2 И-ИЛИ, первый, второй, третий и четвертый входы которого подключены соответственно к первому, третьему и второму управляющим входам блока опроса , выходы регистра подключены к соответствующим информационным выходам блока опроса и к входам элемента ИЛИ, выход которого соединен с управляющим выходом блока опроса (для блоков опроса V -и группы), каждый блок анализа содержит элемент И И группу элементов НЕ, входы которых подключены к соответствующим входам блока анализа, выходы элементов НЕ соединены с соответствующими входами элемента И, выход которого подключен к выходу блока анализа, отличающееся тем, что, с целью расширения области применения , оно содержит группу из п счетчиков, группу из У триггеров и У регистров номера источника запроса, причем нулевой вход казкдого триггера соединен с соответствующим входом запроса устройства, единственный вход каждого триггера соединен с управляющим выходом одноименного блока опроса У)-и группы, нулевой выход каждого триггера соединен с инф« мационным входом пер&ого разряда соответствуюшего блока опроса первой грутшы, счетный вход каждого счетчика соединен Ь соответствующим запросным входом устройства, выходы каждого с : счетчика соединены с информационными входами соответствующего блока опроса первой группы, выходы каждого регистра номера источника запроса соединены с информационными входами соответствующего блока опроса первой группы.

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

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

РЕСПУБЛИН

1024921 A (19) (11) 3(51) 6 06 9/46

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

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, Н АВТ0РСНОМУ СВИДЕТЕЛЬСТВУ (2 1) 333 1347/18-24 (22) 3 1.08.81 (46) 23,06.83. Бюл, № 23 (72) B. И. Горбенко, В. Ф. Зелтиньш, Л. П. Лобанов и Г. С. Тимофеев (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР № 568946, кл. G06 F 9/46, 1975 ..

2. Авторское свидетельство СССР № 92 0702, кл, G 06K 7/04, 1980 (прототип). (54),(57) УСТРОЙСТВО ДЛЯ ВЫБОРА

ПО ПРИОРИТЕТУ, содержащее И групп

По )) блоков опроса, гдв VI -число источников запросов, И блоков анализа и груп, пу элементов ИЛИ, причем каждый ийформационный выход j -ro áëoêa опроса

1 -й группы, гдв 1 1,2, .-, И-1, соединен с информационным входом 1-го разряда (-го блока опроса (a +1)-й группы, информационный выход каждого

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

1024921

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

Эта задача решается программным. путем.

В частности, в многопроцессорном вычиолительном комплексе Эльбрус" реализуется программным способом эффективный алгоритм выделения максимального (минимального) числа из группы чисел.

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

Известно также устройство для выбора по приоритету, содержащее элементы ИЛИ, триггеры, блок сравнения и регистры 1).

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

-го блока опроса 1-й группы., где 1=12,..., ; =1 2, ..., ф, соединен с информационным входом 1-го разряда 1 -го блока опроса (1 +1)-й

Группыр & информационный Выход каж 35 дого .1 -го блока опроса j -й группы

1 подключен. к ) «му входу 1»го элемента ИЛИ, rhe 1=1,2»..., К вход -го разряда каждого j -го блока опроса j-й группы соединен с первым 40 управляющим входом j -го блока опроса 1-й группы и с ) -ым входом 1 го блока анализа, выход которого подключен к вторым входам управления блоков опроса -й группы, третьи входы управ45. ления всех блоков опроса соединены с шиной управления устройством 2) °

Недостатком такого устройства является узкая область применения. gg

Белью изобретения является расши.- . рение области применения устройства.

Поставленная цель достигается тем, что в устройство для выбора по приори,» тету, содержащее И групп по N блоков опроса, где и - число источников зап« росов, и блоков анализа и группу элементов ИЛИ, причем каждый информа1 ционный выход 4 -го блока опроса q -й группы, где = 1в2 . ° > Vl -1 соединен с информационным входом < -ro разряда 1 -ro блока опроса (< Ф1)-й группы, информационный выход каждого 4 -го разряда каждого блока опроса

yl -й группы подключен к соответствующему входу 1-ro элемента ИЛИ каждого блока опроса -й группы, соедиI нен с первым управляющим входом этого блока опроса и с соответствующим входом 1 -го блока анализа, выход " % которого подключен к вторым управляющим входам блоков опроса j -й группы,: третьи управляющие входы всех блоков опроса соединены с тактовым входом устройства, :каждый блок опросасодержит элемент ИЛИ, элемент" 2

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

3 1024921 4 ветствующего блока опроса первой груп- торые устанавливают в нулевое состояние пыл ° соответствующий триггер 4 и одновременНа фиг,. 1 представлена структурная но поступают на вход соответствующих схема устройства для выбора по приори» счетчиков 5 и суммируются с их содертету, на. фиг. 2 - структурная схема S жимым, Таким образом, на вход блоков 1

6no«a о оое; на фщ., 3 - структурная и блоков 2 разрядов, в обшем случае, .. схема блока анализа,. поступят различные числа s обратном

Устройство содержит группы ИЛИ коде Каждое число под действием та«- . блоков 1 опроса, блоки 2 анализа, эле- ового .сигнала 8 проходиг через свою менты ИЛИ 3, триггеры 4, счетчики 8,:группу блоков 1 íà соответствующие !

О регистры 6 номера источника запроса,: входы элементов ИЛИ:-3. В результате входы 7 запроса устройства, тактовый с выходов элементов ИЛИ 3 выдав вход 8.устройства, вйходы 9: устройся- .. двоичйый код нОМера того процессора, .ва. Блок 1 содержит регистр 10 эле-.. которому разрешено обратиться в память. . мент 2М-ИЛИ 11 и элемент ИЛИ 12» 5 Этог код равен коду, хранящемуся в реБлок 2 содержит элементы BE 13 и гисгре 6. Если несколько кодов на счей.. элемент И 14. : . чиках:5 равны,. то на abide устройся

Устройство работает следующим об- ва выдается код. номера того пропесразоМ .. - . сора, номер: которого наименьший. Пс оПеред началом работы все блоки уста-20 .лв появления. информапии на выходах эле. йеливаются.в исходное состояние: .ре-.: ментов ИДИ 3 сигнал с управляющего " гистры. блоков 1 опроса и счетчики В в .. выхода -соответствующего блока. 1 устанулевое состояние; триггеры 4-s единич- . навливает соотватствуюший триггер 4 ...ное состояние; в регистрах 6 находится .:.в единичное состояние. код номера. источника запроса. Через ?, Применение -предлагаемот о изобретения входы 7.на устройство поступают импуль-. -позволяет. расширить о(Ьщсть применения сы -запроса от «аждого пропессора, ко-. ус ройргва+

1024921

° °

1024921

Составитель N, Кудряшев

Редактор Н, Рогулич Техред А.Бабинец Корректор В. Гирняк

Заказ 4396/45 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий. 113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4