Ассоциативное запоминающее устройство Советский патент 1990 года по МПК G11C15/00 

1

(21)4467178/24-24

(22)29.07.88

(46) 07.05.90. Бюл. № 17

(71)Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции

(72)В„И. Корнейчук, A.F. Марковский, Е.А.Маслянчук и Ю.В.Яблуновский

(53) 681.327(088,8)

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

№ 1324070, кл. СПС 15/00, 1985.

Кохонен Т. Ассоциативные запоми- нагацие устройства.- М.: Мир, 1982, с. 169, рис.3.9.

(54) АССОЦИАТИВНОЕ ЗАПОМИНАВШЕЕ УСТРОЙСТВО

(57) Изобретение относится к вычисли- телънои технике, в частности к запоминающим устройствам, и может быть использовано в вычислительных системах повышенного быстродействия. Цель изобретения - повысить быстродействие устройства при поиске по критерию заданных границах11. Устройство содержит накопитель I, регистр 4 результатов поиска, блок 5 анализа многократных совпадении, шифратор 7, селектор 8 адреса, дешифратор 9 ад

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

СП

о

О1

GU

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

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

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

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

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

Устройство также содержит блок 12 управления, в состав которого входят узел 13 анализа, триггер 14. Устройство содержит мультиплексор J5. Блок 12 также содержит триггеры 16 и 17, элементы И 18-21, элементы НЕ 22 и 23. Устройство также содержит п-1 Элементов РАВНОЗНАЧНОСТЬ 24, п-2 элементов ИЛИ 25 (п - разрядность накопителя), вход 26 разрешения записи. Узел 13 имеет первый 27 и второй 28 информационные входы, стробирую- щий вход 29, вход 30 запуска. На Фиг.1 обозначен тактовый вход 31 устройства „ Выход 32 соединен с одним из входов триггера 14. На фиг. 1 показаны установочный вход 33 устройства, вход 34 Конец поиска устройства, вход 35 разрешения поиска накопителя 1, выходы 361 и 36г узла 13, тактовый вход 37 устройства, выходы 38 узла 13, входы 39 маски накопителя 1, выходы 40 мультиплексора 15, признаковые входы 41 накопителя 1, вход 42

12 управления. В состав блока 12 входят узел 13 анализа, триггеры 14, 16 и 17, элементы И 18-21, элементы НЕ 22 и 23. 2 ил.

Q

д 0

5

разрешения записи накопителя 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 устройства.

Сущность операции поиска заключается в следующем.

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

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

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

ВГПВГ„ 1 .. .ВГеОхх.. ,х,

где ВГ- - соответствующий разряд верхней границы интервала поиска.

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

НГПНГ п , ..,НГе1хх...х,

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

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

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

iLv-il ЈP i -iS, ме-и 1-г

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

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

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

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

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

Q разрядов регистров 10 и 11, начиная с n-го по первый до выявления в 1-х разрядах кодовой комбинации 10. Тог- да элементы ИЛИ 51 -51 устанавливаются в нуль, а элементы ИЛИ51- Т5 51( в единицу. Единичный потенциал, поступающий на вход 30 узла 13 анализа, проходит через элементы И 54 и элементы ИЛИ 56 последователь5

0

5

0

5

з

0

но до элемента И 54

0

т -1

Если на информационных входах и 28- узла I3 анализа соответственно находится комбинация 01, то элемент И-HF 53( устанавливается в единицу и пропускает единичный потенциал на вход элемента И 54J2, где производится аналогичный анализ. Во всех других случаях на D-вход триггера поступает единичный потенциал и до момента установки этого триггера в единицу на выходе соответствующего элемента ИЛИ 56. присутствует нуль, что обеспечивает задержку продвижения единичного импульса поиска на один такт. По отрицательному перепаду стробирующего импульса триггер 55- установится в единицу, а следовательно, установится в единицу и выход 38 блока I3 анализа. Этот единичный потенциал поступает на разрешающие входы буферных элементов 49 и 50. , а соответственно на управляющих выходах 36 блока 13 анализа появляется информация, записанная в (i-l)-x разрядах регистров 10 и 11.

Таким образом, узел 13 анализа производит анализ разрядов регистров 10 и 11 и по заднему фронту тактирующего импульса устанавливается в единицу тот информацибнный выход 38 узла 13t анализа, которьгй соответствует номеру старшей пары разрядов регистров 10 и 11, для которой требуется опрос накопителя 1. Одновременно с этим сбрасывается в нуль триггер 14, еди- ничньпй сигнал с инверсного выхода ко- .торого поступает на вход 34 |:Конец поиска устройства, а также на первый вход элемента И 19, разрешая подачу тактирующих импульсов с тактирующего

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

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

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

соответственно, и на входах 41 накопителя 1 во втором такте сформируется признак опроса аналогично, как и при комбинации 00. А также указанным сигналом с инверсного выхода триггера 17 установится низкий потенциал на D-входе триггера 16, которнй при нулевом уровне тактирующего сигнала сбросшся в нуль, обеспечивая таким образом во втором такте прохождение тактирующих импульсов на стробирую- щий вход 29 узла 13 анализа.

В следующем после подачи, импульса

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

20

25

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

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

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

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

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

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

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

14устанавливается в единицу, а соответственно на выходе 34 Конец поиустройства появляется нулевой

потенциал, эапрептая подачу тактирующих импульсов на вход 35 накопителя 1 .

По единичному сигналу на входе 44 Чтение устройства шифратор 7 фор- В первом такте на управляющий вход ,,. мирует адрес первой по счету ответив- мультиплексора 15 поступает единичшей ячейки, этот адрес через селектор 8 адреса и дешифратор 9 адреса поступает на входы накопителя 1, на информационных выходах 3 которого появляется информация, записанная в этой ячейке. Аналогичным образом считываются все ячейки,которым в pi гистре 4 результатов поиска соответст ver единица, Если считаны все ячейки, то на выход 6 устройства поступает единица .

ный сшнал и на входах 41 накопителя 1 формируется признак опроса такта, как и при комбинации 11. В этом же такте устанавливается единичный сигнал на выходе элемента и 21 а соответственно и на D-входе триггера 16, который переключается в единицу по нулевому уровню тактирующего сигнала и низкий потенциал с его инверсного выхода, поступая на вход элемента И 18, запреотает подачу тактируюших импульсов на стробирующий вход 29 узла 13 анализа, работа которой приостанавливается на один такт. А поскольку единичный сигнал с прямого выхода триггера 16 запрета поступает на D-вход триггера 17 запрета, то по заднему фронту тактирующего импульса установится указанный триггер 17 в единицу. И по нулевому сигналу с его инверсного выхода обеспечится подача на управляющий вход мультиплексора 15 низкого потенциала, а

соответственно, и на входах 41 накопителя 1 во втором такте сформируется признак опроса аналогично, как и при комбинации 00. А также указанным сигналом с инверсного выхода триггера 17 установится низкий потенциал на D-входе триггера 16, которнй при нулевом уровне тактирующего сигнала сбросшся в нуль, обеспечивая таким образом во втором такте прохождение тактирующих импульсов на стробирую- щий вход 29 узла 13 анализа.

В следующем после подачи, импульса

поиска такте производится опрос нако-

ска

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

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

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

14устанавливается в единицу, а соответственно на выходе 34 Конец поиустройства появляется нулевой

По единичному сигналу на входе 44 Чтение устройства шифратор 7 фор- мирует адрес первой по счету ответив-

шей ячейки, этот адрес через селектор 8 адреса и дешифратор 9 адреса поступает на входы накопителя 1, на информационных выходах 3 которого появляется информация, записанная в этой ячейке. Аналогичным образом считываются все ячейки,которым в pi гистре 4 результатов поиска соответст ver единица, Если считаны все ячейки, то на выход 6 устройства поступает единица .

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

45

50

Формул

изобретения

Ассоциативное запоминающее устройство, содержащее накопитель, регистр результатов поиска, блок анализа многократных совпадений, шифратор, селектор адреса, дешифратор адреса и блок управления, причем выходы результатов поиска накопителя подключены к соответствующим информационным входам регистра результатов по- иска, выходы которого соединены с соответствующими информационными входами блока анализа многократных совпадений, информационные выходы которого соединены с соответствующими входами шифратора, выходы шифратора подключены к первой группе информа- ционных входов селектора адреса, информационные входы второй группы которого являются адресными входами устройства, выходы селектора адреса подключены -к соответствующим входам дешифратора адреса, выходы которого подключены к соответствующим входам выборки накопителя, вход разрешения записи накопителя и управляющий вход селектора адреса объединены и являют- ся входом Запись устройства, вход разрешения чтения, накопителя и управляющий вход блока анализа многократных совпадений объединены и являются входом Чтение устройства, выход Конец выдачи чисел блока анализа многократных совпадений является одноименным выходом устройства, информационные входы и выходы накопителя являются соответственно одноимен- ными входами и выходами устройства, вход установки в Г0 регистра результатов поиска и вход Начало поиска блока управления объединены и являются входом Начало поиска устройства, тактовый и установочный входы блока управления являются соответственно одноименными входами устройства первый выход блока управления подключен к входу разрешения поиска нако пителя и входу разрешения приема регистра результатов поиска, второй выход блока управления является выходом

5 0 5 0 9

5

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

фиг 2

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

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

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

Заказ 1067

Тираж 484

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

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

ib

Подписное