Ассоциативное запоминающее устройство

,885.90. Бюл, Р 17ский политехнический0-летия ВеликоР ОктябическоР революцииКорнеРчук, А.Р. Маркнчук и О.В.Яблунонск327(088,8)рское с ствокл, С 5/00,н Т. Ас нЪФтройир )рис.З рь ской с в скийий ниде тельС 1социа тив Р с 198,.апоми 1982,ые з ства, И(53) 681,1,56) Авто 1 я 1324070 Кохоне накцие ус с, 169, 04) АСС 011 АТИВ)ОЕ ЗАРЖф 11 ДЯ)ЕЕ УСТАЛО СТВО57) Изобретение относится к вычислительной технике, в частности к запоминак 1 пим устройствам, и может быть ис - полъзонано н вычислительных системах повьппенного быстродействия. Цель изобретения - повысить быстродействие устрйства при поиске по критеию н заданных границах . Устройтно содержит накопитель 1, регистр 4 результатов поиска, блок 5 анализа многократных совпадений, вийратор 7, селектор 8 адреса, депиФратор 9 ад1562956 реса, регистры 10 и 11 верхней и нижней границ поиска соответственно,мультиплексор 15, элементы НЕРАВНОЗНАЧНОСТЬ 24, элементы ИЛИ 25 и блок Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в вычислительных системах повышенного быстродействия.Цель изобретения - повышение быстродействия устройства при поиске по критерию "в заданных границах".На фиг, 1 представлена структурная схема ассоциативного запоминающего устройства; на Фиг. 2 - Функцио О нальная схема одного из возможных вариантов выполнения узла анализа.Устройство содержит (Фиг.1) на-. ,копитель 1 информационные входы которого являются инФормационными вхо дами 2 устройстба, а информационные выходы - инФормационными выходами 3 устройства, регистр 4 результатов поиска, блок 5 анализа многократных совпадений; управляющий выход кото-. рого является выходом 6 "Конец выдачи чисел" устройства, шифратор 7, селектор. 8 адреса, дешиФратор 9 адреса, два регистра 1 О и 11 верхней и нижней границ соответственно.Устройство также содержит блок 12 управления, в состав которого входят узел 13 анализа, триггер 14. Устройства содержит мультиплексор 1 5. Блок 12 также содержит триггеры 16 и 40 17, элементы И 18-21, элементы НЕ 22 и 23. Устройство также содержит и,элементов НЕРАВНОЗНАЧНОСТЬ 24, иэлементов ИЛИ 25 (и - разрядность накопителя), вход 26 разрешения запи си. Узел 1 3 имеет первый 27 и второй 28 информационные входы, стробирующий вход 29, вход 30 запуска. На фиг.1 обозначен тактовый вход 31 устройства. Выход 32 соединен с одним из входов триггера 14. На фиг. 1 показаны установочный вход 33 устройства, вход 34 "Конец поиска" устройства, вход 35 разрешения поиска накопителя , 1 выходы 36 и 36, узла 13, тактовый55 вход 37 устройства, выходы 38 узла 13, входы 39 маски накопителя 1, выходы 40 мультиплексора 15, признаковые входы 41 накопителя 1, вход 42 12 управления. В состав блока 12 входят узел 3 анализа, триггеры14, 16 и 17, элементы И 18-21элементы НЕ 22 и 23. 2 ил. разрешения записи накопителя 1, вход 43 "Запись" и вход 44 "Чтение устройства, вход 45 разрешения поиска накопителя 1, адресные входы 46 накопителя.Узел 13 анализа содержит первую группу элементов И 47, первую группу элементов ИЛИ 48, первую 49 и вторую 50 группы буферных элементов, вторую группу элементов ИЛИ 51, вторую группу элементов И 52, группу элементов И-НЕ 53, третью группу элементов И 54, группу триггеров 55, третью группу элементов ИЛИ 56, группу элементов НЕ 57. Устройство работает следующим образом.В зависимости от сигналов, поступающих на соответствующие управляющие входы, устройство может находиться в трех режимах: запись по адресу, поиск в указанном интервале, чтение.При поступлении единичного сигнала на,вход 43 "Запись" устройства селектор 8 адреса, управляемый этим сигналом, подключает на дешифратор 9 адресные входы 46 устройства. С дешиф-, ратора 9 адрес поступает на входы выборки накопителя 1. Одновременно с этим указанный единичный сигнал с входа 43 накопителя 1 поступает в ячейку накопителя 1, адрес которой указан на адресных входах, производится запись информации с информационных входов 2 устройства.Сущность операции поиска заключается в следующем.Анализируются попарно все разряды верхней и нижней границ интервала поиска, имеющие одинаковый вес, начиная с и-х разрядов до выявления первой комбинации 10 (здесь и дальше первая цифра соответствует 1-му разряду верхней .границы интервала поиска, вторая циФра соответствует 1-му разряду нижней границы интервала поиска (11, п),Пусть такая комбинация встретилась в 1-х разрядах, тогда осуществляется анализ (1-1)-хразрядов, При этом возможны четыреварианта.Первый вариант. В (1-1)-х разрядахверхней и нижней границы находится5единица. В этом случае производитсяопрос накопителя 1, причем признак,опроса формируется следующим образом:ВГ В 1 р е ВГ ОхххОгде ВГ; - соответствующий разряд верхней границы интервала поиска,Второй вариант. В (1-1)-х разрядахверхней и нижней границы интервала,поиска находится комбинация 00, вэтом случае также производится опроснакопителя 1, но признак опроса определяется следующим образом:20НГ НГ , НГ 1 ххх,где НГ. - соответствующий разряд нижней границы интервала поиска.Третий вариант. В указанных разрядах находится комбинация 10, в этомслучае опрос накопителя 1 производится за два такта, причем в первомтакте признак опроса Формируется, каки в первом варианте во втором такте 30так же, как и во втором варианте,Маска Формируется для всех трехслучаев одинаково:(оооь-(е-е( е-е35Четвертый вариант. В (1-1)-х разрядах и нижней границы интервала поиска записана комбинация 01 . В этом случае опрос накопителя 1 не производится.Аналогичным образом анализируются все последующие пары разрядов верхней и нижней границ интервала поиска с (1-2)-го до первого. Причем в каждом 45 такте опроса в регистре 4 результатов поиска устанавливаются в единицу те разряды, которые соответствуют ячейкам накопителя 1, в которых значения незамаскированных разрядов совпадают с заданными разрядами признака опроса,Дпя этого предварительно в регистрах верхней 1 0 и нижней 11 границ Фиксируется верхняя и нижняя граница интервала поиска. Единичным сигналом, поступающим на вход 31 устройства, сбрасываются в нуль разряды регистра 4 результатов поиска, а также инициируется начало работы узла 1 3 анализа. Узел 13 анализа работает следую - щим образом.В момент, когдг в устройстве пе производится поиск, на входе 31 узла 13 анализа присутствуют нулевой потенциал и все триггеры 55 установлены в нуль, элементы И 47 и элементы ИЛИ 51 производят попарный анализ разрядов регистров 1 0 и 11, начиная с и-го по первый до выявления в -х разрядах кодовои комбинации 1 О. Тог -да элементы ИЛИ 51о - 51; устанавливаются в нуль, а элементы ИЛИ 51;, -51 - в единицу. Единичный потенциал, поступающий на вход 30 узла 13 анализа, проходит через элементы И 54 и элементы ИЛИ 56 последовательно до элемента И 54;, . Если на информационных входах 27;, и 28;, узла 13 анализа соответственно находит - ся комбинация 01, то элемент И-РЕ 53;, устанавливается в единицу и пропускает единичный потенциал на вход элемента И 54; , где производится аналогичный анализ. Во всех других случаях на В-вход триггера 55 поступает единичный потенциал и до момента установки этого триггера в единицу на выходе соответствующего элемента ИЛ 1 56. присутствует нуль,1-тчто обеспечивает задержку продвижения единичного импульса поиска на один такт. По отрицательному перепаду стробирующего импульса триггер 55 установится в единицу, а следовательно, установится в единицу и выход 38 блока 13 анализа, Этот единичный по - тенциал поступает на разрешающие входы буферных элементов 49;, и 50а соответственно на управляющих выходах 36 блока 13 анализа появляется инФормация, записанная в (-1)-х разрядах регистров 1 О и 11 .Таким образом, узел 13 анализа производит анализ разрядов регистров 1 О и 11 и по заднему фронту тактирующего импульса устанавливается в единицу тот информационный выход 38 узла 13 анализа, который соответствует номеру старшей пары разрядов регистров 10 и 11, для которой требуется опрос накопителя 1. Одновременно с этим сбрасывается в нуль триггер 14, единичный сигнал с инверсного выхода ко(торого поступает на вход 34 Конец поиска" устройства, а также на первый вход элемента И 9, разрешая подачу тактирующих импульсов с тактирующеговхода 37 устройства на вход 35 накопителя 1, а также на управляющий вход регистра 4 результатов поиска, В это же время на выходах 36 узла 13 ана 5 лиза появляется значение указанных разрядов. Дальнейшие действия зависят от комбинации в этих разрядах .Комбинация 11,В этом случае единичный сигнал с10выхода 36 инвертируется элементомНЕ 23 и поступает через элемент. И 21на 0-вход триггера 16, запрещая егопереключение, а следовательно, и переключение триггера 17, Единичный сиг нал с выхода 36 проходит через элемент И 20 на управляющий вход мультиплексора 15 и на выходы 40 мультиплек-сора 1 5 поступает информация с выходарегистра 10, которая через элементы 20НЕРАВНОЗНАЧНОСТЬ 24 проходит.на входы 41 накопителя 1, причем инвертируется тот разряд, которому на выходах 38 узла 13 анализа соответствуетединица.Комбинация 00,В этом случае на управляющий входмультиплексора 15 поступает нулевойсигнал. мультиплексор 15 пропускаетна выходы информацию записанную в регистре 11, Признак опроса формируется аналогичным образом.Комбинация 10,В первом такте на управляющий вход мультиплексора 15 поступает единичный сигнал и на входах 41 накопителя 1 Формируется признак опроса такта, как и при комбинации 11,. В этом же такте устанавливается единичный сигнал на выходе элемента И 21, а соответственно и на 0-входе триггера 16, который переключается в единицу по нулевому уровню тактирующего сигнала и низкий потенциал с его инверсного 45 выхода, поступая на вход элемента И 18, запрещает подачу тактирующих импульсов на стробирующий вход 29 узла 1 3 анализа, работа которой приостанавливается на один такт. А поскольку единичный сигнал с прямого выхода триггера 16 запрета поступает на 0-вход триггера 17 запрета, то по заднему фронту тактирующего импульса установится указанный триггер 1 755 в единицу. И по нулевому сигналу с его инверсного выхода обеспечится подача на управляющий вход мультиплексора 1.5 низкого потенциала, а соответственно, и на входах 41 накопителя 1 во втором такте сформируется признак опроса аналогично, как и при комбинации 00. А также указанным сигналом с инверсного выхода триггера 17 установится низкий потенциал на Р-входе триггера 16, который при нулевом уровне тактирующего сигнала сбросися в нуль, обеспечивая таким образом во втором такте прохождение тактирующих импульсов на стробирующий вхоц 29 узла 13 анализа.В следующем после подачи.импульса поиска такте производится опрос накопителя 1причем маска формируется на выходах элементов ИЛИ 25 указанным способом. Одновременно с этим узел 13 анализа производит выбор очередной пары разрядов, требующих опроса, и по заднему Фронту тактирующего импульса на его выходах осуществляется смена инФормации. Дальше процесс повторяется.По окончании операции поиска на выход 32 узла 13 анализа поступает единичный сигнал, по которому триггер 14 устанавливается в единицу, а соот-ветственно па выходе 34 Конец поиска устройства появляется нулевой потенциал, запрещая подачу тактирующих импульсов на вход 35 накопителя 1.Ио единичному сигналу на входе 44 "Чтение" устройства шифратор 7 Формирует адрес первой по счету ответившей ячейки, этот адрес через селектор 8 адреса и дешиФратор 9 адреса поступает на входы накопителя 1, на информационных выходах 3 которого появляется информация, записанная в этой ячейке. Аналогичным образом считываются все ячейки, которым в рс гистре 4 результатов поиска соответст ет единица Если считаны все ячейки, то на выход 6 устройства поступает единица .Вход 33 устройства испол зуется только при включении устройства, для установки триггера 14 в единицу.Формула изобретенияАссоциативное запоминающее устройство, содержащее накопитель, регистр результатов поиска, блок анализа многократных совпадений, шифратор, селектор адреса, дешифратор адреса и блок управления, причем выходы результатов поиска накопителя подклю9 156 чены к соответствующим информацион- ным входам регистра результатов поиска, выходы которого соединены с соответствующими информационными входами блока анализа многократных совпадений, инФормационные выходы кото.рого соединены с соответствующими входами шифратора, выходы шифратора подключены к первой группе информационных входов селектора адреса, информационные входы второй группы которого являются адресными входами устройства, выходы селектора адреса подключены к соответствующим входам дешифратора адреса, выходы которого подключены к соответствующим входам выборки накопителя, вход разрешения записи накопителя и управляющий вход селектора адреса объединены и являются входом "Запись" устройства, вход разрешения чтения, накопителя и управляющий вход блока анализа многократных совпадений объединены и являются входом "Чтение" устройства, выход "Конец выдачи чисел" блока анализа многократных совпадений является одноименным выходом устройства, информационные входы и выходы накопителяявляются соответственно одноименными входами и выходами устройства, вход установки в О" регистра результатов поиска и вход Начало поиска" блока управления объединены и являются входом "Начало поиска устройства, тактовый и установочный входы блока управления являются соответственно одноименными входами устройства, первый выход блока управления подключен к входу разрешения поиска накопителя и входу разрешения приема регистра результатов поиска, второй выход блока управления является выходом 2956 1 ОКонец поискаустройства, о т л и -ч а ю щ е е с я тем, что, с цельюповышения быстродействия устройствапри поиске по критерию, " в заданных 511границах , в него введены элементыНЕРАВНОЗНАЧНОСТЬ, элементы ИЛИ и мультиплексор, причем первый информационный вход мультиплексора и вход Верхняя граница поиска блока управленияобъеДинены и являются входом Верхняяграница поиска устройства, второйинформационный вход мультиплексора ивход "Нижняя граница поиска блокауправления объединены и являются входом Нижняя граница поиска" устройства, третий выход блока управлениясоединен с управляющим входом мультиплексора, с первого по (п)-й выхо ды мультиплексора подключены к первым входам соответствующих элементовНЕРАВ 11 ОЗНАЧНОСТЬ (где и - разрядностьнакопителя), и-й выход мультиплексорасоединен с п-признаковым входом нако пителя, с первого по (и)-й признаковые входы накопителя подключены квыходам элементов НЕРАВНОЗНАЧНОСТЬ,вторые входы которых соединены с группой выходов блока управления, с вто- ЗО рого по (и)-й выходы группы блокауправления подключены к первым входам соответствующих элементов ИЛИ,с второго по (и)-й входы маски накопителя соединены с выходами элемен" 35тов ИЛИ, выход (и)-го элемента ИЛИсоединен с п-м входом маски накопителя, второй вход первого элементаИЛИ и первый вход маски накопителяподключены к первому выходу группы 40 блока управления, второй вход каждого элемента 1 Г 1, кроме первого, подкюпочен к выходу предыдущего элемента ИЛИ.Составитель В, РудакоЛ. Зайцева Техред Л, Сердокова Корректор Т,Пали Реда Подписи краж ч аказ Об митета п оизводственно-издательский комбинат фПатент", г, Ужгород, ул, Гагарина И Государственног 113035изобретениям и открьггиям при ГКНТ ССС5, Раушская наб., д. 4/5