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

 

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в вычислительных системах повышенного быстродействия. Цель изобретения - повысить быстродействие устройства при поиске по критерию "в заданных границах". Устройство содержит накопитель 1, регистр 4 результатов поиска, блок 5 анализа многократных совпадений, шифратор 7, селектор 8 адреса, дешифратор 9 адреса, регистры 10 и 11 верхней и нижней границ поиска соответственно, мультиплексор 15, элементы НЕРАВНОЗНАЧНОСТЬ 24, элементы ИЛИ 25 и блок 12 управления. В состав блока 12 входят узел 13 анализа, триггеры 14, 16 и 17, элементы И 18 - 21, элементы НЕ 22 и 23. 2 ил.

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

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

РЕСПУБЛИН

„„Я0„„1562956 (5l ) 5 G l1 С . 5/00

3ИКВ

ЫПЛ 1 -

Б1-1БЛИ

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

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

Г0СУДМ СТВЕННЫй Н0МИТЕт

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ П(НТ СССР (21) 4467178/24-24 (22) 29.07.88 (46) 07.05.90. Вюл. Р 17 (71) Киевский политехнический институт им. 50-летия Великой Октябрьскои социалистической революции (72) В.И. Корнейчук, А .Р. Марковский, K À.Маслянчук и 10.В.яблуновский (53) 681.327(088,8) (56) Авторское свидетельство СССР

11- !324070, кл, С 11 С 15/00, 1985.

Кохонен Т. Ассоциативные запомиЪЮ

1 982 накщие устройства.— N..: :ир, 98 с. 169, рис.3.9.

2 (б4) АССО! !!!АТИВ1!ОЕ ЗА 10!" 1!ВА!0!!!ВЕ УСТ10!» СТВ0 (5! ) Изобретение относится к вычисли†тельной технике, B частности к запоминак1щим устройствам, и может быть ис— пользовано в вычислительных системах повышенного быстродействия. Пель изобретения — повысить быстродействие устройства при поиске по критерию в заданных границах . Устройство содержит накопитель l регистр

4 результатов поиска, блок 5 анализа многократных совпадений, шиФратор 7, селектор 8 адреса, дешиФратор 9 ад1562956 реса, регистры 10 и 11 верхней и нижней границ поиска соответственно, мультиплексор 15, элементы НЕРАВНОЗНАЧНОСТЬ 24, элементы ИЛИ 25 и блок

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

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

На фиг. 1 представлена структурная схема ассоциативного запоминающего устройства; на Фиг. 2 — Функцио- 20 нальная схема одного из возможных вариантов выполнения узла анализа.

Устройство содержит (Фиг.1) на-. ,копитель 1, информационные входы которого являются инФормационными вхо- 25 дами 2 устройства, а информационные выходы — информационными выходами 3 устройства, регистр 4 результатов поиска, блок 5 анализа многократных совпадений; управляющий выход которого является выходом 6 "Конец выдачи чисел" устройства, шифратор 7, селектор. 8 адреса, дешифратор 9 адреса, два регистра 10 и 11 верхней и нижней границ соответственно.

Устройство также содержит блок

12 управления, в состав которого вхо- . дят узел 13 анализа, триггер 14. Устройства содержит мультиплексор l 5.

Блок 12 также содержит триггеры 16 и 40

17, элементы И 18-21, элементы НЕ 22 и 23. Устройство также содержит и-1 элементов НЕРАВНОЗНАЧНОСТЬ 24 элементов ИЛИ 25 (n — разрядность накопителя), вход 26 разрешения запи- 45 си. Узел 1 3 имеет первый 27 и второй

28 информационные входы, стробирующий вход 29, вход 30 запуска. На

Фиг.1 обозначен тактовый вход 31 устройства. Выход 32 соединен с одним из входов триггера 14. На Фиг. 1 показаны установочный вход 33 устройства, вход 34 "Конец поиска" устройства, вход 35 разрешения поиска накопителя . 1 выходы 36 и 36. узла 13, тактовый

9 л л э

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-му разряду верхней границы интервала поиска, вторая цифра соответствует i-му разряду нижней границы интервала поиска (i 1, n).пусть такая комбинация встретилась в 1-х разрядах, тогда ссуществляется анализ (1-1)-х

1562956 разрядов. При этом возможны четыре варианта.

Первый вариант. В (1-1)-х разрядах верхней и нижней границы находится

5 единица. В этом случае производится опрос накопителя 1, причем признак ,опроса формируется следующим образом:

ВГ BI 0 е ...ВГе OXX...X9 !

О где ВГ. — соответствующий разряд верх1 ней границы интервала поиска, Второй вариант. В (1-1)-х разрядах верхней и нижней границы интервала ,поиска находится комбинация 00, в этом случае также производится опрос накопителя 1, но признак опроса определяется следующим образом:

НГ НГ ...НГ Iхх...х, где НГ. — соответствующий разряд нижi ней границы интервала поиска.

Третий вариант. В указанных разря- 25 дах находится комбинация 10, в этом случае onрос накonителя 1 производится за два такта, причем в первом такте признак опроса Формируется, как и в первом варианте во втором такте 30 так же, как и во втором варианте.

Маска формируется для всех трех случаев одинаково:

ii... oî...о ь-<е-ее

Четвертый вариант. В (1-1)-х разрядах и нижней границы интервала поиска записана комбинация Ol В этом случае опрос накопителя 1 не производится.

Аналогичным образом анализируются все последующие пары разрядов верхней и нижней границ интервала поиска с (1-2)-го до первого. Причем в каждом такте опроса в регистре 4 результатов поиска устанавливаются в единицу те разряды, которые соответствуют ячейкам накопителя l в которых значения незамаскированных разрядов совпадают с заданными разрядами признака опроса.

Для этого предварительно в регистрах верхней 1 0 и нижней 11 границ Фиксируется верхняя и нижняя граница интервала поиска. Единичным сигналом, поступающим на вход 31 устройства, сбра сываются в нуль разряды регистра 4 результатов поиска, а также инициируется начало работы узла 1 3 анализа.

Узел 13 анализа работает следующим образом.

В момент, когдг в устройстве не производится поиск, на входе 31 у.l ла 13 анализа присутствуют нулевой потенциал и все триггеры 55 установлены в нуль, элементы И 47 и элементы

ИЛИ 51 производят попарный анализ разрядов регистров 10 и 11, начиная с и-ro по первый до выявления в i-x разрядах кодовои комбинации 1 О. Tor— да элементы ИЛИ 51 „ — 51; устанавливаются в нуль, а элементы ИЛИ 51;,— 51 — в единицу. Единичный потенциал, поступающий на вход 30 узла 13 анализа, проходит через элементы

И 54 и элементы ИЛИ 56 последовательно до элемента И 54;, . Если на информационных входах 27;, и 28;, уз— ла 13 анализа соответственно находит— ся комбинация 01, то элемент И-НЕ

53;, устанавливается в единицу и пропускает единичный потенциал на вход элемента И 54; <, где производится аналогичный анализ. Во всех других случаях на D-вход триггера

55 поступает единичный потенциал и до момента установки этого триггера

B единицу на выходе соответствукщего элемента ИЛИ 56. присутствует нуль, 1-1 что обеспечивает задержку продвижения единичного импульса поиска на один такт. По отрицательному перепаду стробирующего импульса триггер 55 установится в единицу, а следовательно, установится в единицу и выход 38 блока 13 анализа. Этот единичный по— тенциал поступает на разрешающие входы буферных элементов 49;, и

50,, а соответственно на управляющих выходах 36 блока 13 анализа появляется информация, записанная в (i-1)-х разрядах регистров 0 и 11 .

Таким образом, узел !3 анализа производит анализ разрядов регистров l 0 и 11 и по заднему фронту тактирующего импульса устанавливается в единицу тот информационный выход 38 узла 13! анализа, который соответствует номеру старшей пары разрядов регистров

10 и 11, для которой требуется опрос накопителя !. Одновременно с этим сбрасывается в нуль триггер 14, единичный сигнал с инверсного выхода коiторого поступает на вход 34 Конец поиска" устройства, а также на первый вход элемента И 19, разрешая подачу тактирующих импульсов с тактнрующегo

1562956 входа 37 устройства на вход 35 накопителя 1, а также на управляющий вход регистра 4 результатов поиска. В это же время на выходах 36 узла 13 ана5 лиза появляется значение указанных разрядов. Дальнейшие действия зависят от комбинации в этих разрядах .

Комбина ция 1 1 .

В этом случае единичный сигнал с 10 выхода 36> инвертируется элементом

НЕ 23 и поступает через элемент. И 21 на D-вход триггера 16, запрещая его переключение, а следовательно, и переклк чение триггера 17, Единичный сиг-15 нал с выхода 36 проходит через эле1 мент И 20 на управляющий вход мультиплексора 15 и на выходы 40 мультиплексора 15 поступает информация с выходя регистра 10, которая через элементы 20

НЕРАВНОЗНАЧНОСТЬ 24 проходит. на входы 41 накопителя 1, причем инвертируется тот разряд, которому на выходах 38 узла 13 анализа соответствует единица.

Комбинация 00.

В этом случае на управляющий вход мультиплексора 15 поступает нулевой сигнал. мультиплексор 15 пропускает на выходы информацию записанную в ре- 30 гистре 11. Признак опроса формируется аналогичным образом.

Комбинация 10.

В первом такте на управляющий вход Зс мультиплексора 15 поступает единичный сигнал и на входах 41 накопителя

1 формируется признак опроса такта, как и при комбинации 11. В этом же такте устанавливается единичный сигнал на выходе элемента И 21, а соответственно и íà D-входе триггера 16, который переключается в единицу по нулевому уровню тактирующего сигнала и низкий потенциал с его инверсного 45 выхода, поступая на вход элемента

И 18, запрещает подачу тактирующих импульсов на стробирукщий вход 29 узла 1 3 анализа, работа которой приостанавливается на один такт. А поскольку единичный сигнал с прямого выхода триггера 16 запрета поступает на 0-вход триггера 17 запрета, то по заднему фронту тактирующего импульса установится указанный триггер 17

55 в единицу. И по нулевому сигналу с его инверсного выхода обеспечится подача на управляющий вход мультиплексора 15 низкого потенциала, а соответственно, и на входах 41 накопителя 1 во втором такте сформируется признак опроса аналогично, как и при комбинации 00. А также указанным сигналом с инверсного выхода триггера

17 установится низкий потенциал на

D-входе триггера 16, котор Ф при нулевом уровне тактирующего сигнала сброси ся в нуль, обеспечивая таким образом во втором такте прохождение тактирующих импульсов на стробирующий вхоц 29 узла 13 анализа.

В следующем после подачи. импульса поиска такте производится опрос накопителя 1 причем маска формируется на выходах элементов ИЛИ 25 указанным способом. Одновременно с этим узел

I3 анализа производит выбор очередной пары разрядов, требующих опроса, и по заднему Фронту тактирующего импульса на его выходах осуществляется смена инФормации. Дальше процесс повторяется.

По окончании операции поиска на выход 32 узла 13 анализа поступает единичный сигнал, по которому триггер

14 устанавливается в единицу, я соот- ветственно па выходе 34 Конец поиска устройства появляется нулевой потенциал, запрещая подачу тактирующих импульсов на вход 35 накопителя 1.

Но единичному сигналу на входе 44

"Чтение" устройства шифратор 7 Формирует адрес первой по счету ответившей ячейки, этот адрес через селектор 8 адреса и дешифратор 9 адреса поступает на входы накопителя 1, на информапионных выходах 3 которого появляется информация, записанная в этой ячейке. Аналогичным образом считываются все ячейки, которым в рс гнстре

4 результатов поиска соответст ет единица „Если считаны все ячейки, то на выход 6 устройства поступает единица .

Вход 33 устройства исполу зуется только при включении устройства, для установки триггера 14 в единицу.

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

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

9 256 чены к .соответствующим информационным входам регистра результатов поиска, выходы которого соединены с соответствующими информационными входами блока анализа многократных совпадений, инФормационные вьгходы кото.рого соединены с соответствующими входами шифратора, выходы шифратора подключены к первой группе информационных входов селектора адреса, информационные входы второй группы которого являются адресными входами устройства, выходы селектора адреса подключены к соответствующим входам дешифратора адреса, выходы которого подключены к соответствующим входам выборки накопителя, вход разрешения записи накопителя и управляющий вход селектора адреса объединены и являются входом "Запись" устройства, вход разрешения чтения, накопителя и управляющий вход блока анализа многократных совпадений объединены и являются входом "Чтение" устройства, выход

Конец выдачи чисел1 блока анализа многократных совпадений является одноименным выходом устройства, информационные входы и выходы накопителя являются соответственно одноименными входами и выходами устройства, вход установки в О" регистра результатов поиска и вход Начало поиска" блока управления объединены и являются входом "Начало поиска устройства, тактовый и установочный входы блока управления являются соответственно одноименными входами устройства, первый выход блока управления подключен к входу разрешения поиска накопителя и входу разрешения приема регистра результатов поиска, второй выход блока управления является выходом

2956 10

Конец поиска устройства, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства при поиске по критерию, " в заданных

II границах, в него введены элементы

НЕРАВНОЗНАЧНОСТЬ, элементы ИЛИ и мультиплексор, причем первый информационный вход мультиплексора и вход Верхняя граница поиска блока управления объеДинены и являются входом Верхняя граница поиска устройства, второй информационный вход мультиплексора и вход "Нижняя граница поиска блока управления объединены и являются входом Нижняя граница поиска" устройства, третий вьгход блока управления соединен с управляющим входом мультиплексора, с первого по (п-1)-й выходы мультиплексора подключены к первым входам соответствукщих элементов

НЕРАВНОЗНАЧНОСТЬ (где n — разрядность накопителя), и-й выход мультиплексора соединен с п-признаковым входом нако25 пителя, с первого по (n-I)-v признаковые входы накопителя подключены к выходам элементов НЕРАВНОЗНАЧНОСТЬ, вторые входы которых соединены с группой выходов блока управления, с второго по (n-1)-й выходы группы блока управления подключены к первым входам соответствующих элементов ИЛИ, с второго по (n-1)-й входы маски накопителя соединены с вьгходвми элемен35 тов ИЛИ, выход (и-2) -го элемента ИЛИ соединен с п — м входом маски накопителя, второй вход первого элемента

ИЛИ и первый вход маски накопителя подключены к первому выходу группы

4О блока управления, второй вход каждого элемента 2Г"i кроме первого, подкгпочен к выходу предыдущего элеменTB ИЛИ.! 562956

Составитель В, Рудаков

Техред Л, Серд окова Корректор T.Палий

Редактор Л. Зайцева

Подписное

Тираж 484

Заказ 1067

ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 10I